On Local Distributions in Graph Signal Processing

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 power systems [3], robotics [4], neuroscience [5], and recommender systems [6]. 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 [7]. 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 [8], often leading to useful properties such as scale invariance and robustness [9].

The importance of local substructures is an incipient development in the literature. This view has been considered before in the graph wavelet literature [10, 11, 12], where wavelet atoms are constructed by applying graph filters to impulse functions on each node in the graph, yielding a dictionary of atoms with known spectral properties that also exhibit (approximate) spatial localization. As a representational tool for graphs predating the development of graph signal processing, graph kernel methods have put forth the idea of graphs as bags of motifs [13], such as in the paper on graphlets [14]. Works such as [15, 16] have considered the extension of graph kernels for graphs with continuous labels, typically via a neighborhood aggregation or discretization approach. In [17], equivariance to local structures is proposed as a more useful invariant for graph neural networks, as opposed to permutation equivariance. For instance, [18] considers neural networks for graph classification that act on small subgraphs over an entire graph, and [19] considers how to design graph neural networks that can recognize structures more expressive than those of the Weisfeiler-Lehman test. The treatment of graphs as distributions of ego-networks in [20] was used to devise a novel loss function for training of graph neural networks based on the maximization of mutual information. Additionally, local structures at each node need not be deterministic, as [21] considers random walk features and defines the notion of an estimable parameter under such a model.

In this work, we develop machinery for reasoning about basic notions in graph signal processing, with the primacy of local substructures in mind. After reviewing basic definitions for graph signal processing in Section 2, we make the following theoretical contributions:

1. 1.

   We introduce rooted graphs and rooted graph filters as vehicles for describing localized graph filters. In doing so, we develop a measure-theoretic view of graph signal processing that considers distributions of rooted balls and signals supported on them (Section 3).

2. 2.

   Within the proposed framework, we illustrate how convergence of Fourier spectra of graph signals can be understood in terms of weak convergence of measures (Section 4).

3. 3.

   We apply the proposed framework to yield a principled understanding of the transferability of graph summaries via integral probability metrics (Section 5).

4. 4.

   To highlight the flexibility of the proposed approach, we extend the relationship between distributions of local graph structures and the Fourier spectra of graph signals to weighted graphs (Section 6).

5. 5.

   We identify graphings and signals supported on them as the appropriate limiting objects in the proposed framework, and develop basic notions of graphing signal processing. We prove that the proposed framework applies directly to graphing signal processing in a natural way (Section 7), yielding a suitable spectral theory.

Consider an undirected graph $\mathcal{G}=(\mathcal{V},\mathcal{E})$ where $\mathcal{V}$ is the set of nodes and $\mathcal{E}\subseteq\mathcal{V}\times\mathcal{V}$ is the set of edges. Since the graph is undirected, it holds that if edge $(u,v)\in\mathcal{E}$ for $u,v\in\mathcal{V}$, then $(v,u)\in\mathcal{E}$. We further assume the graph to have no self-loops, i.e., $(v,v)\notin\mathcal{E}$ for all $v\in\mathcal{V}$, and to be unweighted. An extension to weighted graphs can be found in Section 6.

The neighborhood $\mathcal{N}(\mathcal{V}^{\prime})$ of a given collection of nodes $\mathcal{V}^{\prime}\subseteq\mathcal{V}$ is defined as

That is, the neighborhood of a collection of nodes is that set of nodes $\mathcal{V}^{\prime}$ as well as those nodes immediately connected to it. The $k$-hop neighborhood $\mathcal{N}^{k}(\mathcal{V}^{\prime})$ can then be conveniently defined in a recursive manner as $\mathcal{N}^{k}(\mathcal{V}^{\prime})=\mathcal{N}(\mathcal{N}^{k-1}(\mathcal{V}^{\prime}))$ for integers $k\geq 1$ and with $\mathcal{N}^{0}(\mathcal{V}^{\prime})=\mathcal{V}^{\prime}$. Note that the $k$-hop neighborhood of a singleton $\mathcal{V}^{\prime}=\{v\}$ is denoted as $\mathcal{N}^{k}(v)$, and that its degree can be easily computed as $\deg(v)=|\mathcal{N}(v)|-1$.

Graph signals can be associated with a graph structure and are defined as a map $\mathbf{x}:\mathcal{V}\to\mathbb{R}$ between the node set $\mathcal{V}$ and the real numbers $\mathbb{R}$. That is, a graph signal simply attaches a single real number $[{\mathbf{x}}]_{v}\in\mathbb{R}$ to each node of the graph $v\in\mathcal{V}$. For a given graph $\mathcal{G}=(\mathcal{V},\mathcal{E})$, we can define the space of graph signals as $\mathbb{X}(\mathcal{G})=\{\mathbf{x}:\mathcal{V}\to\mathbb{R}\}$.

