Revealing graph bandits for maximizing local influence

In plain words

Imagine picking the most persuasive person in a social network without being able to see who knows whom. Each time you pick someone, you only learn which people that person went on to influence. Trying everyone is too slow when the network is huge.

The authors show that you do not need to try everyone. A short random exploration round first reveals which people tend to be strongly connected to many others, and that leaves a small shortlist. A standard "try the options and learn which is best" procedure then runs only on the shortlist. How long the shortlist is depends on the network's structure rather than its size.

The authors prove a guarantee on the loss of this method compared with an oracle that knows the network. Their experiments are plots, with no numeric regret values; they show the method ahead of a baseline that ignores the graph on several network datasets.

TL;DR

• Setting: the learner picks one node per round and observes the set of nodes it influences, but not the rest of the graph §2.1.
• BARE first samples nodes uniformly to build a shortlist of candidates, then runs a minimax-style bandit (GraphMOSS in the experiments) on that shortlist §3 alg. 2 §5.
• The regret bound scales with a detectable dimension D* and an influential-influenced gap ε*, instead of the number of nodes d §3.
• Use it when the graph is large, hidden and you can only probe nodes one at a time. All guarantees are author-reported and hold up to unstated constants.

Problem

A graph with d nodes is unknown. Node i influences node j with an unknown probability p_{i,j}. Each round the learner picks a node and sees the set of influenced nodes; the goal is to maximise the total number of influences over n rounds §2.1. The learner competes with an oracle that always plays the most influential node, and the regret is the expected gap to that oracle §2.1.

If the learner sees only the count of influenced nodes, the graph cannot be used and the problem reduces to a plain bandit over d arms. Then the regret is of the order min(r* n, r* d + sqrt(r* n d)), up to constants §2.2 [thm. 1 in §2.2]. The paper argues that this is the regime where the graph structure is not exploited at all §2.2.

Method

Notation §2.1. The primal influence of node k is r_k = Σ_j p_{k,j}, the expected number of nodes it influences. The dual influence is r°k = Σ_j p{j,k}, the expected number of nodes that influence k. For an undirected graph, r°_k = r_k §2.1. The best dual value is r°* = max_k r°k §2.1, and r* = r{k*} is the primal value of the oracle's node §2.1.

Baseline GraphMOSS §2.2 alg. 1. A MOSS-style bandit adapted so that the width uses an empirical standard deviation. It is the no-structure comparison and also the bandit used inside BARE §5.

# GraphMOSS: choose the next node  [alg. 1] [§2.2]
# Input:  mean (d,), sigma (d,), pulls (d,)   # r_hat, sigma_hat, T_k
# Output: index of the node to pull next

def graph_moss_choose(mean, sigma, pulls, n, d):
    # Elementwise log term, floored at zero  [alg. 1]
    log_term = max(log(n / (d * pulls)), 0)   # (d,)
    # Width: a sigma-driven term plus a range term  [alg. 1]
    width = 2 * sigma * sqrt(log_term / pulls) + 2 * log_term / pulls
    # Optimistic index; tie-breaking is not stated  [alg. 1]
    return argmax(mean + width)

BARE, phase 1: global exploration §3 alg. 2. Pick a node uniformly at random and observe its influenced set alg. 2 §4. For every node k, keep a running estimate of its dual influence built from d·S(k), where S(k) is the 0/1 indicator that node k was influenced §4 alg. 2. After each sample, compute a confidence level σ̂ and a keep-window width w, then retain only the nodes whose estimate lies within w of the best estimate alg. 2. Stop when the test in the while-condition of alg. 2 fails; the stopping time is T̂* and the surviving set is the candidate set D̂* alg. 2.

# BARE global exploration phase  [alg. 2] [§3]
# Input:  d (nodes), n (horizon)
# Output: kept_mask (d,) of candidate nodes, t_hat (phase length)

