pith. sign in

arxiv: 2502.06595 · v3 · submitted 2025-02-10 · 🧮 math.NA · cs.LG· cs.NA

Surrogate models for diffusion on graphs via sparse polynomials

Giuseppe Alessio D'Inverno , Kylian Ajavon , Simone Brugiapaglia This is my paper

Pith reviewed 2026-05-23 03:36 UTC · model grok-4.3

classification 🧮 math.NA cs.LGcs.NA
keywords surrogate modelsdiffusion on graphssparse polynomialsholomorphic regularitycompressed sensingleast squarescommunity structureparametric equations
0
0 comments X

The pith

Sparse polynomial surrogate models approximate parametric diffusion on graphs with community structure using holomorphic regularity for convergence guarantees.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The authors develop sparse polynomial surrogate models for parametric diffusion equations on graphs that have community structure to address the lack of such methods in the literature. They prove that the solutions are holomorphic in the parameters, which justifies convergence rates for approximations constructed via least squares or compressed sensing. The theoretical results are supported by numerical experiments on both synthetic and real-world graphs demonstrating practical effectiveness for modeling diffusion processes.

Core claim

We propose sparse polynomial-based surrogate models for parametric diffusion equations on graphs with community structure and provide convergence guarantees for both least squares and compressed sensing-based approximations by showing the holomorphic regularity of parametric solutions to these diffusion equations.

What carries the argument

sparse polynomial approximations leveraging the holomorphic regularity of the parametric solutions

If this is right

  • The surrogate models can be used to efficiently compute diffusion kernels on graphs.
  • Error bounds hold for both least-squares and compressed-sensing recovery methods.
  • The approach is validated numerically on synthetic and real graphs.
  • Convergence is guaranteed under the holomorphic regularity condition.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The method could be adapted for other parametric problems on graphs, such as wave equations or heat equations with different operators.
  • Applications in network science might benefit from faster evaluation of diffusion-based metrics.
  • Combining with graph neural networks could create hybrid models for learning on graphs.

Load-bearing premise

The parametric solutions to the diffusion equations on graphs with community structure possess sufficient holomorphic regularity in the parameters.

What would settle it

Finding a counterexample diffusion equation on a community graph where the solution is not holomorphic in the parameters, violating the convergence guarantees.

Figures

Figures reproduced from arXiv: 2502.06595 by Giuseppe Alessio D'Inverno, Kylian Ajavon, Simone Brugiapaglia.

