Low-Pass Filters in Graph Signal Processing
Graphs use vertices and edges to represent complex relationships. A low-pass filter emphasizes low-frequency components while suppressing high-frequency ones. The frequency components on graphs are defined using eigenvalue decomposition and eigenvectors. This article explains the theory of low-pass filters in graph signal processing and their implementation methods.
Source Code
GitHub
- The Jupyter Notebook file is available here .
Google Colaboratory
- For execution in Google Colaboratory, click here .
Execution Environment
The OS is macOS. Please note that the options for Linux or Unix commands may differ.
!sw_vers
ProductName: macOS
ProductVersion: 13.5.1
BuildVersion: 22G90
!python -V
Python 3.9.17
We also import essential libraries, check their versions using watermark, and set a random seed.
%matplotlib inline
%config InlineBackend.figure_format = 'svg'
import random
import scipy
import numpy as np
import matplotlib
import matplotlib.pyplot as plt
seed = 123
random_state = 123
random.seed(seed)
np.random.seed(seed)
from watermark import watermark
print(watermark(python=True, watermark=True, iversions=True, globals_=globals()))
Python implementation: CPython
Python version : 3.9.17
IPython version : 8.17.2
scipy : 1.11.2
numpy : 1.25.2
matplotlib: 3.8.1
Watermark: 2.4.3
1. Basics of Graph Signal Processing (GSP)
1.1 Overview of GSP
Graph Signal Processing targets signals defined on graphs. Consider a graph $G=(V,E)$ with vertices $V$ and edges $E$, where $N$ is the number of vertices. Assigning real-valued signals to each vertex yields a signal vector $\mathbf{x} \in \mathbb{R}^N$. GSP examines how to transform and process such signals using adjacency matrices and Laplacian matrices, considering graph structures. Applications include network analysis, recommender systems, and SNS analytics. For instance, companies graph customer relationships to forecast demand and optimize promotional strategies.
1.2 Adjacency and Laplacian Matrices
The adjacency matrix $\mathbf{A} \in \mathbb{R}^{N \times N}$ encodes the presence or weights of edges. For undirected graphs, $\mathbf{A}$ is symmetric. The Laplacian matrix $\mathbf{L}$ is defined as $\mathbf{L} = \mathbf{D} - \mathbf{A}$, where $\mathbf{D}$ is the degree matrix with vertex degrees on its diagonal. The eigenvalues and eigenvectors of $\mathbf{L}$ underpin the definition of frequency components on graphs. As a semi-positive definite matrix, the smallest eigenvalue of $\mathbf{L}$ is 0. These matrices enable Fourier transforms on graph signals.
1.3 Concept of Signals on Graphs
For $N$ vertices, a signal vector $\mathbf{x}$ is $N$-dimensional. For example, consider an SNS where vertices represent users and edges represent friendships. Attributes or activity levels of users serve as signals. GSP processes these signals spatially (considering graph structure) to achieve refined results, applying filters in the frequency domain or smoothing processes. Low-pass filters particularly emphasize low-frequency components.
2. Theoretical Background of Low-Pass Filters
2.1 What is a Filter?
In signal processing, a filter selectively allows certain frequency bands to pass while attenuating others. A low-pass filter passes low-frequency components while blocking or weakening high-frequency ones. In the time domain, it smooths gradual changes and suppresses abrupt ones. On graphs, it smooths signals across highly similar vertices connected by edges, suppressing abrupt changes (high-frequency components) and emphasizing gradual structures.
2.2 Graph Fourier Transform and Low-Pass Filters
The Graph Fourier Transform (GFT) is based on the eigenvalue decomposition of the Laplacian matrix $\mathbf{L}$: $$\mathbf{L} = \mathbf{U} \boldsymbol{\Lambda} \mathbf{U}^\top,$$ where $\mathbf{U}$ contains eigenvectors as columns, and $\boldsymbol{\Lambda}$ is the diagonal matrix of eigenvalues. The Fourier transform of a graph signal $\mathbf{x}$ is defined as: $$\hat{\mathbf{x}} = \mathbf{U}^\top \mathbf{x}.$$ A low-pass filter in the frequency domain passes components with low eigenvalues and suppresses those with high eigenvalues. Using a frequency response function $h(\lambda)$, the filtered signal can be expressed as: $$\mathbf{y} = \mathbf{U} h(\boldsymbol{\Lambda}) \mathbf{U}^\top \mathbf{x}.$$
2.3 Examples of Frequency Response Functions
An ideal low-pass filter passes components below a critical eigenvalue $\lambda_c$ (set to 1) and blocks others (set to 0). However, practical designs often employ smooth attenuation to avoid issues like the Gibbs phenomenon. Examples include:
- Exponential decay: $h(\lambda) = e^{-\alpha \lambda}$,
- Reciprocal decay: $h(\lambda) = \frac{1}{1 + \beta \lambda}$.
Choosing an appropriate function depends on the graph structure and signal characteristics.
3. Relationship Between Graph Fourier Transform and Eigenvalue Decomposition
3.1 Significance of Laplacian Eigenvalues
The eigenvalues of the Laplacian matrix relate to the “smoothness” of a graph. Eigenvectors corresponding to low eigenvalues represent gradual changes across the graph, while those for high eigenvalues indicate abrupt, localized changes. Thus, a low-pass filter retains components corresponding to low eigenvalues, emphasizing smooth regions and reducing noise or abrupt changes.
3.2 Orthogonality of Eigenvectors
For an undirected graph, the Laplacian is symmetric and semi-positive definite. Its eigenvectors $\mathbf{u}_1, \mathbf{u}_2, \dots, \mathbf{u}_N$ form an orthogonal basis. These eigenvectors can fully span the signal space. The Graph Fourier Transform corresponds to this transformation into the eigenvector basis. Filtering in the frequency domain results in smoothing in the spatial domain.
3.3 Approximation with Higher-Order Laplacians
Computing all eigenvectors for large graphs is computationally expensive. For massive graphs, eigenvalue decomposition becomes impractical. Polynomial approximations of $h(\mathbf{L})$ (e.g., Taylor or Chebyshev polynomials) or matrix exponential operations can implement low-pass filters. These methods enable localized computations without requiring full diagonalization.
4. Basic Implementation in Python
4.1 Preparing the Graph Structure
Below is an example of defining an undirected graph using its adjacency matrix:
import numpy as np
N = 5
# Define adjacency matrix (small example)
A = np.array([[0, 1, 1, 0, 0], [1, 0, 1, 1, 0], [1, 1, 0, 0, 0], [0, 1, 0, 0, 1], [0, 0, 0, 1, 0]], dtype=float)
# Degree matrix D
D = np.diag(A.sum(axis=1))
# Laplacian matrix
L = D - A
L
array([[ 2., -1., -1., 0., 0.],
[-1., 3., -1., -1., 0.],
[-1., -1., 2., 0., 0.],
[ 0., -1., 0., 2., -1.],
[ 0., 0., 0., -1., 1.]])
This example defines a graph with 5 vertices. Entries in the adjacency matrix are 1 for existing edges and 0 otherwise. The Laplacian matrix $\mathbf{L}$ is computed as $\mathbf{D} - \mathbf{A}$.
4.2 Eigenvalue Decomposition and Low-Pass Filtering
The Laplacian is decomposed into eigenvalues and eigenvectors, and low eigenvalues are emphasized:
# Eigenvalue decomposition
eigvals, eigvecs = np.linalg.eigh(L)
# Low-pass threshold
lambda_c = 1.5
# Frequency response function
def lowpass_func(lam):
return 1.0 if lam < lambda_c else 0.0
# Define filter as diagonal matrix
H_diagonal = [lowpass_func(val) for val in eigvals]
H = np.diag(H_diagonal)
# Example signal x
x = np.array([1, 0, 2, 3, 1], dtype=float)
# Fourier transform
xhat = eigvecs.T @ x
# Apply filter
yhat = H @ xhat
# Inverse transform
y = eigvecs @ yhat
y.round(2)
array([1.21, 1.31, 1.21, 1.55, 1.72])
This implementation realizes an ideal low-pass filter, retaining components corresponding to low eigenvalues and zeroing out high eigenvalues.
4.3 Example of Smooth Attenuation
To avoid the Gibbs phenomenon, a filter with smooth attenuation can be used:
alpha = 0.5
def exp_lowpass(lam):
return np.exp(-alpha * lam)
H_diagonal = [exp_lowpass(val) for val in eigvals]
H = np.diag(H_diagonal)
yhat = H @ xhat
y = eigvecs @ yhat
yhat.round(2)
array([-3.13, -0.35, 0.27, -0.16, -0.24])
The exponential low-pass filter provides a smoother output.
5. Concrete Examples of Computation
5.1 Calculating Eigenvalues for a Small Graph
Let’s revisit the 5-vertex graph example. The adjacency matrix $\mathbf{A}$ is defined as:
$$ \mathbf{A} = \begin{pmatrix} 0 & 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 1 & 0 \\ 1 & 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 \end{pmatrix} $$
The degree matrix $\mathbf{D}$ is a diagonal matrix with the degree of each vertex:
$$ \mathbf{D} = \begin{pmatrix} 2 & 0 & 0 & 0 & 0 \\ 0 & 3 & 0 & 0 & 0 \\ 0 & 0 & 2 & 0 & 0 \\ 0 & 0 & 0 & 2 & 0 \\ 0 & 0 & 0 & 0 & 1 \end{pmatrix} $$
The Laplacian matrix $\mathbf{L} = \mathbf{D} - \mathbf{A}$ is given by:
$$ \mathbf{L} = \begin{pmatrix} 2 & -1 & -1 & 0 & 0 \\ -1 & 3 & -1 & -1 & 0 \\ -1 & -1 & 2 & 0 & 0 \\ 0 & -1 & 0 & 2 & -1 \\ 0 & 0 & 0 & -1 & 1 \end{pmatrix} $$
Using numerical computation software, the eigenvalues of $\mathbf{L}$ are approximately $[0, 1, 2, 3, 4]$ (minor numerical inaccuracies may occur). The eigenvector corresponding to the eigenvalue $0$ points to the constant vector (all ones). Higher eigenvalues indicate signal components with greater variations between neighboring vertices. A low-pass filter retains components corresponding to low eigenvalues, smoothing the signal.
5.2 Applying a Signal Vector
Consider the signal vector $\mathbf{x} = [1, 0, 2, 3, 1]^\top$. Let $\mathbf{u}_1, \dots, \mathbf{u}_5$ represent the eigenvectors of $\mathbf{L}$. The frequency representation of the signal is:
$$ \hat{\mathbf{x}} = \begin{pmatrix} \mathbf{u}_1^\top \mathbf{x} \\ \mathbf{u}_2^\top \mathbf{x} \\ \mathbf{u}_3^\top \mathbf{x} \\ \mathbf{u}_4^\top \mathbf{x} \\ \mathbf{u}_5^\top \mathbf{x} \end{pmatrix}. $$
A low-pass filter, such as one that retains components corresponding to eigenvalues $\leq 2$, sets higher eigenvalue components to zero. Applying the inverse transform yields a smoothed signal $\mathbf{y}$. For sparse graphs, the difference may not be large, but with denser graphs, the effect becomes more pronounced.
6. Frequently Asked Questions and Solutions
6.1 Setting the Cutoff Value
The cutoff value $\lambda_c$ depends on the purpose and characteristics of the signal. Factors to consider include the graph’s size, edge density, and noise characteristics. The value may be chosen empirically or determined as part of an optimization problem.
6.2 Choosing a Filter Function
Ideal step-shaped filters often suffer from the Gibbs phenomenon. Therefore, smooth functions, such as exponential or reciprocal decay, are generally preferred. The choice of function should match the application and avoid excessive smoothing.
6.3 Application to Large-Scale Graphs
For graphs with millions of vertices, eigenvalue decomposition becomes infeasible. Practical methods include polynomial approximations (e.g., Chebyshev polynomials) or iterative techniques like Monte Carlo simulations. In large-scale network analysis for enterprises, these approximations are essential.
Conclusion
This article introduced the basics of low-pass filters in graph signal processing and provided examples of their implementation. Signal processing based on graph structures effectively removes noise and stabilizes recommender systems. However, challenges like the computational cost of eigenvalue decomposition and filter design issues remain.
In practice, approximation methods and parameter selection are critical for large-scale graphs. While the Python examples provided here illustrate the concepts, leveraging specialized libraries for optimization is advisable.
This article serves as a personal memorandum. For detailed theory and advanced implementation, please refer to textbooks and research papers.