論文の概要: FairAD: Computationally Efficient Fair Graph Clustering via Algebraic Distance

• arxiv url: http://arxiv.org/abs/2510.27136v1
• Date: Fri, 31 Oct 2025 03:20:48 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-11-03 17:52:15.964097
• Title: FairAD: Computationally Efficient Fair Graph Clustering via Algebraic Distance
• Title（参考訳）: FairAD: 代数距離による計算効率の良い公正グラフクラスタリング
• Authors: Minh Phu Vuong, Young-Ju Lee, Iván Ojeda-Ruiz, Chul-Ho Lee,
• Abstract要約: 公正なグラフクラスタリングは、グラフ内のノードのセットを$k$の非結合クラスタに分割することを目的としている。 しかし、既存のグラフクラスタリングアルゴリズムに公平性制約を組み込むことは、計算的に困難である。 計算効率の良いフェアグラフクラスタリング法であるFairADを提案する。 実験結果から、FairADは最先端のグラフクラスタリングアルゴリズムの最大40倍の速度で、公平なクラスタリングを実現することができることがわかった。
• 参考スコア（独自算出の注目度）: 1.2516203168932827
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Due to the growing concern about unsavory behaviors of machine learning models toward certain demographic groups, the notion of 'fairness' has recently drawn much attention from the community, thereby motivating the study of fairness in graph clustering. Fair graph clustering aims to partition the set of nodes in a graph into $k$ disjoint clusters such that the proportion of each protected group within each cluster is consistent with the proportion of that group in the entire dataset. It is, however, computationally challenging to incorporate fairness constraints into existing graph clustering algorithms, particularly for large graphs. To address this problem, we propose FairAD, a computationally efficient fair graph clustering method. It first constructs a new affinity matrix based on the notion of algebraic distance such that fairness constraints are imposed. A graph coarsening process is then performed on this affinity matrix to find representative nodes that correspond to $k$ clusters. Finally, a constrained minimization problem is solved to obtain the solution of fair clustering. Experiment results on the modified stochastic block model and six public datasets show that FairAD can achieve fair clustering while being up to 40 times faster compared to state-of-the-art fair graph clustering algorithms.
• Abstract（参考訳）: 特定の人口集団に対する機械学習モデルの不愉快な行動に対する懸念が高まっているため、近年「公正性」の概念がコミュニティから注目を集めており、グラフクラスタリングにおける公正性の研究の動機となっている。 公正なグラフクラスタリングは、グラフ内のノードの集合を、各クラスタ内の保護されたグループの割合がデータセット全体のグループの割合と一致するように、$k$の非結合クラスタに分割することを目的としている。 しかし、特に大きなグラフの場合、既存のグラフクラスタリングアルゴリズムに公平性制約を組み込むことは計算的に困難である。 この問題に対処するため,計算効率の良いフェアグラフクラスタリング法であるFairADを提案する。 まず、公平性制約が課されるような代数的距離の概念に基づいて、新しい親和性行列を構築する。 この親和性行列上でグラフ粗化処理を行い、$k$クラスタに対応する代表ノードを見つける。 最後に、制約付き最小化問題を解き、公正クラスタリングの解を得る。 修正された確率ブロックモデルと6つの公開データセットの実験結果から、FairADは、最先端の公正グラフクラスタリングアルゴリズムに比べて最大40倍高速で、公正クラスタリングを達成可能であることが示された。

関連論文リスト

• Deep Cut-informed Graph Embedding and Clustering [36.17182061654739]
  我々は,革新的で非GNNベースのDeep Cut-informed Graph Embedding and Clusteringフレームワーク,すなわちDCGCを提案する。 符号化モジュールに対しては,その結合正規化カットを最小化することにより,グラフ構造と属性を融合させる,カットインフォームドグラフ埋め込みの目的を導出する。 クラスタリングモジュールでは,クラスタリングの割り当てを得るために最適な輸送理論を利用する。
  論文  参考訳（メタデータ） (2025-03-09T14:24:09Z)
• Fair Clustering with Minimum Representation Constraints [2.707154152696381]
  我々は、各群が少なくとも指定された数のクラスタにおいて、最小レベルの表現を達成しなければならないという追加の公平性制約の下で、k平均およびkメディアンクラスタリング問題について検討する。 大規模なデータセットであっても,このアプローチを実用的にするための戦略をいくつか提示する。
  論文  参考訳（メタデータ） (2024-09-04T00:13:40Z)
