Graph Topology Identification Based on Covariance Matching
Y. Han (TU Delft - Electrical Engineering, Mathematics and Computer Science)
G Leus – Mentor (TU Delft - Signal Processing Systems)
Elvin Isufi – Graduation committee member (TU Delft - Multimedia Computing)
A. Natali – Mentor (TU Delft - Signal Processing Systems)
More Info
expand_more
Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.
Abstract
Graph signal processing (GSP) extends classical signal processing to signals on graphs, enabling the analysis of complex data structures through graph theory. A core challenge in GSP is graph topology identification, which aims to deduce the graph structure that best explains observed signal dependencies.
This project addresses graph topology identification for applications where the underlying structure of systems like brain and social networks is not directly observable. Traditional approaches based on signal matching and spectral templates have limitations, particularly in handling scale issues and sparsity assumptions. We introduce a novel covariance matching methodology that efficiently reconstructs the graph topology using observable data. For the structural equation model (SEM) using an undirected graph, we demonstrate that our method can converge to the correct result under relatively soft conditions. Furthermore, we extend our methodology to polynomial models, sparse directed graphs, and any known Gaussian distribution of latent variables, broadening its applicability and utility in diverse graph-based systems. Experimental results demonstrate that our method outperforms existing techniques, offering new directions for future research in graph topology identification.