Privacy-Preserving Community Detection for Locally Distributed Multiple Networks

• URL: http://arxiv.org/abs/2306.15709v2
• Date: Mon, 21 Oct 2024 04:21:36 GMT
• Title: Privacy-Preserving Community Detection for Locally Distributed Multiple Networks
• Authors: Xiao Guo, Xiang Li, Xiangyu Chang, Shujie Ma,
• Abstract summary: We propose a new method for consensus community detection and estimation in a multi-layer block model. A novel algorithm named Distributed Spectral Clustering (ppDSC) is developed.
• Score: 11.693304974549893
• License:
• Abstract: Modern multi-layer networks are commonly stored and analyzed in a local and distributed fashion because of the privacy, ownership, and communication costs. The literature on the model-based statistical methods for community detection based on these data is still limited. This paper proposes a new method for consensus community detection and estimation in a multi-layer stochastic block model using locally stored and computed network data with privacy protection. A novel algorithm named privacy-preserving Distributed Spectral Clustering (ppDSC) is developed. To preserve the edges' privacy, we adopt the randomized response (RR) mechanism to perturb the network edges, which satisfies the strong notion of differential privacy. The ppDSC algorithm is performed on the squared RR-perturbed adjacency matrices to prevent possible cancellation of communities among different layers. To remove the bias incurred by RR and the squared network matrices, we develop a two-step bias-adjustment procedure. Then we perform eigen-decomposition on the debiased matrices, aggregation of the local eigenvectors using an orthogonal Procrustes transformation, and k-means clustering. We provide theoretical analysis on the statistical errors of ppDSC in terms of eigen-vector estimation. In addition, the blessings and curses of network heterogeneity are well-explained by our bounds.

Related papers

• Differentially Private Neural Network Training under Hidden State Assumption [2.3371504588528635]
  We present a novel approach called differentially private neural block coordinate descent (DP-SBCD) for neural networks with provable guarantees of privacy under the hidden state assumption.
  arXiv  Detail & Related papers  (2024-07-11T07:14:40Z)
• Bias-Corrected Joint Spectral Embedding for Multilayer Networks with Invariant Subspace: Entrywise Eigenvector Perturbation and Inference [0.0]
  We propose to estimate the invariant subspace across heterogeneous multiple networks using a novel bias-corrected joint spectral embedding algorithm. The proposed algorithm calibrates the diagonal bias of the sum of squared network adjacency matrices by leveraging the closed-form bias formula. We establish a complete recipe for the entrywise subspace estimation theory for the proposed algorithm, including a sharp entrywise subspace perturbation bound.
  arXiv  Detail & Related papers  (2024-06-12T03:36:55Z)
• Private Online Community Detection for Censored Block Models [60.039026645807326]
  We study the private online change detection problem for dynamic communities, using a censored block model (CBM) We propose an algorithm capable of identifying changes in the community structure, while maintaining user privacy.
  arXiv  Detail & Related papers  (2024-05-09T12:35:57Z)
• Collaborative Heterogeneous Causal Inference Beyond Meta-analysis [68.4474531911361]
  We propose a collaborative inverse propensity score estimator for causal inference with heterogeneous data. Our method shows significant improvements over the methods based on meta-analysis when heterogeneity increases.
  arXiv  Detail & Related papers  (2024-04-24T09:04:36Z)
• Initialization Matters: Privacy-Utility Analysis of Overparameterized Neural Networks [72.51255282371805]
  We prove a privacy bound for the KL divergence between model distributions on worst-case neighboring datasets. We find that this KL privacy bound is largely determined by the expected squared gradient norm relative to model parameters during training.
  arXiv  Detail & Related papers  (2023-10-31T16:13:22Z)
• Local Differential Privacy in Graph Neural Networks: a Reconstruction Approach [17.000441871334683]
  We propose a learning framework that can provide node privacy at the user level, while incurring low utility loss. We focus on a decentralized notion of Differential Privacy, namely Local Differential Privacy. We develop reconstruction methods to approximate features and labels from perturbed data.
  arXiv  Detail & Related papers  (2023-09-15T17:35:51Z)
• Differentially Private Distributed Estimation and Learning [2.4401219403555814]
  We study distributed estimation and learning problems in a networked environment. Agents exchange information to estimate unknown statistical properties of random variables from privately observed samples. Agents can estimate the unknown quantities by exchanging information about their private observations, but they also face privacy risks.
  arXiv  Detail & Related papers  (2023-06-28T01:41:30Z)
• On the Privacy-Robustness-Utility Trilemma in Distributed Learning [7.778461949427662]
  We present the first tight analysis of the error incurred by any algorithm ensuring robustness against a fraction of adversarial machines. Our analysis exhibits a fundamental trade-off between privacy, robustness, and utility.
  arXiv  Detail & Related papers  (2023-02-09T17:24:18Z)
• Decentralized Local Stochastic Extra-Gradient for Variational Inequalities [125.62877849447729]
  We consider distributed variational inequalities (VIs) on domains with the problem data that is heterogeneous (non-IID) and distributed across many devices. We make a very general assumption on the computational network that covers the settings of fully decentralized calculations. We theoretically analyze its convergence rate in the strongly-monotone, monotone, and non-monotone settings.
  arXiv  Detail & Related papers  (2021-06-15T17:45:51Z)
• Graph-Homomorphic Perturbations for Private Decentralized Learning [64.26238893241322]
  Local exchange of estimates allows inference of data based on private data. perturbations chosen independently at every agent, resulting in a significant performance loss. We propose an alternative scheme, which constructs perturbations according to a particular nullspace condition, allowing them to be invisible.
  arXiv  Detail & Related papers  (2020-10-23T10:35:35Z)
• Unlabelled Data Improves Bayesian Uncertainty Calibration under Covariate Shift [100.52588638477862]
  We develop an approximate Bayesian inference scheme based on posterior regularisation. We demonstrate the utility of our method in the context of transferring prognostic models of prostate cancer across globally diverse populations.
  arXiv  Detail & Related papers  (2020-06-26T13:50:19Z)

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.