• Learning Uniform Clusters on Hypersphere for Deep Graph-level Clustering [25.350054742471816]
  我々はUDGC(Uniform Deep Graph Clustering)と呼ばれる新しいディープグラフレベルのクラスタリング手法を提案する。 UDGCはインスタンスを異なるクラスタに均等に割り当て、次にこれらのクラスタをユニットハイパースフィア上に分散させ、より均一なクラスタレベルの分散と、より小さなクラスタ崩壊につながる。 8つのよく知られたデータセットに関する実証研究は、UDGCが最先端のモデルを大幅に上回っていることを示している。
  論文  参考訳（メタデータ） (2023-11-23T12:08:20Z)
• Reinforcement Graph Clustering with Unknown Cluster Number [91.4861135742095]
  本稿では,Reinforcement Graph Clusteringと呼ばれる新しいディープグラフクラスタリング手法を提案する。 提案手法では,クラスタ数決定と教師なし表現学習を統一的なフレームワークに統合する。 フィードバック動作を行うために、クラスタリング指向の報酬関数を提案し、同一クラスタの凝集を高め、異なるクラスタを分離する。
  論文  参考訳（メタデータ） (2023-08-13T18:12:28Z)
• Dink-Net: Neural Clustering on Large Graphs [59.10189693120368]
  ディープグラフクラスタリング法 (Dink-Net) は, 拡張と縮小という概念を用いて提案される。 ノードを識別することにより、拡張によって劣化しても、表現は自己教師された方法で学習される。 クラスタリング分布は、提案したクラスタ拡張損失とクラスタ縮小損失を最小化することにより最適化される。 ランナアップと比較して、Dink-Net 9.62%は1100万ノードと16億エッジを持つogbn-papers100MデータセットでNMIの改善を実現している。
  論文  参考訳（メタデータ） (2023-05-28T15:33:24Z)
• One-step Bipartite Graph Cut: A Normalized Formulation and Its Application to Scalable Subspace Clustering [56.81492360414741]
  両部グラフの1ステップ正規化カットを、特に線形時間複雑性で実施する方法を示す。 本稿では、まず、正規化制約付き一段階二分グラフカット基準を特徴付けるとともに、そのトレース問題に対する等価性を理論的に証明する。 このカット基準を、適応アンカー学習、二部グラフ学習、一段階正規化二部グラフ分割を同時にモデル化するスケーラブルなサブスペースクラスタリングアプローチに拡張する。
  論文  参考訳（メタデータ） (2023-05-12T11:27:20Z)
• Graph Representation Learning via Contrasting Cluster Assignments [57.87743170674533]
  GRCCAと呼ばれるクラスタ割り当てを対比して、教師なしグラフ表現モデルを提案する。 クラスタリングアルゴリズムとコントラスト学習を組み合わせることで、局所的およびグローバルな情報を合成的にうまく活用する動機付けがある。 GRCCAは、ほとんどのタスクにおいて強力な競争力を持っている。
  論文  参考訳（メタデータ） (2021-12-15T07:28:58Z)
• Self-supervised Contrastive Attributed Graph Clustering [110.52694943592974]
  我々は,自己教師型コントラストグラフクラスタリング(SCAGC)という,新たな属性グラフクラスタリングネットワークを提案する。 SCAGCでは,不正確なクラスタリングラベルを活用することで,ノード表現学習のための自己教師付きコントラスト損失を設計する。 OOSノードでは、SCAGCはクラスタリングラベルを直接計算できる。
  論文  参考訳（メタデータ） (2021-10-15T03:25:28Z)
• Effective and Efficient Graph Learning for Multi-view Clustering [173.8313827799077]
  マルチビュークラスタリングのための効率的かつ効率的なグラフ学習モデルを提案する。 本手法はテンソルシャッテンp-ノルムの最小化により異なるビューのグラフ間のビュー類似性を利用する。 提案アルゴリズムは時間経済であり,安定した結果を得るとともに,データサイズによく対応している。
  論文  参考訳（メタデータ） (2021-08-15T13:14:28Z)

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

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