A graph shift operator (GSO) $\mathbf{S}$ can also be associated with the graph structure $\mathcal{G}$ as a means of relating graph signals explicitly with the underlying graph support. More precisely, the GSO is defined as a linear operator between graph signals $\mathbf{S}:\mathbb{X}(\mathcal{G})\to\mathbb{X}(\mathcal{G})$ such that the output graph signal $\mathbf{y}=\mathbf{S}\mathbf{x}$ is computed as

The operation (2) shifts the signal around the graph and is analogous to the time-shift in discrete-time signal processing. Note that the GSO can be completely characterized by specifying the adjacency rule that assigns the values ${[\mathbf{S}]}_{vu}$ for every $(u,v)\in\mathcal{E}$. Examples of GSOs that have found widespread use in the literature include the adjacency matrix, the Laplacian matrix, the Markov transition matrix, and their normalized counterparts. While it is technically possible to design adjacency rules that lead to arbitrary values of ${[\mathbf{S}]}_{vu}$, we only consider rules that are determined exclusively by the combinatorial structure of the graph.

A graph filter can then be built from the GSO. More specifically, given a collection of $(K+1)$ scalar coefficients $\{h_{k}\}_{k=0}^{K}$, a $K$-tap graph filter $\mathcal{H}(\mathbf{S}):\mathbb{X}(\mathcal{G})\to\mathbb{X}(\mathcal{G})$ is defined as the linear mapping between two graph signals $\mathbf{y}=\mathcal{H}(\mathbf{S})\mathbf{x}$ given by

where $\mathbf{S}^{k}$ denotes $k$ repeated applications of the GSO (see (2)) to the input signal $\mathbf{x}$. The operator $\mathbf{S}^{0}$ is understood to be the identity map on $\mathbb{X}(\mathcal{G})$.

Graph filters are linear and local operators. They are linear in the input graph signal $\mathbf{x}$. They are local in that they only require information up to the $K$-hop neighborhood. More specifically, the output of the graph filter at each node $[{\mathbf{y}}]_{v}$ can be computed by $K$ repeated exchanges of information with one-hop neighbors $\mathcal{N}(v)$, thus collecting the signal values contained in up to the $K$-hop neighborhood $\mathcal{N}^{K}(v)$. Each node can compute their output separately from the rest. The key observation is that the nodes need not know the global structure of the whole graph $\mathcal{G}$ but only their local neighborhood. Thus, graph filters can be analyzed and understood entirely from looking at this local neighborhood structure.

The local nature of graph filters calls for a local framework to analyze their effects. Towards this end, define a rooted $K$-ball $\,\hbox{\vbox{\hrule height=0.66pt\kern 1.29167pt\hbox{\kern-1.00006pt$\mathcal{G}$\kern-1.00006pt}}}\,_{K}(r)=(\hbox{\vbox{\hrule height=0.66pt\kern 1.29167pt\hbox{\kern-1.00006pt$\mathcal{V}$\kern-1.00006pt}}}_{K},\hbox{\vbox{\hrule height=0.66pt\kern 1.29167pt\hbox{\kern-1.00006pt$\mathcal{E}$\kern-1.00006pt}}}_{K},r)$ as a graph with a root $r\in\hbox{\vbox{\hrule height=0.66pt\kern 1.29167pt\hbox{\kern-1.00006pt$\mathcal{V}$\kern-1.00006pt}}}_{K}$ such that all nodes are at most $K$-hops away from the root, i.e., $\hbox{\vbox{\hrule height=0.66pt\kern 1.29167pt\hbox{\kern-1.00006pt$\mathcal{V}$\kern-1.00006pt}}}_{K}=\mathcal{N}^{K}(r)$. Note that, since the rooted $K$-ball $\,\hbox{\vbox{\hrule height=0.66pt\kern 1.29167pt\hbox{\kern-1.00006pt$\mathcal{G}$\kern-1.00006pt}}}\,_{K}(r)$ is a graph, the notions of graph shift operator and graph signal are immediately well-defined. We denote these as $\,\hbox{\vbox{\hrule height=0.66pt\kern 1.29167pt\hbox{\kern-1.00006pt$\mathbf{S}$\kern-1.00006pt}}}\,_{K}(r)$ and $\,\hbox{\vbox{\hrule height=0.66pt\kern 1.29167pt\hbox{\kern-1.00006pt$\mathbf{x}$\kern-1.00006pt}}}\,_{K}(r)$, respectively. For ease of exposition, the specification of the root node will be dropped, unless necessary to avoid confusion.

