論文の概要: Modification-Fair Cluster Editing

• arxiv url: http://arxiv.org/abs/2112.03183v1
• Date: Mon, 6 Dec 2021 17:22:30 GMT
• ステータス: 処理完了
• システム内更新日: 2021-12-07 18:29:15.707109
• Title: Modification-Fair Cluster Editing
• Title（参考訳）: 修正フェールクラスタ編集
• Authors: Vincent Froese, Leon Kellerhals, and Rolf Niedermeier
• Abstract要約: クラスタ編集問題(Cluster Editing problem)は、少数のエッジ修正によって、グラフをクランプ(クラスタ)の解離結合に変換することを要求する。 NP-hard Cluster Editing問題に対する標準的なアルゴリズムは、データのサブグループに偏った解をもたらす可能性がある。 本稿では,各サブグループに対する編集回数がそのサイズに比例する修正公正度制約を提案する。
• 参考スコア（独自算出の注目度）: 9.675004827418805
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The classic Cluster Editing problem (also known as Correlation Clustering) asks to transform a given graph into a disjoint union of cliques (clusters) by a small number of edge modifications. When applied to vertex-colored graphs (the colors representing subgroups), standard algorithms for the NP-hard Cluster Editing problem may yield solutions that are biased towards subgroups of data (e.g., demographic groups), measured in the number of modifications incident to the members of the subgroups. We propose a modification fairness constraint which ensures that the number of edits incident to each subgroup is proportional to its size. To start with, we study Modification-Fair Cluster Editing for graphs with two vertex colors. We show that the problem is NP-hard even if one may only insert edges within a subgroup; note that in the classic "non-fair" setting, this case is trivially polynomial-time solvable. However, in the more general editing form, the modification-fair variant remains fixed-parameter tractable with respect to the number of edge edits. We complement these and further theoretical results with an empirical analysis of our model on real-world social networks where we find that the price of modification-fairness is surprisingly low, that is, the cost of optimal modification-fair differs from the cost of optimal "non-fair" solutions only by a small percentage.
• Abstract（参考訳）: 古典的なクラスタ編集問題(相関クラスタリング(英語版)とも呼ばれる)は、少数のエッジ修正により、与えられたグラフをクランプ(クラスタ)の解離結合に変換するよう要求する。 頂点色グラフ(サブグループを表す色)に適用した場合、NPハードクラスタ編集問題の標準的なアルゴリズムは、データのサブグループ(例えば、人口統計群)に偏った解を導き、サブグループのメンバーに発生する修正数で測定する。 本稿では,各サブグループに対する編集回数がそのサイズに比例することを保証する修正公平性制約を提案する。 まず,2つの頂点色を持つグラフの修正・フェアクラスタ編集について検討する。 古典的な「非フェア」設定では、このケースは自明に多項式時間で解くことができる。 しかし、より一般的な編集形式では、修正・フェア変種はエッジの編集数に対して固定パラメータの扱いが可能だ。 これらを補完し、実世界のソーシャルネットワーク上でのモデルに関する実証的な分析を行い、修正対フェアネスの価格が驚くほど低いこと、すなわち最適な修正対フェアのコストが最適の「非フェア」ソリューションのコストとわずかに異なることを発見した。

関連論文リスト

• Fair Minimum Representation Clustering via Integer Programming [0.6906005491572401]
  クラスタリングは、データをクラスタの集合に分割することを目的とした教師なしの学習タスクである。 本稿では,各群が最小表現レベルを持つ必要があるという制約を伴って,k平均とkメダニアンのクラスタリング問題を考察する。 フェアネス制約を直接組み込んだ,MiniReLと呼ばれる交代最小化アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-09-04T00:13:40Z)
• Post-hoc Bias Scoring Is Optimal For Fair Classification [12.897626117694317]
  バイアススコアと呼ばれる新しいインスタンスレベルのバイアス尺度を導入し、修正規則は有限量のバイアススコアの上に単純な線形ルールである。 DPとEOpの制約の場合、修正規則は1つのバイアススコアをしきい値にし、EOの制約の場合、線形修正規則を2つのパラメータに適合させることが要求される。
  論文  参考訳（メタデータ） (2023-10-09T13:54:08Z)
• Spectral Normalized-Cut Graph Partitioning with Fairness Constraints [18.835004555146575]
  正規化されたグラフ分割は、グラフ内のノードの集合を$k$ディスジョイントクラスタに分割して、任意のクラスタと他のクラスタ間の全エッジの分画を最小限にすることを目的としている。 本稿では,ノードが異なる階層群に属することを示す分類学的属性によって特徴付けられる分割問題の公平な変種について考察する。 私たちの目標は、正規化されたカット値を最小化しながら、各グループが各クラスタにほぼ比例的に表現されることを保証することです。
  論文  参考訳（メタデータ） (2023-07-22T12:20:46Z)
• 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)
• Personalized Federated Learning via Convex Clustering [72.15857783681658]
  本稿では,局所凸型ユーザコストを用いた個人化フェデレーション学習のためのアルゴリズム群を提案する。 提案するフレームワークは,異なるユーザのモデルの違いをペナル化する凸クラスタリングの一般化に基づいている。
  論文  参考訳（メタデータ） (2022-02-01T19:25:31Z)
• On the Adversarial Robustness of LASSO Based Feature Selection [72.54211869067979]
  検討されたモデルでは、悪意のある敵がデータセット全体を観察し、レスポンス値やフィーチャーマトリックスを慎重に修正する。 両レベルの最適化問題として、敵の修正戦略を定式化する。 合成および実データを用いた数値的な例は,本手法が効率的かつ効果的であることを示している。
  論文  参考訳（メタデータ） (2020-10-20T05:51:26Z)
• Boosting Data Reduction for the Maximum Weight Independent Set Problem Using Increasing Transformations [59.84561168501493]
  最大重み独立集合問題に対する新しい一般化データ削減および変換規則を導入する。 驚くべきことに、これらのいわゆる増進変換は問題を単純化し、還元空間を開き、アルゴリズムの後にさらに小さな既約グラフが得られる。 提案アルゴリズムは, 1つのインスタンスを除くすべての既約グラフを計算し, 従来よりも多くのインスタンスを最適に解き, 最高の最先端解法よりも最大2桁高速に解き, 解法DynWVCやHILSよりも高品質な解を求める。
  論文  参考訳（メタデータ） (2020-08-12T08:52:50Z)
• Fair Correlation Clustering [18.00619071013106]
  本稿では,各ノードが色を持つ相関クラスタリング問題に対して,公平性制約の2つのバリエーションを検討する。 本研究では,実世界のデータセットに対する実験的な評価により,公平なクラスタを生成するアルゴリズムの有効性を示す。
  論文  参考訳（メタデータ） (2020-02-10T02:59:17Z)
• Optimal Clustering from Noisy Binary Feedback [75.17453757892152]
  本稿では,二元的ユーザフィードバックから一組のアイテムをクラスタリングする問題について検討する。 最小クラスタ回復誤差率のアルゴリズムを考案する。 適応選択のために,情報理論的誤差下界の導出にインスパイアされたアルゴリズムを開発する。
  論文  参考訳（メタデータ） (2019-10-14T09:18:26Z)

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

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