Better Bounds on the Adaptivity Gap of Influence Maximization under Full-adoption Feedback

• URL: http://arxiv.org/abs/2006.15374v1
• Date: Sat, 27 Jun 2020 14:43:34 GMT
• Title: Better Bounds on the Adaptivity Gap of Influence Maximization under Full-adoption Feedback
• Authors: Gianlorenzo D'Angelo, Debashmita Poddar, Cosimo Vinci
• Abstract summary: We look for a set of $k$ nodes that maximize the expected number of nodes that are reached by an influence cascade. We show that the adaptivity gap is upper-bounded by $lceil nrceil $, where $n$ is the number of nodes in the graph. We also show that in 0-bounded graphs, i.e. undirected graphs, the adaptivity gap is at most $frac3e3e3-1approx 3.16$.
• Score: 15.533908352376853
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In the influence maximization (IM) problem, we are given a social network and a budget $k$, and we look for a set of $k$ nodes in the network, called seeds, that maximize the expected number of nodes that are reached by an influence cascade generated by the seeds, according to some stochastic model for influence diffusion. In this paper, we study the adaptive IM, where the nodes are selected sequentially one by one, and the decision on the $i$th seed can be based on the observed cascade produced by the first $i-1$ seeds. We focus on the full-adoption feedback in which we can observe the entire cascade of each previously selected seed and on the independent cascade model where each edge is associated with an independent probability of diffusing influence. Our main result is the first sub-linear upper bound that holds for any graph. Specifically, we show that the adaptivity gap is upper-bounded by $\lceil n^{1/3}\rceil $, where $n$ is the number of nodes in the graph. Moreover, we improve over the known upper bound for in-arborescences from $\frac{2e}{e-1}\approx 3.16$ to $\frac{2e^2}{e^2-1}\approx 2.31$. Finally, we study $\alpha$-bounded graphs, a class of undirected graphs in which the sum of node degrees higher than two is at most $\alpha$, and show that the adaptivity gap is upper-bounded by $\sqrt{\alpha}+O(1)$. Moreover, we show that in 0-bounded graphs, i.e. undirected graphs in which each connected component is a path or a cycle, the adaptivity gap is at most $\frac{3e^3}{e^3-1}\approx 3.16$. To prove our bounds, we introduce new techniques to relate adaptive policies with non-adaptive ones that might be of their own interest.

Related papers

• Adaptive Frontier Exploration on Graphs with Applications to Network-Based Disease Testing [25.36924544001149]
  We study a sequential decision-making problem on a $n$-node graph $G$ where each node has an unknown label.<n>We design a Gittins index-based policy that applies to general graphs and is provably optimal when $G$ is a forest.<n>Experiments on synthetic and real-world graphs show that our method consistently outperforms natural baselines.
  arXiv  Detail & Related papers  (2025-05-27T18:48:42Z)
• Identifying General Mechanism Shifts in Linear Causal Representations [58.6238439611389]
  We consider the linear causal representation learning setting where we observe a linear mixing of $d$ unknown latent factors. Recent work has shown that it is possible to recover the latent factors as well as the underlying structural causal model over them. We provide a surprising identifiability result that it is indeed possible, under some very mild standard assumptions, to identify the set of shifted nodes.
  arXiv  Detail & Related papers  (2024-10-31T15:56:50Z)
• Self-Directed Learning of Convex Labelings on Graphs [11.286983359775512]
  We study the problem of classifying the nodes of a given graph in the self-directed learning setup. This learning setting is a variant of online learning, where rather than an adversary determining the sequence in which nodes are, the learner autonomously selects them. While self-directed Euclidean halfspaces, and general multiclass hypothesis classes were considered, no results previously existed specifically for self-directed node classification on graphs.
  arXiv  Detail & Related papers  (2024-09-02T19:13:26Z)
• The Heterophilic Snowflake Hypothesis: Training and Empowering GNNs for Heterophilic Graphs [59.03660013787925]
  We introduce the Heterophily Snowflake Hypothesis and provide an effective solution to guide and facilitate research on heterophilic graphs. Our observations show that our framework acts as a versatile operator for diverse tasks. It can be integrated into various GNN frameworks, boosting performance in-depth and offering an explainable approach to choosing the optimal network depth.
  arXiv  Detail & Related papers  (2024-06-18T12:16:00Z)
