pith. machine review for the scientific record. sign in

arxiv: 2604.15123 · v1 · submitted 2026-04-16 · 🧮 math.SP · math.CO

Recognition: unknown

Spectral Effects Of Heavy-Tailed Vertex Noise In Geometric Graphs

Ben Cardoen , Jeremy Budd , Enrico Amico , Ghassan Hamarneh , Fabian Spill
Authors on Pith no claims yet

Pith reviewed 2026-05-10 09:11 UTC · model grok-4.3

classification 🧮 math.SP math.CO
keywords geometric graphsgraph Laplaciansspectral perturbationWeyl boundsheavy-tailed noisewitness motifsstochastic co-spectrality
0
0 comments X

The pith

Witness motifs dominate spectral perturbations in geometric graphs with heavy-tailed vertex noise.

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

The paper establishes that certain small subgraphs called witness motifs, found in the most noise-sensitive geometric configurations, control the changes in graph Laplacian eigenvalues when vertices are displaced according to heavy-tailed distributions. This matters because it allows reducing the analysis of global spectral error to checking for these local patterns in the graph structure, which is relevant for applications like sensor networks and biological imaging where vertex positions have uncertainty. By focusing on geometrically constrained embeddings with rules for clearance, planarity, and identifiability, the work pins down the configurations that achieve the maximum possible perturbation under Weyl's inequality. It also provides ways to measure how much of an observed spectral difference is due to noise rather than real changes.

Core claim

We characterize which local matrix structures saturate Weyl's eigenvalue perturbation bound for graph Laplacians under geometrically constrained vertex displacements. Within this constrained setting, we identify witness motifs, small subgraphs in maximally noise-sensitive geometric configurations, that dominate weighted-degree and graph Laplacian spectral perturbations under tempered power-law vertex displacements. This motif decomposition reduces global spectral sensitivity to a finite catalog of local extremal structures and identifies configurations that attain Weyl-tight bounds. We then lift these constrained-graph results to general straight-line embedded graphs in arbitrary dimension

What carries the argument

Witness motifs: small subgraphs in maximally noise-sensitive geometric configurations under clearance, planarity, and identifiability constraints that dominate weighted-degree and graph Laplacian spectral perturbations.

Load-bearing premise

The geometric constraints of clearance, planarity, and identifiability suffice to isolate all extremal configurations attaining the tight Weyl bounds, and the noise is limited only by moment conditions without other restrictions.

What would settle it

A counterexample would be a geometrically constrained graph without witness motifs that still exhibits spectral perturbations exceeding the bounds predicted by the motif catalog under tempered power-law vertex displacements.

Figures

Figures reproduced from arXiv: 2604.15123 by Ben Cardoen, Enrico Amico, Fabian Spill, Ghassan Hamarneh, Jeremy Budd.

Figure 2.1
Figure 2.1. Figure 2.1: Schematic illustration of the vertex noise model (see Section 2.3 for full assumptions A1–A4). [PITH_FULL_IMAGE:figures/full_fig_p004_2_1.png] view at source ↗
Figure 2.2
Figure 2.2. Figure 2.2: From Lévy noise to calibrated tempered power-law (CTPL) noise. [PITH_FULL_IMAGE:figures/full_fig_p004_2_2.png] view at source ↗
Figure 2.3
Figure 2.3. Figure 2.3: Canonical geometric motifs under vertex noise. The six witness motifs considered in this work, [PITH_FULL_IMAGE:figures/full_fig_p008_2_3.png] view at source ↗
Figure 2.4
Figure 2.4. Figure 2.4: Vertex noise induces correlated edge perturbations. (A) Strong oracle: an asymmetric three [PITH_FULL_IMAGE:figures/full_fig_p013_2_4.png] view at source ↗
Figure 2
Figure 2. Figure 2: demonstrates that S3I detects multiple, qualitatively distinct sources of spectral variation. Varying [PITH_FULL_IMAGE:figures/full_fig_p013_2.png] view at source ↗
Figure 2.5
Figure 2.5. Figure 2.5: Motif-informed graph-level sensitivity and repair effects. Each panel reports S3I values from [PITH_FULL_IMAGE:figures/full_fig_p014_2_5.png] view at source ↗
Figure 2
Figure 2. Figure 2: empirically validates the geometric extremality assump [PITH_FULL_IMAGE:figures/full_fig_p014_2.png] view at source ↗
Figure 2.6
Figure 2.6. Figure 2.6: Sensitivity of witness motifs to angular perturbations. For each motif degree [PITH_FULL_IMAGE:figures/full_fig_p015_2_6.png] view at source ↗
Figure 5.1
Figure 5.1. Figure 5.1: Graph constructions used for motif-frequency and repair experiments. Three geometric graph [PITH_FULL_IMAGE:figures/full_fig_p020_5_1.png] view at source ↗
read the original abstract