def bare_explore(d, n):
    # Start with all nodes kept and zero estimates  [alg. 2]
    dual_mean = zeros(d)                     # running estimate of r°_k
    kept_count = d                           # D_hat, number of kept nodes
    sigma = d                                # sigma_hat, starts at d
    t = 1
    # Continue while the stop test of [alg. 2] holds  [alg. 2]
    while (t * (sigma - 4 * sqrt(d * log(n * d) / t))
           <= sqrt(kept_count * n)):
        # Sample a uniformly random node and observe its influenced set  [§4]
        k_t = random_node(d)
        revealed = observe_influenced_set(k_t)   # (d,) 0/1 vector
        # Update for every node, exactly as written in [alg. 2]
        dual_mean = (t * dual_mean + d * revealed) / (t + 1)
        # max over k' of sqrt(.) equals sqrt of the max  [alg. 2]
        sigma = sqrt(max(dual_mean) + 8 * d * log(n * d) / (t + 1))
        # Keep-window width  [alg. 2]
        width = (8 * sigma * sqrt(d * log(n * d) / (t + 1))
                 + 40 * d * log(n * d) / (t + 1))
        # Keep nodes whose estimate is within width of the best  [alg. 2]
        kept_mask = max(dual_mean) - dual_mean <= width
        kept_count = sum(kept_mask)
        t = t + 1
    # Phase length and candidate set go to the bandit phase  [alg. 2]
    t_hat = t
    return kept_mask, t_hat

BARE, phase 2: bandit alg. 2. Run a minimax-optimal bandit on the kept nodes for the remaining rounds. The algorithm names the bandit only as "e.g." Algorithm 1 (GraphMOSS), and the experiments use GraphMOSS alg. 2 §5.

Key quantities §3, Definition 1. The detectable horizon T* is the smallest integer with the inequality below, or T* = n if none exists. The detectable dimension is D* = D(Δ*) and the detectable gap is Δ*:

T_\star\, r^\circ_\star \ge \sqrt{D_\star\, n\, r^\circ_\star} §3

\Delta_\star = 16\sqrt{\frac{r^\circ_\star\, d\log(nd)}{T_\star}} + \frac{144\, d\log(nd)}{T_\star} §3

D(\Delta) = \left|\left\{ i \le d :\ r^\circ_\star - r^\circ_i \le \Delta \right\}\right| §3

The influential-influenced gap is ε* = r* − max over the dual-best set of r_k, where the dual-best set is the nodes with r°_i = r°* §3, Remark 2. It is zero when a dual-best node is also primal-best, as in undirected graphs [§3, Remark 2].

Estimator used in the proof §4. The proof treats the exploration estimator as the average of d·S(k) over the t exploration samples, and uses it to show a concentration event ξ eq. 1 and a width bound on the confidence level eq. 2. Together these give the claim that the best dual node survives exploration §4.

Guarantees.

• Theorem 2 (BARE, unrestricted feedback) §3: for a constant C,

E[R_n] \le C \min\left( r_\star n,\; D_\star r_\star + \sqrt{r_\star n D_\star} + n\varepsilon_\star \right) §3

• Corollary 1 (undirected graphs) §3: the same bound without the n ε* term, which the authors call minimax optimal in the case of D* arms §3.
• Theorem 3 (lower bound) §3, app. B: for d ≥ Cn, any algorithm incurs regret of order min(r n, D̄ r + sqrt(r n D̄) + n ε), with a universal constant §3 app. B.

Hyperparameters

Results

Author-reported. The paper reports no numeric regret values. Setup: simulation on graphs with the sizes listed above, averaged over 100 trials, with p = 0.8 unless stated, and the scaled confidence terms §5. The theoretical rows are the bounds from Section 3 and Section 2.2.

The paper says that when p is near zero the performance of BARE and GraphMOSS is similar, and that p near one makes the problem easier §5. Figure 3 and Figure 4 in Appendix C show D̂ against n for the same graphs app. C.