• Graph Sparsification via Mixture of Graphs [67.40204130771967]
  We introduce Mixture-of-Graphs (MoG) to dynamically select tailored pruning solutions for each node. MoG incorporates multiple sparsifier experts, each characterized by unique sparsity levels and pruning criteria, and selects the appropriate experts for each node. Experiments on four large-scale OGB datasets and two superpixel datasets, equipped with five GNNs, demonstrate that MoG identifies subgraphs at higher sparsity levels.
  arXiv  Detail & Related papers  (2024-05-23T07:40:21Z)
• Causal Bandits for Linear Structural Equation Models [58.2875460517691]
  This paper studies the problem of designing an optimal sequence of interventions in a causal graphical model. It is assumed that the graph's structure is known and has $N$ nodes. Two algorithms are proposed for the frequentist (UCB-based) and Bayesian settings.
  arXiv  Detail & Related papers  (2022-08-26T16:21:31Z)
• Graph Neural Network Bandits [89.31889875864599]
  We consider the bandit optimization problem with the reward function defined over graph-structured data. Key challenges in this setting are scaling to large domains, and to graphs with many nodes. We show that graph neural networks (GNNs) can be used to estimate the reward function.
  arXiv  Detail & Related papers  (2022-07-13T18:12:36Z)
• Effects of Graph Convolutions in Deep Networks [8.937905773981702]
  We present a rigorous theoretical understanding of the effects of graph convolutions in multi-layer networks. We show that a single graph convolution expands the regime of the distance between the means where multi-layer networks can classify the data. We provide both theoretical and empirical insights into the performance of graph convolutions placed in different combinations among the layers of a network.
  arXiv  Detail & Related papers  (2022-04-20T08:24:43Z)
• RaWaNet: Enriching Graph Neural Network Input via Random Walks on Graphs [0.0]
  Graph neural networks (GNNs) have gained increasing popularity and have shown very promising results for data that are represented by graphs. We propose a random walk data processing of the graphs based on three selected lengths. Namely, (regular) walks of length 1 and 2, and a fractional walk of length $gamma in (0,1)$, in order to capture the different local and global dynamics on the graphs. We test our method on various molecular datasets by passing the processed node features to the network in order to perform several classification and regression tasks.
  arXiv  Detail & Related papers  (2021-09-15T20:04:01Z)
• Maximizing Influence with Graph Neural Networks [23.896176168370996]
  textscGlie is a graph neural network that learns to estimate the influence spread of the independent cascade. textscGlie relies on a theoretical upper bound that is tightened through supervised training. We develop a provably submodular influence spread based on textscGlie's representations to rank nodes while building the seed set adaptively.
  arXiv  Detail & Related papers  (2021-08-10T12:08:15Z)
• Maximizing Influence of Leaders in Social Networks [15.05158252504978]
  We consider the edge addition problem for the DeGroot model of opinion dynamics in a social network with $n$ nodes and $m$ edges. We show that our algorithm is efficient and effective, which scales to large networks with more than a million nodes.
  arXiv  Detail & Related papers  (2021-06-11T02:31:46Z)
• The Power of $D$-hops in Matching Power-Law Graphs [20.88345367293753]
  We develop an efficient algorithm that exploits the low-degree seeds in suitably-defined $D$-hop neighborhoods. Under the Chung-Lu random graph model with $n$ vertices, max degree $Theta(sqrtn)$, and the power-law exponent $2beta3$, we show that as soon as $D> frac4-beta3-beta$, by optimally choosing the first slice, with high probability our algorithm can correctly match a constant fraction of the true pairs.
  arXiv  Detail & Related papers  (2021-02-23T05:36:58Z)
• Pipeline Interventions [15.27567660320295]
  We present the emphpipeline intervention problem, defined by a layered directed acyclic graph and a set of matrices governing transitions between successive layers. The graph is a stylized model for how people from different populations are presented opportunities, eventually leading to some reward. We consider two objectives: social welfare, and a fairness-motivated maximin objective that seeks to maximize the value to the population with the emphleast expected value.
  arXiv  Detail & Related papers  (2020-02-16T15:28:29Z)
• Curse of Dimensionality on Randomized Smoothing for Certifiable Robustness [151.67113334248464]
  We show that extending the smoothing technique to defend against other attack models can be challenging. We present experimental results on CIFAR to validate our theory.
  arXiv  Detail & Related papers  (2020-02-08T22:02:14Z)

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.