APPROXIMATING SIGNALS SUPPORTED ON GRAPHS

Xiaofan Zhu and Michael Rabbat

Department of Electrical and Computer Engineering, McGill University

3480 University St, Montreal QC, Canada H3A 2A7

ABSTRACT the GFT. Those properties imply that if the eigenvalues of a graphs
Laplacian matrix roughly maintain an increasing trend, then smooth
In this paper, we investigate the notion of smoothness for signals signals on that graph are likely to be compressible.
supported on the vertices of a graph. We provide theoretical expla- The rest of this paper is organized as follows: In Section 2, the
nations when and why the Laplacian eigenbasis can be regarded as notion of smoothness for signals supported on graphs is defined and
a meaningful Fourier transform of such signals. Moreover, we we derive certain properties of the GFT. Based on these properties,
analyze the desired properties of the underlying graphs for better we give rules of thumb for generating graphs where the signal is
compressibility of the signals. We verify our theoretical work by compressible. In Section 3, we conduct experiments on real world
experiments on real world data. data to verify our GFT theory, and we conclude in Section 4.
Index Terms Graph Laplacian, Fourier transform, smooth-
ness, compressibility 2. THE GRAPH FOURIER TRANSFORM

1. INTRODUCTION 2.1. Properties of the Fourier Transform

