Report
Introduction
-
Graph: generic data representation form describing the geometric structures of data domains.
We denote an undirected, connected, weighted graph as
, and the number of vertices is .
- Graph Signal: data that reside on the vertices of a graph, usually represented as a vector $ f \in \mathbb{R}^N $.
-
Edge Weights: usually represent similarity between the two vertices.
Common graph construction methods when edge weights are not naturally defined:
- Gaussian kernel weighting function
- k-nearest neighbors
The Graph Laplacian
-
(Unnormalized) Graph Laplacian:
works as a difference operator for any signal .
Since
- Normalized Graph Laplacian:
the eigenvalues of
- Random Walk Matrix:
There is not a clear answer as to when to use each of these basis.
Graph Fourier Transform
The classical Fourier transform works in the time domain and the frequency domain. Analogously we define the graph Fourier transform, which works in the vertex domain and the graph spectral domain.
For any signal
In matrix form, we have
and the inverse graph Fourier transform:
The eigenvalues and eigenvectors in graph spectral domain provide a similar notation of frequency: the eigenvectors with larger eigenvalues contains more zero crossings.
Discrete Calculus and Signal Smoothness
The edge derivative of a signal
The gradient of
The discrete
When
Seminorm of
The smoother the graph, the smaller the
The discrete regularization framework:
When
Generalized Graph Signal Operators
Filtering
-
graph spectral domain:
let
be the transfer function in spectral domain. let .
$ f_{out} $ can then be calculated through an inverse graph Fourier transform.
- vertex domain: linear combination within K-hop neighborhoods
When the transfer function in graph spectral domain is an order K polynomial, the two forms of filtering can be related.
Convolution
Convolution in the vertex domain (the time domain) is equivalent to multiplication in the graph spectral domain (the frequency domain).
Since in the graph setting there is no
so convolution with
Translation
It's not clear what it means to translate a graph signal, but we can generalize translation as a convolution with a delta centered at
Modulation
Dilation
Coarsening
this operation can be separated in to two subtasks:
- Down Sampling: identifying a reduced set of vertices
- Reduction: assigning edges and weights
For a bipartite graph, it is natural to down sample it by a factor of 2.
For non-bipartite graphs, conditions are much more complex.
Localized Multiscale Transforms
Wavelet transform can localize signal in both time and frequency simultaneously, which is better than Fourier transform.
- vertex domain
- random transforms
- graph wavelets
- lifting-based transforms
- tree wavelets
- graph spectral domain
- diffusion wavelets
- spectral graph wavelet
- graph-quadrature mirror filterbanks
Open Issues & Extension
Open Issues
- How the construction of graph affects properties of the localized, multiscale transforms for signals on graphs.
- When and why to use normalized, unnormalized graph Laplacian or other basis.
- What kind of distance to use in the vertex domain.
- Approximate computational techniques for signal processing on graphs.
- How to link structural properties of graph signals and their underlying graphs to properties.
Extensions
- Directed graph.
- Time series of signal data.
- Time series of underlying graphs.