Metric Embedding Initialization-Based Differentially Private and Explainable Graph Clustering

• URL: http://arxiv.org/abs/2509.06214v1
• Date: Sun, 07 Sep 2025 21:28:23 GMT
• Title: Metric Embedding Initialization-Based Differentially Private and Explainable Graph Clustering
• Authors: Haochen You, Baojing Liu,
• Abstract summary: Graph clustering aims to process graph-structured data while protecting individual privacy.<n>We construct a differentially private and interpretable graph clustering approach based on metric embedding.<n>Our proposed framework outperforms existing methods in various clustering metrics while strictly ensuring privacy.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Towards Federated Clustering: A Client-wise Private Graph Aggregation Framework [57.04850867402913]
  Federated clustering addresses the challenge of extracting patterns from decentralized, unlabeled data.<n>We propose Structural Privacy-Preserving Federated Graph Clustering (SPP-FGC), a novel algorithm that innovatively leverages local structural graphs as the primary medium for privacy-preserving knowledge sharing.<n>Our framework achieves state-of-the-art performance, improving clustering accuracy by up to 10% (NMI) over federated baselines while maintaining provable privacy guarantees.
  arXiv  Detail & Related papers  (2025-11-14T03:05:22Z)
• Parameter-Free Clustering via Self-Supervised Consensus Maximization (Extended Version) [50.41628860536753]
  We propose a novel and fully parameter-free clustering framework via Self-supervised Consensus Maximization, named SCMax.<n>Our framework performs hierarchical agglomerative clustering and cluster evaluation in a single, integrated process.
  arXiv  Detail & Related papers  (2025-11-12T11:17:17Z)
• Differentially Private Federated $k$-Means Clustering with Server-Side Data [19.962475029447127]
  FedDP-KMeans is an algorithm for $k$-means clustering that is fully-federated as well as differentially private.<n>Our algorithm achieves excellent results on synthetic and real-world benchmark tasks.
  arXiv  Detail & Related papers  (2025-06-04T14:53:25Z)
• AdaptiveMDL-GenClust: A Robust Clustering Framework Integrating Normalized Mutual Information and Evolutionary Algorithms [0.0]
  We introduce a robust clustering framework that integrates the Minimum Description Length (MDL) principle with a genetic optimization algorithm.<n>The framework begins with an ensemble clustering approach to generate an initial clustering solution, which is refined using MDL-guided evaluation functions and optimized through a genetic algorithm.<n> Experimental results demonstrate that our approach consistently outperforms traditional clustering methods, yielding higher accuracy, improved stability, and reduced bias.
  arXiv  Detail & Related papers  (2024-11-26T20:26:14Z)
• Self-Supervised Graph Embedding Clustering [70.36328717683297]
  K-means one-step dimensionality reduction clustering method has made some progress in addressing the curse of dimensionality in clustering tasks. We propose a unified framework that integrates manifold learning with K-means, resulting in the self-supervised graph embedding framework.
  arXiv  Detail & Related papers  (2024-09-24T08:59:51Z)
• Self-Supervised Contrastive Graph Clustering Network via Structural Information Fusion [15.293684479404092]
  We propose a novel deep graph clustering method called CGCN. Our approach introduces contrastive signals and deep structural information into the pre-training process. Our method has been experimentally validated on multiple real-world graph datasets.
  arXiv  Detail & Related papers  (2024-08-08T09:49:26Z)
• Adaptive Self-supervised Robust Clustering for Unstructured Data with Unknown Cluster Number [12.926206811876174]
  We introduce a novel self-supervised deep clustering approach tailored for unstructured data, termed Adaptive Self-supervised Robust Clustering (ASRC) ASRC adaptively learns the graph structure and edge weights to capture both local and global structural information. ASRC even outperforms methods that rely on prior knowledge of the number of clusters, highlighting its effectiveness in addressing the challenges of clustering unstructured data.
  arXiv  Detail & Related papers  (2024-07-29T15:51:09Z)
• Contrastive Explainable Clustering with Differential Privacy [25.19112971690494]
  This paper presents a novel approach to Explainable AI (XAI) that combines contrastive explanations with differential privacy for clustering algorithms.<n>Focusing on k-median and k-means problems, we calculate contrastive explanations as the utility difference between original clustering and clustering with a centroid fixed to a specific data point.<n>Our key contribution is demonstrating that these differentially private explanations achieve essentially the same utility bounds as non-private explanations.
  arXiv  Detail & Related papers  (2024-06-07T03:37:36Z)
• Deep Embedding Clustering Driven by Sample Stability [16.53706617383543]
  We propose a deep embedding clustering algorithm driven by sample stability (DECS) Specifically, we start by constructing the initial feature space with an autoencoder and then learn the cluster-oriented embedding feature constrained by sample stability. The experimental results on five datasets illustrate that the proposed method achieves superior performance compared to state-of-the-art clustering approaches.
  arXiv  Detail & Related papers  (2024-01-29T09:19:49Z)
• CueGCL: Cluster-aware Personalized Self-Training for Unsupervised Graph Contrastive Learning [49.88192702588169]
  We propose a Cluster-aware Graph Contrastive Learning Framework (CueGCL) to jointly learn clustering results and node representations.<n>Specifically, we design a personalized self-training (PeST) strategy for unsupervised scenarios, which enables our model to capture precise cluster-level personalized information.<n>We theoretically demonstrate the effectiveness of our model, showing it yields an embedding space with a significantly discernible cluster structure.
  arXiv  Detail & Related papers  (2023-11-18T13:45:21Z)
• DPM: Clustering Sensitive Data through Separation [2.2179058122448922]
  We present a privacy-preserving clustering algorithm called DPM that separates a data set into clusters based on a geometrical clustering approach. We show that DPM achieves state-of-the-art utility on the standard clustering metrics and yields a clustering result much closer to that of the popular non-private KMeans algorithm.
  arXiv  Detail & Related papers  (2023-07-06T13:12:19Z)
• Improving the Utility of Differentially Private Clustering through Dynamical Processing [4.6289929100615]
  This study aims to alleviate the trade-off between utility and privacy differentially private clustering. Existing works focus on simple methods, which show poor performance.
  arXiv  Detail & Related papers  (2023-04-27T00:13:17Z)
• A One-shot Framework for Distributed Clustered Learning in Heterogeneous Environments [54.172993875654015]
  The paper proposes a family of communication efficient methods for distributed learning in heterogeneous environments. One-shot approach, based on local computations at the users and a clustering based aggregation step at the server is shown to provide strong learning guarantees. For strongly convex problems it is shown that, as long as the number of data points per user is above a threshold, the proposed approach achieves order-optimal mean-squared error rates in terms of the sample size.
  arXiv  Detail & Related papers  (2022-09-22T09:04:10Z)
• Towards Uncovering the Intrinsic Data Structures for Unsupervised Domain Adaptation using Structurally Regularized Deep Clustering [119.88565565454378]
  Unsupervised domain adaptation (UDA) is to learn classification models that make predictions for unlabeled data on a target domain. We propose a hybrid model of Structurally Regularized Deep Clustering, which integrates the regularized discriminative clustering of target data with a generative one. Our proposed H-SRDC outperforms all the existing methods under both the inductive and transductive settings.
  arXiv  Detail & Related papers  (2020-12-08T08:52:00Z)
• Scalable Hierarchical Agglomerative Clustering [65.66407726145619]
  Existing scalable hierarchical clustering methods sacrifice quality for speed. We present a scalable, agglomerative method for hierarchical clustering that does not sacrifice quality and scales to billions of data points.
  arXiv  Detail & Related papers  (2020-10-22T15:58:35Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.