論文の概要: Feature Importance-aware Graph Attention Network and Dueling Double Deep
Q-Network Combined Approach for Critical Node Detection Problems
- arxiv url: http://arxiv.org/abs/2112.03404v1
- Date: Fri, 3 Dec 2021 14:23:05 GMT
- ステータス: 処理完了
- システム内更新日: 2021-12-11 07:19:09.799993
- Title: Feature Importance-aware Graph Attention Network and Dueling Double Deep
Q-Network Combined Approach for Critical Node Detection Problems
- Title(参考訳): 臨界ノード検出問題に対する特徴重要度対応グラフアテンションネットワークと二重ディープqネットワーク結合アプローチ
- Authors: Xuwei Tan, Yangming Zhou, Zhang-Hua Fu and Mengchu Zhou
- Abstract要約: クリティカルノード問題(Critical Node Problem, CNP)は、ネットワークから重要なノードの集合を見つけることを目的とした問題である。
本研究は,ノード表現のための特徴重要度対応グラフアテンションネットワークを提案する。
ダブルディープQネットワークと組み合わせて、初めてCNPを解くエンドツーエンドのアルゴリズムを作成する。
- 参考スコア(独自算出の注目度): 61.48763653120301
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Detecting critical nodes in sparse networks is important in a variety of
application domains. A 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. Extensive 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) - Learning to Identify Graphs from Node Trajectories in Multi-Robot
Networks [15.36505600407192]
本稿では,グローバル収束保証付きグラフトポロジを効率的に発見する学習ベースアプローチを提案する。
マルチロボット生成および群れ処理におけるグラフの同定におけるアプローチの有効性を実証する。
論文 参考訳(メタデータ) (2023-07-10T07:09:12Z) - Towards Better Out-of-Distribution Generalization of Neural Algorithmic
Reasoning Tasks [51.8723187709964]
ニューラルネットワーク推論タスクのOOD一般化について検討する。
目標は、ディープニューラルネットワークを使用して入出力ペアからアルゴリズムを学ぶことである。
論文 参考訳(メタデータ) (2022-11-01T18:33:20Z) - 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) - ESPN: Extremely Sparse Pruned Networks [50.436905934791035]
簡単な反復マスク探索法により,非常に深いネットワークの最先端の圧縮を実現することができることを示す。
本アルゴリズムは,シングルショット・ネットワーク・プルーニング法とロッテ・ティケット方式のハイブリッド・アプローチを示す。
論文 参考訳(メタデータ) (2020-06-28T23:09:27Z) - 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) - Deep HyperNetwork-Based MIMO Detection [10.433286163090179]
従来のアルゴリズムは複雑すぎて実用的すぎるか、パフォーマンスが悪いかのどちらかだ。
最近のアプローチでは、ディープニューラルネットワークとして検出器を実装することで、これらの課題に対処しようとした。
本研究では、チャネル行列を入力とし、ニューラルネットワークベースの検出器の重みを生成するハイパーネットワークと呼ばれる追加のニューラルネットワーク(NN)をトレーニングすることで、両方の問題に対処する。
論文 参考訳(メタデータ) (2020-02-07T13:03:22Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。