Online Network Source Optimization with Graph-Kernel MAB

Laura Toni, Pascal Frossard

Introduction

In large-scale network management—ranging from sensor placement in water distribution systems to influencer selection in social networks—the challenge of "source optimization" is often hindered by the curse of dimensionality. Traditional Multi-Armed Bandit (MAB) frameworks, which treat each possible configuration as an independent arm, fail when the action space grows exponentially with the number of nodes. This paper introduces Grab-UCB, a novel online learning framework that leverages Graph Signal Processing (GSP) to overcome these limitations by shifting the learning process from the high-dimensional node domain to a low-dimensional spectral domain.

Problem Formulation

The core challenge addressed is the optimization of source placement when the underlying network process—how a signal diffuses from a source to the rest of the network—is dynamic and initially unknown. In a network of $N$ nodes, selecting a subset of sources creates an astronomically large action space. The goal is to learn the diffusion process "on the fly" while simultaneously making decisions that maximize cumulative rewards, effectively balancing exploration of the network's physics with exploitation of known high-reward configurations.

Methodology

1. Grab-UCB (Graph-Kernel Upper Confidence Bound)

Rather than attempting to learn rewards for every possible node combination, Grab-UCB focuses on learning the graph generating kernel. By modeling the network process as a graph filter—specifically a polynomial of the graph Laplacian—the authors transform the problem into a linear MAB.

The algorithm learns the spectral coefficients ($K$) of this filter. Because $K$ is typically much smaller than the total number of nodes ($N$), the learning complexity scales with the complexity of the network process rather than the size of the physical network. This "spectral shortcut" allows the agent to generalize observations from one part of the graph to others based on the underlying graph topology.

2. Grab-arm-Light

Selecting the optimal arm (source placement) within this spectral framework is an NP-hard problem, as it requires maximizing a convex function over a polytope. To maintain computational feasibility, the authors developed Grab-arm-Light, a heuristic inspired by the simplex algorithm. This solver "walks" along the edges of the decision polytope, swapping active source nodes for inactive ones based on gradient descent until a local optimum is reached. This approach ensures that the algorithm remains performant even as the network size increases.

Experimental Evaluation

The researchers validated Grab-UCB using a mix of synthetic and real-world network models:

  • Barabási-Albert (BA) Models: Scale-free networks representing social and communication structures.
  • Radial Basis Function (RBF) Random Graphs: Geometric graphs where connectivity is distance-dependent.
  • Minnesota Road Network: A benchmark representing real-world transportation infrastructure.

Key Findings

  • Sample Efficiency: Grab-UCB’s cumulative regret scales with the spectral dimension ($K$), making it sustainable for massive networks where traditional MABs would never converge.
  • The Role of Connectivity: The study mathematically demonstrates that higher "algebraic connectivity" in a graph facilitates faster learning. Well-connected graphs allow signals to diffuse more broadly, providing the learner with more informative feedback from fewer actions.
  • Computational Performance: Grab-arm-Light achieved rewards comparable to exact numerical solvers while reducing CPU time significantly. While exact solvers scale exponentially, Grab-arm-Light’s complexity grows linearly with network size.
  • Strategic Placement: The algorithm successfully identified non-intuitive source placements. It proved that the optimal nodes are not always the most "central" ones, but rather those that maximize the reward based on the specific, learned network kernel.

Discussion and Future Work

Grab-UCB represents a significant step forward in applying GSP to online learning. By using "optimism in the face of uncertainty" in the spectral domain, the agent directs its curiosity toward the general rules of the network's physics.

However, some limitations remain. The current framework assumes a linear relationship between the graph signal and the reward, which may not capture highly non-linear dynamics. Additionally, while Grab-arm-Light is highly efficient, it remains a hill-climbing heuristic that could potentially settle in local optima in extremely complex landscapes. Future research may explore Thompson Sampling as an alternative selection strategy or extend the framework to handle heterogeneous feature vectors and multi-mode tensor problems in social advertising.

Conclusion

By integrating graph-kernel methods with MABs, Grab-UCB provides a scalable solution for online source optimization. It effectively bypasses the curse of dimensionality, allowing for efficient learning and decision-making in networks that were previously too large to optimize in real-time.

Summary updated

BibTeX
@inproceedings{toni2023online,
  author = {Laura Toni and Pascal Frossard},
  title = {{Online Network Source Optimization with Graph-Kernel MAB}},
  booktitle = {ECML/PKDD},
  year = {2023},
  doi = {10.1007/978-3-031-43418-1\_15},
}
Figure