Abstract
Graph-based representations play a key role in machine learning. The fundamental step in these representations is the association of a graph structure to a dataset. In this paper, we propose a method that finds a block sparse representation of the data by associating a graph, whose Laplacian matrix admits the sparsifying dictionary as its eigenvectors. The main idea is to associate a graph topology to the data in order to make the observed signals band-limited over the inferred graph. The proposed strategy is composed of the following two optimization steps: first, learning an orthonormal sparsifying transform from the data; and second, recovering the Laplacian matrix, and then topology, from the transform. The first step is achieved through an iterative algorithm whose alternating intermediate solutions are expressed in closed form. The second step recovers the Laplacian matrix from the sparsifying transform through a convex optimization method. Numerical results corroborate the effectiveness of the proposed methods over both synthetic and real data. Specifically, we consider two real-world applications of our methods: the inference of the brain functional activity map from electrocorticography signals taken from patients affected by epilepsy, and the reconstruction of the radio environment map from sparse measurements of the electromagnetic field in an urban area.
Introduction
In fields ranging from neuroscience to sensor networks, we often observe signals—such as brain waves or temperature readings—without knowing the underlying network of connections that influences them. Traditional methods often rely on simple correlations, which can fail to capture true structural dependencies or the "causality" inherent in the data.
This paper addresses the challenge of Graph Topology Inference: identifying a graph that best explains observed data. The authors hypothesize that real-world signals are "smooth" or "band-limited" over their natural graph. Consequently, when projected onto the graph's "frequencies" (its Laplacian eigenvectors), the data should exhibit a sparse representation.
Methodology
The proposed framework utilizes a two-stage optimization strategy to uncover the hidden "skeleton" of a dataset:
- Transform Learning: The algorithm jointly learns an orthonormal transform matrix—effectively a custom Fourier basis—and a block-sparse representation of the data. This is achieved through an efficient iterative process where each intermediate step has a closed-form solution, ensuring computational efficiency.
- Laplacian Recovery: After obtaining the transform, the graph's Laplacian matrix (defining edges and weights) is inferred. Two variants are proposed:
- TV-GL (Total Variation Graph Learning): This method minimizes the signal's variation across the graph.
- ESA-GL (Estimated-Signal-Aided Graph Learning): This uses the sparse signals estimated in the first step to guide the graph recovery process.
Unlike many existing Graph Signal Processing (GSP) methods, this approach does not require signals to be stationary or result from specific diffusion processes, offering greater flexibility for real-world applications.
Key Insights and Results
A significant finding of this work is the link between sparsity and modularity. Enforcing sparsity in the transform domain naturally leads to modular graphs—structures with dense clusters that are weakly connected. This aligns with the architecture of many real-world systems, such as functional brain regions or social networks.
The researchers validated their approach using both synthetic and real-world datasets:
- Synthetic Benchmarks: On modular, Erdős-Rényi, and Barabási-Albert graphs, the algorithms achieved correlation coefficients as high as 0.95 between true and inferred Laplacians.
- Seizure Mapping: In an epilepsy study using ElectroCorticography (ECoG) signals, the inferred graphs revealed a dramatic decrease in connectivity at seizure onset, particularly in the suspected epileptogenic zone.
- Predictive Power: The inferred topologies allowed for accurate reconstruction of missing signal data from unobserved electrodes, confirming the physical relevance of the recovered graphs.
Conclusion and Future Work
While the proposed methods demonstrate high accuracy and practical utility, the authors acknowledge that the overall optimization problem is non-convex, potentially leading to local optima. Furthermore, while the "de-rotation" technique for finding true eigenvectors works well for discrete-valued signals, extending its robustness to all continuous data types remains an open challenge. Future research will explore the relationship between transform accuracy and graph cluster count, as well as the "blind" recovery of transforms without prior knowledge of signal alphabets.
Summary updated