Laplacian eigenmap embedding

Embeds graph nodes by the low eigenvectors of the generalized Laplacian problem \(L f = \lambda D f\) with \(L = D - W\) (source Sec. 2, algorithm step 3), dropping the trivial constant eigenvector at \(\lambda_0 = 0\). Solved through the equivalent symmetric problem \(L_{sym} = D^{-1/2} L D^{-1/2}\) whose eigenvectors v give \(f = D^{-1/2} v\), using a deterministic cyclic Jacobi rotation identical to the Python arm (so both arms return bit-comparable embeddings; LAPACK eigenvector conventions are not relied upon). Sign convention: each eigenvector is scaled so its largest-magnitude entry is positive.

Usage

LapEig(A, k = 2L)

laplacian_eigenmaps(A, k = 2L)

Arguments

A

Symmetric non-negative weight matrix; every node needs positive degree.

k

Embedding dimension.

Value

List with embedding (n by k), eigenvalues, all_eigenvalues (ascending), k, n.

References

Belkin, M. and Niyogi, P. (2003). Laplacian eigenmaps for dimensionality reduction and data representation. Neural Computation, 15(6), 1373-1396, Secs. 2-3.

Examples

C4 <- matrix(0, 4, 4)
C4[cbind(1:4, c(2, 3, 4, 1))] <- 1; C4 <- C4 + t(C4)
LapEig(C4, k = 2)
#> $embedding
#>            [,1]       [,2]
#> [1,] -0.2730617  0.4188524
#> [2,]  0.4188524  0.2730617
#> [3,]  0.2730617 -0.4188524
#> [4,] -0.4188524 -0.2730617
#> 
#> $eigenvalues
#> [1] 1 1
#> 
#> $all_eigenvalues
#> [1] 1.911615e-16 1.000000e+00 1.000000e+00 2.000000e+00
#> 
#> $k
#> [1] 2
#> 
#> $n
#> [1] 4
#> 
#> $method
#> [1] "Laplacian eigenmap, generalized L f = lambda D f via Jacobi"
#>