論文の概要: The CriticalSet problem: Identifying Critical Contributors in Bipartite Dependency Networks

• arxiv url: http://arxiv.org/abs/2604.21537v1
• Date: Thu, 23 Apr 2026 11:00:07 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-24 14:40:06.456537
• Title: The CriticalSet problem: Identifying Critical Contributors in Bipartite Dependency Networks
• Title（参考訳）: クリティカルセット問題:バイパーティイト依存ネットワークにおけるクリティカルコントリビュータの特定
• Authors: Sebastiano A. Piccolo, Andrea Tagarelli,
• Abstract要約: 我々は,最大数のアイテムを除去するk個のコントリビュータを識別するCriticalSet問題を定式化する。 我々は,接続冗長性を明示的に考慮した線形時間反復剥離アルゴリズムMinCovを提案する。 2億5000万のエッジを持つWikipediaグラフを含む、合成および大規模リアルデータセットの実験では、MinCovとShapleyCovは従来のベースラインを大幅に上回っている。
• 参考スコア（独自算出の注目度）: 5.3383934005817
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Identifying critical nodes in complex networks is a fundamental task in graph mining. Yet, methods addressing an all-or-nothing coverage mechanics in a bipartite dependency network, a graph with two types of nodes where edges represent dependency relationships across the two groups only, remain largely unexplored. We formalize the CriticalSet problem: given an arbitrary bipartite graph modeling dependencies of items on contributors, identify the set of k contributors whose removal isolates the largest number of items. We prove that this problem is NP-hard and requires maximizing a supermodular set function, for which standard forward greedy algorithms provide no approximation guarantees. Consequently, we model CriticalSet as a coalitional game, deriving a closed-form centrality, ShapleyCov, based on the Shapley value. This measure can be interpreted as the expected number of items isolated by a contributor's departure. Leveraging these insights, we propose MinCov, a linear-time iterative peeling algorithm that explicitly accounts for connection redundancy, prioritizing contributors who uniquely support many items. Extensive experiments on synthetic and large-scale real datasets, including a Wikipedia graph with over 250 million edges, reveal that MinCov and ShapleyCov significantly outperform traditional baselines. Notably, MinCov achieves near-optimal performance, within 0.02 AUC of a Stochastic Hill Climbing metaheuristic, while remaining several orders of magnitude faster.
• Abstract（参考訳）: 複雑なネットワークにおけるクリティカルノードの同定は、グラフマイニングの基本的な課題である。 しかし、エッジが2つのグループにまたがる依存性関係を表す2種類のノードを持つグラフは、ほとんど探索されていないままである。 コントリビュータ上のアイテムの任意の二部グラフモデルが与えられた場合、削除したアイテムを最も多く分離するkコントリビュータの集合を識別する。 この問題はNPハードであり、標準のフォワードグリードアルゴリズムが近似保証を提供しない超モジュラー集合関数を最大化する必要があることを証明している。 その結果、我々はCriticalSetを連立ゲームとしてモデル化し、Shapley値に基づいて閉形式のShapleyCovを導出する。 この尺度は、コントリビュータの離脱によって孤立したアイテムの期待数と解釈できる。 これらの知見を生かして,多くの項目を独自にサポートしているコントリビュータを優先して,接続冗長性を明示的に考慮した線形時間反復剥離アルゴリズムMinCovを提案する。 2億5000万のエッジを持つWikipediaグラフを含む、合成および大規模リアルデータセットに関する大規模な実験により、MinCovとShapleyCovが従来のベースラインを大幅に上回っていることが明らかになった。 特に、MinCovは、Stochastic Hill Climbing Metaheuristic の0.02 AUCで準最適性能を達成し、数桁高速に維持できる。

関連論文リスト

• ScaleGNN: Towards Scalable Graph Neural Networks via Adaptive High-order Neighboring Feature Fusion [73.85920403511706]
  スケーラブルで効果的なグラフ学習のためのマルチホップノード機能を適応的に融合する新しいフレームワークであるScaleGNNを提案する。 予測精度と計算効率の両面で,ScaleGNNは最先端のGNNよりも一貫して優れていることを示す。
  論文  参考訳（メタデータ） (2025-04-22T14:05:11Z)
• A Greedy Strategy for Graph Cut [95.2841574410968]
  GGCと呼ばれるグラフカットの問題を解決するための欲求戦略を提案する。 これは、各データサンプルがクラスタと見なされる状態から始まり、2つのクラスタを動的にマージする。 GGCはサンプル数に関してほぼ線形な計算複雑性を持つ。
  論文  参考訳（メタデータ） (2024-12-28T05:49:42Z)
• Learning Feature Matching via Matchable Keypoint-Assisted Graph Neural Network [52.29330138835208]
  画像のペア間の局所的な特徴の正確なマッチングは、コンピュータビジョンの課題である。 従来の研究では、注意に基づくグラフニューラルネットワーク(GNN)と、画像内のキーポイントに完全に接続されたグラフを使用するのが一般的だった。 本稿では,非繰り返しキーポイントをバイパスし,マッチング可能なキーポイントを利用してメッセージパッシングを誘導する,疎注意に基づくGNNアーキテクチャであるMaKeGNNを提案する。
  論文  参考訳（メタデータ） (2023-07-04T02:50:44Z)
• Semi-Supervised Clustering of Sparse Graphs: Crossing the Information-Theoretic Threshold [3.6052935394000234]
  ブロックモデルは、ネットワーク構造データのクラスタリングとコミュニティ検出のための標準ランダムグラフモデルである。 ネットワークトポロジに基づく推定器は、モデルパラメータが一定の閾値以下である場合、スパースグラフの確率よりも大幅に向上する。 パラメータ領域全体でラベルの任意の部分で実現可能であることを示す。
  論文  参考訳（メタデータ） (2022-05-24T00:03:25Z)
• Unsupervised Features Ranking via Coalitional Game Theory for Categorical Data [0.28675177318965034]
  教師なしの機能選択は、機能の数を減らすことを目的としている。 導出特徴の選択は、冗長率を下げる競合する手法よりも優れていることを示す。
  論文  参考訳（メタデータ） (2022-05-17T14:17:36Z)
• Learning to Detect Critical Nodes in Sparse Graphs via Feature Importance Awareness [53.351863569314794]
  クリティカルノード問題(CNP)は、削除が残余ネットワークのペア接続性を最大に低下させるネットワークから臨界ノードの集合を見つけることを目的としている。 本研究は,ノード表現のための特徴重要度対応グラフアテンションネットワークを提案する。 ダブルディープQネットワークと組み合わせて、初めてCNPを解くエンドツーエンドのアルゴリズムを作成する。
  論文  参考訳（メタデータ） (2021-12-03T14:23:05Z)
• Bend-Net: Bending Loss Regularized Multitask Learning Network for Nuclei Segmentation in Histopathology Images [65.47507533905188]
  重なり合う核を正確に分離するために、曲げ損失正規化器を備えた新しいマルチタスク学習ネットワークを提案する。 新たに提案されたマルチタスク学習アーキテクチャは、3つのタスクから共有表現を学習することで一般化を促進する。 提案した曲げ損失は,輪郭点を大きな曲率で囲むために高いペナルティを定義し,小さな曲率で凸輪郭点に小さなペナルティを適用した。
  論文  参考訳（メタデータ） (2021-09-30T17:29:44Z)

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

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