Unveiling Environmental Sensitivity of Individual Gains in Influence Maximization

• URL: http://arxiv.org/abs/2301.12226v3
• Date: Tue, 10 Dec 2024 11:34:07 GMT
• Title: Unveiling Environmental Sensitivity of Individual Gains in Influence Maximization
• Authors: Xinyan Su, Zhiheng Zhang, Jiyan Qiu,
• Abstract summary: We introduce a Causal Influence Maximization framework and develop two algorithms, G-CauIM and A-CauIM, where the latter incorporates a novel acceleration technique.<n>In our paper, we demonstrate the effectiveness and robustness of our algorithms.
• Score: 0.6144680854063939
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• Decoupled Graph Energy-based Model for Node Out-of-Distribution Detection on Heterophilic Graphs [61.226857589092]
  OOD detection on nodes in graph learning remains underexplored. GNNSafe adapted energy-based detection to the graph domain with state-of-the-art performance. We introduce DeGEM, which decomposes the learning process into two parts: a graph encoder that leverages topology information for node representations and an energy head that operates in latent space.
  arXiv  Detail & Related papers  (2025-02-25T07:20:00Z)
• Network Causal Effect Estimation In Graphical Models Of Contagion And Latent Confounding [2.654975444537834]
  Key question in many network studies is whether the observed correlations between units are primarily due to contagion or latent confounding. We propose network causal effect estimation strategies that provide unbiased and consistent estimates. We evaluate the effectiveness of our methods with synthetic data and the validity of our assumptions using real-world networks.
  arXiv  Detail & Related papers  (2024-11-02T22:12:44Z)
• Estimating Peer Direct and Indirect Effects in Observational Network Data [16.006409149421515]
  We propose a general setting which considers both peer direct effects and peer indirect effects, and the effect of an individual's own treatment. We use attention mechanisms to distinguish the influences of different neighbors and explore high-order neighbor effects through graph neural networks. Our theoretical findings have the potential to improve intervention strategies in networked systems, with applications in areas such as social networks and epidemiology.
  arXiv  Detail & Related papers  (2024-08-21T10:02:05Z)
• Influence Maximization via Graph Neural Bandits [54.45552721334886]
  We set the IM problem in a multi-round diffusion campaign, aiming to maximize the number of distinct users that are influenced. We propose the framework IM-GNB (Influence Maximization with Graph Neural Bandits), where we provide an estimate of the users' probabilities of being influenced.
  arXiv  Detail & Related papers  (2024-06-18T17:54:33Z)
• IENE: Identifying and Extrapolating the Node Environment for Out-of-Distribution Generalization on Graphs [10.087216264788097]
  We propose IENE, an OOD generalization method on graphs based on node-level environmental identification and extrapolation techniques. It strengthens the model's ability to extract invariance from two granularities simultaneously, leading to improved generalization.
  arXiv  Detail & Related papers  (2024-06-02T14:43:56Z)
• Understanding Virtual Nodes: Oversquashing and Node Heterogeneity [4.59357989139429]
  Augmenting MPNNs with a virtual node (VN) has been found to improve performance on a range of benchmarks. We provide a comprehensive theoretical analysis of the role of VNs and benefits thereof. We propose a variant of VN with the same computational complexity, which can have different sensitivity to nodes based on the graph structure.
  arXiv  Detail & Related papers  (2024-05-22T10:51:12Z)
• ACE : Off-Policy Actor-Critic with Causality-Aware Entropy Regularization [52.5587113539404]
  We introduce a causality-aware entropy term that effectively identifies and prioritizes actions with high potential impacts for efficient exploration. Our proposed algorithm, ACE: Off-policy Actor-critic with Causality-aware Entropy regularization, demonstrates a substantial performance advantage across 29 diverse continuous control tasks.
  arXiv  Detail & Related papers  (2024-02-22T13:22:06Z)
• dugMatting: Decomposed-Uncertainty-Guided Matting [83.71273621169404]
  We propose a decomposed-uncertainty-guided matting algorithm, which explores the explicitly decomposed uncertainties to efficiently and effectively improve the results. The proposed matting framework relieves the requirement for users to determine the interaction areas by using simple and efficient labeling.
  arXiv  Detail & Related papers  (2023-06-02T11:19:50Z)