Of particular interest is the case of rooted $K$-balls obtained as the induced subgraph of the $K$-hop neighborhood of a node. More specifically, given a graph $\mathcal{G}=(\mathcal{V},\mathcal{E})$, a rooted $K$-ball $\,\hbox{\vbox{\hrule height=0.66pt\kern 1.29167pt\hbox{\kern-1.00006pt$\mathcal{G}$\kern-1.00006pt}}}\,_{K}$ can be constructed by selecting a node $r\in\mathcal{V}$, setting $\hbox{\vbox{\hrule height=0.66pt\kern 1.29167pt\hbox{\kern-1.00006pt$\mathcal{V}$\kern-1.00006pt}}}_{K}\equiv\mathcal{N}^{K}(r)$ and $\hbox{\vbox{\hrule height=0.66pt\kern 1.29167pt\hbox{\kern-1.00006pt$\mathcal{E}$\kern-1.00006pt}}}_{K}\equiv\mathcal{E}\cap\mathcal{N}^{K}(r)\times\mathcal{N}^{K}(r)$. In this context, the graph signal $\,\hbox{\vbox{\hrule height=0.66pt\kern 1.29167pt\hbox{\kern-1.00006pt$\mathbf{x}$\kern-1.00006pt}}}\,_{K}$ corresponding to the rooted $K$-ball can be tied to the graph signal $\mathbf{x}$ defined on $\mathcal{G}$ by setting $[\,\hbox{\vbox{\hrule height=0.66pt\kern 1.29167pt\hbox{\kern-1.00006pt$\mathbf{x}$\kern-1.00006pt}}}\,_{K}]_{v}=[{\mathbf{x}}]_{v}\ \text{for all}\ v\in\mathcal{N}^{K}(r)$.

We can now formalize the notion that a graph filter only relies on local information.

Proposition 1 formalizes the well-known fact that a $K$-tap graph filter evaluated at a node only depends on the subgraph of $K$-hops centered at that node (i.e., the ego-network of the node [22]). In this sense, it is not necessary to understand how a graph filter behaves on the global structure of a graph. Rather, one only needs to understand the behavior of a graph filter locally, in particular on the rooted $K$-balls of the graph. This naturally leads to a weaker form of the property of permutation equivariance, discussed next.

For two graphs $\mathcal{G}=(\mathcal{V},\mathcal{E})$ and $\mathcal{G}^{\prime}=(\mathcal{V}^{\prime},\mathcal{E}^{\prime})$, we say that a map $\phi:\mathcal{V}\to\mathcal{V}^{\prime}$ is a $K$-morphism if it preserves the structure of rooted $K$-balls for all nodes in $\mathcal{V}$. The structure of two rooted $K$-balls $\,\hbox{\vbox{\hrule height=0.66pt\kern 1.29167pt\hbox{\kern-1.00006pt$\mathcal{G}$\kern-1.00006pt}}}\,_{K}=(\hbox{\vbox{\hrule height=0.66pt\kern 1.29167pt\hbox{\kern-1.00006pt$\mathcal{V}$\kern-1.00006pt}}}_{K},\hbox{\vbox{\hrule height=0.66pt\kern 1.29167pt\hbox{\kern-1.00006pt$\mathcal{E}$\kern-1.00006pt}}}_{K},r)$ and $\,\hbox{\vbox{\hrule height=0.66pt\kern 1.29167pt\hbox{\kern-1.00006pt$\mathcal{G}$\kern-1.00006pt}}}\,^{\prime}_{K}=(\hbox{\vbox{\hrule height=0.66pt\kern 1.29167pt\hbox{\kern-1.00006pt$\mathcal{V}$\kern-1.00006pt}}}^{\prime}_{K},\hbox{\vbox{\hrule height=0.66pt\kern 1.29167pt\hbox{\kern-1.00006pt$\mathcal{E}$\kern-1.00006pt}}}^{\prime}_{K},r^{\prime})$ with signals $\,\hbox{\vbox{\hrule height=0.66pt\kern 1.29167pt\hbox{\kern-1.00006pt$\mathbf{x}$\kern-1.00006pt}}}\,_{K}$ and $\,\hbox{\vbox{\hrule height=0.66pt\kern 1.29167pt\hbox{\kern-1.00006pt$\mathbf{x}$\kern-1.00006pt}}}\,_{K}^{\prime}$, respectively, is preserved, if there exists an isomorphism $\psi:\mathcal{V}_{K}\to\mathcal{V}^{\prime}_{K}$ such that $\psi(r)=r^{\prime}$, $(\psi(u),\psi(v))\in\mathcal{E}^{\prime}_{K}$ if and only if $(u,v)\in\mathcal{E}_{K}$, and $[\,\hbox{\vbox{\hrule height=0.66pt\kern 1.29167pt\hbox{\kern-1.00006pt$\mathbf{x}$\kern-1.00006pt}}}\,_{K}]_{v}=[\,\hbox{\vbox{\hrule height=0.66pt\kern 1.29167pt\hbox{\kern-1.00006pt$\mathbf{x}$\kern-1.00006pt}}}\,_{K}^{\prime}]_{\psi(v)}$ for all $v\in\hbox{\vbox{\hrule height=0.66pt\kern 1.29167pt\hbox{\kern-1.00006pt$\mathcal{V}$\kern-1.00006pt}}}_{K}$. Then, a $K$-morphism $\phi:\mathcal{V}\to\mathcal{V}^{\prime}$ between two graphs $\mathcal{G}=(\mathcal{V},\mathcal{E})$ and $\mathcal{G}^{\prime}=(\mathcal{V}^{\prime},\mathcal{E}^{\prime})$ with associated signals $\mathbf{x}$ and $\mathbf{x}^{\prime}$, respectively, satisfies that the rooted $K$-balls $(\,\hbox{\vbox{\hrule height=0.66pt\kern 1.29167pt\hbox{\kern-1.00006pt$\mathcal{G}$\kern-1.00006pt}}}\,_{K}(v),\,\hbox{\vbox{\hrule height=0.66pt\kern 1.29167pt\hbox{\kern-1.00006pt$\mathbf{x}$\kern-1.00006pt}}}\,_{K}(v))$ and $(\,\hbox{\vbox{\hrule height=0.66pt\kern 1.29167pt\hbox{\kern-1.00006pt$\mathcal{G}$\kern-1.00006pt}}}\,_{K}^{\prime}(\phi(v)),\,\hbox{\vbox{\hrule height=0.66pt\kern 1.29167pt\hbox{\kern-1.00006pt$\mathbf{x}$\kern-1.00006pt}}}\,_{K}^{\prime}(\phi(v)))$ are isomorphic for all nodes $v\in\mathcal{V}$. Note that $K$-morphisms are not necessarily invertible, nor are they necessarily surjective.

