Understanding Influence Maximization via Higher-Order Decomposition

• URL: http://arxiv.org/abs/2207.07833v4
• Date: Thu, 13 Apr 2023 13:53:45 GMT
• Title: Understanding Influence Maximization via Higher-Order Decomposition
• Authors: Zonghan Zhang and Zhiqian Chen
• Abstract summary: 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.
• Score: 6.542119695695405
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Given its vast application on online social networks, Influence Maximization (IM) has garnered considerable attention over the last couple of decades. Due to the intricacy of IM, most current research concentrates on estimating the first-order contribution of the nodes to select a seed set, disregarding the higher-order interplay between different seeds. Consequently, the actual influence spread frequently deviates from expectations, and it remains unclear how the seed set quantitatively contributes to this deviation. To address this deficiency, this work dissects the influence exerted on individual seeds and their higher-order interactions utilizing the Sobol index, a variance-based sensitivity analysis. To adapt to IM contexts, seed selection is phrased as binary variables and split into distributions of varying orders. Based on our analysis with various Sobol indices, an IM algorithm dubbed SIM is proposed to improve the performance of current IM algorithms by over-selecting nodes followed by strategic pruning. A case study is carried out to demonstrate that the explanation of the impact effect can dependably identify the key higher-order interactions among seeds. SIM is empirically proved to be superior in effectiveness and competitive in efficiency by experiments on synthetic and real-world graphs.

Related papers

• 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)
• 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)
• Influence Maximization with Unknown Individual Effect on General Network [3.4049427793086324]
  The identification of a seed set to maximize information spread in a network is crucial, a concept known as Influence Maximization (IM) IM algorithms could naturally extend to cases where each node is equipped with specific weight, referred to as individual effect, to measure the node's importance. In our paper, we address this through the development of a Causal Influence Maximization (CauIM) algorithm.
  arXiv  Detail & Related papers  (2023-01-28T15:34:03Z)
• Provably Efficient Reinforcement Learning for Online Adaptive Influence Maximization [53.11458949694947]
  We consider an adaptive version of content-dependent online influence problem where seed nodes are sequentially activated based on realtime feedback. Our algorithm maintains a network model estimate and selects seed adaptively, exploring the social network while improving the optimal policy optimistically.
  arXiv  Detail & Related papers  (2022-06-29T18:17:28Z)
• 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)
• Reenvisioning Collaborative Filtering vs Matrix Factorization [65.74881520196762]
  Collaborative filtering models based on matrix factorization and learned similarities using Artificial Neural Networks (ANNs) have gained significant attention in recent years. Announcement of ANNs within the recommendation ecosystem has been recently questioned, raising several comparisons in terms of efficiency and effectiveness. We show the potential these techniques may have on beyond-accuracy evaluation while analyzing effect on complementary evaluation dimensions.
  arXiv  Detail & Related papers  (2021-07-28T16:29:38Z)
• Counterfactual Maximum Likelihood Estimation for Training Deep Networks [83.44219640437657]
  Deep learning models are prone to learning spurious correlations that should not be learned as predictive clues. We propose a causality-based training framework to reduce the spurious correlations caused by observable confounders. We conduct experiments on two real-world tasks: Natural Language Inference (NLI) and Image Captioning.
  arXiv  Detail & Related papers  (2021-06-07T17:47:16Z)
• Demarcating Endogenous and Exogenous Opinion Dynamics: An Experimental Design Approach [27.975266406080152]
  In this paper, we design a suite of unsupervised classification methods based on experimental design approaches. We aim to select the subsets of events which minimize different measures of mean estimation error. Our experiments range from validating prediction performance on unsanitized and sanitized events to checking the effect of selecting optimal subsets of various sizes.
  arXiv  Detail & Related papers  (2021-02-11T11:38:15Z)
• Mutual Information Maximization for Effective Lip Reading [99.11600901751673]
  We propose to introduce the mutual information constraints on both the local feature's level and the global sequence's level. By combining these two advantages together, the proposed method is expected to be both discriminative and robust for effective lip reading.
  arXiv  Detail & Related papers  (2020-03-13T18:47:42Z)

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.