論文の概要: Robustness for Spectral Clustering of General Graphs under Local Differential Privacy

• arxiv url: http://arxiv.org/abs/2309.06867v1
• Date: Wed, 13 Sep 2023 10:23:29 GMT
• ステータス: 処理完了
• システム内更新日: 2024-03-19 04:50:57.993334
• Title: Robustness for Spectral Clustering of General Graphs under Local Differential Privacy
• Title（参考訳）: 局所微分プライバシー下における一般グラフのスペクトルクラスタリングのロバスト性
• Authors: Sayan Mukherjee, Vorapong Suppakitpaisarn,
• Abstract要約: ソーシャルネットワークはブロックモデル(SBM)から派生していないと我々は主張する。 私たちの主な焦点は、エッジフリップメソッド -- ローカルな差分プライバシーを保護するための一般的なテクニック -- にあります。 クラスタリングの結果は、SBMから生成される密集グラフやクラスタリンググラフに対して安定しているが、一般に、スペクトルクラスタリングは特定の密集グラフやクラスタリンググラフに対して非常に不規則な結果をもたらす可能性があることを示す。
• 参考スコア（独自算出の注目度）: 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)$.
• Abstract（参考訳）: スペクトルクラスタリングは、ネットワーク内のクラスタを見つけるために広く使われているアルゴリズムである。 複数の研究者が局所微分プライバシーの下でスペクトルクラスタリングの安定性について研究しており、基礎となるネットワークは確率ブロックモデル(SBM)から生成されると仮定している。 しかし、ソーシャルネットワークはSBMから派生していないため、この仮定は制限的すぎると論じる。 このようにして、この研究における一般グラフの解析を掘り下げる。 私たちの主な焦点は、エッジフリップメソッド -- ローカルな差分プライバシーを保護するための一般的なテクニック -- にあります。 正の面では、ある合理的なクラスタリング仮定を満たす$n$-頂点グラフの辺が$O(\log n/n)$の確率で反転しても、クラスタリングの結果は概ね一貫したものである。 実証実験はこれらの理論的な発見をさらに裏付ける。 逆に、クラスタリングの結果は SBM から生成される密集グラフやクラスタリンググラフに対して安定であるが、一般にスペクトルクラスタリングは、フリップ確率が $\omega(\log n/n)$ であるとき、ある密集グラフに対して非常に不規則な結果が得られることを示す。 これは、一般的なグラフで得られる最高のプライバシー予算が$\Theta(\log n)$であることを示している。

関連論文リスト

• A Unified Framework for Gradient-based Clustering of Distributed Data [51.904327888475606]
  我々は,ユーザのネットワーク上で動作する分散クラスタリングアルゴリズムのファミリーを開発する。 DGC-$mathcalF_rho$は、K$-meansやHuber Losといった一般的なクラスタリング損失に特化している。 DGC-$mathcalF_rho$のコンセンサス固定点は、全データ上の勾配クラスタリングの固定点と等価であることを示す。
  論文  参考訳（メタデータ） (2024-02-02T10:44:42Z)
• Reinforcement Graph Clustering with Unknown Cluster Number [91.4861135742095]
  本稿では,Reinforcement Graph Clusteringと呼ばれる新しいディープグラフクラスタリング手法を提案する。 提案手法では,クラスタ数決定と教師なし表現学習を統一的なフレームワークに統合する。 フィードバック動作を行うために、クラスタリング指向の報酬関数を提案し、同一クラスタの凝集を高め、異なるクラスタを分離する。
  論文  参考訳（メタデータ） (2023-08-13T18:12:28Z)
• Spectral Clustering on Large Datasets: When Does it Work? Theory from Continuous Clustering and Density Cheeger-Buser [0.17188280334580194]
  現代の機械学習では、多くのデータセットは確率密度関数から引き出された多数の点としてモデル化される。 我々の研究は、ラプラス分布の混合から引き出されたデータに対して、シマリクスペクトルクラスタリングがうまく働くことを示唆している。 私たちのキーとなるツールは、不連続なものを含む全ての確率密度に対する新しいCheeger-Buser不等式です。
  論文  参考訳（メタデータ） (2023-05-11T03:08:49Z)
