# Local Measurement and Diffusion Reconstruction for Signals on a Weighted Graph

Authors: Yingchun Jiang; Ting Li
Journal: Mathematical Problems in Engineering
 (2018)

---

## Abstract

Bandlimited graph signals on an unweighted graph can be reconstructed by its local measurement, which is a generalization of decimation. Since most signals are weighted in real life, we extend and improve the iterative local measurement reconstruction (ILMR) by introducing the diffusion operators to reconstruct bandlimited signals on a weighted graph. We prove that the proposed reconstruction converges to the original signal. Moreover, the simulation results demonstrate that the improved algorithm has better convergence and has robustness against noise.


---

## Body

## 1. Introduction

In recent years, the demand for processing of large-scale datasets has been increasing, which has promoted the emerging field of signal processing on graphs. Graphs are useful tools for representing large-scale datasets with irregular geometric structures, in which data elements correspond to the vertices, the relationship between data elements is represented by the edge, and the strength of relationship is reflected in the edge weights. The graph signal can be regarded as a function defined on the graph which contains the spatial relationship of the vertices. Signal processing on graphs is an emerging field mainly solving problems in irregular domain [1], such as neuronal networks, social networks, sensor networks [2], image processing [3], and machine learning [4–6].Sampling and reconstruction play an important role in the processing of graph signals. Some results have been obtained in the sampling and reconstruction of bandlimited graph signals on an unweighted graph. Pesenson [7] put forward the concept of the uniqueness set and proved that bandlimited signals can be exactly reconstructed by samples on a uniqueness set. Based on the frame constructed by a uniqueness set, Narang [8] proposed the iterative least square reconstruction (ILSR) algorithm. However, since it is not easy to find the uniqueness set, Wang et al. gave the concept of local sets which are easy to be found by greedy algorithm [9]. Moreover, they proposed the iterative weighting reconstruction (IWR) and iterative propagating reconstruction (IPR) algorithms. Note that the unsampled vertices of a graph signal are influenced by all the sampled vertices, which should not be limited in the local sets. Based on a local-mean diffusion operator and a global-bias diffusion operator, Yang et al. [10] proposed the iterative global diffusion reconstruction (IGDR), which improved the IPR. In some potential applications, the obtained data may be a combination of signals associated with several vertices, Wang proposed the iterative local measurement reconstruction (ILMR) to reconstruct the bandlimited graph signals [11]. Since most graphs are weighted in real life and local measurement is more reasonable in practice, such as sensor networks with clustering structure, we mainly generalize the ILMR algorithm to weighted graphs and improve its performance by introducing some diffusion operators.This paper is organized as follows. In Section2, some preliminaries on weighted graphs are introduced and the iterative local measurement reconstruction algorithm is reviewed. In Section 3, we propose some diffusion operators associated with centerless local sets and give an iterative local measurement and diffusion reconstruction algorithm. In Section 4, some simulation experiments are presented for both the synthetic and real-world data.


## 2. Preliminaries

In this section, we will introduce the concepts of weighted graphs, graph Fourier transform, and the iterative local measurement reconstruction.


### 2.1. Weighted Graph

A weighted graphG={V,E,W} is composed of a set of vertices V, a set of edges E, and a weight function W:E→R+ which assigns a positive weight to each of the edges. In this paper, we just consider the finite graph of N vertices, where |V|=N<∞.For an undirected weighted graphG={V,E,W}, its Laplacian matrix [12] is defined as L=D-A, where A is the adjacency matrix of G with elements (1)au,v=wu,v,u~v∈E0,otherwise.u~v denotes a side directly connecting nodes u and v. D is the diagonal degree matrix, whose entries are the degree of the corresponding vertices. For a weighted graph, the degree d(u) of each vertex u is defined as (2)du=∑v=1Nau,v.


### 2.2. Graph Fourier Transform and Bandlimited Graph Signals

Suppose{λk}1⩽k⩽N are the eigenvalues and {uk}1⩽k⩽N are corresponding eigenvectors of the Laplacian matrix L. For graph Fourier transform [13], the eigenvectors {uk}1⩽k⩽N are considered as the Fourier basis of the frequency-domain, and eigenvalues {λk}1⩽k⩽N are regarded as frequencies. The graph Fourier transform is defined by (3)f^k=f,uk=∑i=1Nfiuki,where f(i) denotes the entry of f associated with vertex i. Similarly, the inverse Fourier transform can be defined as (4)f=∑k=1Nf^kuk.A graph signalf is ω-bandlimited if (5)f∈PWωG≜spanui∣λi≤ω.That is, the frequency components corresponding to eigenvalues larger than ω are all zero. The subspace PWω(G) of ω-bandlimited signals on graph G is a Hilbert space called Paley-Wiener space [14].