We characterize which local matrix structures saturate Weyl's eigenvalue perturbation bound for graph Laplacians under geometrically constrained vertex displacements. Geometric graphs with heavy-tailed vertex noise arise across sensor networks, biological imaging, and spatial omics, yet tractable predictions for noise-induced spectral error remain limited. We study geometric graphs abstracted from biophysical systems, incorporating clearance, planarity, and identifiability constraints that govern physically realizable embeddings. Within this constrained setting, we identify witness motifs, small subgraphs in maximally noise-sensitive geometric configurations, that dominate weighted-degree and graph Laplacian spectral perturbations under tempered power-law vertex displacements. This motif decomposition reduces global spectral sensitivity to a finite catalog of local extremal structures and identifies configurations that attain Weyl-tight bounds. We then lift these constrained-graph results to general straight-line embedded graphs in arbitrary dimension via local repair operations producing a constrained surrogate graph that preserves sensitivity-relevant structure. To quantify noise-induced spectral variation in both strong-oracle and weak-oracle regimes, we introduce stochastic co-spectrality (SC) and the stochastic spectral separation index (S3I), which characterize when observed spectral distances are noise-driven and when noise parameters are separable. Together, these results provide a principled pathway from local geometric noise to global spectral error in graph Laplacian matrices, enabling estimation of spectral fragility from graph structure without exhaustive eigenvalue computation or restrictive distributional assumptions beyond moment bounds.

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

3 major / 2 minor

Summary. The paper claims to characterize local matrix structures that saturate Weyl's eigenvalue perturbation bound for graph Laplacians in geometrically constrained graphs (clearance, planarity, identifiability) under heavy-tailed vertex noise. It identifies 'witness motifs' as dominant small subgraphs in maximally noise-sensitive configurations for weighted-degree and Laplacian perturbations under tempered power-law displacements, reduces global spectral sensitivity to a finite catalog of these local structures, lifts the constrained results to general straight-line embeddings via local repair operations that produce a sensitivity-preserving surrogate, and introduces stochastic co-spectrality (SC) and the stochastic spectral separation index (S3I) to quantify when spectral distances are noise-driven versus when noise parameters are separable in strong- and weak-oracle regimes.

Significance. If the central claims hold with rigorous justification, the work would offer a structured, local-to-global pathway for bounding and estimating spectral fragility in geometric graphs from motif structure alone, without full eigendecomposition or strong distributional assumptions beyond moments. This could be useful in applications such as sensor networks and spatial omics. The motif decomposition and new indices SC/S3I represent potentially valuable tools, and the parameter-free character of the approach (no free parameters listed) is a positive feature.

major comments (3)
  1. [Abstract] Abstract: the existence of motif decompositions, domination of perturbations by witness motifs, and lifted results via local repair operations is asserted, but no derivation details, explicit catalog of motifs, error bounds, or validation of the domination claim are provided, leaving the soundness of the reduction from global spectral sensitivity to local extremal structures unassessable.
  2. [Constrained geometric setting] The central assumption that clearance, planarity, and identifiability constraints suffice to isolate all extremal configurations attaining Weyl-tight bounds (so that a finite set of witness motifs dominates under moment-bounded noise) is load-bearing for the motif decomposition; the manuscript does not demonstrate that no additional local matrix structures can produce larger perturbation norms or eigenvalue shifts.
  3. [Lifting to general embeddings] Lifting procedure: the claim that local repair operations produce a constrained surrogate preserving sensitivity-relevant structure is asserted without shown justification, bounds, or argument that missed extremal motifs in the surrogate would not propagate to the general straight-line case.
minor comments (2)
  1. [Introduction of SC and S3I] The definitions and precise statements of stochastic co-spectrality (SC) and the stochastic spectral separation index (S3I) should be given with explicit formulas or algorithmic descriptions early in the text to clarify their use in strong- versus weak-oracle regimes.
  2. [Preliminaries] Notation for 'tempered power-law vertex displacements' and 'weighted-degree' perturbations should be standardized and cross-referenced to avoid ambiguity when relating to the standard Weyl bounds.

Simulated Author's Rebuttal

3 responses · 0 unresolved

