Graph Laplacian, Eigenvalues, and GFT

This article explains the theory behind the graph Laplacian and its eigenvalues. It also introduces the Graph Fourier Transform (GFT), its applications, and implementation examples in Python.

Source Code

GitHub

  • The Jupyter notebook file can be found here .

Google Colaboratory

  • For execution in Google Colaboratory, visit this link .

Execution Environment

The operating system used is macOS. Note that the options for Linux or Unix commands may differ.

!sw_vers

ProductName:		macOS
ProductVersion:		15.2
BuildVersion:		24C101

!python -V

Python 3.9.17

Import the basic libraries and use the watermark package to check their versions. Set the random seed for reproducibility.

%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 the Graph Laplacian

1.1 Definition of a Graph

Consider an undirected graph $G = (V, E)$ with $N$ vertices. $V$ is the set of vertices, where $|V| = N$, and $E$ is the set of edges, represented as pairs $(i, j)$. The adjacency matrix $\mathbf{A}$ indicates connections between vertices: $A_{ij} > 0$ for weighted graphs or $A_{ij} \in {0,1}$ for simple graphs. For undirected graphs, $\mathbf{A}$ is symmetric.

1.2 Degree Matrix

The degree matrix $\mathbf{D}$ is diagonal, with each diagonal element $D_{ii}$ representing the degree of vertex $i$. It is defined as $D_{ii} = \sum_{j=1}^{N} A_{ij}$ and contains only non-negative elements.

1.3 Definition of the Graph Laplacian

The graph Laplacian $\mathbf{L}$ is defined as: $$ \mathbf{L} = \mathbf{D} - \mathbf{A}. $$ This is a symmetric, positive semi-definite matrix. For an $N$-vertex graph, $\mathbf{L}$ is an $N \times N$ matrix, with row sums of zero, ensuring an eigenvalue of zero.

1.4 Properties of the Graph Laplacian

  • $\mathbf{L}$ is positive semi-definite (all eigenvalues are non-negative).
  • The smallest eigenvalue is 0, with the corresponding eigenvector being a uniform vector.
  • For connected graphs, the multiplicity of eigenvalue 0 is 1.
  • For disconnected graphs, the number of 0 eigenvalues corresponds to the number of connected components.
  • $\mathbf{L}$ is symmetric, allowing orthogonal eigenvector decomposition.

1.5 Applications

  • Evaluating graph cuts (norm minimization).
  • Clustering (spectral clustering).
  • Data analysis (signal processing on vertices).
  • Applications in recommender systems, such as user-user graphs.

1.6 A Simple Python Implementation Example

The following example assumes a simple graph, using variable names with type annotations.

import numpy as np

# Number of vertices
N = 5

# Example adjacency matrix (symmetric)
A = np.array([[0, 1, 0, 1, 0], [1, 0, 1, 0, 0], [0, 1, 0, 1, 1], [1, 0, 1, 0, 1], [0, 0, 1, 1, 0]], dtype=float)

# Degree matrix
D = np.diag(A.sum(axis=1))

# Graph Laplacian
L = D - A

# Compute eigenvalues and eigenvectors
eigvals, eigvecs = np.linalg.eigh(L)

print("L:")
print(L)
print("Eigenvalues:")
print(eigvals.round(2))
print("Eigenvectors:")
print(eigvecs.round(2))

L:
[[ 2. -1.  0. -1.  0.]
 [-1.  2. -1.  0.  0.]
 [ 0. -1.  3. -1. -1.]
 [-1.  0. -1.  3. -1.]
 [ 0.  0. -1. -1.  2.]]
Eigenvalues:
[0.   1.38 2.38 3.62 4.62]
Eigenvectors:
[[ 0.45  0.51 -0.6  -0.2  -0.37]
 [ 0.45  0.51  0.6  -0.2   0.37]
 [ 0.45 -0.2   0.37  0.51 -0.6 ]
 [ 0.45 -0.2  -0.37  0.51  0.6 ]
 [ 0.45 -0.63  0.   -0.63  0.  ]]
  • This example constructs a simple graph with 5 vertices.
  • By calculating eigenvalues and eigenvectors, the spectral properties of the graph are analyzed.

2. Properties of Eigenvalues and Eigenvectors