Graph filters are invariant under $K$-morphisms, as it follows from Proposition 1, where we see that the same filter applied to two different graphs yields the same result if the local structures are the same.

Note that Corollary 1 is a generalization of the permutation equivariance property that graph filters have [7]. More generally, Corollary 1 opens up ways to compare the performance of a fixed graph filter across two different graphs with different associated graph signals. It would be expected then, that if two graphs have similar distributions of rooted $K$-balls with associated signal, then a fixed graph filter acting on one should yield similar results on the other. We formalize these notions in the ensuing discussion.

One of the key ideas in graph signal processing is that of the graph Fourier transform of a graph signal [2]. For a graph $\mathcal{G}=(\mathcal{V},\mathcal{E})$ on $n$ nodes, consider the GSO $\mathbf{S}$ to be the graph Laplacian, which is a positive semidefinite Hermitian matrix. Thus, it admits the following eigendecomposition

for eigenvalues $0=\lambda_{1}\leq\ldots\leq\lambda_{n}$ with corresponding pairwise orthogonal eigenvectors $\mathbf{u}_{1},\ldots,\mathbf{u}_{n}$. One can check that for any of these eigenvectors, $\langle\mathbf{u}_{j},\mathbf{S}\mathbf{u}_{j}\rangle=\lambda_{j}$. The graph Laplacian induces a quadratic form on a graph signal that measures a useful notion of smoothness [2]. For a given graph signal $\mathbf{x}$ on $\mathcal{G}$, the quadratic form can be shown to be equal to

That is, the quadratic form of the graph Laplacian measures the sum of the squared differences of the graph signal at neighboring pairs of nodes. A signal is called smooth if the quadratic form takes a small value relative to its norm. For instance, the eigenvectors of $\mathbf{S}$ with small corresponding eigenvalues are smooth signals.

We note that this notion of smoothness can be extended to normalized versions of the graph Laplacian in a similar fashion. Furthermore, a notion of smoothness can also be defined using the adjacency matrix [27]. In any case, for ease of exposition and conceptual simplicity, we assume that $\mathbf{S}$ is the graph Laplacian throughout this section, but we remark that the results derived herein are also valid for any other GSO built from adjacency rules that rely on the combinatorial structure of the graph.

Since the eigenvectors $\mathbf{u}_{1},\ldots,\mathbf{u}_{n}$ form an orthonormal basis for $\mathbb{R}^{n}$, any graph signal $\mathbf{x}$ admits a unique representation as a linear combination of the eigenvectors of $\mathbf{S}$. That is, for any graph signal $\mathbf{x}$, there exists a set of coefficients $\{\tilde{x}_{j}\}_{j=1}^{n}$ such that the following holds:

Thus, the representation of a graph signal as a weighted sum of the eigenvectors can be used to conveniently compute the quadratic form in terms of the spectrum. In an analogy to complex exponential functions being the eigenfunctions of the Laplace operator in discrete-time signal processing, we call the representation of the graph signal $\mathbf{x}$ by the coefficients $\tilde{x}_{j}$ the graph Fourier transform (GFT).

When coupled with their corresponding eigenvalues $\lambda_{j}$, the coefficients $\tilde{x}_{j}$ can be used to describe the distribution of energy in a graph signal, in a way concordant with the notion of smoothness described by the Laplacian quadratic form (11). To capture this, define the normalized power spectral distribution of a graph signal . Given a graph signal $\mathbf{x}$ with Fourier coefficients $\tilde{x}_{j}$ and corresponding Laplacian eigenvalues $0=\lambda_{1}\leq\ldots\leq\lambda_{n}$, define

One can easily see that $P_{\mathbf{x}}$ is a monotone, right-continuous function, with $P_{\mathbf{x}}(\lambda)=0$ for $\lambda<0$, and at most $n$ discontinuities (one at each eigenvalue $\lambda_{j}$). Moreover, there is a convenient expression for the moments of $P_{\mathbf{x}}$:

That is to say, the moments of the normalized power spectral distribution are given by scaled quadratic forms of powers of the GSO. Observe that the quadratic form (11) can be expressed as $\langle\mathbf{x},\mathbf{S}\mathbf{x}\rangle=n\cdot\mathbf{m}_{1}(\mathbf{x})$. Indeed, the moments of the graph Fourier transform are an essential quantity in the design of low-order graph filters [28]. This points to a very useful idea: the powers of the GSO are the most primitive types of graph filters, so the proposed local framework provides a path for understanding these moments in terms of functions on the space of distributions of rooted balls.

To see this, let us examine (15). Notice that

As before, let $\,\hbox{\vbox{\hrule height=0.66pt\kern 1.29167pt\hbox{\kern-1.00006pt$\mathbf{S}$\kern-1.00006pt}}}\,_{K}(v)$ be the GSO of the $K$-ball rooted at node $v$. By Proposition 1, the above equation can be written as

That is, the moments of the normalized power spectral distribution of a graph signal can be written as an average of operations that resemble local filtering. In the proposed local framework, this has the following interpretation.

Having reduced the moments of the normalized power spectral distribution to an average over the distribution of rooted balls, we can now reason about the convergence of graph Fourier distributions in terms of weak convergence of measure for graphs with bounded degree $D$. Although the limit of dense graphs has been considered before via graphon models [29, 30], this cannot capture the behavior of bounded degree graphs, as all infinite sequences of growing graphs of bounded degree converge to the zero graphon [31]. However, in the case of sparse graphs, understanding the descension of maps to the space $\Omega_{K}$ is a feasible approach, with the following compactness property.

The proof of Lemma 1 can be found in Appendix C. The constraint of a graph having bounded degree, for instance coming from physical constraints in a real-world system, corresponds to a compact description in the space $\Omega_{K}$. From this, the following convergence result holds.

The proof of Theorem 1 can be found in Appendix B. Theorem 1 casts the power spectral density of a graph signal in terms of the distribution of local structures in the graph. In particular, we treat the power spectral density as a function from graphs with graph signals to Borel measures on a compact subset of the real line, then prove that this function is continuous with respect to the distribution of rooted balls in the graph, where continuity is understood to be with respect to the weak topology for both the distribution in $\Omega_{K}$ and the power distribution of the signal. Although the frequency domain representation of a graph signal is typically understood to be a representation in terms of the global graph structure, owing to the global support of the graph Laplacian’s eigenvectors, this results indicates that it is in essence still subject to fundamentally local phenomena, namely the rooted balls in the graph.

This characterization of the power spectral distribution in terms of the distribution of rooted balls also reflects the local nature of graph filtering. Indeed, as discussed in [28], the moments of the power spectral distribution are key in the understanding of graph filters. More broadly, when designing a graph filter, we often aim to construct a matched filter in the frequency domain, so that the response of the filter aligns with that of the signal, subject to some noise model (additive white Gaussian noise, for instance). Additionally, constraints such as a filter having $K$ taps reduces the space of possible frequency responses to degree $K$ polynomials in the frequency domain, so that the moments become the basic values of interest. This is an immediate consequence of graph filters admitting a distributed implementation [28], so that the expression of a graph filter’s performance in terms of the power spectrum of the signal is actually a distillation of the distribution of rooted balls in $\Omega_{K}$.

