論文の概要: Maximizing Influence with Graph Neural Networks

• arxiv url: http://arxiv.org/abs/2108.04623v6
• Date: Tue, 10 Oct 2023 12:54:03 GMT
• ステータス: 処理完了
• システム内更新日: 2023-10-13 17:34:18.247609
• Title: Maximizing Influence with Graph Neural Networks
• Title（参考訳）: グラフニューラルネットワークによる影響の最大化
• Authors: George Panagopoulos, Nikolaos Tziortziotis, Fragkiskos D. Malliaros, Michalis Vazirgiannis
• Abstract要約: 独立シードセットの影響を推定する方法を学習するグラフニューラルネットワークであるtextscGlieを提案する。 実験の結果,列車セットの最大10倍の実際のグラフに対する正確な影響推定が得られた。 我々は、GLIEの表現に基づいて、適応的にシードセットを構築しながらノードをランク付けするために、証明可能なサブモジュラーの影響を拡大する。
• 参考スコア（独自算出の注目度）: 23.896176168370996
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Finding the seed set that maximizes the influence spread over a network is a well-known NP-hard problem. Though a greedy algorithm can provide near-optimal solutions, the subproblem of influence estimation renders the solutions inefficient. In this work, we propose \textsc{Glie}, a graph neural network that learns how to estimate the influence spread of the independent cascade. GLIE relies on a theoretical upper bound that is tightened through supervised training.Experiments indicate that it provides accurate influence estimation for real graphs up to 10 times larger than the train set.Subsequently, we incorporate it into three influence maximization techniques.We first utilize Cost Effective Lazy Forward optimization substituting Monte Carlo simulations with GLIE, surpassing the benchmarks albeit with a computational overhead. To improve computational efficiency we first devise a Q-learning method that learns to choose seeds sequentially using GLIE's predictions. Finally, we arrive at the most efficient approach by developing a provably submodular influence spread based on GLIE's representations, to rank nodes while building the seed set adaptively. The proposed algorithms are inductive, meaning they are trained on graphs with less than 300 nodes and up to 5 seeds, and tested on graphs with millions of nodes and up to 200 seeds. The final method exhibits the most promising combination of time efficiency and influence quality, outperforming several baselines.
• Abstract（参考訳）: ネットワーク上に広がる影響を最大化するシードセットを見つけることは、よく知られたNPハード問題である。 グリーディアルゴリズムは最適に近い解を与えることができるが、影響推定のサブ確率は解を非効率にする。 本研究では,独立カスケードの影響拡散を推定する方法を学習するグラフニューラルネットワークである \textsc{glie} を提案する。 GLIEは, 教師付きトレーニングによって強化された理論上界に依存しており, 実験により, 実グラフが列車の最大10倍の精度で影響を推定できることが示されている。 計算効率を向上させるため,まずglieの予測を用いて種子選択を逐次学習するq学習法を考案する。 最後に,種集合を適応的に構築しながらノードのランク付けを行うために,glieの表現に基づいて拡散する有理サブモジュラー的影響を開発することで,最も効率的なアプローチに到達した。 提案されたアルゴリズムはインダクティブであり、300ノード未満のグラフと最大5シードのグラフでトレーニングされ、数百万ノードと最大200シードのグラフでテストされる。 最後の方法は、時間効率と影響品質の最も有望な組み合わせを示し、いくつかのベースラインを上回っている。

関連論文リスト

• The Heterophilic Snowflake Hypothesis: Training and Empowering GNNs for Heterophilic Graphs [59.03660013787925]
  ヘテロフィリー・スノーフレーク仮説を導入し、ヘテロ親和性グラフの研究をガイドし、促進するための効果的なソリューションを提供する。 観察の結果,我々のフレームワークは多種多様なタスクのための多目的演算子として機能することがわかった。 さまざまなGNNフレームワークに統合することができ、パフォーマンスを詳細に向上し、最適なネットワーク深さを選択するための説明可能なアプローチを提供する。
  論文  参考訳（メタデータ） (2024-06-18T12:16:00Z)
