Statistical Testing on Directed Graphs by Surrogate Data Generation

Chun Hei Michael Chan, Alexandre Cionca · 2026

Read Statistical Testing on Directed Graphs by Surrogate Data Generation by Chun Hei Michael Chan, Alexandre Cionca (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-00758.txt.

Introduction

Chan, Cionca, and Van De Ville extend a testing method to directed graphs in this 2026 paper. Graph signal processing studies signals that live on a graph's nodes. One use is hypothesis testing with surrogate data: fake signals that mimic the real one's structure. Past surrogate work covers graphs whose edges run both ways. Directed graphs, where edges run one way, lack such tools.

The team first reworks what a stationary graph signal means for directed graphs. They use the eigendecomposition of the graph shift operator to define it. They then build a way to make surrogate signals that keep the covariance structure under that definition. Test scores from real data can be judged against a null spread built from the surrogates. In guide cases and one real-data use, they report, their method beats undirected tools and naive shuffling. The work opens directed graphs to this style of test.

Catalog record

CREATORChun Hei Michael Chan, Alexandre Cionca
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE58 KB
LICENSEhttp://creativecommons.org/licenses/by-sa/4.0/
RIGHTSCC BY SA
SOURCEarXiv

Source: https://arxiv.org/abs/2606.00758

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Statistical Testing on Directed Graphs by Surrogate Data Generation Thanks: CHM. Chan, A. Cionca and D. Van De Ville are with the Neuro-X Institute, Ecole polytechnique fédérale de Lausanne, and the Department of Radiology and Medical Informatics, University of Geneva, Switzerland. E-mail: [email protected]; [email protected] Thanks: This work was supported by the Swiss National Science Foundation, Sinergia project “Precision mapping of electrical brain network dynamics with application to epilepsy”, Grant number 209470. Thanks: Manuscript received XXX; revised XXX. Chun Hei Michael Chan, Alexandre Cionca 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. I Introduction Graph signal processing (GSP) has emerged as a compelling methodology for managing data expressed on structured domains; e.g., in the context of social, biological, technological networks. GSP considers graphs and graph signals in a common framework to revisit classical signal processing operations [ 36 , 24 , 22 ] . In the probabilistic setting, where graph signals are considered as realizations of random processes, GSP is essentially limited to undirected graphs, which motivates this work to provide a framework to enable statistical hypothesis testing on directed graphs. We emphasize that, in contrast to the extensive body of work on directionality inference for causal graph discovery [ 9 , 28 , 35 , 1 ] , the present study addresses statistical hypothesis testing for assessing signals observed on a predefined graph. Several differences also exist in the type of graphs that each framework considers. In conventional signal processing, a random process in the time domain is said to be weakly stationary when the first two moments, mean and autocorrelation, do not vary with respect to time. Equivalently, its covariance matrix is diagonalized by the discrete Fourier transform (DFT) basis [ 5 ] . The latter concept has been used for defining graph wide-sense stationarity (GWSS) for undirected graphs [ 14 , 26 , 21 ] ; i.e., a random process on the graph is GWSS if and only if its covariance matrix is diagonalized by the eigenvectors of the graph shift operator (GSO), commonly the adjacency matrix or the graph Laplacian, that can be considered as the graph Fourier transform (GFT). Stationarity of graph signals has been leveraged in a variety of applications, notably Wiener-based graph signal denoising, the forecasting of graph signal timeseries and graph structure learning [ 8 , 16 , 11 , 6 ] . For non-parametric statistical testing, under the stationarity assumption, we proposed a scheme to generate surrogate graph signals [ 27 ] based on sign randomization of the GFT coefficients. For a chosen test metric, the value from the empirical data can then be compared against the null distribution obtained from surrogates. Recently, the notion of stationarity has been extended to directed graphs [ 15 ] leading to directed GWSS (DGWSS). Here, the covariance matrix can be expressed as a left–right product of a block-diagonal matrix by the generalized eigenvector matrix of the GSO and its Hermitian transpose. However, this formulation relies on the Jordan Normal Form (JNF) of the GSO, which presents two major limitations: the JNF is numerically unstable and computationally inefficient. Yet, most graphs are strongly connected and thus come with a diagonalizable directed GSO [ 33 ] , and, if not, they can be made so by a minimal perturbation [ 32 ] . This provides a complex-valued eigenbasis, but that is not necessarily orthogonal. This allows to obtain meaningful phase information that can be leveraged for operations such as the graph Hilbert transform [ 7 , 43 ] . Surrogate generation on directed graphs has not yet been addressed, except for the special case of complex-valued Hermitian graphs [ 2 ] . In this work, we first revisit the notion of directed graph wide sense stationarity (DGWSS) through the eigendecomposition of the GSO and extend properties from GWSS to DGWSS. Next, we study white noise (WN) on the graph, a particular type of stationary signal with flat power spectral density, highlighting some striking differences between WN on undirected and directed graphs. We then present the framework for non-parametric testing, leveraging our proposed surrogate generation scheme. Throughout all experiments, we will compare our framework against surrogates generated on the undirected graph, and surrogates from naive permutations, demonstrating that directionality is meaningful and useful to be accounted for. We also show results for experimental data from temperature measurements on a sensor network. The remainder of the paper is organized as follows. In Sect. III , we introduce the directed graph signal processing framework. Then, in Sect. IV , we revisit the definition and properties of GWSS and its extension to directed graphs. We focus in Sect. V on white noise for directed graphs and discuss its differences with the undirected setting. Next, in Sect. VI , we present the proposed non-parametric testing framework together with the surrogate generation scheme. Numerical experiments on synthetic and real-world datasets are presented in Sect. VII , including temperature data on a sensor network. Finally, we conclude the paper and outline future research directions. II Notations Lower-case bold letters indicate vectors; e.g., {\mathbf{x}} where {\mathbf{x}}[n] is the n -th element. When the vector indicates a random variable {\mathbf{x}} , different realizations will be denoted with a subscript as {\mathbf{x}}_{k} , and surrogates generated from such a realization with a superscript as {\mathbf{x}}_{k}^{(l)} . Further on, upper-case bold letters are used for matrices; e.g., {\mathbf{U}} with {\mathbf{U}}[n,m] denoting the (n,m) -th entry of {\mathbf{U}} . The notations (.)^{*} , (.)^{T} , (.)^{H} , (.)^{-1} , (.)^{-H} denote conjugate, transpose, Hermitian, inverse, and inverse Hermitian, respectively. We use j to refer to the complex number such that j^{2}=-1 . With ||.||_{2} and ||.||_{F} , we refer to L^{2} -norm and Frobenius norm, respectively. We use \bar{(\cdot)} to refer to matrices related to the undirected graph. III Graph Fourier Transform III-A Undirected Graph Consider an undirected graph with N nodes represented by its symmetric adjacency matrix \bar{{\mathbf{A}}} , which can be eigendecomposed into \bar{{\mathbf{A}}}=\bar{{\mathbf{U}}}\bar{{\mathbf{\Lambda}}}\bar{{\mathbf{U}}}^{T}, (1) where \bar{{\mathbf{U}}} contains the real-valued eigenvectors [\bar{{\mathbf{u}}}_{k}]_{k=1,\ldots,N} that form an orthonormal basis with associated eigenvalues on the diagonal of \bar{{\mathbf{\Lambda}}} . From this decomposition, the GFT of a graph signal

Read the complete text