# Metric Embedding Initialization-Based Differentially Private and Explainable Graph Clustering

arXiv: https://arxiv.org/abs/2509.06214 · HTML: https://mlsanity.com/paper/2509.06214/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 10 of its 26 references that are in the map.
- First posted on arXiv 7 Sep 2025.

## Builds on (most cited first, 10 of 10)

- [Performance of Johnson-Lindenstrauss Transform for k-Means and k-Medians Clustering](https://mlsanity.com/paper/1811.03195/) (2018)
- [Differentially Private Clustering: Tight Approximation Ratios](https://mlsanity.com/paper/2008.08007/) (2020)
- [Federated Quantum Machine Learning with Differential Privacy](https://mlsanity.com/paper/2310.06973/) (2023)
- [SCGC : Self-Supervised Contrastive Graph Clustering](https://mlsanity.com/paper/2204.12656/) (2022)
- [Fast Parallel Algorithms for Euclidean Minimum Spanning Tree and Hierarchical Spatial Clustering](https://mlsanity.com/paper/2104.01126/) (2021)
- [Protect Your Score: Contact Tracing With Differential Privacy Guarantees](https://mlsanity.com/paper/2312.11581/) (2023)
- [k-Median Clustering via Metric Embedding: Towards Better Initialization with Differential Privacy](https://mlsanity.com/paper/2206.12895/) (2022)
- [A Differentially Private Clustering Algorithm for Well-Clustered Graphs](https://mlsanity.com/paper/2403.14332/) (2024)
- [Budget Recycling Differential Privacy](https://mlsanity.com/paper/2403.11445/) (2024)
- [Contrastive Explainable Clustering with Differential Privacy](https://mlsanity.com/paper/2406.04610/) (2024)

## Abstract (arXiv)

Graph clustering under the framework of differential privacy, which aims to process graph-structured data while protecting individual privacy, has been receiving increasing attention. Despite significant achievements in current research, challenges such as high noise, low efficiency and poor interpretability continue to severely constrain the development of this field. In this paper, we construct a differentially private and interpretable graph clustering approach based on metric embedding initialization. Specifically, we construct an SDP optimization, extract the key set and provide a well-initialized clustering configuration using an HST-based initialization method. Subsequently, we apply an established k-median clustering strategy to derive the cluster results and offer comparative explanations for the query set through differences from the cluster centers. Extensive experiments on public datasets demonstrate that our proposed framework outperforms existing methods in various clustering metrics while strictly ensuring privacy.