• FedSpectral+: Spectral Clustering using Federated Learning [0.0]
  本稿では,データプライバシの問題と通信コストの増大を克服するために,FLを用いたスペクトルクラスタリングアルゴリズムを提案する。 FLは、ユーザの生データを収集するのではなく、各学習者のモデルパラメータを蓄積するプライバシー保護アルゴリズムである。 FedSpectralは、局所スペクトルクラスタリングラベルを使用して、類似性グラフを作成することで、グローバルスペクトルクラスタリングを集約するベースラインアプローチである。 最先端のアプローチであるFedSpectral+は、クライアント間で分散された生の情報にアクセスすることなく、グラフデータ全体を組み込むことで、グローバルなスペクトル埋め込みを学習するためにパワーメソッドを使用する。
  論文  参考訳（メタデータ） (2023-02-04T09:28:36Z)
• On consistency of constrained spectral clustering under representation-aware stochastic block model [20.6072287343024]
  制約付きスペクトルクラスタリングは、与えられたテクスト類似性グラフ$mathcalG$でバランスの取れたクラスタを見つけることを目的として研究される。 この環境では、スペクトルクラスタリングの非正規化および正規化の変種を開発する。 これらのアルゴリズムは$mathcalR$を使用して、提案された制約をほぼ満たした$mathcalG$のクラスタを見つける。
  論文  参考訳（メタデータ） (2022-03-03T20:41:14Z)
• Lattice-Based Methods Surpass Sum-of-Squares in Clustering [98.46302040220395]
  クラスタリングは教師なし学習における基本的なプリミティブである。 最近の研究は、低次手法のクラスに対する低い境界を確立している。 意外なことに、この特定のクラスタリングモデルのtextitdoesは、統計的-計算的ギャップを示さない。
  論文  参考訳（メタデータ） (2021-12-07T18:50:17Z)
• Spectral-Spatial Global Graph Reasoning for Hyperspectral Image Classification [50.899576891296235]
  畳み込みニューラルネットワークは、ハイパースペクトル画像分類に広く応用されている。 近年の手法は空間トポロジのグラフ畳み込みによってこの問題に対処しようとしている。
  論文  参考訳（メタデータ） (2021-06-26T06:24:51Z)
• Regularized spectral methods for clustering signed networks [7.547306670351599]
  署名付きグラフにおける$k$-wayクラスタリングの問題について検討する。 我々は,SPONGE と Signed Laplacian の正規化バージョンに対して,[CDGT 2019] の2つの面で結果に基づいて構築する。
  論文  参考訳（メタデータ） (2020-11-03T14:40:34Z)
• Average Sensitivity of Spectral Clustering [31.283432482502278]
  入力グラフにおけるエッジ摂動に対するスペクトルクラスタリングの安定性について検討する。 その結果,入力グラフにクラスタ構造が存在する場合,スペクトルクラスタリングはエッジ摂動に対して安定であることが示唆された。
  論文  参考訳（メタデータ） (2020-06-07T09:14:44Z)
• Computationally efficient sparse clustering [67.95910835079825]
  我々はPCAに基づく新しいクラスタリングアルゴリズムの有限サンプル解析を行う。 ここでは,ミニマックス最適誤クラスタ化率を,体制$|theta infty$で達成することを示す。
  論文  参考訳（メタデータ） (2020-05-21T17:51:30Z)
• Block-Approximated Exponential Random Graphs [77.4792558024487]
  指数乱グラフ(ERG)の分野における重要な課題は、大きなグラフ上の非自明なERGの適合である。 本稿では,非自明なERGに対する近似フレームワークを提案する。 我々の手法は、数百万のノードからなるスパースグラフにスケーラブルである。
  論文  参考訳（メタデータ） (2020-02-14T11:42:16Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。