We have shown how connecting the moments of the power spectral distribution to the space $\Omega_{K}$ yields insights about how features of graphs and graph signals are dependent only on localized information. In particular, a function $\hbox{\vbox{\hrule height=0.66pt\kern 1.29167pt\hbox{\kern-1.00006pt$\mathbf{m}$\kern-1.00006pt}}}_{K}:\Omega_{K}\to\mathbb{R}$ was constructed whose expected value under the pushforward measure of a graph computes the moments of the power spectral distribution. This machinery can be immediately extended to other functions on graphs that act locally, allowing us to compare the behavior of a given function on two graphs in terms of their distributions of rooted balls.

Let $J$ be a function mapping a graph and its corresponding graph signal to a real number. This function is typically known as a graph summary and examples include the graph power spectral distribution discussed in the previous section, as well as the average node degree or node centrality values [32], the clustering coefficient [33], or the conductance [34]. We can also consider cost functions for a given task as graph summaries, since they ultimately take a graph and its signal as input, and output a real number [35, 36]. In this context, we want to study how the function $J$ changes across two different graphs with different graph signals $(\mathcal{G}_{1},\mathbf{x}_{1})$ and $(\mathcal{G}_{2},\mathbf{x}_{2})$.

To study the transference of the graph summary $J$ across different graphs and graph signals, let us assume that there exists a function $\hbox{\vbox{\hrule height=0.66pt\kern 1.29167pt\hbox{\kern-1.00006pt$J$\kern-1.00006pt}}}:\Omega_{K}\to\mathbb{R}$ such that for any pair $(\mathcal{G},\mathbf{x})$ whose associated probability distribution on $\Omega_{K}$ is denoted by $\mu$, we have $J(\mathcal{G},\mathbf{x})=\mathbb{E}_{\mu}[\hbox{\vbox{\hrule height=0.66pt\kern 1.29167pt\hbox{\kern-1.00006pt$J$\kern-1.00006pt}}}]$. This assumption is not too severe, essentially saying that the graph summary is an average over a function on the nodes, with the value at each node determined strictly by the structure of its local neighborhood. Then, consider the transfer equation

as a way of measuring the transferability of $J$, and where $\mu$ and $\nu$ are the distributions of rooted balls on the space $\Omega_{K}$ of the graphs $(\mathcal{G}_{1},\mathbf{x}_{1})$ and $(\mathcal{G}_{2},\mathbf{x}_{2})$, respectively.

To understand (21) in a quantitative manner demands a stronger structure on $\Omega_{K}$ than the disjoint union topology. To this end, we then endow $\Omega_{K}$ with the structure of a metric space, in a way that preserves the original topology. For an arbitrary constant $C>0$, define a metric $d_{C}$ on $\Omega_{K}$ as follows. For $\omega_{1}=(\,\hbox{\vbox{\hrule height=0.66pt\kern 1.29167pt\hbox{\kern-1.00006pt$\mathcal{G}$\kern-1.00006pt}}}\,_{1},\,\hbox{\vbox{\hrule height=0.66pt\kern 1.29167pt\hbox{\kern-1.00006pt$\mathbf{x}$\kern-1.00006pt}}}\,_{1})$ and $\omega_{2}=(\,\hbox{\vbox{\hrule height=0.66pt\kern 1.29167pt\hbox{\kern-1.00006pt$\mathcal{G}$\kern-1.00006pt}}}\,_{2},\,\hbox{\vbox{\hrule height=0.66pt\kern 1.29167pt\hbox{\kern-1.00006pt$\mathbf{x}$\kern-1.00006pt}}}\,_{2})\in\Omega_{K}$, put

where $\|\cdot\|_{2}$ is inherited from the identification of $\mathbb{X}(\,\hbox{\vbox{\hrule height=0.66pt\kern 1.29167pt\hbox{\kern-1.00006pt$\mathcal{G}$\kern-1.00006pt}}}\,)$ with Euclidean space.²²2This metric is again understood modulo the automorphism group of the rooted ball, discussed in Appendix A. Note that $\|\cdot\|_{2}$ is well defined since both $\mathbf{x}_{1}$ and $\mathbf{x}_{2}$ are vectors in the same $|\hbox{\vbox{\hrule height=0.66pt\kern 1.29167pt\hbox{\kern-1.00006pt$\mathcal{V}$\kern-1.00006pt}}}|$-dimensional space when $\,\hbox{\vbox{\hrule height=0.66pt\kern 1.29167pt\hbox{\kern-1.00006pt$\mathcal{G}$\kern-1.00006pt}}}\,_{1}=\,\hbox{\vbox{\hrule height=0.66pt\kern 1.29167pt\hbox{\kern-1.00006pt$\mathcal{G}$\kern-1.00006pt}}}\,_{2}$. One can check that $d_{C}$ is indeed a metric on $\Omega_{K}$ for any $C>0$. The metric $d_{C}$ is constructed in a way that preserves the local metric structure of each signal space $\mathbb{X}(\,\hbox{\vbox{\hrule height=0.66pt\kern 1.29167pt\hbox{\kern-1.00006pt$\mathcal{G}$\kern-1.00006pt}}}\,)$, while also endowing the whole space $\Omega_{K}$ with a global metric structure, at the cost of some local distortion in order to maintain the triangle inequality, as dictated by the constant $C$. When $C$ is chosen to be very large, the local metric structure on each rooted ball of the space is well-preserved, but these rooted balls are otherwise kept “far apart” from each other. On the other hand, when $C$ is very small, the rooted balls become “close,” but the local metric structure on each of them is distorted (i.e. signals belonging to the same rooted ball that are beyond a distance of $2C$ are indistinguishable from signals that belong to different rooted balls). Importantly, the metric topology on $\Omega_{K}$ induced by $d_{C}$ is equal to the disjoint union topology (6), so that all notions of continuity and weak convergence of measure are preserved.

