On Local Distributions in Graph Signal Processing

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.

I. Introduction

Graph filters are a fundamental building block in graph signal processing, where cascaded applications of a graph shift operator model diffusion on the nodes of a graph [1], [2]. The analogy between filtering in discrete time and filtering on graphs has led to a fruitful research direction, with applications including robotics [3], neuroscience [4], and recommender systems [5]. Due to their typical implementation as low-degree matrix polynomials, graph filters are local operators, where the output of a graph filter at a given node is strictly dependent on the connectivity structure and signal values on the node's local neighborhood. This highlights an invariance property of graph filters, typically summarized by the property of permutation equivariance. However, the equivariance of graph filters is much stronger than not being sensitive to permutations of nodes. If the same filter is applied to two different graphs, and two nodes within each of those graphs have identical neighborhoods, then the graph filter output at those nodes will be identical as well [6]. Indeed, graph filters in their usual implementation are equivariant to local substructures, which have been shown to be of primary importance in real-world networks [7], often leading to useful properties such as scale invariance and robustness [8].