Figure 1
Figure 1. Figure 1: Multi-index sets of order n = 4 in N 3 0 (left: total degree; right: hyperbolic cross). where the Pν’s are the univariate Legendre polynomials defined, e.g., via Rodrigues’s formula: Pν(y) = 1 2 νν! d ν dyν (y 2−1)ν , y ∈ [−1, 1], for all ν ∈ N0. Another popular choice for ϱ and {ψν}ν∈Nd 0 is given by the Chebyshev measure and Chebyshev polynomials, respectively; see [1] for further details. Our goal is to… view at source ↗
Figure 2
Figure 2. Figure 2: Convergence plot of average RMSE vs. number of sample points for [PITH_FULL_IMAGE:figures/full_fig_p020_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Convergence plot of average RMSE vs. number of sample points for [PITH_FULL_IMAGE:figures/full_fig_p021_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Convergence plot of average RMSE vs. cardinality of multi-index set for a fixed number [PITH_FULL_IMAGE:figures/full_fig_p022_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Convergence plot of average RMSE vs. cardinality of multi-index set for a fixed number [PITH_FULL_IMAGE:figures/full_fig_p023_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Convergence plots of average RMSE vs. number of sample points for a 24-node graph [PITH_FULL_IMAGE:figures/full_fig_p024_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: Convergence plots of average RMSE vs. number of sample points for a 24-node graph [PITH_FULL_IMAGE:figures/full_fig_p025_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: Convergence plots of average RMSE vs. number of sample points for a 24-node graph [PITH_FULL_IMAGE:figures/full_fig_p025_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: Convergence plots of average RMSE vs. number of sample points for graphs sampled [PITH_FULL_IMAGE:figures/full_fig_p026_9.png] view at source ↗
Figure 10
Figure 10. Figure 10: Left: Average RMSE on the approximation of the diffusion process over the Twitter [PITH_FULL_IMAGE:figures/full_fig_p027_10.png] view at source ↗
read the original abstract

Diffusion kernels over graphs have been widely utilized as effective tools in various applications due to their ability to accurately model the flow of information through nodes and edges. However, there is a notable gap in the literature regarding the development of surrogate models for diffusion processes on graphs. In this work, we fill this gap by proposing sparse polynomial-based surrogate models for parametric diffusion equations on graphs with community structure. In tandem, we provide convergence guarantees for both least squares and compressed sensing-based approximations by showing the holomorphic regularity of parametric solutions to these diffusion equations. Our theoretical findings are accompanied by a series of numerical experiments conducted on both synthetic and real-world graphs that demonstrate the applicability of our methodology.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper proposes sparse polynomial surrogate models for parametric diffusion equations on graphs with community structure. It claims convergence guarantees for both least-squares and compressed-sensing approximations by establishing holomorphic regularity of the parametric solution map, and includes numerical experiments on synthetic and real-world graphs to illustrate the approach.

Significance. If the holomorphic regularity result holds with a radius of analyticity sufficient to support the stated rates, the work supplies a new class of theoretically justified surrogates for a class of graph-based parametric PDEs. This could be useful for uncertainty quantification and reduced-order modeling in network diffusion problems. The combination of analytic arguments with numerical validation on both synthetic and real data is a positive feature.

major comments (2)
  1. [theoretical section on holomorphic regularity] The proof of holomorphic regularity (the load-bearing step for both approximation schemes) must explicitly control the location of singularities induced by the community structure in the graph Laplacian; without a concrete lower bound on the radius of holomorphy in the complex parameter plane, the a-priori error estimates invoked for least-squares and compressed-sensing recovery do not necessarily apply at the claimed rates.
  2. [convergence guarantees] The convergence statements for the two approximation methods rely on the same holomorphic-regularity hypothesis; if the radius is smaller than assumed for graphs with community structure, both the least-squares and compressed-sensing error bounds fail simultaneously, undermining the central claim that the surrogates are provably convergent for the stated graph class.
minor comments (2)
  1. [abstract] The abstract asserts convergence via holomorphic regularity but supplies no derivation outline or explicit error bounds; the main text should include a short roadmap (e.g., “see §3.2, Theorem 3.4”) so readers can locate the key analytic step.
  2. [numerical experiments] Numerical experiments should report the precise parameter domains, community sizes, and observed convergence rates (with tables or figures) so that the claimed rates can be directly compared to the theoretical predictions.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their thorough review and valuable feedback on our manuscript. We address each of the major comments below, focusing on the holomorphic regularity and its implications for the convergence guarantees.

read point-by-point responses

  1. Referee: [theoretical section on holomorphic regularity] The proof of holomorphic regularity (the load-bearing step for both approximation schemes) must explicitly control the location of singularities induced by the community structure in the graph Laplacian; without a concrete lower bound on the radius of holomorphy in the complex parameter plane, the a-priori error estimates invoked for least-squares and compressed-sensing recovery do not necessarily apply at the claimed rates.

    Authors: We acknowledge that the current presentation of the holomorphic regularity result would benefit from a more explicit treatment of the singularities arising from the community structure. The proof in Section 3 establishes that the solution map is holomorphic in a region whose size is determined by the distance to the nearest singularity in the complex plane, which is controlled by the eigenvalues of the graph Laplacian. To strengthen this, we will revise the manuscript to include a proposition that provides a concrete lower bound on the radius of holomorphy in terms of the minimal intra-community connectivity and the community size parameters. This will ensure the a-priori estimates apply with explicit constants. revision: yes

  2. Referee: [convergence guarantees] The convergence statements for the two approximation methods rely on the same holomorphic-regularity hypothesis; if the radius is smaller than assumed for graphs with community structure, both the least-squares and compressed-sensing error bounds fail simultaneously, undermining the central claim that the surrogates are provably convergent for the stated graph class.

    Authors: The referee correctly notes the dependence of both approximation schemes on the holomorphic regularity. However, since the regularity holds for any fixed graph with community structure (as the Laplacian is finite-dimensional and the parameter dependence is affine), the radius is positive, and the convergence rates hold, albeit with constants that may depend on the specific graph. The revision mentioned above will make this dependence explicit, thereby supporting the claimed rates for the class of graphs under consideration. We do not see this as undermining the central claim, as the theoretical results are valid once the radius is quantified. revision: yes

Circularity Check

0 steps flagged

No circularity: holomorphic regularity established independently from model equations

full rationale

The paper's core contribution is the construction of sparse polynomial surrogates together with a-priori convergence rates that rest on a separate analytic proof of holomorphic regularity of the solution map u(·,z) with respect to the diffusion parameters. No equation or claim in the provided text reduces a 'prediction' or error bound to a quantity that is defined by the same surrogate or fitted from the same data; the regularity statement is presented as a first-principles property of the parametric PDE on the given graph class. Self-citations, if present, are not load-bearing for the central derivation. This is the normal, non-circular case.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim depends on the existence and usability of holomorphic regularity for the parametric graph-diffusion solutions; this property is asserted to be shown rather than postulated, but its verification details are absent from the abstract.

axioms (1)
  • domain assumption Parametric solutions to the diffusion equations exhibit holomorphic regularity sufficient for polynomial approximation theory to apply
    Invoked to obtain convergence guarantees for least-squares and compressed-sensing surrogates; location is the theoretical component described in the abstract.

pith-pipeline@v0.9.0 · 5645 in / 1296 out tokens · 30917 ms · 2026-05-23T03:36:38.579012+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

44 extracted references · 44 canonical work pages

  1. [1]

    Adcock, S

    B. Adcock, S. Brugiapaglia, C. Webster, Sparse Polynomial Approximation of High-Dimensional Functions, SIAM, 2022

    work page 2022

  2. [2]

    Cohen, R

    A. Cohen, R. DeVore, Approximation of high-dimensional parametric PDEs, Acta Numerica 24 (2015) 1–159. 26

    work page 2015

  3. [3]

    R. C. Smith, Uncertainty Quantification: Theory, Implementation, and Appli- cations, SIAM, 2024

    work page 2024

  4. [4]

    Lüthen, S

    N. Lüthen, S. Marelli, B. Sudret, Sparse polynomial chaos expansions: Litera- ture survey and benchmark, SIAM/ASA Journal on Uncertainty Quantification 9 (2) (2021) 593–649

    work page 2021

  5. [5]

    Cohen, R

    A. Cohen, R. DeVore, C. Schwab, Analytic regularity and polynomial approxi- mation of parametric and stochastic elliptic PDE’s, Analysis and Applications 9 (01) (2011) 11–47

    work page 2011

  6. [6]

    R. I. Kondor, J. Lafferty, Diffusion kernels on graphs and other discrete struc- tures, in: Proceedings of the 19th International Conference on Machine Learn- ing, Vol. 2002, 2002, pp. 315–322

    work page 2002

  7. [7]

    Calder, N

    J. Calder, N. Garcí Trillos, M. Lewicka, Lipschitz regularity of graph Laplacians on random data clouds, SIAM Journal on Mathematical Analysis 54 (1) (2022) 1169–1222

    work page 2022

  8. [8]

    R. R. Coifman, S. Lafon, Diffusion maps, Applied and computational harmonic analysis 21 (1) (2006) 5–30

    work page 2006

  9. [9]

    García Trillos, M

    N. García Trillos, M. Gerlach, M. Hein, D. Slepčev, Error estimates for spectral convergence of the graph Laplacian on random geometric graphs toward the Laplace–Beltrami operator, Foundations of Computational Mathematics 20 (4) (2020) 827–887

    work page 2020

  10. [10]

    Belkin, P

    M. Belkin, P. Niyogi, Laplacian eigenmaps for dimensionality reduction and data representation, Neural Computation 15 (6) (2003) 1373–1396

    work page 2003

  11. [11]

    R. R. Coifman, S. Lafon, A. B. Lee, M. Maggioni, B. Nadler, F. Warner, S. W. Zucker, Geometric diffusions as a tool for harmonic analysis and structure defi- nition of data: Diffusion maps, Proceedings of the National Academy of Sciences 102 (21) (2005) 7426–7431

    work page 2005

  12. [12]

    A. J. Smola, R. Kondor, Kernels and regularization on graphs, in: Learning Theory and Kernel Machines: 16th Annual Conference on Learning Theory and 7th Kernel Workshop, Springer, 2003, pp. 144–158

    work page 2003

  13. [13]

    X. Dong, D. Thanou, M. Rabbat, P. Frossard, Learning graphs from data: A sig- nal representation perspective, IEEE Signal Processing Magazine 36 (3) (2019) 44–63. 27

    work page 2019

  14. [14]

    H. Ma, H. Yang, M. R. Lyu, I. King, Mining social networks using heat diffusion processes for marketing candidates selection, in: Proceedings of the 17th ACM Conference on Information and Knowledge Management, 2008, pp. 233–242

    work page 2008

  15. [15]

    M. G. Rodriguez, J. Leskovec, D. Balduzzi, B. Schölkopf, Uncovering the struc- ture and temporal dynamics of information propagation, Network Science 2 (1) (2014) 26–65

    work page 2014

  16. [16]

    Gomez-Rodriguez, J

    M. Gomez-Rodriguez, J. Leskovec, A. Krause, Inferring networks of diffusion and influence, ACM Transactions on Knowledge Discovery from Data (TKDD) 5 (4) (2012) 1–37

    work page 2012

  17. [17]

    Groendyke, D

    C. Groendyke, D. Welch, D. R. Hunter, Bayesian inference for contact networks given epidemic data, Scandinavian Journal of Statistics 38 (3) (2011) 600–616

    work page 2011

  18. [18]

    Gasteiger, S

    J. Gasteiger, S. Weißenberger, S. Günnemann, Diffusion improves graph learn- ing, Advances in Neural Information Processing Systems 32 (2019)

    work page 2019

  19. [19]

    Chamberlain, J

    B. Chamberlain, J. Rowbottom, M. I. Gorinova, M. Bronstein, S. Webb, E. Rossi, Grand: Graph neural diffusion, in: International Conference on Ma- chine Learning, PMLR, 2021, pp. 1407–1418

    work page 2021

  20. [20]

    Di Giovanni, J

    F. Di Giovanni, J. Rowbottom, B. P. Chamberlain, T. Markovich, M. M. Bron- stein, Understanding convolution on graphs via energies, Transactions on Ma- chine Learning Research

    work page

  21. [21]

    P. W. Holland, K. B. Laskey, S. Leinhardt, Stochastic blockmodels: First steps, Social Networks 5 (2) (1983) 109–137

    work page 1983

  22. [22]

    M. E. J. Newman, Networks: An Introduction, Oxford University Press, Oxford; New York, 2010

    work page 2010

  23. [23]

    Walter, Ordinary Differential Equations, Graduate Texts in Mathematics, Springer New York, 1998

    W. Walter, Ordinary Differential Equations, Graduate Texts in Mathematics, Springer New York, 1998

    work page 1998

  24. [24]

    Foucart, H

    S. Foucart, H. Rauhut, A Mathematical Introduction to Compressive Sensing, Springer, 2013

    work page 2013

  25. [25]

    Adcock, A

    B. Adcock, A. Bao, S. Brugiapaglia, Correcting for unknown errors in sparse high-dimensional function approximation, Numerische Mathematik 142 (2019) 667–711. 28

    work page 2019

  26. [26]

    Adcock, S

    B. Adcock, S. Brugiapaglia, Monte Carlo is a good sampling strategy for polyno- mial approximation in high dimensions, arXiv preprint arXiv:2208.09045 (2022)

    work page arXiv 2022

  27. [27]

    Henrici, Applied and Computational Complex Analysis, Volume 3: Discrete Fourier Analysis, Cauchy Integrals, Construction of Conformal Maps, Univalent Functions, Vol

    P. Henrici, Applied and Computational Complex Analysis, Volume 3: Discrete Fourier Analysis, Cauchy Integrals, Construction of Conformal Maps, Univalent Functions, Vol. 41, John Wiley & Sons, 1993

    work page 1993

  28. [28]

    R. A. Horn, C. R. Johnson, Matrix Analysis, 2nd Edition, Cambridge University Press, 2012

    work page 2012

  29. [29]

    T. H. Gronwall, Note on the derivatives with respect to a parameter of the solutions of a system of differential equations, Annals of Mathematics 20 (4) (1919) 292–296

    work page 1919

  30. [30]

    Hagberg, P

    A. Hagberg, P. Swart, S. Chult, Exploring network structure, dynamics, and function using NetworkX, Tech. rep., Los Alamos National Lab.(LANL), Los Alamos, NM (United States) (2008)

    work page 2008

  31. [31]

    Seshadri, G

    P. Seshadri, G. Parks, Effective-Quadratures (EQ): Polynomials for Computa- tional Engineering Studies., Journal of Open Source Software 2 (11) (2017) 166

    work page 2017

  32. [32]

    Parés, D

    F. Parés, D. G. Gasulla, A. Vilalta, J. Moreno, E. Ayguadé, J. Labarta, U.Cortés, T.Suzumura, Fluidcommunities: Acompetitive, scalableanddiverse community detection algorithm, in: Complex Networks & Their Applications VI: Proceedings of Complex Networks 2017, Springer, 2018, pp. 229–240

    work page 2017

  33. [33]

    C. G. Fink, N. Omodt, S. Zinnecker, G. Sprint, A Congressional Twitter network dataset quantifying pairwise probability of influence, Data in Brief (2023)

    work page 2023

  34. [34]

    Leskovec, A

    J. Leskovec, A. Krevl, SNAP Datasets: Stanfords Large Network Dataset Col- lection,http://snap.stanford.edu/data(Jun. 2014)

    work page 2014

  35. [35]

    Leskovec, J

    J. Leskovec, J. Mcauley, Learning to discover social circles in ego networks, Advances in neural information processing systems 25 (2012)

    work page 2012

  36. [36]

    F. A. Rodrigues, T. K. D. Peron, P. Ji, J. Kurths, The Kuramoto model in complex networks, Physics Reports 610 (2016) 1–98

    work page 2016

  37. [37]

    Adcock, S

    B. Adcock, S. Brugiapaglia, N. Dexter, S. Moraga, Deep Neural Networks Are EffectiveAtLearningHigh-DimensionalHilbert-ValuedFunctionsFromLimited Data, Vol. 145 of Proceedings of Machine Learning Research, 2022, pp. 1–36. 29

    work page 2022

  38. [38]

    Adcock, S

    B. Adcock, S. Brugiapaglia, N. Dexter, S. Moraga, Near-optimal learning of Banach-valued, high-dimensional functions via deep neural networks, Neural Networks 181 (2025) 106761

    work page 2025

  39. [39]

    Scarselli, M

    F. Scarselli, M. Gori, A. C. Tsoi, M. Hagenbuchner, G. Monfardini, The graph neural network model, IEEE Transactions on Neural Networks 20 (1) (2008) 61–80

    work page 2008

  40. [40]

    T. N. Kipf, M. Welling, Semi-Supervised Classification with Graph Convo- lutional Networks, in: International Conference on Learning Representations, 2022

    work page 2022

  41. [41]

    Chamberlain, J

    B. Chamberlain, J. Rowbottom, D. Eynard, F. Di Giovanni, X. Dong, M. Bron- stein, Beltrami flow and neural diffusion on graphs, Advances in Neural Infor- mation Processing Systems 34 (2021) 1594–1609

    work page 2021

  42. [42]

    Topping, F

    J. Topping, F. Di Giovanni, B. P. Chamberlain, X. Dong, M. M. Bronstein, Understanding over-squashing and bottlenecks on graphs via curvature, in: In- ternational Conference on Learning Representations

    work page

  43. [43]

    Gilmer, S

    J. Gilmer, S. S. Schoenholz, P. F. Riley, O. Vinyals, G. E. Dahl, Neural mes- sage passing for quantum chemistry, in: International Conference on Machine Learning, PMLR, 2017, pp. 1263–1272. Appendix A. Supplementary information about multi-index sets Consider the setup of Section 2. When noa prioriassumption is given on the multi- index setS,a possible s...

    work page 2017

  44. [44]

    Definition 4(Lower sets).A multi-index setΛ⊆N d 0 islowerif the following holds for everyν,µ∈N d 0:(ν∈Λandµ≤ν) =⇒µ∈Λ,where the inequality is understood componentwise

    Therefore, we need to consider setsSwith additional structure to ensure that we obtain a finite set. Definition 4(Lower sets).A multi-index setΛ⊆N d 0 islowerif the following holds for everyν,µ∈N d 0:(ν∈Λandµ≤ν) =⇒µ∈Λ,where the inequality is understood componentwise. Intuitively, lower sets do not have any “holes”. Note that the sets illustrated in Figure...

    work page