PaperlayerView exact revision on arXiv

Source-linked AI summary

Revealing graph bandits for maximizing local influence

Alexandra Carpentier, Michal Valko

arXiv:2605.00489v1cs.LGstat.ML

TL;DR

Existing graph-bandit methods require graph information beyond the local feedback available in some social-network marketing settings. This paper proposes BARE, which learns on an initially unknown graph from the influenced set revealed after each choice. Its guarantees scale with detectable dimension, and it is minimax-optimal over problems with that dimension.

  • Problem

    Existing graph-bandit approaches require knowledge of graph portions, while the setting considered here reveals only the chosen node’s first neighborhood; social-network links may also be unavailable to advertisers.

    Source: §1 · p. 2

  • Method

    BARE learns on an initially unknown graph by selecting nodes sequentially and observing the set each selected node influences.

    Source: §1 · p. 2

  • Results

    BARE is minimax-optimal over the set of problems with detectable dimension D⋆.

    Source: §4.1 · p. 7

  • Takeaways & Limitations

    When detectable dimension is small, BARE does not need to sample the entire graph, and its guarantees do not scale with node count.

    Source: §1 · p. 2

    The setting assumes influence is mutual to a certain degree, and the conclusion identifies more elaborate propagation models as future extensions.

    Source: §2.1 · p. 3, §6 · p. 8

Abstract

from arXiv · show

We study a graph bandit setting where the objective of the learner is to detect the most influential node of a graph by requesting as little information from the graph as possible. One of the relevant applications for this setting is marketing in social networks, where the marketer aims at finding and taking advantage of the most influential customers. The existing approaches for bandit problems on graphs require either partial or complete knowledge of the graph. In this paper, we do not assume any knowledge of the graph, but we consider a setting where it can be gradually discovered in a sequential and active way. At each round, the learner chooses a node of the graph and the only information it receives is a stochastic set of the nodes that the chosen node is currently influencing. To address this setting, we propose BARE, a bandit strategy for which we prove a regret guarantee that scales with the detectable dimension, a problem dependent quantity that is often much smaller than the number of nodes.

1 Introduction

Graph structure can help bandit learners identify influential users, but prior graph-bandit approaches require more network knowledge than the local feedback available in some marketing settings. The paper studies learning influence from an initially unknown graph and introduces BARE, whose guarantees scale with detectable dimension rather than node count.

1 Introduction

  • Graph structure can speed learning in bandits [Mannor & Shamir, 2011; Caron et al., 2012], with guarantees expressed using quantities such as clique partition number, independence number, or minimum dominating set [Caron et al., 2012; Alon et al., 2013].Source: §1 · p. 1
  • Social-network operators may withhold links, while promotional codes or likes can let advertisers observe which users were influenced by targeted customers.Source: §1 · pp. 1–2
  • BARE addresses sequential influence learning on an initially unknown graph, with guarantees scaling by detectable dimension and no need to sample the entire graph when that dimension is small.At each round, the learner selects a node and observes the set of nodes it influences.Source: §1 · p. 2
  • Prior graph-learning approaches typically need the whole graph or substantial information such as second neighborhoods, while this setting reveals only the chosen node’s first neighborhood.Source: §1 · pp. 1–2
  • Related online influence-maximization work combines offline methods with bandits under independent-cascade and semi-bandit feedback, while other approaches constrain graph exploration [Lei et al., 2015; Chen et al., 2015; Vaswani & Lakshmanan, 2015; Bnaya et al., 2013a,b; Singla et al., 2015].Source: §1 · p. 2

2 Local influence bandit settings

The setting begins with an unknown graph: selecting a node reveals its influenced set, and the learner seeks to maximize influence over a finite budget against an oracle that knows the graph. A restricted count-only feedback version becomes a classic multi-arm bandit problem, for which the paper gives lower- and upper-bound results.

2.1 Description of the problem

  • At each round, the learner selects a node and observes its influenced set; the objective is to maximize the number of influences over n rounds against an oracle choosing a node with maximal expected influence.Source: §2.1 · p. 3