### 2.3. Iterative Local Measurement Reconstruction

In this subsection, we will introduce the iterative local measurement reconstruction algorithm given in [11].Step 1 (centerless local sets).
For a weighted graphG=V,E,W, V is divided into disjoint local sets {Ni}i∈I, which satisfy (6)⋃i∈INi=V,Ni∩Nj=∅∀i,j∈I,i≠j.Step 2 (local measurement).
A local weightφi∈RN associated with a centerless local set Ni satisfies (7)φiv>0,v∈Ni=0,v∉Ni,∑v∈Niφiv=1.Then a set of local measurements for a graph signal is {〈f,φi〉}i∈I.Step 3 (ILMR).
The iterative process of iterative local measurement reconstruction (ILMR) is(8)f0=Pω∑i∈If,φiδNifk+1=fk+Pω∑i∈If-fk,φiδNi,where Pω is an orthogonal projection on PWω(G), and δNi is defined as (9)δNiv=1,v∈Ni0,v∉Ni.


## 2.1. Weighted Graph

A weighted graphG={V,E,W} is composed of a set of vertices V, a set of edges E, and a weight function W:E→R+ which assigns a positive weight to each of the edges. In this paper, we just consider the finite graph of N vertices, where |V|=N<∞.For an undirected weighted graphG={V,E,W}, its Laplacian matrix [12] is defined as L=D-A, where A is the adjacency matrix of G with elements (1)au,v=wu,v,u~v∈E0,otherwise.u~v denotes a side directly connecting nodes u and v. D is the diagonal degree matrix, whose entries are the degree of the corresponding vertices. For a weighted graph, the degree d(u) of each vertex u is defined as (2)du=∑v=1Nau,v.


## 2.2. Graph Fourier Transform and Bandlimited Graph Signals

Suppose{λk}1⩽k⩽N are the eigenvalues and {uk}1⩽k⩽N are corresponding eigenvectors of the Laplacian matrix L. For graph Fourier transform [13], the eigenvectors {uk}1⩽k⩽N are considered as the Fourier basis of the frequency-domain, and eigenvalues {λk}1⩽k⩽N are regarded as frequencies. The graph Fourier transform is defined by (3)f^k=f,uk=∑i=1Nfiuki,where f(i) denotes the entry of f associated with vertex i. Similarly, the inverse Fourier transform can be defined as (4)f=∑k=1Nf^kuk.A graph signalf is ω-bandlimited if (5)f∈PWωG≜spanui∣λi≤ω.That is, the frequency components corresponding to eigenvalues larger than ω are all zero. The subspace PWω(G) of ω-bandlimited signals on graph G is a Hilbert space called Paley-Wiener space [14].


## 2.3. Iterative Local Measurement Reconstruction

In this subsection, we will introduce the iterative local measurement reconstruction algorithm given in [11].Step 1 (centerless local sets).
For a weighted graphG=V,E,W, V is divided into disjoint local sets {Ni}i∈I, which satisfy (6)⋃i∈INi=V,Ni∩Nj=∅∀i,j∈I,i≠j.Step 2 (local measurement).
A local weightφi∈RN associated with a centerless local set Ni satisfies (7)φiv>0,v∈Ni=0,v∉Ni,∑v∈Niφiv=1.Then a set of local measurements for a graph signal is {〈f,φi〉}i∈I.Step 3 (ILMR).
The iterative process of iterative local measurement reconstruction (ILMR) is(8)f0=Pω∑i∈If,φiδNifk+1=fk+Pω∑i∈If-fk,φiδNi,where Pω is an orthogonal projection on PWω(G), and δNi is defined as (9)δNiv=1,v∈Ni0,v∉Ni.


## 3. Improved Local Measurement Reconstruction

In this section, we propose some diffusion operators associated with centerless local sets and give an iterative local measurement and diffusion reconstruction algorithm.


### 3.1. The Proposed Diffusion Operators

