AZ-whiteness test: a test for signal uncorrelation on spatio-temporal graphs

Daniele Zambon, Cesare Alippi

Introduction

In traditional time-series analysis, a "white" signal is one where observations are uncorrelated over time—essentially, pure noise. When evaluating a predictive model, researchers want the residuals (the errors) to be white. If they are not, it indicates that the model missed an underlying pattern it could have learned, leaving predictable "juice" in the residuals.

However, modern data often lives on complex structures like graphs (e.g., traffic sensors on a highway or users in a social network). In these settings, "whiteness" is more complex: a signal must be uncorrelated both across time (serial correlation) and across space (spatial correlation between neighboring nodes). Existing tests like Durbin-Watson or Ljung-Box only handle univariate time series and ignore graph structure. To address this gap, researchers introduce the AZ-whiteness test, the first statistical hypothesis test designed to detect spatio-temporal correlations in signals defined over dynamic graphs.

The AZ-Test Methodology

The AZ-test (named after Alippi and Zambon) provides a crucial model assessment tool for graph deep learning. Its core intuition is based on counting the signs of products between spatially and temporally adjacent observations.

  1. The Spatial Statistic: For a static graph, the test statistic $C(G)$ sums the weights of edges multiplied by the sign of the product of the signals at the connected nodes. If neighbors tend to have the same sign (positive correlation) or opposite signs (negative correlation) more often than chance, the null hypothesis of "whiteness" is rejected.
  2. Spatio-Temporal Extension: To handle time, the authors construct a "multiplex" graph $G^*$. In this representation, nodes are replicated for each time step, and "temporal edges" are added to connect a node to itself at the next time step. This allows the same mathematical framework to detect both spatial and serial dependencies simultaneously.
A dynamic graph represented as a sequence of snapshots, where temporal edges (dashed lines) connect nodes across time steps.
  1. Versatility: The test is "distribution-free" in its asymptotic limit, meaning it doesn't require the data to follow a specific distribution (like Gaussian). It also handles weighted edges and dynamic graphs where nodes or connections appear and disappear.

Key Insights and Experimental Results

By incorporating the graph topology into the test, the authors solve an otherwise ill-posed problem. Testing for independence among thousands of observations with only one sample each is usually impossible; the graph provides the necessary relational inductive bias to make the test statistically valid. Furthermore, the authors prove that as the number of edges in the graph grows, the test statistic converges to a standard Gaussian distribution, providing a reliable way to set significance thresholds (e.g., $\alpha = 0.05$).

The authors evaluated the AZ-test using both synthetic benchmarks (GPVAR) and real-world traffic datasets (PemsBay and MetrLA).

Statistical Power

The AZ-test demonstrates high statistical power, meaning it reliably detects correlation as the strength of the dependency ($c$) or the number of time steps ($T$) increases, across various underlying data distributions.

Heatmaps showing the rate of rejected null hypotheses. As correlation (c) and time steps (T) increase, the test correctly identifies non-white signals across various distributions.

Model Diagnostics

The test acts as a rigorous diagnostic "sanity check" for Graph Neural Networks (GNNs).

  • Optimal vs. Suboptimal: On synthetic data with a known ground truth, the test correctly identified that an "optimal" predictor produced white residuals, while a simpler FCRNN model did not.
  • SOTA Gaps: When applied to state-of-the-art models (like DCRNN and Graph WaveNet) on real-world traffic data, the AZ-test often rejected the whiteness hypothesis. This suggests that even these advanced models struggle to fully capture the complex spatio-temporal correlations present in real-world sensor networks, leaving room for architectural improvements.

Limitations and Future Work

While powerful, the AZ-test has a few limitations. It assumes the signal has a median of zero (or that the median is known and subtracted), which is a prerequisite for the correlation test. Additionally, the current work focuses on 1-hop spatial and 1-lag temporal correlations. Future extensions could expand to $K$-hop or $K$-lag dependencies to detect more distant relationships in the graph. Finally, extending this framework to settings where the graph structure itself is stochastic remains an open direction for future research.

Summary updated

Abstract

We present the first whiteness hypothesis test for graphs, i.e., a whiteness test for multivariate time series associated with the nodes of a dynamic graph; as such, the test represents an important model assessment tool for graph deep learning, e.g., in forecasting setups. The statistical test aims at detecting existing serial dependencies among close-in-time observations, as well as spatial dependencies among neighboring observations given the underlying graph. The proposed AZ-test can be intended as a spatio-temporal extension of traditional tests designed for system identification to graph signals. The AZ-test is versatile, allowing the underlying graph to be dynamic, changing in topology and set of nodes over time, and weighted, thus accounting for connections of different strength, as it is the case in many application scenarios like sensor and transportation networks. The asymptotic distribution of the designed test can be derived under the null hypothesis without assuming identically distributed data. We show the effectiveness of the test on both synthetic and real-world problems, and illustrate how it can be employed to assess the quality of spatio-temporal forecasting models by analyzing the prediction residuals appended to the graph stream.
BibTeX
@inproceedings{zambon2022az,
  author = {Daniele Zambon and Cesare Alippi},
  title = {{AZ-whiteness test: a test for signal uncorrelation on spatio-temporal graphs}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
}
Figure