Graph Spectral Series and Its Signatures

A. Graph Fourier transform and signal spectrum

• The GFT maps a graph signal to an ordered sequence of frequency coefficients, which the paper treats as a time-ordered sequence.Source: §I · p. 1, A. Graph Fourier transform and signal… · p. 2

I. INTRODUCTION

• Non-bandlimited spectra can have rough local fluctuations, motivating path signatures that aggregate information along the frequency-ordered spectrum.Source: §I · p. 2
• For signed spectra in a fixed GFT basis, the framework establishes recoverability up to a stated ambiguity and linear approximation on suitable compact signal sets.Source: §I · p. 2
• The paper provides convergence results for graph spectral series along sequences of expanding graphs, supporting their interpretation as time series.Source: §I · p. 2
• Signature features improve performance over original graph signals on real-world trend-prediction and change-point-detection tasks.Source: §I · p. 2

B. Signature of time series

• A signature represents a time series through iterated path integrals, with low-order terms encoding global geometric information such as Levy area.Source: B. Signature of time series · pp. 2–3

• The section introduces graph spectral series and the use of signatures to analyze graph signals through this representation.Source: §III · p. 3

A. Graph spectral series and its signature

• A graph spectral series interpolates the ordered GFT coefficients on [0, 1], and its signature represents the resulting path as a graph-signal feature.The construction may use signed or absolute coefficients; the absolute version is invariant to eigenvector sign choices when comparing signals across graphs.Source: A. Graph spectral series and its… · pp. 3–4
• Appending the identity function as a time component makes the signature more informative than the one-channel signature alone.For one channel without this augmentation, the signature consists only of powers of the endpoint difference.Source: A. Graph spectral series and its… · p. 4

B. Characterizing signals and graphs

• For fixed GFT bases, signatures leave at most one other unit-norm signal with the same signature, while n independent probes leave finitely many possible GFTs.The results support using signatures to characterize either normalized signals or a chosen Fourier basis, up to the stated ambiguities.Source: B. Characterizing signals and graphs · pp. 4–5
• With strongly consistent interpolation, finite signature features vary continuously with the input, and on suitable compact sets their linear functions uniformly approximate any continuous real-valued feature map.The compact-set condition excludes distinct inputs whose Fourier transforms differ only by channel-wise additive constants.Source: B. Characterizing signals and graphs · pp. 4–5
• A signature-based classifier using node features reaches 87.2% test accuracy on MUTAG and 73.8% on PROTEIN, comparable to the reported WL-kernel results.The WL subtree kernel scores 85.6% and 72.5%, and the WL graph kernel scores 86.9% and 74.3%, respectively.Source: B. Characterizing signals and graphs · p. 5
• The paper interprets graph spectral series for expanding graphs through a random-expansion setup, providing a time-series perspective for its theoretical development.The section presents this as a conceptual foundation for the framework.Source: B. Characterizing signals and graphs · p. 5

A. The intuitive picture: random expanding graphs

• At each step, the subgraph grows by adding a randomly chosen neighbor from the ambient graph.The process begins from a single seed node.Source: A. The intuitive picture: random… · p. 5, Figure 4 · p. 5
• Restricted signals on successive subgraphs agree on existing nodes, so each new signal can be viewed as extending the prior time series by one component.This consistency applies to the signals themselves, not their GFTs.Source: A. The intuitive picture: random… · p. 5
• The restricted signal alone carries no graph information, while successive GFTs can differ across all components, so the paper studies their convergence as graph size grows.Source: A. The intuitive picture: random… · p. 5

B. The analytical framework

• The framework studies convergence of f_n, formed by interpolating partitioned, normalized absolute GFT coefficients across a sequence of expanding graphs.The setup seeks conditions under which the absolute spectral series converges as n grows.Source: B. The analytical framework · p. 5
• Regular and consistent interpolation controls continuity through endpoint values, with linear interpolation satisfying both properties.Regularity bounds interpolation behavior across intervals; consistency requires dependence on relative position within an interval.Source: B. The analytical framework · p. 6
• The partition conditions prevent asymptotically trivial intervals and require a finite initial block to carry nearly all interval length.Index-wise convergence additionally requires each interval length to have a limit.Source: B. The analytical framework · p. 6
• In the random expansion model, each graph grows by adding a uniformly chosen node from the finite outer boundary of an infinite, locally finite graph.The resulting construction warrants subsequential convergence; scaling γ_n is used to prevent the restricted signal from growing without bound.Source: B. The analytical framework · p. 6
• The graphon sampling model draws nested graphs from a bounded symmetric graphon and, under negative spectral separation and other stated conditions, supports stronger uniform convergence.The stated spectral separation condition is sufficient, not necessary, for convergence in general.Source: B. The analytical framework · p. 6

C. The convergence theorems

• Under a norm bound, non-vanishing partitions, diminishing tails, and regular interpolation, a subsequence of spectral series converges uniformly on every [0,t], t < 1, to a BV function.The result applies to any graph, shift-operator, and signal sequence satisfying the stated norm bound.Source: C. The convergence theorems · pp. 6–7
• In the graphon sampling model, the spectral series converges almost surely and uniformly on every [0,t], t < 1, under the stated assumptions.This is a stronger convergence result in a different scenario, not a theorem that subsumes the subsequential result.Source: C. The convergence theorems · p. 7
• For fixed t < 1 and truncation level η, the results also give convergence of signatures of normalized, time-augmented paths restricted to [0,t].Signature convergence follows from uniform convergence and uniform variation bounds, which imply p-variation convergence for 1 < p < 2.Source: C. The convergence theorems · p. 7

