Graph Laplacian Matrix

The unnormalized Graph Laplacian is defined as L = D - A, where D is the diagonal degree matrix and A is the adjacency matrix. Each diagonal entry D_ii equals the degree of node i, while off-diagonal entries L_ij = -1 if an edge exists between nodes i and j, and 0 otherwise. For a graph with n nodes, L is an n × n symmetric positive semi-definite matrix. The normalized variants—symmetric: L_sym = I - D^(-1/2) A D^(-1/2) and random walk: L_rw = I - D^(-1) A—are often preferred in practice to mitigate the influence of high-degree nodes.

The quadratic form of the Laplacian, f^T L f, measures the smoothness of a signal f defined on the graph's nodes. It expands to:

• Σ (f_i - f_j)² over all edges (i,j)

This sum penalizes large differences between connected nodes. A small value indicates the signal varies slowly across the graph topology, while a large value indicates high-frequency variation. This property makes the Laplacian the natural regularizer for graph-based semi-supervised learning, where the goal is to find label assignments that are smooth with respect to the underlying data manifold.

Since L is real symmetric, it admits an eigendecomposition L = U Λ U^T, where:

• Λ is a diagonal matrix of non-negative eigenvalues 0 = λ_0 ≤ λ_1 ≤ ... ≤ λ_(n-1)
• U is an orthonormal matrix whose columns are the corresponding eigenvectors

The eigenvectors form the graph Fourier basis, ordered by frequency. The eigenvalue λ_k quantifies the frequency of eigenvector u_k—small eigenvalues correspond to slowly-varying signals across the graph. The Graph Fourier Transform of a signal x is x̂ = U^T x, projecting the signal onto this spectral basis. The inverse transform is x = U x̂.

Convolution on a graph is defined in the spectral domain via the Convolution Theorem: the convolution of a signal x with a filter g_θ is:

• g_θ ★ x = U g_θ(Λ) U^T x

where g_θ(Λ) is a diagonal matrix of filter parameters applied to the eigenvalues. This operation is the foundation of Spectral Graph Convolutional Networks. However, it is computationally expensive—requiring full eigendecomposition of L (O(n³)) and dense matrix multiplications with U. This motivated the development of polynomial approximations like ChebNet and the first-order Graph Convolutional Network (GCN) approximation.

The second smallest eigenvalue λ_1 is called the algebraic connectivity, and its corresponding eigenvector u_1 is the Fiedler vector. Key properties:

• λ_1 > 0 if and only if the graph is connected
• Larger λ_1 indicates a more robustly connected graph, harder to disconnect
• The Fiedler vector provides an approximate solution to the minimum normalized cut problem

In cellular topology graphs, λ_1 can quantify the resilience of the interference graph—a low value indicates a bottleneck where removing a few edges partitions the network into isolated clusters, creating natural boundaries for frequency reuse planning.

To avoid the O(n³) eigendecomposition cost, spectral filters are approximated by K-order polynomials of the Laplacian:

• g_θ ★ x ≈ Σ θ_k T_k(L̃) x (Chebyshev polynomials)
• g_θ ★ x ≈ θ (I + D^(-1/2) A D^(-1/2)) x (1st-order GCN)

This is critically important because a K-order polynomial in L is strictly K-localized—the output at node i depends only on nodes within K hops. This transforms a global spectral operation into an efficient local message-passing operation, enabling GNNs to scale to massive cellular topologies with thousands of base stations while preserving the spectral motivation.

A GNN operation that defines convolution in the Fourier domain of the graph Laplacian. By decomposing the Laplacian into its eigenvectors and eigenvalues, graph signals can be transformed into the spectral domain, filtered, and transformed back. This enables the design of frequency-specific filters that capture smooth or oscillatory patterns across the graph topology.

• The Laplacian's eigenvectors serve as the graph Fourier basis
• Eigenvalues correspond to frequencies (small = low frequency, large = high frequency)
• Chebyshev polynomial approximations avoid expensive eigendecomposition

A diagonal matrix D where each diagonal entry Dᵢᵢ equals the degree (number of connections) of node i. The degree matrix is a direct component of the Laplacian definition: L = D - A.

• For weighted graphs, entries are the sum of incident edge weights
• The normalized Laplacian uses D^(-1/2) for symmetric normalization
• Self-loops in GNNs modify the degree matrix by adding 1 to each diagonal entry

A square matrix A where Aᵢⱼ = 1 if an edge exists between nodes i and j, and 0 otherwise. The adjacency matrix encodes the raw connectivity structure of the graph and is subtracted from the degree matrix to form the Laplacian: L = D - A.

• For weighted graphs, entries store edge weights instead of binary values
• The adjacency matrix alone lacks normalization, making the Laplacian essential for stable spectral analysis
• Powers of A (A², A³) reveal multi-hop connectivity patterns

The projection of a graph signal onto the eigenvectors of the Laplacian matrix, analogous to the classical Fourier transform decomposing a signal into sinusoidal components. Smooth signals concentrate energy in low-frequency (small eigenvalue) components.

• The transform is defined as x̂ = Uᵀx, where U contains the Laplacian eigenvectors
• The inverse transform is x = Ux̂
• Enables frequency-domain filtering before the advent of spatial GNNs

An unsupervised learning algorithm that uses the eigenvectors of the graph Laplacian to partition nodes into clusters. By embedding nodes into a low-dimensional space spanned by the first k eigenvectors and applying k-means, it identifies communities that minimize the normalized cut criterion.

• The Fiedler vector (second smallest eigenvector) provides the optimal bipartition
• The eigengap heuristic helps determine the number of clusters
• Directly leverages the Laplacian's spectral properties for structure discovery

A technique to approximate spectral graph convolutions without computing the full eigendecomposition of the Laplacian. By expressing the filter as a truncated Chebyshev polynomial expansion of the scaled Laplacian L̃, the convolution becomes a localized, K-hop operation.

• Reduces computational complexity from O(N³) to O(K|E|)
• Chebyshev polynomials are recursively defined: Tₖ(x) = 2xTₖ₋₁(x) - Tₖ₋₂(x)
• Forms the theoretical bridge between spectral and spatial GNNs like ChebNet and GCN