論文の概要: GraMeR: Graph Meta Reinforcement Learning for Multi-Objective Influence
Maximization
- arxiv url: http://arxiv.org/abs/2205.14834v1
- Date: Mon, 30 May 2022 03:48:51 GMT
- ステータス: 処理完了
- システム内更新日: 2022-06-01 08:02:15.036763
- Title: GraMeR: Graph Meta Reinforcement Learning for Multi-Objective Influence
Maximization
- Title(参考訳): GraMeR:多目的影響最大化のためのグラフメタ強化学習
- Authors: Sai Munikoti, Balasubramaniam Natarajan and Mahantesh Halappanavar
- Abstract要約: インフルエンス(IM)とは、ネットワーク内のシードノードと呼ばれるノードのサブセットを特定する問題である(グラフ)。
IMには、バイラルマーケティング、疫病対策、センサー配置、その他のネットワーク関連タスクなど、数多くの応用がある。
我々は、本質的および影響的アクティベーションの両方を扱うマルコフ決定プロセスとして、一般的なIM問題を開発する。
- 参考スコア(独自算出の注目度): 1.7311053765541482
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Influence maximization (IM) is a combinatorial problem of identifying a
subset of nodes called the seed nodes in a network (graph), which when
activated, provide a maximal spread of influence in the network for a given
diffusion model and a budget for seed set size. IM has numerous applications
such as viral marketing, epidemic control, sensor placement and other
network-related tasks. However, the uses are limited due to the computational
complexity of current algorithms. Recently, learning heuristics for IM have
been explored to ease the computational burden. However, there are serious
limitations in current approaches such as: (1) IM formulations only consider
influence via spread and ignore self activation; (2) scalability to large
graphs; (3) generalizability across graph families; (4) low computational
efficiency with a large running time to identify seed sets for every test
network. In this work, we address each of these limitations through a unique
approach that involves (1) formulating a generic IM problem as a Markov
decision process that handles both intrinsic and influence activations; (2)
employing double Q learning to estimate seed nodes; (3) ensuring scalability
via sub-graph based representations; and (4) incorporating generalizability via
meta-learning across graph families. Extensive experiments are carried out in
various standard networks to validate performance of the proposed Graph Meta
Reinforcement learning (GraMeR) framework. The results indicate that GraMeR is
multiple orders faster and generic than conventional approaches.
- Abstract(参考訳): 影響最大化(im)は、ネットワーク内のシードノード(graph)と呼ばれるノードのサブセットを識別する組合せ問題であり、活性化されると、与えられた拡散モデルとシードセットサイズの予算に対してネットワーク内の影響の最大拡散を提供する。
IMには、バイラルマーケティング、疫病対策、センサー配置、その他のネットワーク関連タスクなど、数多くの応用がある。
しかし、現在のアルゴリズムの計算量は限られている。
近年,IMの学習ヒューリスティックスは計算負担を軽減するために研究されている。
しかしながら,1) IM の定式化は,自己活性化による影響のみを考慮し,(2) グラフへの拡張性,(3) グラフファミリ間の一般化性,(4) テストネットワーク毎にシードセットを識別するための実行時間の多い計算効率の低下など,現在のアプローチには重大な制限がある。
本研究では,(1)内在的および影響的アクティベーションの両方を扱うマルコフ決定過程として汎用IM問題を定式化すること,(2)シードノードを推定するために二重Q学習を採用すること,(3)サブグラフベース表現によるスケーラビリティを確保すること,(4)グラフファミリ間のメタラーニングによる一般化性を取り入れること,など,これらの制限に対処する。
提案するグラフメタ強化学習(GraMeR)フレームワークの性能を評価するため,各種標準ネットワークで大規模な実験を行った。
その結果,GraMeRは従来の手法よりも高速で汎用的であることが示唆された。
関連論文リスト
- Multitask Active Learning for Graph Anomaly Detection [48.690169078479116]
MultItask acTIve Graph Anomaly Detection framework,すなわちMITIGATEを提案する。
ノード分類タスクを結合することにより、MITIGATEは既知の異常を伴わずに配布外ノードを検出する能力を得る。
4つのデータセットに関する実証的研究は、MITIGATEが異常検出のための最先端の手法を著しく上回っていることを示している。
論文 参考訳(メタデータ) (2024-01-24T03:43:45Z) - Network Alignment with Transferable Graph Autoencoders [87.28177782039265]
本稿では,強力で堅牢なノード埋め込みを抽出するグラフオートエンコーダアーキテクチャを提案する。
生成した埋め込みがグラフの固有値と固有ベクトルと結びついていることを証明する。
提案フレームワークは転送学習とデータ拡張を利用して,大規模なネットワークアライメントを実現する。
論文 参考訳(メタデータ) (2023-10-05T02:58:29Z) - NodeFormer: A Scalable Graph Structure Learning Transformer for Node
Classification [70.51126383984555]
本稿では,任意のノード間のノード信号を効率的に伝搬する全ペアメッセージパッシング方式を提案する。
効率的な計算は、カーナライズされたGumbel-Softmax演算子によって実現される。
グラフ上のノード分類を含む様々なタスクにおいて,本手法の有望な有効性を示す実験を行った。
論文 参考訳(メタデータ) (2023-06-14T09:21:15Z) - Deep Graph Representation Learning and Optimization for Influence
Maximization [10.90744025490539]
インフルエンサー(IM)は、ソーシャルネットワークから初期ユーザのセットを選択して、影響を受けたユーザの期待人数を最大化する。
本稿では,シードセットの潜在表現を生成的に特徴付けるための新しいフレームワークであるDeepIMを提案する。
また、フレキシブルなノード分散性に基づく予算制約の下で最適なシードセットを推論する新たな目的関数を設計する。
論文 参考訳(メタデータ) (2023-05-01T15:45:01Z) - Causal Influence Maximization in Hypergraph [0.8185725740857595]
インフルエンス・最大化(IM)とは、あるネットワーク内の一定の数のシードノードを選択し、拡散効果を最大化するタスクである。
感染者の個別治療効果(ITE)の総和を最大化するために,textbfCauIMと呼ばれる新しいアルゴリズムを導入する。
論文 参考訳(メタデータ) (2023-01-28T15:34:03Z) - ToupleGDD: A Fine-Designed Solution of Influence Maximization by Deep
Reinforcement Learning [4.266866385061998]
本稿では、影響最大化(IM)問題に対処するため、新しいエンドツーエンドDRLフレームワークToupleGDDを提案する。
我々のモデルは、小さな予算でランダムに生成されたいくつかの小さなグラフで訓練され、様々な大きな予算の下で全く異なるネットワークでテストされる。
論文 参考訳(メタデータ) (2022-10-14T03:56:53Z) - Identifying critical nodes in complex networks by graph representation
learning [2.304938062591095]
影響は臨界ノードの採掘における主要な問題の一つである。
IMGNNは、ネットワーク内のノードの集中度を入力とし、最適な初期スプレッドラー内のノードを出力とするグラフ学習フレームワークである。
IMGNNは、ヒトベースのアルゴリズムよりも、固定感染規模で初期スプレッドラーのサイズを最小化するのに効率的である。
論文 参考訳(メタデータ) (2022-01-20T03:41:22Z) - MGAE: Masked Autoencoders for Self-Supervised Learning on Graphs [55.66953093401889]
Masked Graph Autoencoder (MGAE) フレームワークは、グラフ構造データの効果的な学習を行う。
自己指導型学習から洞察を得て、私たちはランダムに大量のエッジを隠蔽し、トレーニング中に欠落したエッジを再構築しようとします。
論文 参考訳(メタデータ) (2022-01-07T16:48:07Z) - FastCover: An Unsupervised Learning Framework for Multi-Hop Influence
Maximization in Social Networks [39.86798194955807]
ソーシャルネットワークで影響力のあるユーザーを見つけることは、多くの有用なアプリケーションにおいて根本的な問題である。
本稿では,IM の問題を予算制約付き d-hop 支配集合問題 (kdDSP) に還元する。
我々は、効率的な欲求戦略を教師なしで学習することでkdDSPを解決するために、統合機械学習(ML)フレームワークであるFastCoverを提案する。
FastCoverは、GNNの1つの前方伝播で計算されたノードのスコアから設定されたシード全体を決定する。
論文 参考訳(メタデータ) (2021-10-31T10:49:21Z) - Unveiling Anomalous Edges and Nominal Connectivity of Attributed
Networks [53.56901624204265]
本研究では、相補的な強さを持つ2つの異なる定式化を用いて、属性グラフの異常なエッジを明らかにする。
まず、グラフデータマトリックスを低ランクとスパースコンポーネントに分解することで、パフォーマンスを著しく向上させる。
第2は、乱れのないグラフを頑健に復元することにより、第1のスコープを広げ、異常識別性能を高める。
論文 参考訳(メタデータ) (2021-04-17T20:00:40Z) - Multi-hop Attention Graph Neural Network [70.21119504298078]
マルチホップアテンショングラフニューラルネットワーク(MAGNA)は、マルチホップコンテキスト情報を注目計算のすべての層に組み込む方法である。
MAGNAは各層における大規模構造情報を捕捉し,低域効果によりグラフデータからノイズの多い高周波情報を除去することを示す。
論文 参考訳(メタデータ) (2020-09-29T22:41:19Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。