Paper vs code

No official code.

The LaTeX source contains no code or project link §5. The searches were: GitHub repository search for "graph bandits local influence", "bandit revelator", "carpentier valko bandit" and "graph bandit influence"; GitHub user search for "alexandra carpentier"; and the repository list for the second author's account (misovalko). Nothing belonging to the authors implements BARE. The only hits for the influence-bandit terms were third-party reimplementations (tangih/InfluenceMaximisation, alfasst/OIM-GNB), which were not used. A web search was not available in this run.

Pitfalls

• The exploration estimator is off by one. The pseudocode starts the running mean at zero with t = 1, then updates r̂ ← (t · r̂ + d · S) / (t + 1) alg. 2. That divides the sum of samples by one more than the number of samples, so the estimate is lower than the average defined in the proof, (1/t) Σ d·S(k) §4. The paper does not say which one to implement. Use the proof's average if you want the concentration event eq. 1 to hold as written.
• Dual versus primal. Exploration ranks nodes by the dual influence r°, but the regret is measured with the primal r. The two agree only for undirected graphs §2.1. For directed graphs, ε* adds an extra n ε* term §3, Remark 2; the algorithm does not compensate for it.
• Experiments do not run the analysed algorithm. The confidence terms are multiplied by 0.01 in the experiments §5, and the proof's constants do not appear there. Results cannot be read as a test of the stated bounds.
• δ is set but unused. The experiments set δ = 0.01 §5. No algorithm takes δ as an input, and the widths use log(nd) only alg. 2. Treat the confidence level as log(nd) with no further constant.
• Two different T conditions.* Definition 1 says T* is the smallest integer greater than 0 §3. Remark 1 says greater than 1 §3, Remark 1. Pick one.
• Theorem 2 is an expectation bound with a failure term. The proof works on a high-probability event ξ eq. 1 and adds r*/n to cover the failure case §4. The constant C is not given.
• GraphMOSS's variance estimator is not specified. The algorithm updates "σ̂" and "T" without a formula alg. 1. The appendix calls σ̂² the empirical variance app. A but does not state whether it is biased or unbiased.
• Bandit phase warm start. The paper does not say whether the samples collected during exploration are reused to initialise the bandit on the kept set, or how the first 2d GraphMOSS pulls relate to the d-round exploration. Section 5 says GraphMOSS "pulls each arm once" up to t = d §5, while the algorithm says "sample each arm twice" alg. 1.
• Minimax claims are informal. Corollary 1 says BARE is minimax optimal for the detectable dimension. The argument is sketched in §4.1 and refers back to the Theorem 1 construction, and the lower bound (Theorem 3) requires d ≥ Cn §3 §4.1.
• Horizon dependence. The widths and T* depend on n, so BARE is not an anytime algorithm as written alg. 2 §3, Def. 1.
• Per-round cost. Each exploration step updates the estimate of all d nodes and recounts the kept set alg. 2. The per-round work is therefore at least linear in d. The paper does not state a complexity or memory bound.
• Numbering. Equation, theorem and figure numbers here were counted in source order from bare.tex, not from a compiled PDF. Source labels are swapped: GraphMOSS (label alg:2) is printed as Algorithm 1 and BARE (label alg:1) as Algorithm 2. Figures 3 and 4 are in the appendix, and are cited as app. C.
• Neighbour probabilities. The experiment text sets p_{i,j} = 0.8 "for all i and j" and then describes neighbours only §5. Assume edges only, and state that as your own reading.

Lineage

• Builds on: the MOSS bandit, cited in the source as audibert2009minimax §2.2; the graph-bandit line with side observations, for example caron2012leveraging and mannor2011from §1; and the minimum dominating-set and independence-number bounds for known graphs §1.
• Compared against: GraphMOSS on the d nodes, ignoring the graph §2.2 §5.
• Superseded by: not known from content on this wiki.