The Fourier transform is a mathematical operation that decomposes
Signals on graphs are now common in various applications rang-
a signal into its constituent frequencies. It plays an important role
ing from biological signal processing to network monitoring and the
in the area of signal processing. In this subsection, we will review
smart grid. For example, in field estimation [1, 2], a large number of
some of the important properties of the Fourier transform.
wireless sensors are distributed randomly in a field to collect mea-
surements, such as temperature or solar radiation, where the whole Definition 1. For a continuous differentiable function f , the total
R +
sensor network can be modeled as a random geometric graph. In variation is defined as kf kV = |f 0 (t)|dt, where f 0 (t) is the
computer graphics, the shape of a 3D object can be approximated P
derivative, and kf kV = n |f (n) f (n 1)| for discrete signals.
by a regular graph, with its nodes containing the coordinate infor- We say that f has a bounded variation if kf kV < +.
mation [3, 4]. In the traditional realm of signal processing, we are
interested in approximating a certain function by a simpler one and Total variation measures the total amplitude of signal oscilla-
approximation theory has been well developed. So far approxima- tions. It plays an important role in signal processing since it im-
tion theory has focused on 1D signals and 2D images, while less pacts the decaying behavior of its Fourier coefficients. If a sig-
work has considered signals on graphs. Thus, a general question one nal f is Psquare integrable over [0, 1], we can decompose a signal
+ i2mu
might ask is: how can we approximate signals supported on graphs? f (t) = m= |hf (u), e i|ei2mt with hf (u), ei2mu i =
To address this problem, first let us delve into traditional approx- R1
f (u)ei2mu
du. Then the M -term Fourier approximation is
0
imation theory. It is well known that the Fourier transform plays a
fM = |m|<M/2 |hf (u), ei2mu i|ei2mt .
P
core role in this area. Moreover, the idea that any arbitrary periodic
function can be represented as a series of harmonically related sinu- Definition 2. M-term Linear Fourier Approximation Error: l (M, f ) =
soids has a profound impact in mathematical analysis, physics, and P i2mu 2
|m|>M/2 |hf (u), e i| .
engineering. In signal processing, it has been shown that a smooth
signal can be well approximated by a small portion of its Fourier co- The linear approximation keeps the M lowest frequency compo-
efficients because of compressibility. Thus our question becomes nents while discarding the rest. It has a number of important proper-
more specific: can we find a Fourier transform for signals on ties with implications for signal acquisition and compression.
graphs? In the research community, it has been believed for quite
a while that the eigenbases of a Laplacian matrix can be deemed as Proposition 2.1 ([9]). If f (t) is differentiable and f[() =
R +
the Fourier basis for its corresponding graph. In this paper, we re- f (t)eiwt
dt denotes its Fourier transform, then |f[
()|

fer to it as the Graph Fourier Transform (GFT). Furthermore, the kf kV
GFT has appeared in data compression [3, 5], signal denoising [6] ||
.
and compressed sensing [7, 8]. However, none of them provides a
detailed theoretical analysis for when and why the graph Laplacian Theorem 2.2 ([9]). If kf kV < +, then l (M, f ) = O(kf kV M 1 ).
eigenbases can be regarded as the Fourier transform of graphs; they Theorem 2.3 ([9]). For any s > 1/2, if +
P 2s 2
m=0 |m| |hf, gm i| <
do not discuss whether the Laplacian eigenvectors are meaningful + where gm is the mth vector of an orthogonal basis, then
basis vectors on all graphs. l (M, f ) o(M 2s ).
In this paper, we address these issues. We first generalize
the concept of smooth signals and define a metric to measure the The theorems above describe the decay rate of Fourier coeffi-
smoothness of a graph signal. Later, we derive certain properties of cients and the behavior of linear approximation error. It is worth
noting that Theorem 2.1 is consistent with the fact that a smooth Definition 4. We say that f RV has a bounded variation if we can
signal is likely to be compressible in the Fourier domain. Theorem find a positive C  N 1 such that kf k2G Ckf k22 , where N 1
2.2 shows that the linear approximation error is upper bounded by is the largest Laplacian eigenvalue of the underlying graph. Bounded
total variation and thus signals with small total variation will result variation can also be defined for graphs with an infinite number of
in less linear approximation error. Theorem 2.3 states that the be- nodes: if kf kG < +, then f has a bounded variation.
havior of the linear approximation error depends on the decay rate
of |hf, gm i|. In the next several subsections, we show that similar Although there exists no infinitely large graphs in real ap-
statements of all the three theorems above apply to the GFT. plications, discussing the properties of such graphs can provide
certain implications about the behavior of large graphs. Actu-
ally, the bounded variation for infinitely large graphs implies
2.2. Towards Properties of the Graph Fourier Transform P+ \ 2 \2
i=0 i |f (i )| < +, which gives lim i |f (i )| = 0. Hence,
i
Signals supported on graphs are fairly common in real applications. the notion of bounded graph variation is closely tied to the Lapla-
For a given graph G = (V, E) and we write f RV to mean that f cian eigenvalues i , and thus the graph structure. For example, if we
is supported on the vertices of G. consider a complete graph1 , |f\ (i )| 0 since i +, where
Since the topology of an underlying graph is crucial to the sig- i = 1, 2, , i.e., only signals containing a DC component can be
nals supported on it, we need some tools to analyze the graph topol- considered smooth for complete graphs.
ogy. For an undirected, unweighted graph G = (V, E), which con- Next lets define the linear and non-linear approximation error
sists of a set of edges E and a set of vertices V , the adjacency matrix for the GFT. They are similar to those of the Fourier transform.
A of G is the N N matrix with entries
 Definition 5. The M -term linear approximation error is l (M, f ) =
1 : if there is an edge between vertix i, j PN 1 \ 2
i=M |f (i )| , where f (i ) = hf, ui i denotes the ith GFT co-
Ai,j = \
0 : otherwise
efficient of signal f , and where ui is the ith eigenvector of the
Laplacian matrix of graph G.
and N = |V | is the number of nodes. The degree of vertex i, denoted
by di , is the number of all the edges incident to i. The degree matrix Definition 6. The M -term non-linear approximation error is
D is a diagonal matrix with entries Di,i = di and off-diagonals P \2
n (M, f ) = / |f (i )| , where is the set of indices of
i
equal to zero. The graph Laplacian is defined as: L = D A. the M largest graph Fourier coefficients in magnitude.
An interesting fact which has been noted many times is that the
1-D ring and the 2-D grid are examples of circulant graphs, and it is The following theorems describe the properties of the GFT.
well known that the Discrete Fourier Transform (DFT) is an eigen-
basis for all circulant matrices[10]; i.e., the Laplacian matrix of any Theorem 2.4. Given a signal f RV on vertices of a graph G =
circulant graph is diagonalized by the DFT basis. This has been a (V, E), let i denote the ith eigenvalue of the Laplacian matrix L
starting point for some researchers to adopt the Laplacian eigenba- and f\
(i ) denotes the ith GFT coefficient of the signal f . Then,
sis (i.e., the GFT) as a Fourier transform of graphs. Naturally,
kf kG
one might ask: Is it possible for graphs with more general structures (i )|
|f\
to have similar properties of the Fourier transform? The following i
subsection considers this issue.
Proof Sketch: It is straightforward to see that i |f\ (i )|2
2.3. Properties of the Graph Fourier Transform PN 1 \ 2 T PN 1
= f ( i=0 i ui ui )f = f Lf = kf k2G ,
T T
i=0 i |f (i )|
One vital concept closely related to the Fourier transform is the where ui is the ith eigenvector of the Laplacian matrix L. 
smoothness of signals, since smooth signals have compressible Compared with Proposition 2.1, Theorem 2.4 implies that eigen-
Fourier coefficients; i.e., the sorted magnitudes of their Fourier co- values of the graph Laplacian play the same role as frequencies
efficients exhibit a power law decay. Hence, we can keep a small in traditional signal processing; i.e., 0 , , N 1 index the GFT
portion of the large ones to approximate the signal while discarding coefficients from low to high frequencies. Accordingly, the eigen-
all the others. Similarly, in the graph setting we need a notion of the vectors of the Laplacian are actually the frequency components of
smoothness of signals on graphs. Karni and Gotsman [3] argue the a graph. The next theorem discusses the bound for linear approxi-
smoothness for spectral compression is when the coordinates of a mation error.
vertex are very close to the average coordinates of its neighbors. Theorem 2.5. Consider a signal f RV on the graph G = (V, E).
Their work is limited to meshes, while we care about more general If f has a bounded variation, then for adequately large M :
graphs and signals. Accordingly, we extend this notion to the value
associated with a vertex is very close to that of its neighbors. More l (M, f ) kf k2G 1
M
concretely, the following definition of 2-norm graph total variation
describes the overall smoothness of a signal.
PN 1 \ 2 PN 1 \ 2
Proof Sketch: Notice that i=M i |f (i )| i=0 i |f (i )| =
Definition 3. 2-norm Graph P Total Variation: Given a signal f N 1 \ 2
kf k2G and l (M, f ) =
P
RV , kf kG = (f T Lf )1/2 = ( ij (f (i)f (j))2 )1/2 , where i j i=M | f (i )| . We can relax the above
means there exists an edge between node i and node j. conditions and consider the optimization problem:
N 1 N 1
The 2-norm graph total variation describes the smoothness of a X X
maximize x2i subject to i x2i kf k2G . (1)
signal defined on graph vertices. The smaller graph total variation a
i=M i=M
signal has, the smoother the signal is on the graph. Zhu et al. [11]
also mention that f T Lf measures the smoothness of f on the graph. 1 Where every node is neighbors with all other nodes
By solving this problem, we obtain its solution xM = kf k2G 1 Theorem 2.7 along with Lemma 2.6 describe the behavior of
PN 1 2M
and xi = 0 for all i = M + 1, , N 1. Thus, i=M (xi ) is the linear approximation error of graphs with an infinite number of
clearly an upper bound for l (M, f ). Since kf k2 also upper bounds nodes when its eigenvalues are strictly increasing. The condition
l (M, f ), l (M, f ) min{kf k2 , kf k2G 1
P+ \ 2 < + implies |f\
M }. Due to the bounded i=0 ii |f (i )| (i )|2 = o( i1i ), which is
variation condition, we have kf k2G 1 C 2
M M kf k . Since C  stronger than the bounded variation condition. Then, a similar decay
N , we can always find M > C for adequately large M such that rate of o( M 1 ) is guaranteed for the linear approximation error.
kf k2G 1 2 M/2
M < kf k .  The above theorems provide us with some implications about
This statement is analogous to Theorem 2.2 for the classical which signals on which graphs are likely to be compressible in the
Fourier transform. From Theorem 2.5, the upper bound of the lin- corresponding graph Fourier domain. To summarize, there are two
ear approximation error is related to both the Laplacian eigenvalues main principles: First, from the perspective of signals, we need a
and the graph total variation. It implies that if the eigenvalues keep smooth signal on the underlying graph, i.e., kf kG is small, since
strictly increasing, the linear approximation error will have the de- it controls the upper bound of linear approximation error. Second,
caying property. Moreover, the linear approximation error is also af- from the perspective of the underlying graphs, the Laplacian eigen-
fected by the graph total variation kf kG , i.e., bounded kf kG results value of the graph must have an increasing trend, roughly, in order
in smaller linear approximation error. This is consistent with our in- to ensure the graph Fourier coefficients decay.
tuition that a smoother signal tends to be better linear-approximated.
Lemma 2.6. Consider a signal f RV on a connected graph: 2.4. Constructing Graphs for Signal Compression
N
X 1 N
X 1 N
X 1
Given a signal f RN , what graph leads to a GFT basis of best
(i )|2
i |f\ M l (M, f ) (i )|2
ii |f\ compression for f ? The properties of the GFT provide us with cer-
i=0 M =0 i=0 tain implications of this question. First, each entry in f can be re-
If we consider a graph G with infinite number of nodes, then garded as a node allocated one value. From Theorem 2.4 and its
corollary, we want f to be smooth on the graph, i.e., kf kG should be
+ + +
X X X kept small enough. One possible solution to this problem is to use -
(i )|2
i |f\ M l (M, f ) (i )|2
ii |f\ graphs or K-nearest-neighbor(KNN) graphs. An -graph is obtained
i=0 M =0 i=0
by connecting pairs of nodes whose distance is smaller than , and
P 1
Proof. Notice the fact that N
PN 1 \ 2 a KNN graph is constructed by connecting each node to its K near-
M =0 M i=M |f (i )| =
PN 1 \ 2 Pi est neighbors. More concretely, we construct the graph by putting
i=0 |f ( i )| (
M =0 M ), which immediately gives the left- an edge P between the nodes which are likely to share similar values
hand inequality. Moreover, since n m for all n m , we so that ( ij (f (i) f (j))2 )1/2 is kept small. The next question
obtain the upper bound. is: how do we choose K or ? From the perspective of bounding
kf kG , we prefer the parameters to be small since fewer edges will
Theorem 2.7. Given a graph G with infinite nodes, if
P+ \2 result in smaller kf kG . Moreover, we should avoid constructing a
i=0 ii |f (i )| < +, then the M term linear approximation complete graph. Hence, the parameters shouldnt be too large. On
error obeys the other hand, if the value of K or  is too small, the connectivity
1
l (M, f ) = o( ). of the graph will be weak and the eigenvalues corresponding to low
M M/2 frequencies might be equal to or close to 0. Such behavior contra-
Proof. From the second statement of Lemma 2.6, we notice that dicts the increasing trend of eigenvalues that we desire. Thus, the
graph we construct should at least be a connected one.
M 1 M 1
X X In typical applications, we may not have prior information about
l (M, f ) m m l (m, f ) (2) the exact distribution of the signal f , but we can construct the graph
m=M/2 m=M/2
based on other information. For example, for field estimation in a
+
X wireless sensor network, it is fairly reasonable to assume the val-
m l (m, f ) (3) ues measured at each node is highly correlated to its location, and
m=M/2 thus nodes that are geographically close to each other are likely to
+
X have similar readings. Hence, we can build the graph based on the
(i )|2 .
ii |f\ (4) location information.
i=0

The first inequality holds due to the fact l (M, f ) l (m, f ) for all 3. EXPERIMENT RESULTS
m M . Since + \2
P
P+ i=0 ii |f (i )| < +, we have 3.1. Experiment Setup
m=M/2 m l (m, f ) < +. Thus,
In this section, we investigate the performance of the graph Fourier
+
X on the data from California Irrigation Management Information Sys-
lim m l (m, f ) = 0. (5) tem (CIMIS) [12]. This dataset is generated by weather stations
M
m=M/2 around the state of California. We use the solar radiation data for one
PM 1 day which contains 135 readings from different weather stations. We
Moreover, it is clear that M
2 M/2
m=M/2 m , Accordingly, utilize KNN graphs based on the geographical information of each
Eq.2, Eq.3, along with Eq.5 implies that
weather station to build its GFT basis.
lim M M/2 l (f, M ) = 0. We will compare the performance of compressed sensing
M
[13, 14], linear approximation and non-linear approximation on
this dataset. For compressed sensing, we randomly select a number
of the readings from the sensor nodes as the measurement and use earlier discussion about the choice of parameter K. Given a constant
LASSO in graph Fourier basis as the signal recovery algorithm. All compression rate, the best performance of Compressed Sensing ap-
experiments repeat 50 times and the average values are reported. pears when K is in 510. When K is smaller than 5, the graph
is unconnected with high probability. In this case, we have multiple
10 zero eigenvalues. When K become larger than 30, the graph approx-
Compressed Sensing imate the complete graph, which also gives a poor compressibility.
0 Linear Approximation
Nonlinear Approximation
10 4. CONCLUSION
20
This paper analyzes a concept of the GFT. To the best of our knowl-
Distortion(dB)

30
edge, this is the very first work to address (i) when we can com-
press signals supported on graphs using he graph Laplacian eigen-
40 basis, and (ii) what conditions the graph and signals should satisfy
for approximation. We define the smoothness of signals supported
50
on graphs and show its impact on the linear approximation error.
60 The GFT extends the conventional approximation theory to signals
on graphs. We believe it has a lot of potential applications including
70 in the realms of sensor networks, computer graphics and compressed
80
sensing.
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1
Compression Ratio
5. REFERENCES

Fig. 1. Performance comparison of Compressed Sensing, linear ap- [1] W. Bajwa, J. Haupt, A. Sayeed, and R. Nowak, Compressive wire-
proximation and non-linear approximation on the CIMIS dataset. less sensing, in Proceedings of the 5th international conference on
Information processing in sensor networks. ACM, 2006, pp. 134142.
[2] W. Bajwa, A. Sayeed, and R. Nowak, Matched source-channel com-
munication for field estimation in wireless sensor networks, in Pro-
0.7
ceedings of the 4th international symposium on Information processing
M=80
M=60
in sensor networks. IEEE Press, 2005, pp. 44es.
0.6 M=20 [3] Z. Karni and C. Gotsman, Spectral compression of mesh geome-
try, in Proceedings of the 27th annual conference on Computer graph-
0.5 ics and interactive techniques. ACM Press/Addison-Wesley Publishing
Co., 2000, pp. 279286.
Distortion(MSE)

0.4 [4] M. Ben-Chen and C. Gotsman, On the optimality of spectral compres-

sion of mesh data, ACM Transactions on Graphics (TOG), vol. 24, no.
0.3 1, pp. 6080, 2005.
[5] D. Ustebay, R. Castro, and M. Rabbat, Efficient decentralized approx-
0.2 imation via selective gossip, IEEE Journal of Selected Topics in Signal
Processing, vol. 5, no. 4, pp. 805816, 2011.
0.1 [6] D.I. Shuman, P. Vandergheynst, and P. Frossard, Chebyshev polyno-
mial approximation for distributed signal processing, Arxiv preprint
arXiv:1105.1891, 2011.
0
0 10 20 30 40 50 60 70 80 90 100
Connectivity
[7] X. Zhu and M. Rabbat, Graph spectral compressed sensing via sensor
networks, Tech. Rep., McGill University, 2011.
[8] X. Zhu and M. Rabbat, Graph spectral compressed sensing, Tech.
Fig. 2. Performance of Compressed Sensing with different graph
Rep., McGill University, 2011.
Fourier bases, for different numbers of measurements, M . The hori-
zontal axis shows the number of neighbors used to formulate a sym- [9] S.G. Mallat, A Wavelet Tour of Signal Processing, Third Edition: The
Sparse Way, Academic Press, 2008.
metric KNN graph.
[10] R.M. Gray, Toeplitz and circulant matrices: A review, Information
Systems Laboratory, Stanford University, 1971.
[11] X. Zhu, J. Kandola, J. Lafferty, and Z. Ghahramani, Graph kernels
3.2. Results by spectral transforms, in O. Chapelle, B. Schoelkopf, and A. Zien,
editors, Semi- Supervised Learning. 2006, pp. 277291, MIT Press.
Fig 1 illustrates the performance of CS, linear approximation and
[12] Cimis data, [Online]. Available: http://www.cimis.water.ca.gov,
non-linear approximation with increasing compression rate. The
2010.
compression ratio is defined as MN
, where M is the number of mea-
surements and N is the dimension of signal. Distortion is calcu- [13] D.L. Donoho, Compressed sensing, IEEE Transactions on Informa-
tion Theory, vol. 52, no. 4, pp. 12891306, 2006.
lated with Mean Square Error(MSE). It is well implicated that the
non-linear approximation outperforms the other two methods, while [14] E.J. Candes, J. Romberg, and T. Tao, Robust uncertainty principles:
linear approximation performs a little bit better than Compressed Exact signal reconstruction from highly incomplete frequency infor-
mation, IEEE Transactions on Information Theory, vol. 52, no. 2, pp.
Sensing. 489509, 2006.
Fig 2 describes explicitly how the connectivity of a graph affects
the performance of compressed sensing. The result agrees with our