Sampling signals on multigraphs for better data reconstruction
Sampling of Signals on Multigraphs: From Removable and Uniqueness sets to Spectral Proxies
Machine Learning
Summary
Often, signals are collected from complex networks represented by one graph, but sometimes multiple overlapping networks (multigraphs) describe different relationships on the same nodes. The authors study how to pick the best points for sampling signals defined on these multigraphs so that the original signals can be uniquely recovered. They introduce a new way to define frequencies for signals that capture all layers and propose an algorithm to find sampling points without complex calculations. Their approach improves the accuracy of signal reconstruction compared to using just a single graph.
What this means in practice
- •For network engineers: Optimize sensor placement on complex networks with multiple relationship types to improve data quality and reduce the number of sensors needed.
- •For data analysts in social networks: Select user subsets for sampling to accurately reconstruct information spreading over multiple social connection types without excessive data collection.
Authors
Alejandro Parada-Mayorga
Abstract
In this paper, we study the sampling of bandlimited signals on multigraphs, where several graphs with different shift operators are defined on the same set of nodes. Since the shift operators do not commute in general, they admit only a joint block diagonalization, and the frequencies of the multigraph signal model are matrices rather than scalars. Relying on a formal algebraic convolutional signal model, we introduce a notion of frequency and bandwidth for multigraph signals that does not depend on any individual layer, and we extend the notions of removable and uniqueness sets to multigraphs. We prove that the optimality of a sampling set is determined exclusively by the common Fourier basis and its invariant subspaces, and not by any individual layer, although the individual layers provide computable sufficient conditions that certify a sampling set as a uniqueness set. Since identifying which layers provide reliable certificates requires spectral information, we propose an aggregate operator that pools the information of all the layers, is computable directly from the shift operators, and certifies uniqueness without any assumption on the individual layers. This operator leads to a greedy sampling algorithm that does not require computing the joint block diagonalization. Numerical experiments on multigraphs whose layers order the frequencies inconsistently show that the proposed algorithm selects better-conditioned sampling sets and attains lower reconstruction errors than single-layer methods.