論文の概要: Learning to Maximize Influence

• arxiv url: http://arxiv.org/abs/2108.04623v1
• Date: Tue, 10 Aug 2021 12:08:15 GMT
• ステータス: 処理完了
• システム内更新日: 2021-08-11 18:43:23.989195
• Title: Learning to Maximize Influence
• Title（参考訳）: 影響を最大化する学習
• Authors: George Panagopoulos, Nikolaos Tziortziotis, Fragkiskos D. Malliaros, Michalis Vazirgiannis
• Abstract要約: 我々は、影響推定、#P-ハードカウント問題、NP-ハード問題という2つの問題に焦点をあてる。 我々は,ニューラルネットワーク(GNN)であるGLIEを開発し,上界の影響をパラメータ化し,小さなシミュレーショングラフ上で学習する。 実験により、GLIEは影響推定の代替手段よりも正確な予測を高速に行えることが示された。
• 参考スコア（独自算出の注目度）: 22.80468577945578
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: As the field of machine learning for combinatorial optimization advances, traditional problems are resurfaced and readdressed through this new perspective. The overwhelming majority of the literature focuses on small graph problems, while several real-world problems are devoted to large graphs. Here, we focus on two such problems that are related: influence estimation, a \#P-hard counting problem, and influence maximization, an NP-hard problem. We develop GLIE, a Graph Neural Network (GNN) that inherently parameterizes an upper bound of influence estimation and train it on small simulated graphs. Experiments show that GLIE can provide accurate predictions faster than the alternatives for graphs 10 times larger than the train set. More importantly, it can be used on arbitrary large graphs for influence maximization, as the predictions can rank effectively seed sets even when the accuracy deteriorates. To showcase this, we propose a version of a standard Influence Maximization (IM) algorithm where we substitute traditional influence estimation with the predictions of GLIE.We also transfer GLIE into a reinforcement learning model that learns how to choose seeds to maximize influence sequentially using GLIE's hidden representations and predictions. The final results show that the proposed methods surpasses a previous GNN-RL approach and perform on par with a state-of-the-art IM algorithm.
• Abstract（参考訳）: コンビネート最適化のための機械学習の分野が進むにつれて、従来の問題は新たな視点で再浮上し、読み直される。 文学の圧倒的多数は小さなグラフ問題に焦点を合わせているが、いくつかの実世界の問題は大きなグラフに当てられている。 ここでは, 影響推定, \#p-ハードカウント問題, 影響最大化, np-ハード問題という2つの問題に焦点を当てた。 我々は,自然に影響評価の上限をパラメータ化し,それを小さなシミュレーショングラフ上で訓練するグラフニューラルネットワーク(GNN)であるGLIEを開発した。 実験により、GLIEは列車の10倍のグラフの代替よりも正確に予測できることがわかった。 さらに重要なことに、任意の大きなグラフで影響の最大化に利用することができ、精度が低下しても効果的に種集合をランク付けすることができる。 これを示すために,従来の影響推定をGLIEの予測に置き換える標準影響最大化(IM)アルゴリズムのバージョンを提案する。また,GLIEの隠れ表現と予測を用いて,影響を逐次的に最大化する種の選択方法を学ぶ強化学習モデルにGLIEを移す。 その結果,提案手法は従来のGNN-RL手法を超越し,最先端のIMアルゴリズムに匹敵する性能を示した。

関連論文リスト

• 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)

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

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