論文の概要: FastCover: An Unsupervised Learning Framework for Multi-Hop Influence Maximization in Social Networks

• arxiv url: http://arxiv.org/abs/2111.00463v1
• Date: Sun, 31 Oct 2021 10:49:21 GMT
• ステータス: 処理完了
• システム内更新日: 2021-11-02 17:07:51.603084
• Title: FastCover: An Unsupervised Learning Framework for Multi-Hop Influence Maximization in Social Networks
• Title（参考訳）: FastCover: ソーシャルネットワークにおけるマルチホップ影響最大化のための教師なし学習フレームワーク
• Authors: Runbo Ni, Xueyan Li, Fangqi Li, Xiaofeng Gao, Guihai Chen
• Abstract要約: ソーシャルネットワークで影響力のあるユーザーを見つけることは、多くの有用なアプリケーションにおいて根本的な問題である。 本稿では,IM の問題を予算制約付き d-hop 支配集合問題 (kdDSP) に還元する。 我々は、効率的な欲求戦略を教師なしで学習することでkdDSPを解決するために、統合機械学習(ML)フレームワークであるFastCoverを提案する。 FastCoverは、GNNの1つの前方伝播で計算されたノードのスコアから設定されたシード全体を決定する。
• 参考スコア（独自算出の注目度）: 39.86798194955807
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Finding influential users in social networks is a fundamental problem with many possible useful applications. Viewing the social network as a graph, the influence of a set of users can be measured by the number of neighbors located within a given number of hops in the network, where each hop marks a step of influence diffusion. In this paper, we reduce the problem of IM to a budget-constrained d-hop dominating set problem (kdDSP). We propose a unified machine learning (ML) framework, FastCover, to solve kdDSP by learning an efficient greedy strategy in an unsupervised way. As one critical component of the framework, we devise a novel graph neural network (GNN) architecture, graph reversed attention network (GRAT), that captures the diffusion process among neighbors. Unlike most heuristic algorithms and concurrent ML frameworks for combinatorial optimization problems, FastCover determines the entire seed set from the nodes' scores computed with only one forward propagation of the GNN and has a time complexity quasi-linear in the graph size. Experiments on synthetic graphs and real-world social networks demonstrate that FastCover finds solutions with better or comparable quality rendered by the concurrent algorithms while achieving a speedup of over 1000x.
• Abstract（参考訳）: ソーシャルネットワークで影響力のあるユーザーを見つけることは、多くの有用なアプリケーションにおいて根本的な問題である。 ソーシャルネットワークをグラフとして見ていると、各ホップが影響拡散のステップを示すネットワーク内の所定のホップ数内に位置する隣人の数によって、一組のユーザの影響を測定することができる。 本稿では,IM の問題を予算制約付き d-hop 支配集合問題 (kdDSP) に還元する。 我々は、効率的な欲求戦略を教師なしで学習することでkdDSPを解決するための統合機械学習(ML)フレームワークであるFastCoverを提案する。 このフレームワークの重要なコンポーネントの1つとして、新しいグラフニューラルネットワーク(gnn)アーキテクチャであるgraph reversed attention network(grat)を開発し、隣人間の拡散プロセスをキャプチャする。 組合せ最適化問題のための多くのヒューリスティックアルゴリズムや並行mlフレームワークとは異なり、fastcoverはgnnの1つの前方伝播で計算されたノードのスコアからシードセット全体を決定し、グラフサイズで時間複雑性の準線形を持つ。 合成グラフと現実世界のソーシャルネットワークの実験により、fastcoverは並列アルゴリズムによってレンダリングされた優れた、あるいは同等の品質のソリューションを見つけ、1000倍以上のスピードアップを達成している。

関連論文リスト

• Decentralized Optimization in Time-Varying Networks with Arbitrary Delays [22.40154714677385]
  通信遅延によるネットワークの分散最適化問題を考察する。 そのようなネットワークの例としては、協調機械学習、センサーネットワーク、マルチエージェントシステムなどがある。 通信遅延を模倣するため、ネットワークに仮想非計算ノードを追加し、有向グラフを生成する。
  論文  参考訳（メタデータ） (2024-05-29T20:51:38Z)
• Learning Cooperative Beamforming with Edge-Update Empowered Graph Neural Networks [29.23937571816269]
  グラフエッジ上での協調ビームフォーミングを学習するためのエッジグラフニューラルネットワーク(Edge-GNN)を提案する。 提案したEdge-GNNは、最先端の手法よりも計算時間をはるかに短くして、より高い和率を達成する。
  論文  参考訳（メタデータ） (2022-11-23T02:05:06Z)
• 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)
• Learning to Solve Combinatorial Graph Partitioning Problems via Efficient Exploration [72.15369769265398]
  実験により、ECORDは最大カット問題に対するRLアルゴリズムのための新しいSOTAを実現する。 最も近い競合と比較して、ECORDは最適性ギャップを最大73%削減する。
  論文  参考訳（メタデータ） (2022-05-27T17:13:10Z)
• VQ-GNN: A Universal Framework to Scale up Graph Neural Networks using Vector Quantization [70.8567058758375]
  VQ-GNNは、Vector Quantization(VQ)を使用して、パフォーマンスを損なうことなく、畳み込みベースのGNNをスケールアップするための普遍的なフレームワークである。 我々のフレームワークは,グラフ畳み込み行列の低ランク版と組み合わせた量子化表現を用いて,GNNの「隣の爆発」問題を回避する。
  論文  参考訳（メタデータ） (2021-10-27T11:48:50Z)
• Scaling Graph Neural Networks with Approximate PageRank [64.92311737049054]
  GNNにおける情報拡散の効率的な近似を利用したPPRGoモデルを提案する。 高速であることに加えて、PPRGoは本質的にスケーラブルであり、業界設定で見られるような大規模なデータセットに対して、自明に並列化することができる。 このグラフのすべてのノードに対するPPRGoのトレーニングとラベルの予測には1台のマシンで2分未満で、同じグラフ上の他のベースラインをはるかに上回ります。
  論文  参考訳（メタデータ） (2020-07-03T09:30:07Z)
• Communication-Efficient Distributed Stochastic AUC Maximization with Deep Neural Networks [50.42141893913188]
  本稿では,ニューラルネットワークを用いた大規模AUCのための分散変数について検討する。 我々のモデルは通信ラウンドをはるかに少なくし、理論上はまだ多くの通信ラウンドを必要としています。 いくつかのデータセットに対する実験は、我々の理論の有効性を示し、我々の理論を裏付けるものである。
  論文  参考訳（メタデータ） (2020-05-05T18:08:23Z)
• Fitting the Search Space of Weight-sharing NAS with Graph Convolutional Networks [100.14670789581811]
  サンプルサブネットワークの性能に適合するグラフ畳み込みネットワークを訓練する。 この戦略により、選択された候補集合において、より高いランク相関係数が得られる。
  論文  参考訳（メタデータ） (2020-04-17T19:12:39Z)

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

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