pith. sign in

arxiv: 2606.00758 · v1 · pith:NE3LAM2Rnew · submitted 2026-05-30 · 📊 stat.ML · cs.LG· eess.SP· stat.ME

Statistical Testing on Directed Graphs by Surrogate Data Generation

Chun Hei Michael Chan , Alexandre Cionca , Dimitri Van De Ville This is my paper

Pith reviewed 2026-06-28 18:03 UTC · model grok-4.3

classification 📊 stat.ML cs.LGeess.SPstat.ME
keywords directed graphssurrogate datastatistical hypothesis testinggraph signal processingwide-sense stationaritycovariance preservationnon-parametric testing
0
0 comments X

The pith

Surrogate signals preserving covariance under directed-graph stationarity enable non-parametric hypothesis testing.

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

The paper extends surrogate-based statistical testing to signals defined on directed graphs. It first defines wide-sense stationarity for such signals through the eigendecomposition of the graph shift operator. A generation procedure then produces surrogate signals that retain the covariance structure implied by that stationarity. Null distributions for any chosen test metric can be built from the surrogates and compared with the statistic observed on real data. The resulting tests are shown to be feasible and to outperform both naive permutations and adaptations of undirected-graph methods.

Core claim

Through the eigendecomposition of the graph shift operator, directed graph wide-sense stationary signals are defined. A new framework then generates surrogate graph signals that preserve covariance structure under stationarity assumptions. Null distributions of the test metric are constructed from these surrogates and serve as a reference for the empirical data, providing a non-parametric approach to hypothesis testing on directed graphs.

What carries the argument

Surrogate generation framework for directed-graph wide-sense stationary signals, which preserves the covariance implied by the eigendecomposition of the graph shift operator so that null distributions can be built.

If this is right

  • Any test metric can be equipped with a non-parametric null distribution derived from the surrogates.
  • Testing becomes possible on directed graphs without requiring parametric distributional assumptions beyond stationarity.
  • The method outperforms both naive permutation baselines and direct application of undirected-graph surrogates on the same data.
  • Real directed-graph datasets can be analyzed by comparing observed statistics against the surrogate-derived reference distributions.

Where Pith is reading between the lines

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

  • The same surrogate construction could be applied to any test statistic that depends on second-order structure, not only those illustrated in the examples.
  • Domains whose natural graphs are directed, such as neural connectivity or citation networks, become candidates for the same style of non-parametric testing.
  • If the stationarity definition proves too restrictive in practice, the framework could be relaxed by replacing the shift-operator eigendecomposition with other graph operators while retaining the surrogate idea.

Load-bearing premise

Signals on the directed graph must obey the wide-sense stationarity definition obtained from the eigendecomposition of the graph shift operator.

What would settle it

If controlled simulations of stationary directed-graph signals produce surrogates whose empirical covariance matrices differ systematically from the true covariance, the preservation step fails.

Figures

Figures reproduced from arXiv: 2606.00758 by Alexandre Cionca, Chun Hei Michael Chan, Dimitri Van De Ville.

