Local-set-based Graph Signal Reconstruction

1 Introduction

In recent years, the increasing demands for signal and information processing in irregular domains have resulted in an emerging field of signal processing on graphs. Bringing a new perspective for analyzing data associated with graphs, graph signal processing has found potential applications in sensor networks, image processing, semi-supervised learning, and recommendation systems. Smooth signals or approximately smooth signals over graph are common in practical applications. Exploiting the smoothness of a graph signal, it may be reconstructed through its entries on only a part of the vertices, i.e. samples of the graph signal.

In this work, we develop efficient methods to solve the problem of reconstructing a bandlimited graph signal from known samples. The smooth signal is supposed to be within a low-frequency subspace. Based on a new concept of local set, two iterative algorithms named as iterative weighting reconstruction (IWR) and iterative propagating reconstruction (IPR) are proposed to recover the missing entries from known sampled data.

This work has been published at IEEE Transactions on Signal Processing 63(9): 2432-2444, 2015 in the paper Local-set-based Graph Signal Reconstruction by Xiaohan Wang, Pengfei Liu, and Yuantao Gu.

2 Notations

An undirected graph is denoted as $\mathcal{G}(\mathcal{V}, \mathcal{E})$, where $\mathcal{V}$ denotes a set of $N$ vertices and $\mathcal{E}$ denotes the edge set. If one real number is associated with each vertex, these numbers of all the vertices are collectively referred as a graph signal. A graph signal can also be regarded as a mapping $f: \mathcal{V}\rightarrow \mathbb{R}$. Similar with classical Fourier analysis, eigenvalues $\{\lambda_k\}$ of the Laplacian of $\mathcal{G}$ are regarded as frequencies of the graph, and the corresponding eigenvectors $\{{\bf u}_k\}$ is regarded as the Fourier basis. A graph signal ${\mathbf f}\in\mathbb{R}^N$ is called $\omega$-bandlimited if its spectral support is within $[0,\omega]$. The subspace of $\omega$-bandlimited signals on $\mathcal{G}$ is denoted as $PW_{\omega}(\mathcal{G})$. Suppose that for a bandlimited graph signal ${\mathbf f}\in PW_{\omega}(\mathcal{G})$, only $\{f(u)\}_{u\in \mathcal{S}}$ on the sampling set $\mathcal{S}\subseteq \mathcal{V}$ are known, the problem is to obtain the original signal ${\mathbf f}$ from the sampled data.

Iterative Reconstruction Algorithms

For a sampling set $\mathcal{S}$ on graph $\mathcal{G}(\mathcal{V},\mathcal{E})$, assume that $\mathcal{V}$ is divided into disjoint local sets $\{\mathcal{N}(u)\}_{u\in \mathcal{S}}$ associated with the sampled vertices. For each $u\in\mathcal{S}$, denote the subgraph of $\mathcal{G}$ restricted to $\mathcal{N}(u)$ by $\mathcal{G}_{\mathcal{N}(u)}$, which is composed of vertices in $\mathcal{N}(u)$ and edges between them in $\mathcal{E}$. For each $u\in\mathcal{S}$, its local set satisfies $\mathcal{N}(u)\ni u$, and the subgraph $\mathcal{G}_{\mathcal{N}(u)}$ is connected.  Besides, $\{\mathcal{N}(u)\}_{u\in \mathcal{S}}$ should satisfy $\bigcup_{u\in \mathcal{S}} \mathcal{N}(u)=\mathcal{V}$, $\mathcal{N}(u)\cap \mathcal{N}(v)=\emptyset$ for $u, v\in\mathcal{S}$ and $u\neq v$.

Based on the definition of local set, we could prove that the set of lowpass $\delta$-functions and its two variations are frames for $PW_{\omega}(\mathcal{G})$, and their bounds are given in the following Table I.

Using the frames, two reconstruction algorithms are proposed.

Proposition 1 (Iterative Weighting Reconstruction): For a given sampling set $\mathcal S$ and associated local sets $\{\mathcal{N}(u)\}_{u\in\mathcal{S}}$ on a graph $\mathcal{G}(\mathcal{V},\mathcal{E})$, $\forall {\mathbf f}\in PW_{\omega}(\mathcal{G})$, where $\omega<1/Q_{\rm max}^2$, ${\bf f}$ can be reconstructed by the sampled data $\{f(u)\}_{u\in \mathcal{S}}$ through IWR

$${\bf f}^{(k+1)}={\bf f}^{(k)}+\frac{1}{1+\gamma^2}\mathcal{P}_{\omega}\left(\sum_{u\in \mathcal{S}}|\mathcal{N}(u)|(f(u)-f^{(k)}(u)){\delta}_{u}\right)$$

with the error bound satisfying

$$\|{\mathbf f}^{(k)}-{\mathbf f}\|\le \left(\frac{2\gamma}{1+\gamma^2}\right)^{k}\|{\mathbf f}^{(0)}-{\mathbf f}\|,$$

where $\gamma =Q_{\rm max}\sqrt{\omega}$ and $Q_{\rm max}$ is determined by the division of local sets.

