Graph Laplacian

The unnormalized graph Laplacian is defined as L = D - A, where D is the degree matrix (a diagonal matrix of node degrees) and A is the adjacency matrix. Each diagonal entry L_ii equals the degree of node i, and each off-diagonal entry L_ij equals -1 if an edge exists between nodes i and j, and 0 otherwise. This construction captures both local connectivity and global structure.

The graph Laplacian is a positive semi-definite matrix, meaning all its eigenvalues are non-negative (λ_i ≥ 0). This property is crucial because it guarantees that the quadratic form x^T L x = Σ (x_i - x_j)^2 is always non-negative, measuring the smoothness of a signal across the graph's edges. The smallest eigenvalue is always 0, with multiplicity equal to the number of connected components.

The eigendecomposition L = U Λ U^T reveals the graph's frequency domain. The eigenvectors (columns of U) form an orthonormal basis that generalizes the Fourier transform to graphs, ordered by their corresponding eigenvalues (Λ). Eigenvectors with small eigenvalues represent low-frequency signals that vary slowly across the graph, while those with large eigenvalues capture high-frequency variations between neighboring nodes.

Two common normalized versions exist to account for heterogeneous degree distributions:

• Symmetric normalized Laplacian: L_sym = I - D^(-1/2) A D^(-1/2), with eigenvalues bounded in [0, 2]
• Random walk normalized Laplacian: L_rw = I - D^(-1) A, closely related to diffusion processes These variants are preferred in spectral GNNs like the Graph Convolutional Network (GCN) to prevent gradient explosion from high-degree nodes.

The second smallest eigenvalue, λ_2, is known as the algebraic connectivity or Fiedler value. It measures how well-connected the overall graph is: λ_2 > 0 if and only if the graph is connected. The corresponding Fiedler vector provides an approximate solution to the minimum cut problem and is used directly in spectral clustering to partition nodes by their sign.

Spectral graph neural networks define convolution as multiplication in the frequency domain: g_θ * x = U g_θ(Λ) U^T x, where g_θ is a learnable filter on the eigenvalues. To avoid the O(n^3) cost of eigendecomposition, modern approaches use polynomial approximations like Chebyshev polynomials, enabling localized filtering without explicit spectral decomposition. This is the theoretical basis for architectures like ChebNet and GCN.

An unsupervised learning technique that uses the eigenvalues and eigenvectors of the Graph Laplacian to partition nodes into clusters. The algorithm:

• Computes the first k eigenvectors of the Laplacian
• Embeds nodes into a low-dimensional space defined by these vectors
• Applies k-means to the embedded representation This method excels at detecting non-convex clusters and is foundational for identifying tightly-knit fraud rings that are not linearly separable in the original feature space.

The mathematical operation at the heart of spectral Graph Neural Networks (GNNs). It defines convolution on graphs by:

• Decomposing the graph signal using the Fourier basis (eigenvectors of the Laplacian)
• Applying a learnable filter in the spectral domain
• Transforming the signal back to the spatial domain This is the core mechanism behind the Graph Convolutional Network (GCN), enabling the aggregation of neighborhood information based on the graph's intrinsic structure.

A fundamental measure of how much a signal varies across connected nodes. The Dirichlet energy of a signal x is defined as xᵀLx, where L is the Graph Laplacian. A low value indicates that connected nodes share similar values—a property exploited in:

• Semi-supervised learning: penalizing rapid signal changes to propagate labels
• Anomaly detection: flagging nodes whose features are highly dissimilar from their neighbors, a strong indicator of fraudulent behavior in a transaction graph

A technique to make spectral convolutions computationally tractable for large graphs. Exact eigendecomposition of the Laplacian is O(n³). Chebyshev polynomials approximate the spectral filter as a K-order polynomial of the Laplacian, enabling:

• Localized filtering: each node's update depends only on its K-hop neighborhood
• Linear complexity: computation scales with the number of edges This approximation is the bridge between pure spectral methods and efficient spatial GNNs like ChebNet.

The second smallest eigenvalue of the Graph Laplacian, denoted λ₂, also known as the Fiedler value. It is a critical measure of a graph's overall connectivity:

• λ₂ > 0: the graph is connected; higher values indicate stronger cohesion
• λ₂ = 0: the graph is disconnected, revealing isolated components In fraud analytics, a sudden drop in algebraic connectivity over time can signal the fragmentation of a transaction network or the isolation of a fraud ring attempting to hide its activity.

Two primary variants of the Laplacian matrix, each with distinct spectral properties:

• Unnormalized (L = D - A): sensitive to node degree; high-degree nodes dominate the spectrum
• Symmetric normalized (L_sym = I - D⁻¹/²AD⁻¹/²): scales influence by degree, making it robust for graphs with power-law degree distributions
• Random walk normalized (L_rw = I - D⁻¹A): relates directly to diffusion processes Choosing the correct variant is critical for financial graphs where transaction volume varies wildly between accounts.