Definition 1 (diffusion operators).
For a given reconstructed residualfis (if fis is the reconstructed residual of kth step, then fis=f-fk,φiδNi) of ith centerless local sets, we define the diffusion operator Pd,Ni as (10)Pd,Nifis=ui′ui′′Tfis,where ui′ denotes the modified Laplacian eigenvector matrix in which the rows corresponding to the vertices of ith centerless local sets are set to the zero sequence and the columns corresponding to out of the bandwidth ω are set to the zero sequence, and ui′′ denotes the modified Laplacian eigenvector matrix in which the rows corresponding to the vertices out of the ith centerless local sets are set to the zero sequence and the columns corresponding to out of the bandwidth ω are set to the zero sequence.Example 2.
As shown in Figure1, assume that we have three centerless local sets Ni, i=1,2,3, and the bandwidth λ3≤ω<λ4.
By Definition1, we obtain (11)u1′=000000000000u13u23u33000u14u24u34000u15u25u35000u16u26u36000,u1′′=u11u21u31000u12u22u32000000000000000000000000000
Suppose thatf1s is the reconstructed residual in the kth step, and then (12)Pd,N1f1s=u1′u1′′Tf1s=u11u13+u21u23+u31u33+u12u13+u22u23+u32u33δ3+u11u14+u21u24+u31u34+u12u14+u22u24+u32u34δ4+u11u15+u21u25+u31u35+u12u15+u22u25+u32u35δ5+u11u16+u21u26+u31u36+u12u16+u22u26+u32u36δ6f-fk,φ1Figure 1
A weighted graph with three centerless local sets.As the above example shows, the diffusion is to transmit the local measurement error of some centerless local set to all other vertices out of this centerless local set.


### 3.2. Iterative Local Measurement and Diffusion Reconstruction

In this subsection, we give a new reconstruction method based on local measurement and diffusion operators, which is iterative local measurement and diffusion reconstruction (ILMDR). The proposed algorithm can be written as follows:(13)f0=Pω∑i∈If,φiδNi+Pω∑i∈IPd,Nif,φiδNifk+1=fk+Pω∑i∈If-fk,φiδNi+Pω∑i∈IPd,Nif-fk,φiδNi.Theorem 3.
For given centerless local sets and the associated local weights{(Ni,φi)}i∈I, suppose that ωmin is the smallest weight on the graph G=V,E,W, PNi is the sampling operator on local set Ni, and Di0:=maxu,v∈Nidist0u,v is the maximal number of edges in Ni, where dist0u,v denotes the number of edges in the shortest path connecting u and v. If (14)r≔Cmaxωωmin+∑i∈IφiPωI-PNiPωδNi<1,where Cmax=maxi∈I|Ni|Di0, then any signals f∈PWω(G) can be reconstructed by algorithm (13), with the error at the kth iteration satisfying (15)f-fk≤rkf-f0.Proof.
The proof is postponed to the Appendix.


## 3.1. The Proposed Diffusion Operators

Definition 1 (diffusion operators).
For a given reconstructed residualfis (if fis is the reconstructed residual of kth step, then fis=f-fk,φiδNi) of ith centerless local sets, we define the diffusion operator Pd,Ni as (10)Pd,Nifis=ui′ui′′Tfis,where ui′ denotes the modified Laplacian eigenvector matrix in which the rows corresponding to the vertices of ith centerless local sets are set to the zero sequence and the columns corresponding to out of the bandwidth ω are set to the zero sequence, and ui′′ denotes the modified Laplacian eigenvector matrix in which the rows corresponding to the vertices out of the ith centerless local sets are set to the zero sequence and the columns corresponding to out of the bandwidth ω are set to the zero sequence.Example 2.
As shown in Figure1, assume that we have three centerless local sets Ni, i=1,2,3, and the bandwidth λ3≤ω<λ4.
By Definition1, we obtain (11)u1′=000000000000u13u23u33000u14u24u34000u15u25u35000u16u26u36000,u1′′=u11u21u31000u12u22u32000000000000000000000000000
Suppose thatf1s is the reconstructed residual in the kth step, and then (12)Pd,N1f1s=u1′u1′′Tf1s=u11u13+u21u23+u31u33+u12u13+u22u23+u32u33δ3+u11u14+u21u24+u31u34+u12u14+u22u24+u32u34δ4+u11u15+u21u25+u31u35+u12u15+u22u25+u32u35δ5+u11u16+u21u26+u31u36+u12u16+u22u26+u32u36δ6f-fk,φ1Figure 1
A weighted graph with three centerless local sets.As the above example shows, the diffusion is to transmit the local measurement error of some centerless local set to all other vertices out of this centerless local set.