2.2 Baseline comparison: Observing only |Skt|, the number of influenced nodes

  • With count-only feedback, the observed reward is the number of influenced nodes rather than their identities, so graph structure cannot be exploited and the problem maps to a classic multi-arm bandit.The count reward is a noisy version of the selected node’s expected influence.Source: §2.2 · p. 3
  • For count-only feedback, Theorem 1 supplies a lower bound under an intermediate-influence condition and an upper bound for GraphMOSS.Source: §2.2 · pp. 3–4
  • The lower bound also holds for undirected graphs, where the influence matrix is symmetric.Source: §2.2 · p. 4

3 The BARE algorithm and results

BARE uses the detectable dimension to narrow graph discovery to a small candidate set, then searches that set for an influential node. For undirected social networks, its regret is minimax-optimal as if the problem had D⋆ nodes instead of d.

3 The BARE algorithm and results

  • In the unrestricted setting, the minimax-optimal rate matches the restricted-information setting, and no adaptive strategy improves it in the minimax sense.The paper illustrates the equivalence with networks where graph structure provides little useful information about influence.Source: §3 · p. 4
  • Cases where the identities of influenced nodes do not help are described as somewhat pathological; informative cases include networks where highly influential nodes are also likely to be influenced.The paper points to symmetric networks as an example of the latter situation.Source: §3 · p. 4
  • The detectable dimension depends on graph topology: a star can have D⋆=1, while a graph with all but two nodes disconnected can have D⋆ of order d.The paper also identifies many small cliques as a bad case.Source: §3 · p. 5
  • BARE first extracts at most a constant multiple of D⋆ candidates containing a node within ε⋆ of the most influential node, then searches that smaller set.The extraction avoids scanning all d nodes, even when d exceeds the time budget n.Source: §3 · p. 5
  • BARE has a regret guarantee for unrestricted local influence with information about neighbors, without requiring preliminary information about the graph.The theorem statement supplies the setting, while the following remark contrasts BARE with a classic multi-arm bandit strategy requiring preliminary graph information.Source: §3 · p. 5
  • For undirected social networks, BARE attains the minimax-optimal regret for D⋆ nodes instead of d.The paper’s corollary describes this as the method’s dimensionality-reduction potential.Source: §3 · p. 5

4 Proof of Theorem 2

The discussion argues that BARE is minimax-optimal over problems with detectable dimension D⋆. Its proof uses global exploration to retain promising nodes, then applies a minimax bandit algorithm to them.

4 Proof of Theorem 2

  • During global exploration, nodes are sampled uniformly, and concentration bounds support retaining the most influential nodes with gap at most ε⋆.The proof uses the event ξ and a Bernstein inequality to show the most-influenced nodes are among those retained.Source: §4 · pp. 6–7
  • BARE then runs a minimax bandit algorithm on the retained nodes to bound regret over the remaining rounds.The proof identifies GraphMOSS as one suitable algorithm for this phase.Source: §4 · p. 7

4.1 Discussion

  • BARE is minimax-optimal over problems with detectable dimension D⋆, including an undirected-graph case with ε⋆ = 0.The discussion notes this optimality even when the learner is given a set containing the optimal node, for n ≥ d.Source: §4.1 · p. 7
  • For n ≪ d, the discussion says BARE has lower regret than the order nr⋆ incurred by strategies in the restricted setting.This is the large-network regime where an advertiser may not have budget to target all users.Source: §4.1 · p. 7
  • When D⋆ ≤ n in the unrestricted setting, BARE's regret is smaller than nr⋆, and the problem becomes learnable.The discussion associates this regime with a small number of nodes being noticeably more influential than the others.Source: §4.1 · p. 7

5 Experiments

The experiments compare BARE with GraphMOSS on synthetic and real networks, finding that BARE's gains depend on network structure and revelation probability. In the Barabási–Albert experiment, BARE identifies promising nodes sooner, with gains evident around t = 300.

