TY - JOUR
T1 - On Local Distributions in Graph Signal Processing
AU - Roddenberry, T. Mitchell
AU - Gama, Fernando
AU - Baraniuk, Richard G.
AU - Segarra, Santiago
N1 - Funding Information:
The work of T. Mitchell Roddenberry and Santiago Segarra was supported by NSF under Grant CCF-2008555.
Publisher Copyright:
© 2022 IEEE.
PY - 2022
Y1 - 2022
N2 - Graph filtering is the cornerstone operation in graph signal processing (GSP). Thus, understanding it is key in developing potent GSP methods. Graph filters are local and distributed linear operations, whose output depends only on the local neighborhood of each node. Moreover, a graph filter's output can be computed separately at each node by carrying out repeated exchanges with immediate neighbors. Graph filters can be compactly written as polynomials of a graph shift operator (typically, a sparse matrix description of the graph). This has led to relating the properties of the filters with the spectral properties of the corresponding matrix - which encodes global structure of the graph. In this work, we propose a framework that relies solely on the local distribution of the neighborhoods of a graph. The crux of this approach is to describe graphs and graph signals in terms of a measurable space of rooted balls. Leveraging this, we are able to seamlessly compare graphs of different sizes and coming from different models, yielding results on the convergence of spectral densities, transferability of filters across arbitrary graphs, and continuity of graph signal properties with respect to the distribution of local substructures.
AB - Graph filtering is the cornerstone operation in graph signal processing (GSP). Thus, understanding it is key in developing potent GSP methods. Graph filters are local and distributed linear operations, whose output depends only on the local neighborhood of each node. Moreover, a graph filter's output can be computed separately at each node by carrying out repeated exchanges with immediate neighbors. Graph filters can be compactly written as polynomials of a graph shift operator (typically, a sparse matrix description of the graph). This has led to relating the properties of the filters with the spectral properties of the corresponding matrix - which encodes global structure of the graph. In this work, we propose a framework that relies solely on the local distribution of the neighborhoods of a graph. The crux of this approach is to describe graphs and graph signals in terms of a measurable space of rooted balls. Leveraging this, we are able to seamlessly compare graphs of different sizes and coming from different models, yielding results on the convergence of spectral densities, transferability of filters across arbitrary graphs, and continuity of graph signal properties with respect to the distribution of local substructures.
KW - Graph signal processing
KW - graph Fourier transform
KW - graph filtering
KW - graphing signal processing
KW - transferability
KW - weak convergence
UR - http://www.scopus.com/inward/record.url?scp=85134702730&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85134702730&partnerID=8YFLogxK
U2 - 10.1109/TSP.2022.3223217
DO - 10.1109/TSP.2022.3223217
M3 - Article
AN - SCOPUS:85134702730
SN - 1053-587X
VL - 70
SP - 5564
EP - 5577
JO - IEEE Transactions on Signal Processing
JF - IEEE Transactions on Signal Processing
ER -