論文の概要: A Semidefinite Relaxation Approach for Fair Graph Clustering

• arxiv url: http://arxiv.org/abs/2410.15233v1
• Date: Sat, 19 Oct 2024 22:51:24 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-10-22 13:22:39.348469
• Title: A Semidefinite Relaxation Approach for Fair Graph Clustering
• Title（参考訳）: フェアグラフクラスタリングのための半有限緩和手法
• Authors: Sina Baharlouei, Sadra Sabouri,
• Abstract要約: 本研究では、異なる影響原理の枠組みの中で、公正なグラフクラスタリングを導入する。 我々は、基礎となる最適化問題を近似するために半定緩和法を用いる。
• 参考スコア（独自算出の注目度）: 1.03590082373586
• License:
• Abstract: Fair graph clustering is crucial for ensuring equitable representation and treatment of diverse communities in network analysis. Traditional methods often ignore disparities among social, economic, and demographic groups, perpetuating biased outcomes and reinforcing inequalities. This study introduces fair graph clustering within the framework of the disparate impact doctrine, treating it as a joint optimization problem integrating clustering quality and fairness constraints. Given the NP-hard nature of this problem, we employ a semidefinite relaxation approach to approximate the underlying optimization problem. For up to medium-sized graphs, we utilize a singular value decomposition-based algorithm, while for larger graphs, we propose a novel algorithm based on the alternative direction method of multipliers. Unlike existing methods, our formulation allows for tuning the trade-off between clustering quality and fairness. Experimental results on graphs generated from the standard stochastic block model demonstrate the superiority of our approach in achieving an optimal accuracy-fairness trade-off compared to state-of-the-art methods.
• Abstract（参考訳）: 公平なグラフクラスタリングは、ネットワーク分析における多様なコミュニティの公平な表現と扱いを確保するために不可欠である。 伝統的な手法は、社会的、経済的、人口集団間の格差を無視し、偏見のある結果に永続し、不平等を補強する。 本研究では,異なる影響原理の枠組み内での公正なグラフクラスタリングを導入し,クラスタリング品質と公正性制約を統合した共同最適化問題として扱う。 この問題のNPハード性を考えると、基礎となる最適化問題を近似するために半定値緩和法を用いる。 中規模グラフでは特異値分解に基づくアルゴリズムを用いるが、大規模グラフでは乗算器の代替方向法に基づく新しいアルゴリズムを提案する。 既存の方法とは異なり、私たちの定式化はクラスタリングの品質と公平性の間のトレードオフを調整できます。 標準確率ブロックモデルから生成されたグラフに関する実験結果は,最先端手法と比較して,最適精度・公正トレードオフを実現する上で,我々のアプローチの優位性を示している。

関連論文リスト

• Distributed Solution of the Inverse Rig Problem in Blendshape Facial Animation [0.0]
  リグのインバージョンは、アバターの現実的で魅力的なパフォーマンスを可能にするため、顔アニメーションの中心である。 より高速なソリューションへのアプローチとして、顔の空間的性質を活用するクラスタリングがある。 本稿では、重なり合うコンポーネントのより確実な推定を得るために、クラスタ結合を伴ってさらに一歩進める。
  論文  参考訳（メタデータ） (2023-03-11T10:34:07Z)
• Optimal Propagation for Graph Neural Networks [51.08426265813481]
  最適グラフ構造を学習するための二段階最適化手法を提案する。 また、時間的複雑さをさらに軽減するために、低ランク近似モデルについても検討する。
  論文  参考訳（メタデータ） (2022-05-06T03:37:00Z)
• Data-heterogeneity-aware Mixing for Decentralized Learning [63.83913592085953]
  グラフの混合重みとノード間のデータ不均一性の関係に収束の依存性を特徴付ける。 グラフが現在の勾配を混合する能力を定量化する計量法を提案する。 そこで本研究では,パラメータを周期的かつ効率的に最適化する手法を提案する。
  論文  参考訳（メタデータ） (2022-04-13T15:54:35Z)
• Bayesian Graph Contrastive Learning [55.36652660268726]
  本稿では,ランダムな拡張がエンコーダにつながることを示すグラフコントラスト学習手法の新たな視点を提案する。 提案手法は,各ノードを決定論的ベクトルに埋め込む既存の手法とは対照的に,各ノードを潜在空間の分布で表現する。 いくつかのベンチマークデータセットにおける既存の最先端手法と比較して,性能が大幅に向上したことを示す。
  論文  参考訳（メタデータ） (2021-12-15T01:45:32Z)
• Group-Aware Threshold Adaptation for Fair Classification [9.496524884855557]
  複数のフェアネス制約を克服する新しいポストプロセッシング手法を提案する。 理論的には,同条件下での既存手法よりも近似最適に近い上界を許容する。 実験の結果,本手法は最先端の手法よりも優れていた。
  論文  参考訳（メタデータ） (2021-11-08T04:36:37Z)
• Multilayer Graph Clustering with Optimized Node Embedding [70.1053472751897]
  多層グラフクラスタリングは、グラフノードをカテゴリまたはコミュニティに分割することを目指しています。 与えられた多層グラフの層をクラスタリングに親しみやすい埋め込みを提案する。 実験の結果,本手法は著しい改善をもたらすことがわかった。
  論文  参考訳（メタデータ） (2021-03-30T17:36:40Z)
• Towards Optimal Problem Dependent Generalization Error Bounds in Statistical Learning Theory [11.840747467007963]
  我々は,「ベスト勾配仮説」で評価された分散,有効損失誤差,ノルムとほぼ最適にスケールする問題依存率について検討する。 一様局所収束(uniform localized convergence)と呼ばれる原理的枠組みを導入する。 我々は,既存の一様収束と局所化解析のアプローチの基本的制約を,我々のフレームワークが解決していることを示す。
  論文  参考訳（メタデータ） (2020-11-12T04:07:29Z)
• Multilayer Clustered Graph Learning [66.94201299553336]
  我々は、観測された層を代表グラフに適切に集約するために、データ忠実度用語として対照的な損失を用いる。 実験により,本手法がクラスタクラスタw.r.tに繋がることが示された。 クラスタリング問題を解くためのクラスタリングアルゴリズムを学習する。
  論文  参考訳（メタデータ） (2020-10-29T09:58:02Z)
• Fair Correlation Clustering [92.15492066925977]
  相関クラスタリングの近似アルゴリズムは,いくつかの重要なフェアネス制約の下で得られる。 相関クラスタリングに対する公平な解は、最先端の(不公平な)アルゴリズムと比較して、コストを抑えながら得られることを示す。
  論文  参考訳（メタデータ） (2020-02-06T14:28:21Z)

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

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