---
title: "Sparse Polynomial Surrogates Cut Graph Diffusion Simulations to Near-Optimal Rates"
subtitle: "A new sparse polynomial framework builds fast surrogates for parametric diffusion on community-structured graphs, with proven convergence and a public code release."
url: "https://alphasignal.ai/news/sparse-polynomial-surrogates-cut-graph-diffusion-simulations-to-near-optimal"
author: "AlphaSignal Newsroom"
author_url: "https://alphasignal.ai/editorial-team"
company: "AlphaSignal"
company_url: "https://alphasignal.ai/company/alphasignal"
published: "2026-04-13T00:00:00.000Z"
updated: "2026-08-24T03:06:27.439Z"
type: "Paper"
topics:
  - "Data"
  - "Benchmarks"
subtopics:
  - "Datasets"
upvotes: 1282
source_url: "https://arxiv.org/abs/2502.06595"
comments: 0
truncated: true
---

# 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.

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](https://arxiv.org/abs/2502.06595) 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

_Preview only. Full text requires an AlphaSignal Pro account._

## Sources

- [Surrogate models for diffusion on graphs via sparse polynomials](https://arxiv.org/abs/2502.06595)
- [surrogate_graph_diffusion (GitHub)](https://github.com/k-yoan/surrogate_graph_diffusion)
- [SNAP: Congressional Twitter network dataset](https://snap.stanford.edu/data/)
- [NetworkX](https://networkx.org/)