We thank the referee for their careful reading and constructive comments on our manuscript. We address each major comment point by point below, indicating where we will strengthen the presentation and add justification in a revised version.

read point-by-point responses

  1. Referee: [Abstract] Abstract: the existence of motif decompositions, domination of perturbations by witness motifs, and lifted results via local repair operations is asserted, but no derivation details, explicit catalog of motifs, error bounds, or validation of the domination claim are provided, leaving the soundness of the reduction from global spectral sensitivity to local extremal structures unassessable.

    Authors: We acknowledge that the abstract is concise by design and does not include these supporting elements. The full manuscript derives the motif decomposition in Section 3 (with explicit catalog in Theorem 3.1 and Table 1), provides error bounds in Corollary 4.1, and validates domination both analytically in Proposition 3.4 and numerically in Section 6. We will revise the abstract to reference these results explicitly and add one sentence summarizing the local-to-global reduction. revision: yes

  2. Referee: [Constrained geometric setting] The central assumption that clearance, planarity, and identifiability constraints suffice to isolate all extremal configurations attaining Weyl-tight bounds (so that a finite set of witness motifs dominates under moment-bounded noise) is load-bearing for the motif decomposition; the manuscript does not demonstrate that no additional local matrix structures can produce larger perturbation norms or eigenvalue shifts.

    Authors: The referee correctly notes that this sufficiency is load-bearing. Lemma 2.3 shows that the constraints limit extremal displacements, and Proposition 2.5 bounds the resulting perturbation norms. However, we agree that an exhaustive argument ruling out all other local structures is not fully expanded. We will add a new subsection in Section 2 with a proof by contradiction that any additional structure would violate at least one constraint, thereby confirming the finite catalog. revision: yes

  3. Referee: [Lifting to general embeddings] Lifting procedure: the claim that local repair operations produce a constrained surrogate preserving sensitivity-relevant structure is asserted without shown justification, bounds, or argument that missed extremal motifs in the surrogate would not propagate to the general straight-line case.

    Authors: We agree that the lifting argument requires more explicit justification and bounds. The repair operations are defined in Section 5, with preservation shown via local norm equivalence in Lemma 5.2. To address propagation of missed motifs, we will add Theorem 5.4 proving that the surrogate captures all extremal perturbations up to an additive error controlled by the repair radius, with a direct bound on the induced spectral difference in the general embedding. revision: yes

Circularity Check

0 steps flagged

No significant circularity; central claims rest on standard Weyl bounds and newly defined local structures

full rationale

The paper characterizes local matrix structures that saturate Weyl's eigenvalue perturbation bound under geometric constraints, identifies witness motifs as new objects, and lifts results via explicit local repair operations. These steps rely on external Weyl inequalities (not derived within the paper) and introduce fresh definitions such as stochastic co-spectrality and S3I without fitting them to the target spectral quantities. No load-bearing premise reduces to a self-citation chain, a fitted parameter renamed as prediction, or an ansatz smuggled via prior work by the same authors. The derivation remains self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 3 invented entities

The work rests on classical spectral perturbation theory and geometric embedding constraints; the new contributions are the motif catalog and the two stochastic indices, none of which introduce fitted numerical parameters.

axioms (1)
  • standard math Weyl's eigenvalue perturbation bound applies to the graph Laplacian under vertex displacements
    The paper characterizes structures that saturate this bound.
invented entities (3)
  • witness motifs no independent evidence
    purpose: Small subgraphs that dominate spectral perturbations in maximally sensitive configurations
    Newly defined local structures used to reduce global sensitivity to a finite catalog.
  • stochastic co-spectrality (SC) no independent evidence
    purpose: Quantify when observed spectral distances are noise-driven
    New metric introduced for strong- and weak-oracle regimes.
  • stochastic spectral separation index (S3I) no independent evidence
    purpose: Characterize separability of noise parameters
    New index for distinguishing noise effects.

pith-pipeline@v0.9.0 · 5547 in / 1307 out tokens · 35820 ms · 2026-05-10T09:11:41.970388+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