Proposition 2 (Iterative Propagating Reconstruction): For a given sampling set $\mathcal S$ and associated local sets $\{\mathcal{N}(u)\}_{u\in\mathcal{S}}$ on a graph $\mathcal{G}(\mathcal{V},\mathcal{E})$, $\forall {\mathbf f}\in PW_{\omega}(\mathcal{G})$, where $\omega<1/Q_{\rm max}^2$, ${\mathbf f}$ can always be reconstructed by its samples $\{f(u)\}_{u\in \mathcal{S}}$ through IPR

$${\mathbf f}^{(k+1)}={\mathbf f}^{(k)}+\mathcal{P}_{\omega}\left(\sum_{u\in \mathcal{S}}(f(u)-f^{(k)}(u)){\delta}_{\mathcal{N}(u)}\right)$$

with the error bound satisfying

$$\|{\mathbf f}^{(k)}-{\mathbf f}\|\le \gamma^{k}\|{\mathbf f}^{(0)}-{\bf f}\|.$$

Figure 1: Illustration of the iterations of the three algorithms. Compared with ILSR, IPR needs to assign the residuals on the sampled vertices to the vertices in the local set, while IWR needs to multiply the residuals on the sampled vertices by different weights.

As illustrated in Fig. 1, the differences among IWR, IPR, and an existing algorithm ILSR lie in the way of their dealing with the residuals at the sampled vertices. In each iteration the sampled residual $\sum_{u\in\mathcal{S}}(f(u)-f^{(k)}(u)){\delta}_u$ is directly projected onto the $\omega$-bandlimited space $PW_{\omega}(\mathcal{G})$ in ILSR. In IWR, the sampled residuals are multiplied by weights $|\mathcal{N}(u)|$ and then projected onto the low-frequency space. For IPR, the sampled residuals are copied and assigned to the vertices in the corresponding local sets and then the projection procedure is conducted.

Relationship with Time Domain Results

Bandlimited signal sampling and reconstruction on graph is closely related to irregular sampling or nonuniform sampling in the time domain, which sheds light on the analysis of graph signal. There have existed several iterative reconstruction methods and theoretically analysis of time-domain irregular sampling. By exploiting the similarities between time-domain irregular sampling and graph signal sampling, some results of this work have consistent formulation with the corresponding results in the time domain. The reconstruction methods also have correspondences in the time domain.

Results on time-domain irregular sampling show that $\{\mathcal{T}_{t_i}{\rm sinc}_{\Omega}\}_{t_i\in\mathcal{S}}$ is a frame for $\mathcal{B}_{\Omega}^2$ if the sampling set $\mathcal{S}$ satisfies some particular conditions, where $\mathcal{T}_{t_i}f(t)=f(t-t_i)$ denotes the translation of $f(t)$, ${\rm sinc}_{\Omega}$ denotes the sinc function whose bandwidth is $\Omega$ and $\mathcal{B}_{\Omega}^2$ denotes the space of $\Omega$-bandlimited square integrable signal.

Correspondingly, for the graph signal ${\mathbf f}\in PW_{\omega}(\mathcal{G})$, $\{\mathcal{P}_{\omega}({\delta}_u)\}_{u\in\mathcal{S}}$ is a frame under some conditions. The result is consistent with that in the time domain. The correspondence between irregular sampling in the time domain and that on graph is illustrated in Fig. 2. In the graph signal sampling problem, $\{\mathcal{P}_{\omega}({\delta}_u)\}_{u\in\mathcal{S}}$ corresponds to the frame $\{\mathcal{T}_{t_i}{\rm sinc}_{\Omega}\}_{t_i\in\mathcal{S}}$ in the time domain. The essence of the two problem is very similar and theoretical results on sampling and reconstruction of graph signals can be obtained enlightened by irregular sampling in the time domain.

Figure 2: The correspondence between irregular sampling in the time domain and that on graph.

Both $\mathcal{T}_{t_i}{\rm sinc}_{\Omega}$ and $\mathcal{P}_{\omega}({\delta}_u)$ are the projections of $\delta$-functions onto bandlimited spaces. Under certain conditions, for all the sampled points or vertices, these kinds of signals $\{\mathcal{T}_{t_i}{\rm sinc}_{\Omega}\}_{t_i\in\mathcal{S}}$ and $\{\mathcal{P}_{\omega}({\delta}_u)\}_{u\in\mathcal{S}}$ become frames. Consequently, the original signals can be reconstructed by the sampled data.

The ideas of graph signal reconstruction algorithms ILSR, IWR and IPR have correspondences in time-domain, which are shown in Table II.

5 Numerical Results

The Minnesota road graph is chosen as the graph, which has $2640$ vertices and $6604$ edges, to test the proposed reconstruction algorithms. The bandlimited signal is generated by first generating a random signal and then removing its high-frequency components. A one-hop sampling set is chosen as the sampling set. This sampling set has $872$ vertices, which is about one third of all. The cutoff frequency is $0.25$. The convergence curves of ILSR, IWR, and IPR are illustrated in Fig. 3. It is obvious that the convergence rate of the proposed algorithms is significantly improved compared with the reference. Furthermore, IPR is better than IWR on the convergence rate.

Figure 3: Convergence curves of ILSR, IWR, and IPR.