2.1 Definition of Eigenvalues

For a matrix $\mathbf{M}$, if there exists a vector $\mathbf{x}$ and a scalar $\lambda$ such that: $$ \mathbf{M}\mathbf{x} = \lambda \mathbf{x}, $$ then $\lambda$ is called an eigenvalue, and $\mathbf{x}$ is called an eigenvector.

2.2 Eigenvalue Decomposition of the Graph Laplacian

Since $\mathbf{L}$ is a real symmetric matrix, its eigenvalues are real numbers, and it is positive semi-definite. The spectral decomposition of $\mathbf{L}$ is expressed as: $$ \mathbf{L} = \mathbf{U} \Lambda \mathbf{U}^\top, $$ where $\Lambda$ is a diagonal matrix of eigenvalues, and $\mathbf{U}$ is an orthogonal matrix of eigenvectors.

2.3 Ordering of Eigenvalues

The eigenvalues are sorted in ascending order as: $$ 0 = \lambda_1 \le \lambda_2 \le \cdots \le \lambda_N. $$ For a connected graph, $\lambda_2 > 0$. $\lambda_2$, often called the Fiedler value, indicates the connectivity of the graph.

2.4 Interpretation of Eigenvectors

  • The eigenvector corresponding to $\lambda_1 = 0$ is a uniform vector.
  • The eigenvector corresponding to $\lambda_2$ (the Fiedler vector) suggests a partition of the graph.
  • Other eigenvectors represent oscillation modes along the graph structure.

2.5 Mathematical Perspective and Mapping

The graph Laplacian acts as a linear map $\mathbf{L}: \mathbb{R}^N \to \mathbb{R}^N$, transforming vectors in $\mathbb{R}^N$. Eigenvectors represent directions invariant under this transformation, scaled by the corresponding eigenvalues.

2.6 Computational Cost of Eigenvalue Calculation

  • Eigenvalue calculation typically requires $O(N^3)$ operations.
  • For large graphs, iterative or approximation algorithms are often used.
  • For industrial applications with millions of vertices, efficiency is critical.

2.7 Numerical Example

For a graph with $N = 4$, let the adjacency matrix be: $$ \mathbf{A} = \begin{pmatrix} 0 & 1 & 0 & 0 \\ 1 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 \\ 0 & 1 & 1 & 0 \end{pmatrix}. $$ The degree matrix is: $$ \mathbf{D} = \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 3 & 0 & 0 \\ 0 & 0 & 2 & 0 \\ 0 & 0 & 0 & 2 \end{pmatrix}. $$ Thus, the graph Laplacian is: $$ \mathbf{L} = \begin{pmatrix} 1 & -1 & 0 & 0 \\ -1 & 3 & -1 & -1 \\ 0 & -1 & 2 & -1 \\ 0 & -1 & -1 & 2 \end{pmatrix}. $$ The eigenvalues are approximately $[0, 2, 3, 4]$. By examining the orthogonal eigenvector space, structural features of the graph can be revealed.

3. Graph Fourier Transform (GFT)

3.1 Definition of GFT

The Graph Fourier Transform (GFT) is a method to transform signals on a graph into the frequency domain. Just as the traditional Fourier transform decomposes periodic functions into sinusoidal bases, the GFT uses the eigenvectors of the graph Laplacian as the basis to reflect the graph’s structure.

3.2 Mathematical Representation of GFT

Let the signal on the vertices be a vector $\mathbf{x} \in \mathbb{R}^N$, and let $\mathbf{U}$ be the orthogonal matrix of eigenvectors of the graph Laplacian. Then the GFT is defined as: $$ \hat{\mathbf{x}} = \mathbf{U}^\top \mathbf{x}, $$ where $\hat{\mathbf{x}}$ is the representation of the signal in the frequency domain. The inverse transform is given by: $$ \mathbf{x} = \mathbf{U} \hat{\mathbf{x}}. $$

3.3 Concepts of Low and High Frequencies

  • Small eigenvalues correspond to smooth variations across the graph (low frequency).
  • Large eigenvalues represent abrupt changes between adjacent vertices (high frequency).
  • GFT enables spectral analysis that adapts to the graph’s unique structure.

3.4 Applications of GFT

  • Filter design in graph signal processing.
  • Noise removal and compression.
  • Recommender systems.
  • Community detection in social network analysis.