• Unifews: Unified Entry-Wise Sparsification for Efficient Graph Neural Network [10.556366638048384]
  グラフニューラルネットワーク(GNN)は、様々なグラフ学習タスクにおいて有望な性能を示すが、リソース集約型計算のコストがかかる。 従来の研究では,グラフレベルやネットワークレベルのスペーシフィケーション技術を活用して,計算予算の削減を試みた。 個々の行列要素を考慮したエントリワイズ方式で2つの演算を統一するUnifewsを提案する。
  論文  参考訳（メタデータ） (2024-03-20T03:07:30Z)
• Efficient Heterogeneous Graph Learning via Random Projection [58.4138636866903]
  不均一グラフニューラルネットワーク(HGNN)は、異種グラフを深層学習するための強力なツールである。 最近のプリ計算ベースのHGNNは、一時間メッセージパッシングを使用して不均一グラフを正規形テンソルに変換する。 我々はRandom Projection Heterogeneous Graph Neural Network (RpHGNN) というハイブリッド計算前HGNNを提案する。
  論文  参考訳（メタデータ） (2023-10-23T01:25:44Z)
• NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification [70.51126383984555]
  本稿では,任意のノード間のノード信号を効率的に伝搬する全ペアメッセージパッシング方式を提案する。 効率的な計算は、カーナライズされたGumbel-Softmax演算子によって実現される。 グラフ上のノード分類を含む様々なタスクにおいて,本手法の有望な有効性を示す実験を行った。
  論文  参考訳（メタデータ） (2023-06-14T09:21:15Z)
• DAG Matters! GFlowNets Enhanced Explainer For Graph Neural Networks [30.19635147123557]
  我々はGFlowNetsベースのGNN Explainer(GFlowExplainer)という生成構造を提案する。 我々のGFlowExplainerは、サブグラフの確率がその報酬に比例するサブグラフの分布を生成するポリシーを学習することを目的としています。 我々は合成データと実データの両方について広範な実験を行い、質的および定量的な結果はGFlowExplainerの優位性を示している。
  論文  参考訳（メタデータ） (2023-03-04T16:15:25Z)
• Influence Maximization (IM) in Complex Networks with Limited Visibility Using Statistical Methods [2.320417845168326]
  影響文学(IM)問題はNP完全問題(NP完全問題)として知られており、時間内に解が存在しない。 この複雑さを改善するために提案された手法のほとんどは、グラフ全体が見えるという仮定に基づいている。 本研究では,リンク予測手法による現在の手法を擬似可視グラフに拡張する。
  論文  参考訳（メタデータ） (2022-08-28T07:55:54Z)
• GraMeR: Graph Meta Reinforcement Learning for Multi-Objective Influence Maximization [1.7311053765541482]
  インフルエンス(IM)とは、ネットワーク内のシードノードと呼ばれるノードのサブセットを特定する問題である(グラフ)。 IMには、バイラルマーケティング、疫病対策、センサー配置、その他のネットワーク関連タスクなど、数多くの応用がある。 我々は、本質的および影響的アクティベーションの両方を扱うマルコフ決定プロセスとして、一般的なIM問題を開発する。
  論文  参考訳（メタデータ） (2022-05-30T03:48:51Z)
• Optimal Propagation for Graph Neural Networks [51.08426265813481]
  最適グラフ構造を学習するための二段階最適化手法を提案する。 また、時間的複雑さをさらに軽減するために、低ランク近似モデルについても検討する。
  論文  参考訳（メタデータ） (2022-05-06T03:37:00Z)
• Neighbor2Seq: Deep Learning on Massive Graphs by Transforming Neighbors to Sequences [55.329402218608365]
  本研究では,各ノードの階層的近傍をシーケンスに変換するためにNeighbor2Seqを提案する。 1100万以上のノードと160億のエッジを持つ大規模グラフ上で,本手法の評価を行った。 その結果,提案手法は大規模グラフに対してスケーラブルであり,大規模グラフと中規模グラフにまたがる優れた性能を実現する。
  論文  参考訳（メタデータ） (2022-02-07T16:38:36Z)
• Fast Graph Attention Networks Using Effective Resistance Based Graph Sparsification [70.50751397870972]
  FastGATは、スペクトルスペーシフィケーションを用いて、注目に基づくGNNを軽量にし、入力グラフの最適プルーニングを生成する手法である。 我々は,ノード分類タスクのための大規模実世界のグラフデータセット上でFastGATを実験的に評価した。
  論文  参考訳（メタデータ） (2020-06-15T22:07:54Z)

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

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