Ye Yuan
0%

Spectral Graph Theory

Posted on Edited on

Spectral Graph Theory

Fourier Transform [1]

Taylor expansion

making , we get . The one-parameter family of Fourier basis: .

Fourier Transform

Inverse Fourier Transform

We will adopt , and . We know that: .

The properties of Fourier transform:

  • and its inverse are linear operators

  • Fourier transform of a translation

  • Fourier transform of a rescaling

The convolution of two functions and is defined as:

  • Fourier transform of a convolution

  • Fourier transform of a product

  • Perseval's equation

Cross-correlation The cross-correlation is similar in nature to the convolution of two functions.

which is equivalent to

The cross-correlation of functions and is equivalent to the convolution (denoted by ) of and . That is:

Paley-Wiener theorem A function vanishes almost everywhere outside and interval if and only if its Fourier transform satisfies

and is the restriction to the real line of a certain entire analytic function of a complex variable satisfying for all .

Linear Filters

  • A filter maps a signal into another signal .
  • A filter is called linear if
  • A filter is time invariant if

Theorem Let be a linear and time invariant filter. There exists a function such that

And, is called the impulse response function of the filter.

Graph Laplacian

Why is so interesting about the Graph Laplacian (GL)?

  • The GL is a symmetric matrix (real eigenvalues and eigenvectors, the latter forming an orthogonal basis)
  • The GL is positive semidefinite (assuming non-negative edge weights)
  • The eigenvectors are "nice" functions defined on the graph.

Property 3 Supposing is connected, the eigenvector associated to the smallest non-zero eigenvalue (Fiedler Vector) provides the best one-dimensional embedding of .

In mathematical terms, we want to find for each node in , so as to minimize

Imposing the additional constraint , the Courant-Fiecher theorem ensures that the minimum is reached when is the eigenvector associated to the second smallest eigenvalue.

Property 3+

For any holds, then it can be general form:

As a quadratic form:

Graph Fourier Transform

Let be a weighted graph, be its corresponding graph Laplacian, and a function defined on the vertices of .

Graph Fourier Transform The Graph Fourier Transform of is defined as

Inverse Graph Fourier Transform

The eigenvalues of play the role of frequencies and the eigenvectors the Fourier basis. The graph Fourier transform and its inverse gives a way to represent a signal in two different domains: the vertex domain and the graph spectral domain.

If we think of and as vectors, we then these definitions become:

Graph Fourier Transform: Filtering

In classical signal processing, frequency filtering is given by amplifying or attenuating the contributions of some Fourier Basis.

Taking the IGFT

Suppose and the definition of in above, we get

Let and , we get

Therefore, when the filter is a polynomial in the spectral domain, the filtered signal in each node i is a linear combination of the original signal in the neighborhood of i.

Theorem It can be shown that when the shortest distance between nodes i and j is greater than k.

Lemma 5.4, the localization result for integer powers of the Laplacian [2] Let be a weighted graph, the graph Laplacian and an integer. For any two vertices and , if then .

Graph Fourier Transform: Convolution

The definition of convolution between two functions and is

such definition can not be directly applied because the shift (or signal translation) is not defined in the context of graphs. However, convolution can be defined as:

Some properties of the convolution:

Graph Fourier Transform: Translation

The classical translation

cannot be directly generalized to the graph setting. However, translation can be seen as a convolution with the delta function

Recalling that , we define translation to a vertex j as:

The normalizing constant ensures that the translation operator preserves the mean of a signal, i.e. .

Some properties of translation:

Graph Fourier Transform: Dilation

in the graph setting, is not well defined, impairing the direct generalization of dilation in the graph domain. An alternative is to define dilation via GFT:

Notice that might not be in the interval . Therefore, dilation can only be used when is generated from a kernel defined in the whole spectral domain.

Graph Fourier Transform: Modulation

Continuous case:

In the graph setting we can define

In contrast to the continous case, modulation in the graph setting deos not correspond to a translation in the spectral domain. However, if is generated from a kernel localized in , then is concentrated in .

Wavelets and Graph Wavelets

The admissibility condition Let be a function satisfying the admissibility condition

The property above ensures that , and . Therefore, the admissibility condition allows for and effective localization in both time and frequency for the basis functions, contrary to the Fourier basis that are of infinite duration waves.

Wavelet Transform: Continuous Wavelet Transform (CWT) and Discrete Wavelet Transform (DWT)

Consider the doubly-indexed family of functions:

where , and satisfies the admissibility condition. The normalization ensures that . The function are called wavelets and the mother wavelet. The CWT is defined as:

function can be recovered from coefficients by

The admissibility condition guarantees the reconstruction above.

Frames A family of functions (in a Hilbert space) is called a frame if there exist and such that for all

If , the frame is called a tight frame.

Spectral Graph Wavelet Transform: Hammond's Formualtion

Let be a weighted graph and the corresponding graph Laplacian. We will denote the eigenvalues and eigenvectors of by and , respectively. The main idea behind Hammond’s approach is to perform the wavelet transform by properly define a kernel function in the spectral domain, which plays to role of . The kernel should behave as a band-pass filter (similarly to scaled wavelets) satisfying and .

Analogous to Graph Fourier transform, Spectral Graph Wavelet Transform of a function defined on the vertices of as follows:

SGWT Reconstruction

The Laplacian and eigenvalues

In a graph , let denote the degree of the vertex . We first define the Laplacian for graphs without loops and multiple edges.

Let denote the diagonal matrix with the -th entry having value . The Laplacian of is defined to be the matrix

We can write

with the convention for . We say is an isolated vertex if . A graph is said to be nontrivial if it contains at least one edge.

References

[1] Luis Gustavo Nonato, 2017

[2] @article{hammond2011wavelets, title={Wavelets on graphs via spectral graph theory}, author={Hammond, David K and Vandergheynst, Pierre and Gribonval, R{'e}mi}, journal={Applied and Computational Harmonic Analysis}, volume={30}, number={2}, pages={129--150}, year={2011}, publisher={Elsevier} }