V. NUMERICAL RESULTS

• The numerical experiments use conventional graph-Laplacian shifts, uniform partitions, and linear interpolation rather than the strict asymptotic setup.The paper notes that this is a finite-regime evaluation.Source: §V · p. 7

A. Trend prediction: Covid-19 dataset

• LightGBM and XGBoost reach about 96% accuracy at η = 9, 10, while linear classifiers achieve reasonable performance around η ≈ 5 with limited gains from increasing η.Accuracy generally increases with signature length across classifiers.Source: A. Trend prediction: Covid-19 dataset · p. 8, Figure 6 · p. 8
• LinearSVM exceeds 85% accuracy at η = 5 with 63 parameters, and LinearSVM and LogisticElasticNet outperform the higher-parameter MLP.The reported comparison aligns with the paper's universal linear-approximation result.Source: A. Trend prediction: Covid-19 dataset · p. 8, Table III · p. 8
• On expanding subgraphs, LinearSVM and LightGBM performance quickly stabilizes, with stabilization faster for the linear model.The evaluation uses 30 random seeds and does not require the physical meaning, location, or date of each node to be known.Source: A. Trend prediction: Covid-19 dataset · p. 8, Figure 7 · p. 8

B. Change detection: the ECoG dataset

• The ECoG experiments compare signature features with original signals and graph wavelet and scattering features using kernel-based detection methods.The dataset comprises recordings from 76 electrodes across five epilepsy patients.Source: B. Change detection: the ECoG dataset · pp. 8–9
• For online change detection, signature features outperform the baselines overall; for offline detection, they yield reasonably good results while baselines have very low detection rates.The method is generally strong at detecting the first transition from pre-ictal to ictal conditions, though outliers can produce large second-change-point errors.Source: B. Change detection: the ECoG dataset · p. 9, Table IV · p. 9, Table V · p. 9
• The online change-detection runtime averages 1.47 ms per detection across patients with the small truncation length η.The authors describe this runtime as viable for time-critical online detection.Source: B. Change detection: the ECoG dataset · p. 9
• Across both studies, the authors report reasonable performance for small η and conclude that short signatures encode many useful global signal characterizations.The ECoG experiment uses η = 3 for its change-detection features.Source: B. Change detection: the ECoG dataset · pp. 8–9

VI. CONCLUSIONS

• Graph spectral series use path signatures to represent the global spectral structure of graph signals not well described by bandlimited models.The paper establishes theoretical properties supporting this construction.Source: §VI · p. 9
• Experiments on real-world trend-prediction and change-detection tasks demonstrate the practical value of the resulting features.The conclusion positions graph spectral series as a principled representation for analyzing non-bandlimited graph signals.Source: §VI · p. 10
• The paper establishes an initial connection between graph signal processing and signature methods, but fully exploiting signature theory requires further development.The discussion describes its treatment as focused on foundational aspects.Source: §VI · p. 10
• Characterizing the optimal sorting or permutation ordering of GFT components remains an open challenge.Including graph shift operator eigenvalues in the spectral series could yield richer geometric representations.Source: §VI · p. 10
• The framework’s convergence results are an initial step; future work could extend the construction to the high-index spectral tail near 1 and investigate unique limits and relaxed spectral-separation assumptions.The paper also identifies robust inverse algorithms for reconstructing graph signals from signature features as an important future direction.Source: §VI · p. 10

Proof of Theorem 1

• For unit-norm signals in a fixed GFT basis, equal signatures allow at most one other coefficient vector, so the signal is recoverable up to the stated ambiguity.The proof uses translation invariance of signatures and the intersection of a line with the unit sphere.Source: Appendix A · p. 10
• Only finitely many orthogonal GFT matrices can yield the same signature for a basis of signals.For each basis signal, the proof obtains at most two possibilities for its transformed vector; the resulting ordered collections determine the matrix.Source: Appendix A · p. 10

Proof of Theorem 2

• The map from signals to interpolated paths is continuous in the bounded-variation norm, using continuity of the truncated signature and the GFT interpolation.The proof reduces continuity to that of the interpolation as a function of its coefficient vector.Source: Appendix A · p. 10
• On the specified compact set, the time-augmented path map is continuous and injective, and preserves the signature of the original path.Compactness then supports approximation of continuous functions on the path image by functions of truncated signatures.Source: Appendix A · pp. 10–11

Proof of Theorem 3

• Uniform boundedness and equicontinuity on [0, t] yield a uniformly convergent subsequence whose limit has bounded variation.The proof applies Arzelà–Ascoli and passes the variation bound to the limit.Source: Appendix B · p. 11
• For each fixed t in (0, 1), finitely many interpolation intervals cover [0, t], with their lengths bounded away from zero for the relevant indices.The proof states these bounds hold for the full sequence, without requiring a subsequence of interval lengths.Source: Appendix B · p. 11

Proof of Theorem 4

• For expanding graphs, graphon convergence and convergence of isolated eigenfunctions support convergence of the corresponding spectral coefficients.The proof orders vertices by latent sample points and uses the strong law and spectral separation assumptions.Source: Appendix B · pp. 11–12
• The interpolated functions converge uniformly on [0, t], and the limit has variation at most Kt g(2M).The proof combines pointwise convergence, uniform equicontinuity, and passage to the limit in finite variation sums.Source: Appendix B · p. 12
• The convergence argument extends from continuous signals to L2 signals through continuous approximations and convergence of their sorted step embeddings.The proof concludes that the sorted embeddings converge in L2 almost surely.Source: Appendix B · p. 12