論文の概要: Learning to Detect Critical Nodes in Sparse Graphs via Feature Importance Awareness

• arxiv url: http://arxiv.org/abs/2112.03404v2
• Date: Wed, 8 May 2024 08:11:58 GMT
• ステータス: 処理完了
• システム内更新日: 2024-05-09 19:50:32.320328
• Title: Learning to Detect Critical Nodes in Sparse Graphs via Feature Importance Awareness
• Title（参考訳）: 特徴重要度認識によるスパースグラフにおける臨界ノード検出の学習
• Authors: Xuwei Tan, Yangming Zhou, MengChu Zhou, Zhang-Hua Fu,
• Abstract要約: クリティカルノード問題(CNP)は、削除が残余ネットワークのペア接続性を最大に低下させるネットワークから臨界ノードの集合を見つけることを目的としている。 本研究は,ノード表現のための特徴重要度対応グラフアテンションネットワークを提案する。 ダブルディープQネットワークと組み合わせて、初めてCNPを解くエンドツーエンドのアルゴリズムを作成する。
• 参考スコア（独自算出の注目度）: 53.351863569314794
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Detecting critical nodes in sparse graphs is important in a variety of application domains, such as network vulnerability assessment, epidemic control, and drug design. The critical node problem (CNP) aims to find a set of critical nodes from a network whose deletion maximally degrades the pairwise connectivity of the residual network. Due to its general NP-hard nature, state-of-the-art CNP solutions are based on heuristic approaches. Domain knowledge and trial-and-error are usually required when designing such approaches, thus consuming considerable effort and time. This work proposes a feature importance-aware graph attention network for node representation and combines it with dueling double deep Q-network to create an end-to-end algorithm to solve CNP for the first time. It does not need any problem-specific knowledge or labeled datasets as required by most of existing methods. Once the model is trained, it can be generalized to cope with various types of CNPs (with different sizes and topological structures) without re-training. Computational experiments on 28 real-world networks show that the proposed method is highly comparable to state-of-the-art methods. It does not require any problem-specific knowledge and, hence, can be applicable to many applications including those impossible ones by using the existing approaches. It can be combined with some local search methods to further improve its solution quality. Extensive comparison results are given to show its effectiveness in solving CNP.
• Abstract（参考訳）: スパースグラフにおけるクリティカルノードの検出は、ネットワーク脆弱性評価、疫病対策、薬物設計など、さまざまなアプリケーション領域において重要である。 クリティカルノード問題(CNP)は、削除が残余ネットワークのペア接続性を最大に低下させるネットワークから臨界ノードの集合を見つけることを目的としている。 一般のNPハードの性質のため、最先端のCNP解はヒューリスティックなアプローチに基づいている。 ドメインの知識と試行錯誤は通常、そのようなアプローチを設計する際に必要となるため、かなりの労力と時間を要する。 本研究は,ノード表現のための特徴量認識グラフアテンションネットワークを提案し,これを二重深度Qネットワークと組み合わせて,初めてCNPを解くエンドツーエンドアルゴリズムを作成する。 既存のほとんどのメソッドで必要とされる問題固有の知識やラベル付きデータセットは必要ない。 モデルが訓練されると、様々な種類のCNP(大きさと位相構造が異なる)に再学習することなく対処するように一般化することができる。 28の実世界のネットワーク上での計算実験により,提案手法は最先端の手法に非常に匹敵することを示した。 問題固有の知識は一切必要とせず、従って既存のアプローチを用いることで、不可能なものを含む多くのアプリケーションに適用することができる。 ソリューションの品質をさらに向上するために、いくつかのローカル検索手法と組み合わせることができる。 CNPの解法の有効性を示すために, 大規模な比較結果が得られた。

関連論文リスト