## 3.2. Iterative Local Measurement and Diffusion Reconstruction

In this subsection, we give a new reconstruction method based on local measurement and diffusion operators, which is iterative local measurement and diffusion reconstruction (ILMDR). The proposed algorithm can be written as follows:(13)f0=Pω∑i∈If,φiδNi+Pω∑i∈IPd,Nif,φiδNifk+1=fk+Pω∑i∈If-fk,φiδNi+Pω∑i∈IPd,Nif-fk,φiδNi.Theorem 3.
For given centerless local sets and the associated local weights{(Ni,φi)}i∈I, suppose that ωmin is the smallest weight on the graph G=V,E,W, PNi is the sampling operator on local set Ni, and Di0:=maxu,v∈Nidist0u,v is the maximal number of edges in Ni, where dist0u,v denotes the number of edges in the shortest path connecting u and v. If (14)r≔Cmaxωωmin+∑i∈IφiPωI-PNiPωδNi<1,where Cmax=maxi∈I|Ni|Di0, then any signals f∈PWω(G) can be reconstructed by algorithm (13), with the error at the kth iteration satisfying (15)f-fk≤rkf-f0.Proof.
The proof is postponed to the Appendix.


## 4. The Simulation Results

In this paper, we choose the simulation data and real data to analyze the performance of the proposed algorithm, which is evaluated from convergence rate and robustness against additive noise. In the simulation data, we choose the Minnesota path graph [15] with 700 vertices. In real data, we choose the data structure diagram of air quality index (AQI) [16] of the 31 capital cities in China and the temperature (2017.10.1) data [17, 18] of 80 cities of Guangdong province and Guangxi province of China. Since all the selected graphs are unweighted, we take random numbers in [0.5,1] as the weights on the edges of the corresponding graph. Moreover, we use greedy method to partition centerless local sets with maximal cardinality Nmax=maxi∈I|Ni|. Three kinds of weights for local measurement are considered(1)
uniform weight, whereφiv=1/|Ni|,∀v∈Ni;(2)
random weight, whereφiv=φi′v/∑u∈Niφi′(u),∀v∈Ni,φi′(u)~U(0,1);(3)
supposing that the observed signal associated with each vertex is corrupted by additive noise. If noises associated with vertices are independent and follow zero-mean Gaussian distributionsnv~N0,σ2v, the optimal weight [11] is (16)φiv=σ2v-1∑v∈Niσ2v-1,∀v∈Ni.


### 4.1. The Convergence Performance for the Selection of Maximal CardinalityNmax

The convergence of the proposed algorithm is verified for various of partition of centerless local sets. The Minnesota path graph is divided into 244, 192, and 150 centerless local sets forNmax being 3, 4, and 5, respectively. The local weights are tested including cases (1) and (2). As shown in Figure 2, the convergence is accelerated when the graph is divided into more local sets and has a smaller Nmax. Moreover, the proposed ILMDR algorithm always convergences faster than the ILMR algorithm for both local weights.Figure 2
The convergence behavior of ILMR and ILMDR for various division of centerless local sets with uniform weight (left) and random weight (right).


### 4.2. Robustness against Gaussian Noise

We assume that the observation of the sampled signals is corrupted by noise, and the independent zero-mean Gaussian noise is added to each vertex with different variance. All of the vertices are randomly divided into three groups with the standard deviations of the noise chosen as1×10-4, 2×10-4, and 5×10-4, respectively. The performance of the proposed algorithm against independent zero-mean Gaussian noise is tested for three kinds of local weights including cases (1), (2), and (3). The graph is partitioned into 150 centerless local sets with Nmax equaling 5. The robustness of the proposed algorithm is given in the left side of Figure 3, which shows that the steady-state relative error for the uniform weight is smaller than those of random weight and optimal weight.Figure 3
The robustness of ILMDR against noise.For the special case of independent and identically distributed Gaussian noise, the robustness of the proposed algorithm against noise with different SNR is considered. It demonstrates in the right side of Figure3 that ILMDR has almost the same performance for three kinds of local weights.


### 4.3. The Analysis of Real Data