Figure 1
Figure 1. Figure 1: Examples of WN on directed graphs. (a) Bi-cycle graph indicating nodal variances associated with WN. (b) Covariance matrix associated with [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: (a) Set of nodes on the USA graph with irregular signal contributions. (b) Nodal statistical significance [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: (a) Set of irregular edges. (b,c) Detected pairs using directed-graph surrogates (red), undirected-graph surrogates (blue). Ground truth pairs in green [PITH_FULL_IMAGE:figures/full_fig_p006_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: (a) Nodal timecourses of graph diffusion for different nodes with the irregular node ( [PITH_FULL_IMAGE:figures/full_fig_p008_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: (a) Nodal timecourses of graph diffusion for a set of irregular nodes. (b) ROC curves for different sets [PITH_FULL_IMAGE:figures/full_fig_p008_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: (a) Number of days with significant temperature detected by directed-graph surrogates. (b) Number of days with significant temperature detected by [PITH_FULL_IMAGE:figures/full_fig_p010_6.png] view at source ↗
read the original abstract

In recent years, graph signal processing has emerged as a powerful framework at the intersection of signal processing and graph theory, providing tools for the analysis of signals defined on nodes while accounting for their relationships represented by edges. These tools have been successfully applied to various settings, including statistical hypothesis testing. In particular, non-parametric approaches based on surrogate generation have been proposed for signals on undirected graphs. However, they are yet to be extended to directed graphs. In this work, we first revisit the notion of stationary graph signals on directed graphs. Specifically, and through the eigendecomposition of the graph shift operator, we define directed graph wide-sense stationary signals. Then, we propose a new framework to generate surrogate graph signals that preserve covariance structure under stationarity assumptions. Null distributions of the test metric can then be constructed from these surrogates and serve as a reference for the empirical data. Finally, we provide guiding examples and an application on real data, in which we compare the performance of our framework with existing techniques for undirected graphs or based on naive permutation, demonstrating feasibility and superiority of the proposed approach.

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

1 major / 1 minor

Summary. The paper proposes a framework for statistical hypothesis testing on directed graphs via surrogate data generation. It first defines wide-sense stationarity for directed graph signals through the eigendecomposition of the graph shift operator, then constructs surrogates that preserve the covariance structure under this assumption to generate null distributions for test metrics, and illustrates the method with guiding examples plus a real-data application comparing performance to undirected-graph or naive-permutation baselines.

Significance. If the central construction is valid, the work fills a gap by extending non-parametric surrogate testing from undirected to directed graphs in the graph signal processing literature, with potential utility for applications involving asymmetric relationships. The real-data comparison provides some evidence of feasibility, though the absence of detailed quantitative validation metrics limits assessment of practical gains.

major comments (1)
  1. [stationarity definition and surrogate framework] The definition of directed-graph wide-sense stationarity (abstract; § on stationarity) is obtained via eigendecomposition of the graph shift operator. For a general directed graph the adjacency matrix need not be diagonalizable (non-symmetric matrices can possess Jordan blocks), so the Fourier basis does not exist and the stationarity notion, together with the covariance-preserving surrogate procedure, cannot be applied as stated. The manuscript must either restrict the scope to diagonalizable shift operators, supply an alternative (e.g., Jordan-form) construction, or demonstrate that the surrogate generation remains well-defined without a full eigenbasis.
minor comments (1)
  1. [abstract and results] The abstract states that examples and a real-data comparison are provided but supplies no quantitative performance metrics, error bars, or explicit verification that the surrogates match the claimed covariance structure; the full manuscript should include these in the results section.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the detailed and constructive comment on the diagonalizability assumption underlying our stationarity definition. We agree that the issue is substantive and will revise the manuscript to make the framework's scope and assumptions explicit.

read point-by-point responses

  1. Referee: The definition of directed-graph wide-sense stationarity (abstract; § on stationarity) is obtained via eigendecomposition of the graph shift operator. For a general directed graph the adjacency matrix need not be diagonalizable (non-symmetric matrices can possess Jordan blocks), so the Fourier basis does not exist and the stationarity notion, together with the covariance-preserving surrogate procedure, cannot be applied as stated. The manuscript must either restrict the scope to diagonalizable shift operators, supply an alternative (e.g., Jordan-form) construction, or demonstrate that the surrogate generation remains well-defined without a full eigenbasis.

    Authors: We acknowledge that the manuscript implicitly relies on the existence of an eigendecomposition of the graph shift operator and does not address non-diagonalizable cases. In the revision we will explicitly restrict the proposed framework to directed graphs for which the chosen shift operator is diagonalizable. This restriction is consistent with the eigendecomposition-based definition already used in the paper and covers a broad class of directed graphs arising in applications (e.g., those with distinct eigenvalues or acyclic topologies). We will also insert a brief discussion of the limitation for non-diagonalizable operators and note that extensions via the Jordan canonical form remain an open direction for future work. These changes will render the stationarity notion and the surrogate-generation procedure rigorously well-defined within the stated scope. revision: yes

Circularity Check

0 steps flagged

No circularity: definition and surrogate framework are self-contained

full rationale

The paper defines directed wide-sense stationarity explicitly via eigendecomposition of the graph shift operator and then constructs surrogates that preserve covariance under that definition. No quoted step reduces a claimed prediction or result to a fitted input, self-citation chain, or renaming by construction. The central procedure is presented as building directly on the newly stated stationarity assumption without the derivation collapsing to its own inputs. External applicability concerns (e.g., diagonalizability) are correctness issues, not circularity.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the domain assumption that wide-sense stationarity can be meaningfully defined for directed graphs via the graph shift operator; no free parameters or invented entities are mentioned.

axioms (1)
  • domain assumption Directed graph signals can be defined as wide-sense stationary through the eigendecomposition of the graph shift operator.
    This definition is invoked to extend the surrogate method from undirected to directed graphs.

pith-pipeline@v0.9.1-grok · 5730 in / 1265 out tokens · 24269 ms · 2026-06-28T18:03:56.353813+00:00 · methodology

discussion (0)

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

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Optimal Wiener-Filter Solutions for Denoising of Graph Signals on Directed Graphs

    eess.SP 2026-06 unverdicted novelty 5.0

    Derives optimal Wiener filters for denoising graph signals on directed graphs under uncorrelated and correlated noise stationarity assumptions, with a temperature graph proof-of-concept.

Reference graph

Works this paper leans on

45 extracted references · 1 linked inside Pith · cited by 1 Pith paper

  1. [1]

    The emerging field of signal processing on graphs: Ex- tending high-dimensional data analysis to networks and other irregular domains,

    D. I. Shuman, S. K. Narang, P. Frossard, A. Ortega, and P. Van- dergheynst, “The emerging field of signal processing on graphs: Ex- tending high-dimensional data analysis to networks and other irregular domains,”IEEE Signal Processing Magazine, vol. 30, pp. 83–98, May 2013

    2013

  2. [2]

    Graph Signal Processing: Overview, Challenges, and Ap- plications,

    A. Ortega, P. Frossard, J. Kova ˇcevi´c, J. M. F. Moura, and P. Van- dergheynst, “Graph Signal Processing: Overview, Challenges, and Ap- plications,”Proceedings of the IEEE, vol. 106, pp. 808–828, May 2018

    2018

  3. [3]

    Signal Processing on Directed Graphs: The Role of Edge Directionality When Processing and Learning From Network Data,

    A. G. Marques, S. Segarra, and G. Mateos, “Signal Processing on Directed Graphs: The Role of Edge Directionality When Processing and Learning From Network Data,”IEEE Signal Processing Magazine, vol. 37, pp. 99–116, Nov. 2020

    2020

  4. [4]

    Topology Inference of Directed Graphs by Gaussian Processes With Sparsity Constraints,

    C. Cui, P. Banelli, and P. M. Djuri ´c, “Topology Inference of Directed Graphs by Gaussian Processes With Sparsity Constraints,”IEEE Trans- actions on Signal Processing, vol. 72, pp. 2147–2159, 2024

    2024

  5. [5]

    Diffusion Causal Models for Counter- factual Estimation,

    P. Sanchez and S. A. Tsaftaris, “Diffusion Causal Models for Counter- factual Estimation,” Feb. 2022. arXiv:2202.10166 [cs]

    arXiv 2022

  6. [6]

    Causal Link Discovery With Unequal Edge Error Tolerance,

    J. Shaska and U. Mitra, “Causal Link Discovery With Unequal Edge Error Tolerance,”IEEE Transactions on Signal Processing, vol. 73, pp. 2848–2861, 2025

    2025

  7. [7]

    Build with precision: Bottom-up inference of linear dags,

    H. Ajorlou, S. Rey, G. Mateos, G. Leus, and A. G. Marques, “Build with precision: Bottom-up inference of linear dags,”arXiv preprint arXiv:2512.16111, 2025

    Pith/arXiv arXiv 2025

  8. [8]

    P. J. Brockwell and R. A. Davis,Time Series: Theory and Methods. Springer Series in Statistics, New York, NY: Springer New York, 1991

    1991

  9. [9]

    Stationary graph signals using an isometric graph transla- tion,

    B. Girault, “Stationary graph signals using an isometric graph transla- tion,” in2015 23rd European Signal Processing Conference (EUSIPCO), (Nice), pp. 1516–1520, IEEE, Aug. 2015

    2015

  10. [10]

    Stationary Signal Processing on Graphs,

    N. Perraudin and P. Vandergheynst, “Stationary Signal Processing on Graphs,”IEEE Transactions on Signal Processing, vol. 65, pp. 3462– 3477, July 2017

    2017

  11. [11]

    Stationary Graph Processes and Spectral Estimation,

    A. G. Marques, S. Segarra, G. Leus, and A. Ribeiro, “Stationary Graph Processes and Spectral Estimation,”IEEE Transactions on Signal Processing, vol. 65, pp. 5911–5926, Nov. 2017

    2017

  12. [12]

    Graph Spectral Image Processing,

    G. Cheung, E. Magli, Y . Tanaka, and M. K. Ng, “Graph Spectral Image Processing,”Proceedings of the IEEE, vol. 106, pp. 907–930, May 2018

    2018

  13. [13]

    Forecasting Time Series With V ARMA Recursions on Graphs,

    E. Isufi, A. Loukas, N. Perraudin, and G. Leus, “Forecasting Time Series With V ARMA Recursions on Graphs,”IEEE Transactions on Signal Processing, vol. 67, pp. 4870–4885, Sept. 2019

    2019

  14. [14]

    Graph learning from filtered signals: Graph system and diffusion kernel identification,

    H. E. Egilmez, E. Pavez, and A. Ortega, “Graph learning from filtered signals: Graph system and diffusion kernel identification,”IEEE Trans- actions on Signal and Information Processing over Networks, vol. 5, no. 2, pp. 360–374, 2018

    2018

  15. [15]

    Graph Learning from Gaussian and Stationary Graph Signals,

    A. Buciulea and A. G. Marques, “Graph Learning from Gaussian and Stationary Graph Signals,” inICASSP 2023 - 2023 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), (Rhodes Island, Greece), pp. 1–5, IEEE, June 2023

    2023

  16. [16]

    A Spectral Method for Generating Surrogate Graph Signals,

    E. Pirondini, A. Vybornova, M. Coscia, and D. Van De Ville, “A Spectral Method for Generating Surrogate Graph Signals,”IEEE Signal Processing Letters, vol. 23, pp. 1275–1278, Sept. 2016

    2016

  17. [17]

    WSS Processes and Wiener Filters on Digraphs,

    M. B. Iraji, M. Eini, and A. Amini, “WSS Processes and Wiener Filters on Digraphs,”IEEE Transactions on Signal Processing, vol. 73, pp. 1– 11, 2025

    2025

  18. [18]

    Harmonic analysis on directed graphs and applications: From Fourier analysis to wavelets,

    H. Sevi, G. Rilling, and P. Borgnat, “Harmonic analysis on directed graphs and applications: From Fourier analysis to wavelets,”Applied and Computational Harmonic Analysis, vol. 62, pp. 390–440, Jan. 2023

    2023

  19. [19]

    Digraph Signal Processing With Generalized Boundary Conditions,

    B. Seifert and M. Puschel, “Digraph Signal Processing With Generalized Boundary Conditions,”IEEE Transactions on Signal Processing, vol. 69, pp. 1422–1437, 2021

    2021

  20. [20]

    Hilbert Transform on Graphs: Let There Be Phase,

    C. H. M. Chan, A. Cionca, and D. V . D. Ville, “Hilbert Transform on Graphs: Let There Be Phase,”IEEE Signal Processing Letters, vol. 32, pp. 1725–1729, 2025. Publisher: Institute of Electrical and Electronics Engineers (IEEE)

    2025

  21. [21]

    On Hilbert transform, analytic signal, and modulation analysis for signals over graphs,

    A. Venkitaraman, S. Chatterjee, and P. H ¨andel, “On Hilbert transform, analytic signal, and modulation analysis for signals over graphs,”Signal Processing, vol. 156, pp. 106–115, Mar. 2019

    2019

  22. [22]

    A New Surrogating Algorithm by the Complex Graph Fourier Transform (CGFT),

    Belda, Vergara, Safont, Salazar, and Parcheta, “A New Surrogating Algorithm by the Complex Graph Fourier Transform (CGFT),”Entropy, vol. 21, p. 759, Aug. 2019

    2019

  23. [23]

    Discrete Signal Processing on Graphs,

    A. Sandryhaila and J. M. F. Moura, “Discrete Signal Processing on Graphs,”IEEE Transactions on Signal Processing, vol. 61, pp. 1644– 1656, Apr. 2013

    2013

  24. [24]

    G. W. Stewart,Matrix Algorithms: Volume II: Eigensystems. SIAM, 2001

    2001

  25. [25]

    Discrete Signal Processing on Graphs: Frequency Analysis,

    A. Sandryhaila and J. M. F. Moura, “Discrete Signal Processing on Graphs: Frequency Analysis,”IEEE Transactions on Signal Processing, vol. 62, pp. 3042–3054, June 2014

    2014

  26. [26]

    Translation on Graphs: An Isometric Shift Operator,

    B. Girault, P. Goncalves, and E. Fleury, “Translation on Graphs: An Isometric Shift Operator,”IEEE Signal Processing Letters, vol. 22, pp. 2416–2420, Dec. 2015

    2015

  27. [27]

    J. J. Shynk and J. J. Shynk,Probability, random variables, and random processes: theory and signal processing applications. Hoboken, NJ: Wiley, 1. ed ed., 2013

    2013

  28. [28]

    The distribution of rademacher sums,

    S. J. Montgomery-Smith, “The distribution of rademacher sums,”Pro- ceedings of the American Mathematical Society, vol. 109, no. 2, pp. 517– 522, 1990

    1990

  29. [29]

    Multiple comparisons among means,

    O. J. Dunn, “Multiple comparisons among means,”Journal of the American statistical association, vol. 56, no. 293, pp. 52–64, 1961

    1961

  30. [30]

    A comparison of four methods for simulating the diffusion process,

    F. Tuerlinckx, E. Maris, R. Ratcliff, and P. De Boeck, “A comparison of four methods for simulating the diffusion process,”Behavior Research Methods, Instruments, & Computers, vol. 33, no. 4, pp. 443–456, 2001

    2001

  31. [31]

    Statistical methods for research workers,

    R. A. Fisher, “Statistical methods for research workers,” inBreak- throughs in statistics: Methodology and distribution, pp. 66–70, Springer, 1970

    1970

  32. [32]

    Controlling the false discovery rate: a practical and powerful approach to multiple testing,

    Y . Benjamini and Y . Hochberg, “Controlling the false discovery rate: a practical and powerful approach to multiple testing,”Journal of the Royal statistical society: series B (Methodological), vol. 57, no. 1, pp. 289–300, 1995. SUBMITTED TO IEEE TRANSACTIONS ON SIGNAL AND INFORMATION PROCESSING OVER NETWORKS 12

    1995

  33. [33]

    Graph Fourier transform based on directed Laplacian,

    R. Singh, A. Chakraborty, and B. S. Manoj, “Graph Fourier transform based on directed Laplacian,” in2016 International Conference on Signal Processing and Communications (SPCOM), (Bangalore, India), pp. 1–5, IEEE, June 2016

    2016

  34. [34]

    A Directed Graph Fourier Transform With Spread Frequency Components,

    R. Shafipour, A. Khodabakhsh, G. Mateos, and E. Nikolova, “A Directed Graph Fourier Transform With Spread Frequency Components,”IEEE Transactions on Signal Processing, vol. 67, pp. 946–960, Feb. 2019

    2019

  35. [35]

    The Maritime Influence on Diurnal Temperature Range in the Chesapeake Bay Area,

    K. Scheitlin, “The Maritime Influence on Diurnal Temperature Range in the Chesapeake Bay Area,”Earth Interactions, vol. 17, pp. 1–14, Oct. 2013

    2013

  36. [36]

    Zero-padding on Connected Directed Acyclic Graphs for Spectral Pro- cessing,

    L. Stankovi ´c, M. Dakovi ´c, M. Brajovi ´c, I. Stankovi ´c, and A. B. Bardi, “Zero-padding on Connected Directed Acyclic Graphs for Spectral Pro- cessing,” in2023 31st Telecommunications Forum (TELFOR), (Belgrade, Serbia), pp. 1–4, IEEE, Nov. 2023

    2023

  37. [37]

    Pearl,Causality

    J. Pearl,Causality. Cambridge university press, 2009

    2009

  38. [38]

    S. R. Jammalamadaka and A. SenGupta,Topics in Circular Statistics, vol. 5 ofSeries on Multivariate Analysis. WORLD SCIENTIFIC, Apr. 2001

    2001

  39. [39]

    Testing for nonlinearity in time series: the method of surrogate data,

    J. Theiler, S. Eubank, A. Longtin, B. Galdrikian, and J. Doyne Farmer, “Testing for nonlinearity in time series: the method of surrogate data,” Physica D: Nonlinear Phenomena, vol. 58, pp. 77–94, Sept. 1992

    1992

  40. [40]

    Test- ing Stationarity With Surrogates: A Time-Frequency Approach,

    P. Borgnat, P. Flandrin, P. Honeine, C. Richard, and J. Xiao, “Test- ing Stationarity With Surrogates: A Time-Frequency Approach,”IEEE Transactions on Signal Processing, vol. 58, pp. 3459–3470, July 2010

    2010

  41. [41]

    A graph signal processing perspective of network multiple hypothesis testing with false discovery rate control,

    X. Jian, M. G ¨olz, F. Ji, W. P. Tay, and A. M. Zoubir, “A graph signal processing perspective of network multiple hypothesis testing with false discovery rate control,”IEEE Transactions on Signal Processing, 2025

    2025

  42. [42]

    Maiwald, E

    T. Maiwald, E. Mammen, S. Nandi, and J. Timmer,Surrogate Data — A Qualitative and Quantitative Analysis, pp. 41–74. Berlin, Heidelberg: Springer Berlin Heidelberg, 2008

    2008

  43. [43]

    Vertex-frequency Analysis on Directed Graphs,

    D. Wei and S. Yuan, “Vertex-frequency Analysis on Directed Graphs,” IEEE Transactions on Signal Processing, pp. 1–15, 2025

    2025

  44. [44]

    Joint Sampling and Reconstruction of Time-Varying Signals Over Directed Graphs,

    Z. Xiao, H. Fang, S. Tomasin, G. Mateos, and X. Wang, “Joint Sampling and Reconstruction of Time-Varying Signals Over Directed Graphs,” IEEE Transactions on Signal Processing, vol. 71, pp. 2204–2219, 2023

    2023

  45. [45]

    Frequency Analysis and Filter Design for Directed Graphs with Polar Decomposition,

    S. Kwak, L. Shimabukuro, and A. Ortega, “Frequency Analysis and Filter Design for Directed Graphs with Polar Decomposition,” inICASSP 2024 - 2024 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), (Seoul, Korea, Republic of), pp. 9661– 9665, IEEE, Apr. 2024

    2024