Robustness for Spectral Clustering of General Graphs under Local Differential Privacy

• URL: http://arxiv.org/abs/2309.06867v1
• Date: Wed, 13 Sep 2023 10:23:29 GMT
• Title: Robustness for Spectral Clustering of General Graphs under Local Differential Privacy
• Authors: Sayan Mukherjee, Vorapong Suppakitpaisarn,
• Abstract summary: We argue that social networks do not originate from the block model (SBM) Our primary focus is the edge flipping method -- a common technique for protecting local differential privacy. Although clustering outcomes have been stable for dense and well-clustered graphs produced from the SBM, we show that in general, spectral clustering may yield highly erratic results on certain dense and well-clustered graphs.
• Score: 2.4447259440166302
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: Spectral clustering is a widely used algorithm to find clusters in networks. Several researchers have studied the stability of spectral clustering under local differential privacy with the additional assumption that the underlying networks are generated from the stochastic block model (SBM). However, we argue that this assumption is too restrictive since social networks do not originate from the SBM. Thus, delve into an analysis for general graphs in this work. Our primary focus is the edge flipping method -- a common technique for protecting local differential privacy. On a positive side, our findings suggest that even when the edges of an $n$-vertex graph satisfying some reasonable well-clustering assumptions are flipped with a probability of $O(\log n/n)$, the clustering outcomes are largely consistent. Empirical tests further corroborate these theoretical findings. Conversely, although clustering outcomes have been stable for dense and well-clustered graphs produced from the SBM, we show that in general, spectral clustering may yield highly erratic results on certain dense and well-clustered graphs when the flipping probability is $\omega(\log n/n)$. This indicates that the best privacy budget obtainable for general graphs is $\Theta(\log n)$.

Related papers

• A Unified Framework for Gradient-based Clustering of Distributed Data [51.904327888475606]
  We develop a family of distributed clustering algorithms that work over networks of users. DGC-$mathcalF_rho$ is specialized to popular clustering losses like $K$-means and Huber loss. We show that consensus fixed points of DGC-$mathcalF_rho$ are equivalent to fixed points of gradient clustering over the full data.
  arXiv  Detail & Related papers  (2024-02-02T10:44:42Z)
• Reinforcement Graph Clustering with Unknown Cluster Number [91.4861135742095]
  We propose a new deep graph clustering method termed Reinforcement Graph Clustering. In our proposed method, cluster number determination and unsupervised representation learning are unified into a uniform framework. In order to conduct feedback actions, the clustering-oriented reward function is proposed to enhance the cohesion of the same clusters and separate the different clusters.
  arXiv  Detail & Related papers  (2023-08-13T18:12:28Z)
• Spectral Clustering on Large Datasets: When Does it Work? Theory from Continuous Clustering and Density Cheeger-Buser [0.17188280334580194]
  In modern machine learning, many data sets are modeled as a large number of points drawn from a probability density function. Our work suggests that Shi-Malik spectral clustering works well on data drawn from mixtures of Laplace distributions. Our key tool is a new Cheeger-Buser inequality for all probability densities, including discontinuous ones.
  arXiv  Detail & Related papers  (2023-05-11T03:08:49Z)
• FedSpectral+: Spectral Clustering using Federated Learning [0.0]
  We propose a spectral clustering algorithm using federated learning (FL) to overcome issues of data privacy and increased communication costs. FL is a privacy-protecting algorithm that accumulates model parameters from each local learner rather than collecting users' raw data. FedSpectral is a baseline approach that uses local spectral clustering labels to aggregate the global spectral clustering by creating a similarity graph. FedSpectral+, a state-of-the-art approach, uses the power method to learn the global spectral embedding by incorporating the entire graph data without access to the raw information distributed among the clients.
  arXiv  Detail & Related papers  (2023-02-04T09:28:36Z)
• On consistency of constrained spectral clustering under representation-aware stochastic block model [20.6072287343024]
  We study constrained spectral clustering with the aim of finding balanced clusters in a given textitsimilarity graph $mathcalG$. We develop unnormalized and normalized variants of spectral clustering in this setting. These algorithms use $mathcalR$ to find clusters in $mathcalG$ that approximately satisfy the proposed constraint.
  arXiv  Detail & Related papers  (2022-03-03T20:41:14Z)
• Lattice-Based Methods Surpass Sum-of-Squares in Clustering [98.46302040220395]
  Clustering is a fundamental primitive in unsupervised learning. Recent work has established lower bounds against the class of low-degree methods. We show that, perhaps surprisingly, this particular clustering model textitdoes not exhibit a statistical-to-computational gap.
  arXiv  Detail & Related papers  (2021-12-07T18:50:17Z)
• Spectral-Spatial Global Graph Reasoning for Hyperspectral Image Classification [50.899576891296235]
  Convolutional neural networks have been widely applied to hyperspectral image classification. Recent methods attempt to address this issue by performing graph convolutions on spatial topologies.
  arXiv  Detail & Related papers  (2021-06-26T06:24:51Z)
• Regularized spectral methods for clustering signed networks [7.547306670351599]
  We study the problem of $k$-way clustering in signed graphs. We build on the results in [CDGT 2019] on two fronts for the normalized versions of SPONGE and the Signed Laplacian.
  arXiv  Detail & Related papers  (2020-11-03T14:40:34Z)
• Average Sensitivity of Spectral Clustering [31.283432482502278]
  We study the stability of spectral clustering against edge perturbations in the input graph. Our results suggest that spectral clustering is stable against edge perturbations when there is a cluster structure in the input graph.
  arXiv  Detail & Related papers  (2020-06-07T09:14:44Z)
• Computationally efficient sparse clustering [67.95910835079825]
  We provide a finite sample analysis of a new clustering algorithm based on PCA. We show that it achieves the minimax optimal misclustering rate in the regime $|theta infty$.
  arXiv  Detail & Related papers  (2020-05-21T17:51:30Z)
• Block-Approximated Exponential Random Graphs [77.4792558024487]
  An important challenge in the field of exponential random graphs (ERGs) is the fitting of non-trivial ERGs on large graphs. We propose an approximative framework to such non-trivial ERGs that result in dyadic independence (i.e., edge independent) distributions. Our methods are scalable to sparse graphs consisting of millions of nodes.
  arXiv  Detail & Related papers  (2020-02-14T11:42:16Z)

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.