5 Experiments

  • Experiments assess whether BARE outperforms algorithms that ignore graph structure in regime n ≤ d; GraphMOSS serves both as BARE’s minimax-optimal bandit-phase algorithm and as the graph-ignoring baseline.The confidence parameter δ was 0.01 and pᵢ,ⱼ was 0.8 for all i and j. Figures show results averaged over 100 trials.Source: §5 · p. 7
  • On the 1,000-node Barabási–Albert graph, BARE's benefit from revealed information is visible around t = 300, while GraphMOSS pulls each arm once through t = d.GraphMOSS eventually detects the best node after its regret stops being linear beyond d.Source: §5 · p. 8
  • When revelation probability p is near one, more graph structure is revealed and the problem becomes easier; near zero, BARE and GraphMOSS perform similarly.Figure 2 varies p from 0.2 to 1 on a Barabási–Albert graph.Source: §5 · p. 8, Figure 2 · p. 8
  • BARE's gains over GraphMOSS are significant on Enron and Facebook but much smaller on Gnutella, indicating network-dependent performance.The authors interpret the pattern as suggesting relatively few influential nodes in Enron and Facebook and a more decentralized Gnutella network.Source: §5 · p. 8, Figure 1 · p. 8
  • The authors report empirical estimates of detectable dimension D̂⋆ and horizon T̂⋆, relating smaller values relative to d and n to earlier learning by BARE.The comparison is with GraphMOSS.Source: §5 · p. 8

6 Conclusion

The conclusion identifies local revelation and complete graph-structure agnosticism as the setting studied, and points to richer propagation models and graph-structure assumptions as directions for extension.

6 Conclusion

  • The authors propose extending local revelation to more elaborate propagation models and using structural assumptions from graph generator models to improve learning rates.They also suggest more feedback, such as identities of influencing paths, as a possible extension.Source: §6 · p. 8

A Proof of Theorem 1

The appendix establishes upper and lower regret bounds for the graph bandit problem under its stated setup. The upper bound adapts MOSS with a Bernstein-based confidence term, while the lower-bound discussion distinguishes sampling and unlearnable regimes.

A Proof of Theorem 1

  • Theorem 1 gives a regret bound for the graph bandit problem when reward is the number of influenced nodes.The theorem statement identifies this reward as |Sₖₜ,ₜ| rather than the influenced-node set itself.Source: A Proof of Theorem 1 · p. 10
  • The lower-bound construction adapts Lai and Robbins' d-armed problems to graph structure under a stated range for r⋆ and ε.The supplied theorem passage states that εd < r⋆ < (1 − ε)d for sufficiently large n.Source: A Proof of Theorem 1 · p. 10
  • The upper bound for Algorithm 1 follows from Audibert and Bubeck's MOSS analysis using a Bernstein confidence term.The proof bounds the variance of the influenced-node count by r⋆ because it is a sum of Bernoulli variables.Source: A Proof of Theorem 1 · p. 10
  • The lower-bound discussion attributes r⋆d to sampling each arm when n ≥ d and r⋆n to the unlearnable case n ≤ d.The passage states that otherwise a worst-case permutation of arms can be considered.Source: A Proof of Theorem 1 · p. 10

B Proof of Theorem 3

Theorem 3 establishes a worst-case expected-regret lower bound under stated restrictions on maximal influence, detectable dimension, and the influential-influence gap. Its proof constructs cases where graph structure does not significantly help or is completely useless.

B Proof of Theorem 3

  • Theorem 3 lower-bounds worst-case expected regret for unrestricted settings with bounded maximal influence, D*≤D, and a small influential-influence gap.The statement specifies a universal constant C′′.Source: B Proof of Theorem 3 · p. 10
  • In one construction, even revealing the identities of the D best nodes leaves D*=D, ε*=0, and r*=r, while graph structure does not significantly help.The proof sets edge probabilities differently depending on whether either endpoint is the optimal node.Source: B Proof of Theorem 3 · p. 11
  • The proof splits into n≤d and n≥d cases, constructing asymmetric graphs with detectable dimension 1 where graph structure does not help or is completely useless.Source: B Proof of Theorem 3 · p. 11

C Detectable dimension

Appendix plots illustrate how detectable dimension varies with graph structure and the number of rounds. A star graph has D*=1, whereas a complete graph and an empty graph have D*=d even for large n.

C Detectable dimension

Loading 2605.00489v1…