Given the additional metric structure on $\Omega_{K}$, we can quantitatively characterize the transfer equation (21) by comparing distributions of rooted balls on the metric space $(\Omega_{K},d_{C})$. To do so, we make the following assumption on the function  $J$ .

This is not a difficult assumption to satisfy. For instance, it is sufficient for  $J$ to be continuously differentiable on each signal space for this to hold. In fact, the set of Lipschitz continuous functions on a compact space is dense in the set of continuous functions with respect to the uniform norm [37].

The proof of Theorem 2 can be found in Appendix D. Theorem 2 bounds the transfer equation (21) in terms of the $1$-Wasserstein distance between the two distributions of rooted balls. The appearance of the $1$-Wasserstein distance in this setting is intuitive: the dual formulation of the $1$-Wasserstein distance defines the distance between two distributions via an integral probability metric over $1$-Lipschitz functions [38], yielding a transferability bound that holds for all Lipschitz functions. We illustrate the notion of the $1$-Wasserstein distance between graphs in Fig. 2.

In this section, we consider how ideas from the unweighted case (Sections 4 and 5) can be extended to weighted graphs. We define a weighted graph as a graph $\mathcal{G}=(\mathcal{V},\mathcal{E})$ coupled with a weight function $w:\mathcal{E}\to\mathbb{R}_{\geq 0}$. For a given graph $\mathcal{G}$, the set of all possible weight functions on it is denoted $\mathbb{W}(\mathcal{G})=\{w:\mathcal{E}\to\mathbb{R}_{\geq 0}\}$. We use the same notation for the set of weight functions on a rooted graph: $\mathbb{W}(\,\hbox{\vbox{\hrule height=0.66pt\kern 1.29167pt\hbox{\kern-1.00006pt$\mathcal{G}$\kern-1.00006pt}}}\,)$.

We now expand our definition of a rooted $K$-ball with a signal to include weight functions. Define

Similar to the definition of $\Omega_{K}$ in (6), the space $\Omega_{K}^{W}$ consists of all rooted $K$-balls with both edge weights and graph signals on them. As before, a weighted graph with a signal $(\mathcal{G},w,\mathbf{x})$ yields elements of $\Omega_{K}^{W}$ via a suitably defined sampling map $\Sigma_{K}$, defined for nodes $v\in\mathcal{V}$:

where $\hbox{\vbox{\hrule height=0.66pt\kern 1.29167pt\hbox{\kern-1.00006pt$w$\kern-1.00006pt}}}_{K}(v)$ denotes the restriction of $w$ to the edges of $\,\hbox{\vbox{\hrule height=0.66pt\kern 1.29167pt\hbox{\kern-1.00006pt$\mathcal{G}$\kern-1.00006pt}}}\,_{K}(v)$. As before, a given weighted graph with a signal defines a probability measure on $\Omega_{K}^{W}$ via the pushforward of the uniform measure by $\Sigma_{K}$, which we denote by $\mu=(\Sigma_{K})_{*}(\mathcal{G},w,\mathbf{x})$. For a weighted graph $(\mathcal{G},w)$, define the weighted degree of a node $v\in\mathcal{V}$ as follows:

The set of weighted graphs whose nodes have weighted degree at most $D$ is denoted by $\mathbb{G}^{W}_{D}$ for real number $D>0$.

We now develop a local description of the graph Fourier transform for weighted graphs, much like in Section 4. For a graph $\mathcal{G}=(\mathcal{V},\mathcal{E})$ with weight function $w$, define the weighted graph Laplacian as a shift operator such that, for any $u,v\in\mathcal{V}$,