3.5 Python Implementation of GFT

Below is a simple example demonstrating the GFT:

import numpy as np

# Adjacency matrix (example)
A = np.array([[0, 1, 0, 0], [1, 0, 1, 1], [0, 1, 0, 1], [0, 1, 1, 0]], dtype=float)

# Degree matrix
D = np.diag(A.sum(axis=1))

# Graph Laplacian
L = D - A

# Eigenvalues and eigenvectors
eigvals, eigvecs = np.linalg.eigh(L)

# Example signal on vertices
x = np.array([1, 2, 3, 4], dtype=float)

# GFT
xhat = eigvecs.T @ x

# Inverse GFT
x_inv = eigvecs @ xhat

print("Original Signal:", x)
print("Transformed Signal:", xhat.round(2))
print("Inverse Signal:", x_inv.round(2))

Original Signal: [1. 2. 3. 4.]
Transformed Signal: [-5.   -2.04  0.71 -0.58]
Inverse Signal: [1. 2. 3. 4.]
  • The eigenvectors (eigvecs) are used as the Fourier basis.
  • xhat is the frequency domain representation of the signal.
  • x_inv is the reconstructed signal after the inverse GFT.

3.6 Advantages of GFT

  • Enables frequency analysis tailored to graph structures.
  • Supports dimensionality reduction and clustering.
  • Useful for noise reduction and feature extraction.

3.7 Disadvantages of GFT

  • Computationally expensive eigenvalue calculations for large graphs.
  • Inefficient for dynamically updating graphs (re-computation needed).
  • Requires understanding of underlying theory, posing a learning curve.

4. Applications in Industry

4.1 Recommender Systems

GFT can analyze user-item relationships represented as graphs. By decomposing signals using graph eigenvectors, flexible predictions can be made. GFT is often combined with collaborative filtering. Large-scale implementations, such as in e-commerce platforms with tens of millions of users, face efficiency challenges.

4.2 Social Network Analysis

Graph structures represent user connections, allowing community detection and visualization. Eigenvectors help identify clusters or influential nodes, supporting applications like discovering users likely to create viral content.

4.3 Transportation Network Analysis

Graph nodes represent intersections, and edges represent roads or paths. GFT can analyze traffic patterns in the frequency domain, aiding in congestion prediction and route optimization.

4.4 IoT Device Management

Networks of sensors often form large graphs. Eigenvalue spectra can identify abnormal sensors for early intervention. Cluster-level anomaly detection or failure prediction becomes feasible.

5. Numerical and Mathematical Examples

5.1 Eigenvalue Decomposition of a Small Graph Laplacian

Consider a graph with $N = 3$. The adjacency matrix is: $$ \mathbf{A} = \begin{pmatrix} 0 & 2 & 0 \\ 2 & 0 & 1 \\ 0 & 1 & 0 \end{pmatrix}. $$ The degree matrix is: $$ \mathbf{D} = \begin{pmatrix} 2 & 0 & 0 \\ 0 & 3 & 0 \\ 0 & 0 & 1 \end{pmatrix}. $$ Thus, the graph Laplacian is: $$ \mathbf{L} = \begin{pmatrix} 2 & -2 & 0 \\ -2 & 3 & -1 \\ 0 & -1 & 1 \end{pmatrix}. $$ The eigenvalues are approximately $[0, 2, 4]$. The corresponding eigenvectors provide the GFT basis.

5.2 Signal Interpretation Using Eigenvectors

The eigenvector corresponding to eigenvalue 0 usually indicates uniform values across the graph. Higher eigenvalues represent variations localized to specific edges or subgraphs.

5.3 Designing Filters

GFT allows designing filters to enhance or suppress specific frequency components of the signal. For example: $$ \hat{\mathbf{y}} = \mathbf{H} \hat{\mathbf{x}}, $$ where $\mathbf{H}$ is a diagonal filter matrix. The inverse GFT reconstructs the filtered signal: $$ \mathbf{y} = \mathbf{U} \hat{\mathbf{y}}. $$

5.4 Python Example of Filtering

The following code filters low-frequency components of a signal on a graph:

import numpy as np