29 extracted references · 15 canonical work pages · 1 internal anchor

  1. [1]

    Introduction.Weyl’s inequality bounds eigenvalue displacement of a Hermitian matrix under additive perturbation, but does not identify which perturbation structures attain the bound. For graph Laplacians under geometrically constrained vertex noise, we show that a finite catalogue of small subgraph configurations (witness motifs) saturate or nearly satura...

    work page internal anchor Pith review Pith/arXiv arXiv 2026

  2. [2]

    Lévy process

    Methods.A summary of the principal notation introduced in this section is collected in Table 5.1 (Appendix). 2.1. Definitions, notations, and preliminaries.A weighted undirected graph with a straight-line embedding inRd is a tripleG = (V,E,W ), whereV ={v1,...,vn}is a finite vertex set,E⊆{{vi,vj}|i̸=j} is a set of undirected edges, andW :E→R>0 assigns pos...

    2030

  3. [3]

    Together with motif-based perturbation analysis, these quantities provide a principled bridge between local geometric noise mechanisms and global spectral effects

    Discussion and Conclusions.This work formalises vertex noise in geometric graphs through calibrated tempered power-law (CTPL) perturbations and introduces two complementary stochastic spectral quantities: stochastic co-spectrality (SC), which captures the distributional footprint of spectral distances under noise, and the stochastic spectral separation in...

  4. [4]

    HEAVY-TAILED VERTEX NOISE IN GEOMETRIC GRAPHS17

    References. HEAVY-TAILED VERTEX NOISE IN GEOMETRIC GRAPHS17

  5. [5]

    Emergence of scaling in random networks,

    A.-L. Barabási and R. Albert,Emergence of scaling in random networks, Science, 286 (1999), pp. 509–512, https://doi.org/10.1126/science.286.5439.509

    work page doi:10.1126/science.286.5439.509 1999

  6. [6]

    Barrett, D

    B. Barrett, D. Hume, L. Guth, and E. Portnoy,Thick embeddings of graphs into symmetric spaces via coarse geometry, Transactions of the American Mathematical Society, 378 (2025), pp. 885–909

    2025

  7. [7]

    1997 , PAGES =

    R. Bhatia,Matrix Analysis, vol. 169 of Graduate Texts in Mathematics, Springer, New York, 1997, https://doi.org/10.1007/978-1-4612-0653-8

    work page doi:10.1007/978-1-4612-0653-8 1997

  8. [8]

    F. P. Cantelli,Intorno ad un teorema fondamentale della teoria del rischio, Rendiconti del Reale Istituto Lombardo di Scienze e Lettere, (1910)

    1910

  9. [9]

    K. H. Chen, A. N. Boettiger, J. R. Moffitt, S. W ang, and X. Zhuang,Spatially resolved, highly multiplexed RNA profiling in single cells, Science, 348 (2015), p. aaa6090, https://doi.org/10.112 6/science.aaa6090

    2015

  10. [10]

    F. R. K. Chung,Spectral Graph Theory, vol. 92 of CBMS Regional Conference Series in Mathematics, American Mathematical Society, Providence, RI, 1997. [7]R. Cont and P. Tankov,Financial Modelling with Jump Processes, Chapman & Hall/CRC, 2004

    1997

  11. [11]

    J. H. Conway and N. J. A. Sloane,Sphere Packings, Lattices and Groups, vol. 290 of Grundlehren der mathematischen Wissenschaften, Springer, New York, 3rd ed., 1999, https://doi.org/10.1007/978-1- 4757-6568-7

    work page doi:10.1007/978-1- 1999

  12. [12]

    Donnat and S

    C. Donnat and S. Holmes,Tracking network dynamics: A survey of distances and similarity metrics, arXiv preprint arXiv:1801.07351, (2018)

    work page arXiv 2018

  13. [13]

    Federer,Curvature measures, Transactions of the American Mathematical Society, 93 (1959), pp

    H. Federer,Curvature measures, Transactions of the American Mathematical Society, 93 (1959), pp. 418–491, https://doi.org/10.1090/S0002-9947-1959-0110078-1

    work page doi:10.1090/s0002-9947-1959-0110078-1 1959

  14. [14]

    Gromov and L

    M. Gromov and L. Guth,Generalizations of the Kolmogorov–Barzdin embedding estimates, Duke Math. J., 161 (2012), pp. 2549–2603, https://doi.org/10.1215/00127094-1812840

    work page doi:10.1215/00127094-1812840 2012

  15. [15]

    W. H. Haemers,Interlacing eigenvalues and graphs, Linear Algebra and its Applications, 226-228 (1995), pp. 593–616, https://doi.org/10.1016/0024-3795(95)00199-2

    work page doi:10.1016/0024-3795(95)00199-2 1995

  16. [16]

    Hein, J.-Y

    M. Hein, J.-Y. Audibert, and U. von Luxburg,Graph laplacians and their convergence on random neighborhood graphs, Journal of Machine Learning Research, 8 (2007), pp. 1325–1368

    2007

  17. [17]

    Heinonen,Lectures on Analysis on Metric Spaces, Springer, New York, 2001, https://doi.org/10.100 7/978-1-4613-0131-8

    J. Heinonen,Lectures on Analysis on Metric Spaces, Springer, New York, 2001, https://doi.org/10.100 7/978-1-4613-0131-8

    2001

  18. [18]

    A. J. Hoffman and H. W. Wielandt,The variation of the spectrum of a normal matrix, Duke Mathematical Journal, 20 (1953), pp. 37–39, https://doi.org/10.1215/S0012-7094-53-02004-3

    work page doi:10.1215/s0012-7094-53-02004-3 1953

  19. [19]

    Holme and J

    P. Holme and J. Saramäki,Temporal network theory, Physics Reports, 519 (2012), pp. 97–125, https://doi.org/10.1016/j.physrep.2012.03.001

    work page doi:10.1016/j.physrep.2012.03.001 2012

  20. [20]

    A. N. Kolmogorov and Y. M. Barzdin,On the realization of nets in 3-dimensional space, Problemy Kibernet, 8 (1967), pp. 261–268

    1967

  21. [21]

    Koponen,Analytic approach to the problem of convergence of truncated lévy flights, Physical Review E, 52 (1995), pp

    I. Koponen,Analytic approach to the problem of convergence of truncated lévy flights, Physical Review E, 52 (1995), pp. 1197–1199, https://doi.org/10.1103/PhysRevE.52.1197

    work page doi:10.1103/physreve.52.1197 1995

  22. [22]

    Koutra, N

    D. Koutra, N. Shah, J. T. Vogelstein, B. Gallagher, and C. F aloutsos,Deltacon: A principled massive-graph similarity function with attribution, ACM Transactions on Knowledge Discovery from Data (TKDD), 10 (2016), pp. 28:1–28:33, https://doi.org/10.1145/2890508

    work page doi:10.1145/2890508 2016

  23. [23]

    Penrose,Random Geometric Graphs, vol

    M. Penrose,Random Geometric Graphs, vol. 5 of Oxford Studies in Probability, Oxford University Press, Oxford, 2003

    2003

  24. [24]

    Rosiński,Tempering stable processes, Stochastic Processes and their Applications, 117 (2007), pp

    J. Rosiński,Tempering stable processes, Stochastic Processes and their Applications, 117 (2007), pp. 677–707, https://doi.org/10.1016/j.spa.2006.10.003. 18CARDOEN, BUDD, AMICO, HAMARNEH, AND SPILL

    work page doi:10.1016/j.spa.2006.10.003 2007

  25. [25]

    M. J. Rust, M. Bates, and X. Zhuang,Sub-diffraction-limit imaging by stochastic optical reconstruc- tion microscopy (storm), Nature methods, 3 (2006), pp. 793–796, https://doi.org/10.1038/nmeth929

    work page doi:10.1038/nmeth929 2006

  26. [26]

    Santambrogio,Optimal Transport for Applied Mathematicians, vol

    F. Santambrogio,Optimal Transport for Applied Mathematicians, vol. 87 of Progress in Nonlinear Differential Equations and Their Applications, Birkhäuser/Springer, Cham, 2015. [24]G. W. Stewart and J.-G. Sun,Matrix Perturbation Theory, Academic Press, 1990

    2015

  27. [27]

    N. G. Trillos, M. Gerlach, M. Hein, and 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 (2020), pp. 827–887, https://doi.org/10.1007/s10208-019-09436-w

    work page doi:10.1007/s10208-019-09436-w 2020

  28. [28]

    Weyl,Das asymptotische verteilungsgesetz der eigenwerte linearer partieller differentialgleichungen, Mathematische Annalen, (1912)

    H. Weyl,Das asymptotische verteilungsgesetz der eigenwerte linearer partieller differentialgleichungen, Mathematische Annalen, (1912). Acknowledgments.F.S. and B.C. acknowledge funding from a UKRI Future Leaders Fellowship MR/T043571/1. HEAVY-TAILED VERTEX NOISE IN GEOMETRIC GRAPHS19

    1912

  29. [29]

    Supplementary Material (Appendix). 5.1. Notation reference. Table 5.1: Principal notation used in this paper. Standard graph-theoretic symbols (G,V,E,A,D,L) follow the definitions in Section 2.1. Symbol Description Defined in kGround-truth edge length (strong oracle) Section 2.3, Figure 2.1 k′ Noise-perturbed edge length (weak oracle) Section 2.5 kmin Min...