In this experiment, we use real data to test the performance of the proposed ILMDR algorithm. As an example of real data, we adopt the day’s AQI of 31 capital cities in October1, 2017. We represent these capital cities by an undirected two-nearest neighbor graph as in Figure 4(a), in which every capital city corresponds to a vertex and two cities are connected by an edge if their AQI are close. The cut-off frequency considered here is 0.5. Another example of real data is the daily temperature data of 80 cities of Guangdong province and Guangxi province in October 1, 2017. The graph in Figure 4(b) is randomly generated from the 80 cities under the requirement that the degree of each node is not more than 3. The graph cut-off frequency is set to be 0.65. We can see from Figure 5 that the ILMDR algorithm has much faster convergence than the ILMR algorithm for both local weights.Figure 4
Graphs of real data.
(a)
The capital cities of China (b)
The temperature data graph of Guangdong province and Guangxi provinceFigure 5
The convergence behavior of ILMR and ILMDR for air quality index (AQI) (up) and temperature data (down) with uniform weight (left) and random weight (right).


## 4.1. The Convergence Performance for the Selection of Maximal CardinalityNmax

The convergence of the proposed algorithm is verified for various of partition of centerless local sets. The Minnesota path graph is divided into 244, 192, and 150 centerless local sets forNmax being 3, 4, and 5, respectively. The local weights are tested including cases (1) and (2). As shown in Figure 2, the convergence is accelerated when the graph is divided into more local sets and has a smaller Nmax. Moreover, the proposed ILMDR algorithm always convergences faster than the ILMR algorithm for both local weights.Figure 2
The convergence behavior of ILMR and ILMDR for various division of centerless local sets with uniform weight (left) and random weight (right).


## 4.2. Robustness against Gaussian Noise

We assume that the observation of the sampled signals is corrupted by noise, and the independent zero-mean Gaussian noise is added to each vertex with different variance. All of the vertices are randomly divided into three groups with the standard deviations of the noise chosen as1×10-4, 2×10-4, and 5×10-4, respectively. The performance of the proposed algorithm against independent zero-mean Gaussian noise is tested for three kinds of local weights including cases (1), (2), and (3). The graph is partitioned into 150 centerless local sets with Nmax equaling 5. The robustness of the proposed algorithm is given in the left side of Figure 3, which shows that the steady-state relative error for the uniform weight is smaller than those of random weight and optimal weight.Figure 3
The robustness of ILMDR against noise.For the special case of independent and identically distributed Gaussian noise, the robustness of the proposed algorithm against noise with different SNR is considered. It demonstrates in the right side of Figure3 that ILMDR has almost the same performance for three kinds of local weights.


## 4.3. The Analysis of Real Data

In this experiment, we use real data to test the performance of the proposed ILMDR algorithm. As an example of real data, we adopt the day’s AQI of 31 capital cities in October1, 2017. We represent these capital cities by an undirected two-nearest neighbor graph as in Figure 4(a), in which every capital city corresponds to a vertex and two cities are connected by an edge if their AQI are close. The cut-off frequency considered here is 0.5. Another example of real data is the daily temperature data of 80 cities of Guangdong province and Guangxi province in October 1, 2017. The graph in Figure 4(b) is randomly generated from the 80 cities under the requirement that the degree of each node is not more than 3. The graph cut-off frequency is set to be 0.65. We can see from Figure 5 that the ILMDR algorithm has much faster convergence than the ILMR algorithm for both local weights.Figure 4
Graphs of real data.
(a)
The capital cities of China (b)
The temperature data graph of Guangdong province and Guangxi provinceFigure 5
The convergence behavior of ILMR and ILMDR for air quality index (AQI) (up) and temperature data (down) with uniform weight (left) and random weight (right).


## 5. Conclusion

Most graphs are weighted graphs in real life, so this paper mainly studies the sampling and reconstruction of bandlimited signals on a weighted graph. We propose a new definition of diffusion operators, where the diffusion is to transmit the local measurement error of some centerless local set to all other vertices out of this centerless local set. Based on the local measurement and the proposed diffusion operators, an iterative local measurement and diffusion reconstruction method is given to reconstruct the missing data from the observed local samples. We also present the analysis of the convergence for the proposed algorithm. Moreover, the numerical results demonstrate that the original iterative local measurement reconstruction algorithm can still be used for the reconstruction of weighted graphs. However, our improved algorithm has better convergence and also has noise resistance.



---

*Source: 3264294-2018-07-19.xml*