# Adjacency matrix
A = np.array([[0, 1, 0, 1], [1, 0, 1, 1], [0, 1, 0, 1], [1, 1, 1, 0]], dtype=float)

# Degree matrix
D = np.diag(A.sum(axis=1))

# Laplacian
L = D - A

# Eigenvalues and eigenvectors
eigvals, eigvecs = np.linalg.eigh(L)

# Signal
x = np.array([10, 5, 3, 1], dtype=float)

# GFT
xhat = eigvecs.T @ x

# Filter for low frequencies (threshold = 2)
H = np.diag([1 if val < 2 else 0 for val in eigvals])

# Apply filter
xhat_filtered = H @ xhat

# Inverse GFT
x_filtered = eigvecs @ xhat_filtered

# Evaluate error
error = x - x_filtered
error_norm = np.linalg.norm(error)

print("Original Signal     :", x.round(2))
print("Eigenvalues        :", eigvals.round(2))
print("GFT Coefficients   :", xhat.round(2))
print("Filtered Coeffs    :", xhat_filtered.round(2))
print("Filtered Signal    :", x_filtered.round(2))
print("Error Vector       :", error.round(2))
print("Error Norm         :", error_norm.round(2))

Original Signal     : [10.  5.  3.  1.]
Eigenvalues        : [-0.  2.  4.  4.]
GFT Coefficients   : [-9.5   4.95  2.87  3.46]
Filtered Coeffs    : [-9.5  0.   0.   0. ]
Filtered Signal    : [4.75 4.75 4.75 4.75]
Error Vector       : [ 5.25  0.25 -1.75 -3.75]
Error Norm         : 6.69

This demonstrates how to selectively retain low-frequency components, smoothing the signal.

6. Summary and Practical Applications

6.1 Theoretical Summary

  • The graph Laplacian $\mathbf{L} = \mathbf{D} - \mathbf{A}$ is a fundamental matrix for graph analysis.
  • It always has at least one eigenvalue of 0, which relates to the graph’s connectivity.
  • Eigenvectors serve as spectral bases and are used in GFT.
  • GFT maps vertex signals into the frequency domain, enabling various forms of spectral analysis.

6.2 Implementation Considerations

  • For small graphs, eigenvalue calculations can be easily implemented using NumPy.
  • For large graphs, it is crucial to use specialized algorithms or approximate methods designed for sparse matrices.
  • Python libraries like SciPy or PyTorch can handle sparse matrix operations effectively.
  • Trade-offs between computational time and precision must be carefully managed.

6.3 Benefits in Industry Applications

  • Enables high-dimensional analysis of social graphs or user-item interactions.
  • Detects complex clustering structures that are difficult to identify with simpler methods.
  • Once eigenvalue decomposition is computed, the results can be reused for multiple signal processing tasks.
  • Useful in recommender systems, sensor data analysis, and more.

6.4 Challenges in Industry Applications

  • Eigenvalue decomposition is computationally expensive for large graphs with millions or billions of nodes.
  • Dynamic graphs require repeated eigenvalue calculations whenever the structure changes.
  • The mathematical theory and computational methods require expertise, which can be costly in terms of training and recruitment.

6.5 Recent Developments

  • Integration with Graph Neural Networks (GNNs) is advancing.
  • Spectral GNNs use graph Laplacian eigenvalues to define localized operations.
  • Research into faster graph signal processing and approximation algorithms is ongoing.

Conclusion

This article has provided an overview of the graph Laplacian, its eigenvalues, and the Graph Fourier Transform (GFT). The graph Laplacian is a critical tool for analyzing graph structures and performing spectral clustering. Understanding the meaning of eigenvalues and eigenvectors allows for deeper analysis of graph signals. Through GFT, vertex signals can be transformed into the frequency domain, enabling applications such as smoothing, feature extraction, and noise reduction.

In industry, these techniques can be applied to recommender systems, social network analysis, transportation networks, and IoT sensor data. However, challenges such as the computational cost of eigenvalue decomposition and the difficulty of working with dynamic graphs remain significant barriers. Advances in approximation algorithms and the integration of GFT with GNNs are promising directions for overcoming these challenges.

By mastering the theoretical and practical aspects of graph Laplacians and GFT, data scientists and engineers can unlock new insights into graph-structured data, paving the way for innovative solutions in various fields.