• Improving Critical Node Detection Using Neural Network-based Initialization in a Genetic Algorithm [3.5877750256097465]
  CNP-1aの主な目的は、ネットワークから限られた数のノードを削除した後、残りのネットワークにおけるペアワイズ接続を最小限にすることである。 CNP-1aを解く効率を改善するために、K2GAという知識誘導型遺伝的アルゴリズムが提案されている。 提案した知識誘導型遺伝的アルゴリズムの有効性は,26の実世界の複雑なネットワーク上での実験により検証された。
  論文  参考訳（メタデータ） (2024-02-01T07:53:25Z)
• A Fast Algorithm for Moderating Critical Nodes via Edge Removal [19.130541561303293]
  対象ノードの情報集中度を最小限に抑えるために,ネットワークから$k$エッジを除去する問題について検討する。 ランダムウォークに基づくシュア補数近似や高速和推定などの新しい手法を用いて、3つの近似グリードアルゴリズムを提案する。 理論的解析を補完するため、100万以上のノードを持つ合成および実ネットワークに関する包括的な実験を行う。
  論文  参考訳（メタデータ） (2023-09-09T13:54:34Z)
• NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification [70.51126383984555]
  本稿では,任意のノード間のノード信号を効率的に伝搬する全ペアメッセージパッシング方式を提案する。 効率的な計算は、カーナライズされたGumbel-Softmax演算子によって実現される。 グラフ上のノード分類を含む様々なタスクにおいて,本手法の有望な有効性を示す実験を行った。
  論文  参考訳（メタデータ） (2023-06-14T09:21:15Z)
• Towards Better Out-of-Distribution Generalization of Neural Algorithmic Reasoning Tasks [51.8723187709964]
  ニューラルネットワーク推論タスクのOOD一般化について検討する。 目標は、ディープニューラルネットワークを使用して入出力ペアからアルゴリズムを学ぶことである。
  論文  参考訳（メタデータ） (2022-11-01T18:33:20Z)
• A Differentiable Approach to Combinatorial Optimization using Dataless Neural Networks [20.170140039052455]
  我々は、ソリューションを生成するニューラルネットワークのトレーニングにデータを必要としないという、根本的に異なるアプローチを提案する。 特に、最適化問題をニューラルネットワークに還元し、データレストレーニングスキームを用いて、それらのパラメータが関心の構造をもたらすように、ネットワークのパラメータを洗練する。
  論文  参考訳（メタデータ） (2022-03-15T19:21:31Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)
• Exclusion and Inclusion -- A model agnostic approach to feature importance in DNNs [3.6888633946892044]
  入力特徴のフレーズ単位の重要度を計算するモデルアルゴリズムを提案する。 我々のアプローチは外れ値に対して堅牢であり、入力の本質的な側面のみをキャプチャすることを意味する。
  論文  参考訳（メタデータ） (2020-07-13T07:50:53Z)
• Graph Prototypical Networks for Few-shot Learning on Attributed Networks [72.31180045017835]
  グラフメタ学習フレームワーク - Graph Prototypeal Networks (GPN) を提案する。 GPNは、属性付きネットワーク上でテキストミータ学習を行い、ターゲット分類タスクを扱うための高度に一般化可能なモデルを導出する。
  論文  参考訳（メタデータ） (2020-06-23T04:13:23Z)
• Neighborhood Information-based Probabilistic Algorithm for Network Disintegration [7.511240139514371]
  本稿では,近隣情報とノードの重要度に基づく確率的アプローチを提案する。 新たな中心性に基づく重要度尺度(IM)も定義する。 実験の結果,提案したNIPAは4つの手法の中で最も有効であることが示唆された。
  論文  参考訳（メタデータ） (2020-03-08T15:09:25Z)
• Towards an Efficient and General Framework of Robust Training for Graph Neural Networks [96.93500886136532]
  グラフニューラルネットワーク(GNN)は、いくつかの基本的な推論タスクに大きく進歩している。 GNNの目覚ましい性能にもかかわらず、グラフ構造上の摂動を慎重に作り、誤った予測を下すことが観察されている。 我々は,強靭なGNNを得るために,欲求探索アルゴリズムとゼロ階法を利用する汎用フレームワークを提案する。
  論文  参考訳（メタデータ） (2020-02-25T15:17:58Z)

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

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