• Understanding Influence Maximization via Higher-Order Decomposition [6.542119695695405]
  Influence Maximization (IM) has garnered considerable attention over the last couple of decades. This work dissects the influence exerted on individual seeds and their higher-order interactions utilizing the Sobol index. An IM algorithm dubbed SIM is proposed to improve the performance of current IM algorithms by over-selecting nodes.
  arXiv  Detail & Related papers  (2022-07-16T04:44:16Z)
• GraMeR: Graph Meta Reinforcement Learning for Multi-Objective Influence Maximization [1.7311053765541482]
  Influence (IM) is a problem of identifying a subset of nodes called the seed nodes in a network (graph) IM has numerous applications such as viral marketing, epidemic control, sensor placement and other network-related tasks. We develop a generic IM problem as a Markov decision process that handles both intrinsic and influence activations.
  arXiv  Detail & Related papers  (2022-05-30T03:48:51Z)
• Preference Enhanced Social Influence Modeling for Network-Aware Cascade Prediction [59.221668173521884]
  We propose a novel framework to promote cascade size prediction by enhancing the user preference modeling. Our end-to-end method makes the user activating process of information diffusion more adaptive and accurate.
  arXiv  Detail & Related papers  (2022-04-18T09:25:06Z)
• Handling Distribution Shifts on Graphs: An Invariance Perspective [78.31180235269035]
  We formulate the OOD problem on graphs and develop a new invariant learning approach, Explore-to-Extrapolate Risk Minimization (EERM) EERM resorts to multiple context explorers that are adversarially trained to maximize the variance of risks from multiple virtual environments. We prove the validity of our method by theoretically showing its guarantee of a valid OOD solution.
  arXiv  Detail & Related papers  (2022-02-05T02:31:01Z)
• Localisation determines the optimal noise rate for quantum transport [68.8204255655161]
  Localisation and the optimal dephasing rate in 1D chains are studied. A simple power law captures the interplay between size-dependent and size-independent responses. Relationship continues to apply at intermediate and high temperature but breaks down in the low temperature limit.
  arXiv  Detail & Related papers  (2021-06-23T17:52:16Z)
• Unveiling Anomalous Edges and Nominal Connectivity of Attributed Networks [53.56901624204265]
  The present work deals with uncovering anomalous edges in attributed graphs using two distinct formulations with complementary strengths. The first relies on decomposing the graph data matrix into low rank plus sparse components to improve markedly performance. The second broadens the scope of the first by performing robust recovery of the unperturbed graph, which enhances the anomaly identification performance.
  arXiv  Detail & Related papers  (2021-04-17T20:00:40Z)
• On Dynamic Noise Influence in Differentially Private Learning [102.6791870228147]
  Private Gradient Descent (PGD) is a commonly used private learning framework, which noises based on the Differential protocol. Recent studies show that emphdynamic privacy schedules can improve at the final iteration, yet yet theoreticals of the effectiveness of such schedules remain limited. This paper provides comprehensive analysis of noise influence in dynamic privacy schedules to answer these critical questions.
  arXiv  Detail & Related papers  (2021-01-19T02:04:00Z)
• Graph Backdoor [53.70971502299977]
  We present GTA, the first backdoor attack on graph neural networks (GNNs) GTA departs in significant ways: it defines triggers as specific subgraphs, including both topological structures and descriptive features. It can be instantiated for both transductive (e.g., node classification) and inductive (e.g., graph classification) tasks.
  arXiv  Detail & Related papers  (2020-06-21T19:45:30Z)
• The Effects of Randomness on the Stability of Node Embeddings [5.126380982787905]
  We apply five node embeddings algorithms to graphs and evaluate their stability under randomness. We find significant instabilities in the geometry of embedding spaces independent of the centrality of a node. This suggests that instability effects need to be taken into account when working with node embeddings.
  arXiv  Detail & Related papers  (2020-05-20T13:36:09Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.