論文の概要: Spectral Normalized-Cut Graph Partitioning with Fairness Constraints

• arxiv url: http://arxiv.org/abs/2307.12065v1
• Date: Sat, 22 Jul 2023 12:20:46 GMT
• ステータス: 処理完了
• システム内更新日: 2023-07-25 18:08:16.473545
• Title: Spectral Normalized-Cut Graph Partitioning with Fairness Constraints
• Title（参考訳）: フェアネス制約付きスペクトル正規化カットグラフ分割
• Authors: Jia Li, Yanhao Wang, Arpit Merchant
• Abstract要約: 正規化されたグラフ分割は、グラフ内のノードの集合を$k$ディスジョイントクラスタに分割して、任意のクラスタと他のクラスタ間の全エッジの分画を最小限にすることを目的としている。 本稿では,ノードが異なる階層群に属することを示す分類学的属性によって特徴付けられる分割問題の公平な変種について考察する。 私たちの目標は、正規化されたカット値を最小化しながら、各グループが各クラスタにほぼ比例的に表現されることを保証することです。
• 参考スコア（独自算出の注目度）: 18.835004555146575
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: Normalized-cut graph partitioning aims to divide the set of nodes in a graph into $k$ disjoint clusters to minimize the fraction of the total edges between any cluster and all other clusters. In this paper, we consider a fair variant of the partitioning problem wherein nodes are characterized by a categorical sensitive attribute (e.g., gender or race) indicating membership to different demographic groups. Our goal is to ensure that each group is approximately proportionally represented in each cluster while minimizing the normalized cut value. To resolve this problem, we propose a two-phase spectral algorithm called FNM. In the first phase, we add an augmented Lagrangian term based on our fairness criteria to the objective function for obtaining a fairer spectral node embedding. Then, in the second phase, we design a rounding scheme to produce $k$ clusters from the fair embedding that effectively trades off fairness and partition quality. Through comprehensive experiments on nine benchmark datasets, we demonstrate the superior performance of FNM compared with three baseline methods.
• Abstract（参考訳）: 正規化カットグラフパーティショニングは、グラフ内のノードの集合を$k$disjointクラスタに分割し、任意のクラスタと他のすべてのクラスタ間のエッジの比率を最小化することを目的としている。 本稿では,ノードの分類に敏感な属性(性別や人種など)を特徴とし,異なる集団へのメンバシップを示す分断問題の公正な変種を考察する。 私たちの目標は、正規化されたカット値を最小化しながら、各グループが各クラスタにほぼ比例的に表現されることを保証することです。 この問題を解決するために, fnmと呼ばれる2相スペクトルアルゴリズムを提案する。 第1段階では、より公正なスペクトルノードの埋め込みを得る目的関数に、我々の公正度基準に基づく拡張ラグランジアン項を付加する。 そして、第2フェーズでは、公平性と分割品質を効果的にトレードオフするフェア埋め込みから$k$クラスタを生成する丸めスキームを設計します。 9つのベンチマークデータセットを包括的に実験した結果,3つのベースライン法と比較して,fnmの優れた性能を示す。

関連論文リスト

• Self-Supervised Graph Embedding Clustering [70.36328717683297]
  K-means 1-step dimensionality reduction clustering method は,クラスタリングタスクにおける次元性の呪いに対処する上で,いくつかの進歩をもたらした。 本稿では,K-meansに多様体学習を統合する統一フレームワークを提案する。
  論文  参考訳（メタデータ） (2024-09-24T08:59:51Z)
• A Unified Framework for Fair Spectral Clustering With Effective Graph Learning [12.343382413705394]
  群フェアネス制約下でのスペクトルクラスタリングの問題点を考察する。 実際には、グラフは通常不明であり、潜在的にノイズの多いデータから基盤となるグラフを構築する必要がある。 雑音データからグラフを学習するためのノード適応グラフフィルタを用いた新しいグラフ構築法を提案する。
  論文  参考訳（メタデータ） (2023-11-23T01:43:00Z)
• Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model [79.46465138631592]
  観測されたラベルを用いてクラスタを復元する効率的なアルゴリズムを考案する。 本稿では,期待値と高い確率でこれらの下位境界との性能を一致させる最初のアルゴリズムであるIACを提案する。
  論文  参考訳（メタデータ） (2023-06-18T08:46:06Z)
• One-step Bipartite Graph Cut: A Normalized Formulation and Its Application to Scalable Subspace Clustering [56.81492360414741]
  両部グラフの1ステップ正規化カットを、特に線形時間複雑性で実施する方法を示す。 本稿では、まず、正規化制約付き一段階二分グラフカット基準を特徴付けるとともに、そのトレース問題に対する等価性を理論的に証明する。 このカット基準を、適応アンカー学習、二部グラフ学習、一段階正規化二部グラフ分割を同時にモデル化するスケーラブルなサブスペースクラスタリングアプローチに拡張する。
  論文  参考訳（メタデータ） (2023-05-12T11:27:20Z)
• Multi-View Clustering via Semi-non-negative Tensor Factorization [120.87318230985653]
  半負のテンソル因子分解(Semi-NTF)に基づく新しいマルチビュークラスタリングを開発する。 本モデルは、ビュー間の関係を直接考慮し、ビュー間の補完情報を利用する。 さらに,提案手法の最適化アルゴリズムを提案し,そのアルゴリズムが常に定常KKT点に収束することを数学的に証明する。
  論文  参考訳（メタデータ） (2023-03-29T14:54:19Z)
• Total Variation Graph Neural Networks [5.571369922847262]
  最近提案されたグラフニューラルネットワーク(GNN)は、教師なしの最小カット目標を用いて訓練されている。 本稿では,最小カットの厳密な緩和を最適化し,クラスタ割り当てを計算するGNNモデルを提案する。
  論文  参考訳（メタデータ） (2022-11-11T14:13:14Z)
• Self-supervised Contrastive Attributed Graph Clustering [110.52694943592974]
  我々は,自己教師型コントラストグラフクラスタリング(SCAGC)という,新たな属性グラフクラスタリングネットワークを提案する。 SCAGCでは,不正確なクラスタリングラベルを活用することで,ノード表現学習のための自己教師付きコントラスト損失を設計する。 OOSノードでは、SCAGCはクラスタリングラベルを直接計算できる。
  論文  参考訳（メタデータ） (2021-10-15T03:25:28Z)
• Scalable Hierarchical Agglomerative Clustering [65.66407726145619]
  既存のスケーラブルな階層的クラスタリング手法は、スピードの質を犠牲にする。 我々は、品質を犠牲にせず、数十億のデータポイントまでスケールする、スケーラブルで集約的な階層的クラスタリング法を提案する。
  論文  参考訳（メタデータ） (2020-10-22T15:58:35Z)
• A Performance Guarantee for Spectral Clustering [0.6445605125467572]
  スペクトルクラスタリングはいつ,最小比カット問題に対する大域的な解を見つけることができるのか? 我々は、グラフラプラシアンの不変部分空間に対して、$k$最小固有値に対応する決定論的2-無限ノルムを開発する。 これら2つの結果を組み合わせることで、スペクトルクラスタリングが保証され、大域的な解を最小比カット問題に出力する条件を与える。
  論文  参考訳（メタデータ） (2020-07-10T22:03:43Z)
• Efficient Clustering for Stretched Mixtures: Landscape and Optimality [4.2111286819721485]
  本稿では,2つの楕円分布の平衡混合から抽出された未ラベルのサンプルを受信する正準クラスタリング問題について考察する。 非最適クラスタリング関数は、サンプルサイズが一定の統計的目標を超えると、望ましい幾何学的性質を示す。
  論文  参考訳（メタデータ） (2020-03-22T17:57:07Z)

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

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