The weighted Laplacian for a graph on $n$ nodes is positive semidefinite, and admits an eigendecomposition $\mathbf{S}=\sum_{j=1}^{n}\lambda_{j}\mathbf{u}_{j}\mathbf{u}_{j}^{\mathsf{T}}$, with a Fourier representation for graph signals defined in a way analogous to (12). For a given graph signal $\mathbf{x}\in\mathbb{X}(\mathcal{G})$, there is a power spectral distribution associated with $\mathbf{x}$ via the weighted Laplacian, whose moments are given by (15). We characterize the properties of the power spectral distribution in terms of the distribution of rooted $K$-balls in the following theorem.

The proof of Theorem 3 can be found in Appendix E. Theorem 3 establishes that the power spectral distribution of a graph signal on a weighted graph is continuous with respect to the weak topology of distributions of rooted $K$-balls, under boundedness assumptions. Unlike the regime of Theorem 1, the convergence of the power spectral distribution for weighted graphs here is not dependent on the combinatorial constraint of having bounded node degrees. Rather, any node may have an arbitrarily large number of neighbors, as long as the total influence remains bounded. This is a realistic assumption for many systems, where an agent may be allowed to exert influence on a large collection of other agents, but the total influence is bounded by some physical constraint, such as power consumption.

In Sections 5 and 6, the (weak) continuity of the power spectral density with respect to the distribution of rooted balls was established. Specifically, it was shown that weakly convergent sequences of distributions of rooted balls yielded weakly convergent power spectra. Given that these distributions correspond to underlying graphs, it remains to be established precisely what objects these sequences are converging to. In general, a weakly convergent sequence of finite graphs does not necessarily converge to a finite graph. When studying graph limits using graphon models, the homomorphism density of motifs is of primary concern [42]. This setting is slightly different, depending on the isomorphism density of rooted graphs. In this setting, a more appropriate model is that of a graphing. We show that the basic ideas in the discussion so far can be transferred directly to these limiting objects. Let us define the basic object of study for this section.

A graphing is a way to describe a graph with a potentially uncountable number of nodes (elements of $\mathcal{V}$), yet with bounded node degrees. We tacitly assume that all graphings considered are of degree $D$, for some $D\geq 1$. Unlike a graphon, which describes dense graphs with unbounded node degrees, the structures that arise from a graphing are typically sparse, and notions of graph filtering and graph shifts reduce to finite sums, rather than continuous integrals. Given a graphing $\mathbf{G}=(\mathcal{V},\mathcal{E},\lambda)$, a graphing signal is a map $\mathbf{x}:\mathcal{V}\to\mathbb{R}$ between the nodes $\mathcal{V}$ and the real numbers $\mathbb{R}$ such that $\mathbf{x}$ is a measurable function. Endowing this with the usual vector space structure, we define the space of graphing signals as

Much like how a graphon describes a model for dense random graphs, a graphing carries with it a distribution of random rooted graphs. As before, let $\mathcal{N}$ be the neighborhood operator, returning all of the one-hop neighbors of a node $v\in\mathcal{V}$, so that $\mathcal{N}^{K}$ is the $K$-hop neighborhood operator. For a graphing $\mathbf{G}=(\mathcal{V},\mathcal{E},\lambda)$ with associated signal $\mathbf{x}\in\mathbb{X}(\mathbf{G})$, the rooted $K$-ball at a node $r\in\mathcal{V}$ is defined in the same way as in Section 3, denoted by $\,\hbox{\vbox{\hrule height=0.66pt\kern 1.29167pt\hbox{\kern-1.00006pt$\mathcal{G}$\kern-1.00006pt}}}\,_{K}(r)$, with the same notation used to denote the corresponding graph signal $\,\hbox{\vbox{\hrule height=0.66pt\kern 1.29167pt\hbox{\kern-1.00006pt$\mathbf{x}$\kern-1.00006pt}}}\,_{K}(r)$. Due to the bounded degree condition on the graphing, $\,\hbox{\vbox{\hrule height=0.66pt\kern 1.29167pt\hbox{\kern-1.00006pt$\mathcal{G}$\kern-1.00006pt}}}\,_{K}(r)$ is always a finite rooted graph of maximum degree at most $D$. With this in mind, we define a sampling map $\Sigma_{K}:\mathcal{V}\to\Omega_{K}$ for graphings much like the sampling map (7) for finite graphs:

The sampling map $\Sigma_{K}$ is illustrated in Fig. 3 for a simple graphing. Much like for finite graphs, we can pushforward the measure $\lambda$ to yield a probability measure $\mu$ on $\Omega_{K}$. That is to say, $\mu=(\Sigma_{K})_{*}(\mathbf{G},\mathbf{x})$, in the same way as before, where we adopt $\lambda$ as the probability measure over $\mathcal{V}$ to be pushed forward. This differs slightly from the case of finite graphs, where we implicitly assume that the initial measure was the uniform probability measure on the finite node set.