Sparse Polynomial Surrogates Cut Graph Diffusion Simulations to Near-Optimal Rates
A new sparse polynomial framework builds fast surrogates for parametric diffusion on community-structured graphs, with proven convergence and a public code release.
PRO- New sparse polynomial surrogate models approximate parametric diffusion on community-structured graphs without repeated ODE solves.
- Authors prove the parameter-to-solution map is holomorphic, unlocking near-optimal polynomial convergence rates.
- Convergence guarantees cover both least squares and weighted compressed sensing (SR-LASSO, QCBP) decoders.
- Experiments on Stochastic Block Model graphs and a 475-node US Congress Twitter network validate the theory.
- Hyperbolic cross index sets outperform total-degree sets at higher parameter dimensions like d=10.
- Open-source Python code released at github.com/k-yoan/surrogate_graph_diffusion.
Diffusion on graphs quietly powers a lot of modern ML tooling, from epidemic modeling and influence prediction to the message-passing rules inside graph neural networks. There is a gap most practitioners run into eventually: if the diffusion coefficients on your edges are parameters you want to sweep, tune, or do uncertainty quantification over, you end up solving the same ODE thousands of times. A new paper from D'Inverno, Ajavon, and Brugiapaglia proposes a principled shortcut, building sparse polynomial surrogates for parametric graph diffusion and proving they converge at near-optimal rates.
The missing surrogate
Surrogate modeling via sparse polynomials is well established for parametric PDEs like elliptic equations, where the parameter-to-solution map is holomorphic and polynomial approximations dodge the curse of dimensionality. Diffusion on graphs has never gotten the same treatment, despite being used for marketing selection over social networks, information flow on media graphs, and epidemic spread prediction. If you want to know how a diffusion signal at some node depends on a vector of edge-weight parameters, your options have basically been Monte Carlo or brute-force resimulation.
The setup the authors tackle is the time-and-edge-dependent diffusion equation on a weighted graph, where the diffusion coefficient matrix
This story is for Pro members
You've reached the end of the free preview. Upgrade to AlphaSignal Pro to read the full article - and everything else behind the paywall.
Comments
