Surrogate models for diffusion on graphs via sparse polynomials

Our new paper ‘Surrogate models for diffusion on graphs via sparse polynomials’ in collaboration with Kylian Ajavon and Simone Brugiapaglia is out! You can find the paper here.

Over the past two decades, sparse polynomial approximation has become a key tool for constructing surrogate models, particularly in uncertainty quantification. This approach approximates high-dimensional parametric models, especially parametric PDEs, using polynomials. These models often have fast convergence rates, enabling efficient approximation and mitigating the curse of dimensionality. While much of the focus has been on PDEs, diffusion on graphs has emerged as another important approach. Diffusion kernels, commonly used in applications like social networks and epidemic prediction, have recently gained attention in graph deep learning. However, little research has explored surrogate models for parametric diffusion on graphs, which this work addresses.

The main contributions of our work are the following:

• We introduce sparse polynomial-based surrogate models for parametric diffusion on graphs using least squares and compressed sensing.
• We prove that the parameter-to-solution map for these models is holomorphic and demonstrate that sparse polynomial models can achieve optimal approximation rates, alleviating the curse of dimensionality.
• We validate the approach with numerical experiments on synthetic graphs and a real-world Twitter graph.