Abstract
Graph Learning (GL) is at the core of inference and analysis of connections in data mining and machine learning. By observing a dataset of graph signals and considering specific assumptions, Graph Signal Processing (GSP) tools can provide practical constraints in the GL approach. One applicable constraint can infer a graph with desired frequency signatures, i.e., spectral templates. However, a severe computational burden is a challenging barrier, especially for inference from high-dimensional graph signals. To address this issue and in the case of the underlying graph having graph product structure, we propose learning product (high dimensional) graphs from product spectral templates with significantly reduced complexity rather than learning them directly from high-dimensional graph signals. Experimental results on both synthetic and real-world data illustrate explainable and meaningful factor graphs as well as outperforming current restricted approaches.
Introduction
In Graph Signal Processing (GSP), learning the underlying graph structure from observed signals is a fundamental task. However, as the number of nodes ($N$) grows, the computational cost of learning an $N \times N$ adjacency matrix explodes, typically scaling at $O(N^3)$. This "curse of dimensionality" is particularly acute for multi-domain data, such as EEG signals where relationships exist both spatially (between sensors) and temporally (between time steps). Such structures are naturally modeled as product graphs. Existing methods for learning these are often limited to two factors, require prior knowledge of the product type (e.g., Cartesian vs. Kronecker), or struggle with high-dimensional variables.
Methodology
The proposed method, ProdSpecTemp, addresses these challenges by leveraging two key pillars:
- Spectral Templates: For stationary graph signals, the eigenvectors of the signal's covariance matrix match the eigenvectors of the graph's adjacency matrix.
- Factorization via Tensor Unfolding: By treating data as a multi-dimensional tensor, the authors prove that Eigendecomposition (EVD) on "mode-unfolded" covariance matrices can recover the eigenvectors of individual, smaller factor graphs ($V_P, V_Q$, etc.) independently.
Once factor eigenvectors are obtained, the SpecTemp-IALM algorithm (based on inexact Augmented Lagrange Multipliers) identifies the sparsest adjacency matrices fitting those templates. This approach is "product-agnostic," recovering factor graphs without needing to know the specific product type used to generate the data.
Experimental Evaluation
The authors validated ProdSpecTemp on synthetic and real-world datasets. In synthetic tests using Erdos-Renyi factor graphs, ProdSpecTemp demonstrated superior accuracy in recovering both Cartesian and "Strong" product graphs.
As shown in Figure 1, ProdSpecTemp consistently outperforms state-of-the-art methods like BiGLasso and PGL. Notably, on Strong product graphs, competing methods often fail to converge or exhibit high error rates, while ProdSpecTemp maintains high F1 scores and low edge error.
In real-world applications, the method was applied to the MASS-SS3 EEG dataset to learn spatial and temporal connectivity across sleep stages.
Figure 6 illustrates how the model distinguishes sleep stages. The results align with neuroscientific literature, showing complex connectivity in the N1 stage (light sleep) and significantly reduced activity in the N3 stage (deep sleep). Additionally, on the COIL-20 image dataset, the learned pixel graph correctly identified the 80x80 grid structure, while the rotation graph accurately linked circular views.
Conclusion
ProdSpecTemp offers a massive complexity reduction, dropping the computational burden from $O(N^3)$ to $O(P^3 + Q^3)$ for factor graphs of size $P$ and $Q$. While the method assumes stationarity and requires prior knowledge of factor sizes, it provides a robust, explainable framework for high-dimensional graph learning. Future work includes automating factor size discovery and extending the framework to rank-constrained structures for multi-view clustering.
Summary updated