論文の概要: Learning to maximize global influence from local observations
- arxiv url: http://arxiv.org/abs/2109.11909v1
- Date: Fri, 24 Sep 2021 11:59:44 GMT
- ステータス: 処理完了
- システム内更新日: 2021-09-27 20:50:37.782053
- Title: Learning to maximize global influence from local observations
- Title（参考訳）: 局所観測から世界への影響を最大化する学習
- Authors: G\'abor Lugosi, Gergely Neu, Julia Olkhovskaya
- Abstract要約: 本研究では,一連のラウンドが$t=1,ldots,T$であり,意思決定者が影響力を最大化する目的で多数のエージェントの中から1つを選択するという,オンライン・インフルエンス問題の研究を行う。
意思決定者の目標は、ネットワーク内の影響ノードの総数でエージェントのシーケンスを選択することである。
- 参考スコア（独自算出の注目度）: 12.611900695498218
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study a family online influence maximization problems where in a sequence
of rounds $t=1,\ldots,T$, a decision maker selects one from a large number of
agents with the goal of maximizing influence. Upon choosing an agent, the
decision maker shares a piece of information with the agent, which information
then spreads in an unobserved network over which the agents communicate. The
goal of the decision maker is to select the sequence of agents in a way that
the total number of influenced nodes in the network. In this work, we consider
a scenario where the networks are generated independently for each $t$
according to some fixed but unknown distribution, so that the set of influenced
nodes corresponds to the connected component of the random graph containing the
vertex corresponding to the selected agent. Furthermore, we assume that the
decision maker only has access to limited feedback: instead of making the
unrealistic assumption that the entire network is observable, we suppose that
the available feedback is generated based on a small neighborhood of the
selected vertex. Our results show that such partial local observations can be
sufficient for maximizing global influence. We model the underlying random
graph as a sparse inhomogeneous Erd\H{o}s--R\'enyi graph, and study three
specific families of random graph models in detail: stochastic block models,
Chung--Lu models and Kronecker random graphs. We show that in these cases one
may learn to maximize influence by merely observing the degree of the selected
vertex in the generated random graph. We propose sequential learning algorithms
that aim at maximizing influence, and provide their theoretical analysis in
both the subcritical and supercritical regimes of all considered models.
- Abstract（参考訳）: 本研究では,数列のラウンドが$t=1,\ldots,T$である家族のオンライン影響最大化問題について検討する。
エージェントを選択すると、意思決定者はエージェントと情報の一部を共有し、エージェントが通信する未観測ネットワークにその情報が拡散する。
意思決定者の目標は、ネットワーク内の影響のあるノードの総数という方法でエージェントのシーケンスを選択することである。
本研究では,ある固定分布と未知分布にしたがって,ネットワークを$t$ごとに独立に生成するシナリオを考察し,影響ノードの集合が選択されたエージェントに対応する頂点を含むランダムグラフの連結成分に対応するようにした。
さらに,ネットワーク全体が観測可能であるという非現実的な仮定ではなく,選択した頂点の小さな近傍に基づいて,利用可能なフィードバックが生成されると仮定する。
これらの部分的な局所的な観測は、地球への影響を最大化するのに十分であることを示す。
基礎となるランダムグラフを疎不均一な erd\h{o}s--r\'enyi グラフとしてモデル化し、確率ブロックモデル、chung-luモデル、クロネッカーランダムグラフの3種類のランダムグラフモデルを詳細に研究した。
このような場合、選択された頂点の次数だけをランダムグラフで観測することで、影響を最大化することができる。
我々は,影響を最大化することを目的とした逐次学習アルゴリズムを提案し,それらの理論解析を,すべての考慮モデルのサブクリティカル・スーパークリティカル・レジームの両方において提供する。
関連論文リスト
- Influence Maximization via Graph Neural Bandits [54.45552721334886]
IM問題を多ラウンド拡散キャンペーンに設定し,影響を受けやすいユーザ数を最大化することを目的とした。
IM-GNB(Influence Maximization with Graph Neural Bandits)を提案する。
論文 参考訳（メタデータ） (2024-06-18T17:54:33Z) - Towards Generalizability of Multi-Agent Reinforcement Learning in Graphs with Recurrent Message Passing [0.9353820277714449]
分散化されたアプローチでは、エージェントは与えられたグラフ内で動作し、部分的または時代遅れな観察に基づいて決定を行う。
この研究は一般化性に焦点をあて、グラフ全体の連続的な情報フローで観測された近傍のサイズのトレードオフを解消する。
我々の手法は、実行時に分散的に使用することができ、選択した強化学習アルゴリズムと組み合わせることができる。
論文 参考訳（メタデータ） (2024-02-07T16:53:09Z) - Distributed Learning over Networks with Graph-Attention-Based
Personalization [49.90052709285814]
分散ディープラーニングのためのグラフベースパーソナライズアルゴリズム(GATTA)を提案する。
特に、各エージェントのパーソナライズされたモデルは、グローバルな部分とノード固有の部分で構成される。
グラフ内の各エージェントを1つのノードとして扱うことにより、ノード固有のパラメータを特徴として扱うことにより、グラフアテンション機構の利点を継承することができる。
論文 参考訳（メタデータ） (2023-05-22T13:48:30Z) - Graph Learning Across Data Silos [12.343382413705394]
本稿では,スムーズなグラフ信号からグラフトポロジを推定する問題を考える。
データは分散クライアントにあり、プライバシー上の懸念などの要因により、ローカルクライアントを去ることは禁じられている。
本稿では,各ローカルクライアントに対してパーソナライズされたグラフと,全クライアントに対して単一のコンセンサスグラフを共同で学習する,自動重み付き多重グラフ学習モデルを提案する。
論文 参考訳（メタデータ） (2023-01-17T02:14:57Z) - Optimal Propagation for Graph Neural Networks [51.08426265813481]
最適グラフ構造を学習するための二段階最適化手法を提案する。
また、時間的複雑さをさらに軽減するために、低ランク近似モデルについても検討する。
論文 参考訳（メタデータ） (2022-05-06T03:37:00Z) - Graph-wise Common Latent Factor Extraction for Unsupervised Graph
Representation Learning [40.70562886682939]
我々は、教師なしグラフ表現学習のための新しい原則を提案する:グラフワイド共通潜在因子抽出(GCFX)
GCFXは入力グラフから一般的な潜伏因子を明示的に抽出し、現在の最先端のタスクで改善された結果を達成する。
広範囲な実験と分析により,GCFXは個々のノードや周辺地域の局所的な変動による障害を軽減するため,グラフレベルのタスクに有用であることを示す。
論文 参考訳（メタデータ） (2021-12-16T12:22:49Z) - Bayesian Graph Contrastive Learning [55.36652660268726]
本稿では,ランダムな拡張がエンコーダにつながることを示すグラフコントラスト学習手法の新たな視点を提案する。
提案手法は,各ノードを決定論的ベクトルに埋め込む既存の手法とは対照的に,各ノードを潜在空間の分布で表現する。
いくつかのベンチマークデータセットにおける既存の最先端手法と比較して,性能が大幅に向上したことを示す。
論文 参考訳（メタデータ） (2021-12-15T01:45:32Z) - Explicit Pairwise Factorized Graph Neural Network for Semi-Supervised
Node Classification [59.06717774425588]
本稿では,グラフ全体を部分的に観測されたマルコフ確率場としてモデル化するEPFGNN(Explicit Pairwise Factorized Graph Neural Network)を提案する。
出力-出力関係をモデル化するための明示的なペアワイズ要素を含み、入力-出力関係をモデル化するためにGNNバックボーンを使用する。
本研究では,グラフ上での半教師付きノード分類の性能を効果的に向上できることを示す。
論文 参考訳（メタデータ） (2021-07-27T19:47:53Z) - Influence Maximization Under Generic Threshold-based Non-submodular
Model [1.5780411262109524]
社会的影響の概念は、ソーシャルネットワークから最も影響力のあるノード(シードノード)の数を選択し、彼らが共同で最大の影響の拡散をトリガーできるようにすることです。
本稿では,ネットワークグラフを用いた一般化されたしきい値ベースモデルであるインフルエンサーバリケードモデルにおける種選択戦略を提案する。
私たちの知る限りでは、これは非サブモジュラーな影響を直接取り扱う最初のグラフベースのアプローチです。
論文 参考訳（メタデータ） (2020-12-18T16:14:49Z) - Block-Approximated Exponential Random Graphs [77.4792558024487]
指数乱グラフ(ERG)の分野における重要な課題は、大きなグラフ上の非自明なERGの適合である。
本稿では,非自明なERGに対する近似フレームワークを提案する。
我々の手法は、数百万のノードからなるスパースグラフにスケーラブルである。
論文 参考訳（メタデータ） (2020-02-14T11:42:16Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。