論文の概要: Unveiling Environmental Sensitivity of Individual Gains in Influence Maximization
- arxiv url: http://arxiv.org/abs/2301.12226v3
- Date: Tue, 10 Dec 2024 11:34:07 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-12-11 14:33:22.532632
- Title: Unveiling Environmental Sensitivity of Individual Gains in Influence Maximization
- Title(参考訳): 影響最大化における個人利得の環境感受性の解放
- Authors: Xinyan Su, Zhiheng Zhang, Jiyan Qiu,
- Abstract要約: 本稿では、因果影響の最大化フレームワークを導入し、G-CauIMとA-CauIMの2つのアルゴリズムを開発した。
本稿では,アルゴリズムの有効性とロバスト性を実証する。
- 参考スコア(独自算出の注目度): 0.6144680854063939
- License:
- Abstract: Influence Maximization (IM) is to identify the seed set to maximize information dissemination in a network. Elegant IM algorithms could naturally extend to cases where each node is equipped with a specific weight, reflecting individual gains to measure the node's importance. Prevailing literature typically assumes such individual gains remain constant throughout the cascade process and are solvable through explicit formulas based on the node's characteristics and network topology. However, this assumption is not always feasible for two reasons: 1)Unobservability: The individual gains of each node are primarily evaluated by the difference between the outputs in the activated and non-activated states. In practice, we can only observe one of these states, with the other remaining unobservable post-propagation. 2)Environmental sensitivity: In addition to the node's inherent properties, individual gains are also sensitive to the activation status of surrounding nodes, which is dynamic during iteration even when the network topology remains static. To address these challenges, we extend the consideration of IM to a broader scenario with dynamic node individual gains, leveraging causality techniques. In our paper, we introduce a Causal Influence Maximization (CauIM) framework and develop two algorithms, G-CauIM and A-CauIM, where the latter incorporates a novel acceleration technique. Theoretically, we establish the generalized lower bound of influence spread and provide robustness analysis. Empirically, in synthetic and real-world experiments, we demonstrate the effectiveness and robustness of our algorithms.
- Abstract(参考訳): 影響の最大化(IM)とは、ネットワーク内の情報拡散を最大化するシードセットを特定することである。
エレガントIMアルゴリズムは、各ノードが特定の重みを持つ場合に自然に拡張することができ、ノードの重要性を測定するために個々のゲインを反映する。
一般的な文献では、そのような個々のゲインはカスケード過程を通して一定であり、ノードの特性とネットワークトポロジーに基づいた明示的な公式によって解決可能であると仮定している。
可観測性: 各ノードの個々のゲインは、活性化状態と非活性化状態の出力の違いによって主に評価される。
実際には、これらの状態のうちの1つしか観察できないが、残りは観測不可能なポストプロパゲーションである。
2)環境感度: ノード固有の特性に加えて, ネットワークトポロジが静的である場合でも, 周辺ノードの活性化状態にも敏感である。
これらの課題に対処するため、我々は、因果関係の手法を活用して、動的ノード個別ゲインによるより広いシナリオにIMの考察を拡張した。
本稿では、因果影響最大化(CauIM)フレームワークを導入し、G-CauIMとA-CauIMの2つのアルゴリズムを開発した。
理論的には、一般化された影響拡散の低境界を確立し、ロバスト性解析を提供する。
経験的に、人工的および実世界の実験では、アルゴリズムの有効性とロバスト性を実証する。
関連論文リスト
- Influence Maximization via Graph Neural Bandits [54.45552721334886]
IM問題を多ラウンド拡散キャンペーンに設定し,影響を受けやすいユーザ数を最大化することを目的とした。
IM-GNB(Influence Maximization with Graph Neural Bandits)を提案する。
論文 参考訳(メタデータ) (2024-06-18T17:54:33Z) - IENE: Identifying and Extrapolating the Node Environment for Out-of-Distribution Generalization on Graphs [10.087216264788097]
ノードレベルの環境識別と外挿技術に基づくグラフのOOD一般化手法であるIENEを提案する。
モデルが2つの粒度から不変性を同時に抽出する能力を強化し、一般化が向上する。
論文 参考訳(メタデータ) (2024-06-02T14:43:56Z) - Understanding Virtual Nodes: Oversmoothing, Oversquashing, and Node Heterogeneity [4.59357989139429]
仮想ノード(VN)によるMPNNの拡張は、さまざまなベンチマークのパフォーマンス向上に寄与している。
VNは、通常、表現力を維持するための非平滑化アプローチの複製を避ける。
グラフ構造に基づいてノードに対して異なる感度を持つ計算複雑性を持つVNの変種を提案する。
論文 参考訳(メタデータ) (2024-05-22T10:51:12Z) - ACE : Off-Policy Actor-Critic with Causality-Aware Entropy Regularization [52.5587113539404]
因果関係を考慮したエントロピー(entropy)という用語を導入し,効率的な探索を行うための潜在的影響の高いアクションを効果的に識別し,優先順位付けする。
提案アルゴリズムであるACE:Off-policy Actor-critic with Causality-aware Entropy regularizationは,29種類の連続制御タスクに対して,大幅な性能上の優位性を示す。
論文 参考訳(メタデータ) (2024-02-22T13:22:06Z) - STERLING: Synergistic Representation Learning on Bipartite Graphs [78.86064828220613]
二部グラフ表現学習の基本的な課題は、ノードの埋め込みを抽出する方法である。
最近の二部グラフSSL法は、正ノード対と負ノード対を識別することによって埋め込みを学習する対照的な学習に基づいている。
負のノードペアを持たないノード埋め込みを学習するための新しい相乗的表現学習モデル(STERling)を提案する。
論文 参考訳(メタデータ) (2023-01-25T03:21:42Z) - Understanding Influence Maximization via Higher-Order Decomposition [6.542119695695405]
影響の最大化(IM)はここ数十年で大きな注目を集めている。
この研究は、ソボル指数を用いた個々の種子とその高次相互作用への影響を識別する。
過剰選択ノードによる現行のIMアルゴリズムの性能向上のために,SIMと呼ばれるIMアルゴリズムを提案する。
論文 参考訳(メタデータ) (2022-07-16T04:44:16Z) - GraMeR: Graph Meta Reinforcement Learning for Multi-Objective Influence
Maximization [1.7311053765541482]
インフルエンス(IM)とは、ネットワーク内のシードノードと呼ばれるノードのサブセットを特定する問題である(グラフ)。
IMには、バイラルマーケティング、疫病対策、センサー配置、その他のネットワーク関連タスクなど、数多くの応用がある。
我々は、本質的および影響的アクティベーションの両方を扱うマルコフ決定プロセスとして、一般的なIM問題を開発する。
論文 参考訳(メタデータ) (2022-05-30T03:48:51Z) - Handling Distribution Shifts on Graphs: An Invariance Perspective [78.31180235269035]
我々は、グラフ上のOOD問題を定式化し、新しい不変学習手法である探索・拡張リスク最小化(EERM)を開発する。
EERMは、複数の仮想環境からのリスクの分散を最大化するために、敵対的に訓練された複数のコンテキストエクスプローラーを利用する。
理論的に有効なOOD解の保証を示すことによって,本手法の有効性を実証する。
論文 参考訳(メタデータ) (2022-02-05T02:31:01Z) - Unveiling Anomalous Edges and Nominal Connectivity of Attributed
Networks [53.56901624204265]
本研究では、相補的な強さを持つ2つの異なる定式化を用いて、属性グラフの異常なエッジを明らかにする。
まず、グラフデータマトリックスを低ランクとスパースコンポーネントに分解することで、パフォーマンスを著しく向上させる。
第2は、乱れのないグラフを頑健に復元することにより、第1のスコープを広げ、異常識別性能を高める。
論文 参考訳(メタデータ) (2021-04-17T20:00:40Z) - Graph Backdoor [53.70971502299977]
GTAはグラフニューラルネットワーク(GNN)に対する最初のバックドア攻撃である。
GTAは、トポロジカル構造と記述的特徴の両方を含む特定の部分グラフとしてトリガーを定義する。
トランスダクティブ(ノード分類など)とインダクティブ(グラフ分類など)の両方のタスクに対してインスタンス化することができる。
論文 参考訳(メタデータ) (2020-06-21T19:45:30Z) - The Effects of Randomness on the Stability of Node Embeddings [5.126380982787905]
グラフに5つのノード埋め込みアルゴリズムを適用し,その安定性をランダムに評価する。
ノードの中心性に依存しない埋め込み空間の幾何学において重要な不安定性を見出す。
これは、ノードの埋め込みを扱う場合、不安定性の影響を考慮する必要があることを示唆している。
論文 参考訳(メタデータ) (2020-05-20T13:36:09Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。