Spectral Layout via Graph Laplacian

Computes a graph layout using the spectral geometry of the graph Laplacian. Nodes that are well-connected in the graph are placed close together, while structurally distant nodes are separated. Layout coordinates are always passed through normalize_layout_coordinates before being returned.

Usage

layout_with_spectral(
  g,
  dim = 3,
  normalize_laplacian = TRUE,
  solver = c("svd", "eigen"),
  jitter_sd = 0,
  seed = 123,
  verbose = FALSE,
  ...
)

Arguments

g

A tbl_graph or igraph object.

dim

Number of dimensions for the layout (default is 3). Must be 2 or 3.

normalize_laplacian

Whether to use the normalized graph Laplacian. Only supported for solver = "eigen"; the SVD solver always uses the normalized Laplacian.

solver

One of "svd" (default) or "eigen". See the sections above. "svd" requires a named bipartite graph.

jitter_sd

Adds a small amount of jitter to the node coordinates. Degree-1 nodes can have nearly identical solutions and therefore overlay each other when plotting. Setting jitter_sd = 1e-2 is typically sufficient to displace these while having a negligible effect on higher-degree node coordinates. By default, no jitter is applied.

seed

Random seed for reproducibility.

verbose

Whether to print messages about the graph and eigenvalues/singular values.

...

Additional arguments passed to RSpectra::eigs_sym or irlba::irlba.

Value

A numeric matrix of layout coordinates with dim columns named "x", "y", and (when dim = 3) "z", with one row per node in g.

eigen

The layout coordinates are the eigenvectors corresponding to the (dim) smallest non-trivial eigenvalues of the Laplacian or the normalized Laplacian, also known as Laplacian Eigenmaps or the spectral embedding of the graph.

1. Compute the sparse adjacency matrix \(A\). When normalize_laplacian = FALSE, form the unnormalized graph Laplacian \(L = D - A\), where \(D\) is the diagonal degree matrix. When normalize_laplacian = TRUE, form the normalized graph Laplacian \(L = I - D^{-1/2}AD^{-1/2}\), where \(D^{-1/2}\) is the inverse-square-root diagonal degree matrix. The Laplacian is positive semi-definite, so all eigenvalues are non-negative.

2. Use an iterative sparse eigensolver (RSpectra::eigs_sym) to compute the dim + 1 smallest-magnitude eigenvalues and their eigenvectors. For a connected graph, the smallest eigenvalue is exactly 0 and its eigenvector is the trivial constant vector.

3. Discard the trivial eigenvector (eigenvalue \(\approx 0\)) and set the remaining dim eigenvectors as layout coordinates. If normalize_laplacian = TRUE, the coordinates are corrected using \(D^{-1/2}\) (mapping back to the random-walk Laplacian embedding).

svd

The layout coordinates are the singular vectors corresponding to the (dim) largest non-trivial singular values of the normalized biadjacency matrix. This solver requires a bipartite graph (attr(g, "type") == "bipartite") with a node_type vertex attribute and named vertices, and always uses the normalized Laplacian (normalize_laplacian = TRUE).

Spectral graph layouts require finding the eigenvectors corresponding to the smallest non-zero eigenvalues of the Laplacian matrix. For bipartite graphs, finding the bottom eigenvalues of the normalized Laplacian is equivalent to finding the largest singular values of the normalized biadjacency matrix. This allows replacing the eigenvalue solver with an SVD solver tailored for rectangular data, which often converges faster.

1. Compute the sparse biadjacency matrix \(B\), the diagonal degree matrices \(D_1\) (row sums of \(B\)) and \(D_2\) (column sums of \(B\)), then form the normalized biadjacency matrix \(B_{\mathrm{norm}} = D_1^{-1/2} B D_2^{-1/2}\).

2. Use singular value decomposition (irlba::irlba) to compute the dim + 1 largest-magnitude singular values and their singular vectors from \(B_{\mathrm{norm}}\). For a connected graph, the largest singular value is exactly 1.

3. Discard the trivial singular vector (singular value \(\approx 1\)) and return the remaining dim singular vectors as layout coordinates. Left and right singular vectors are combined so that every node receives coordinates. The coordinates are corrected using \(D_1^{-1/2}\) and \(D_2^{-1/2}\) (mapping back to the random-walk Laplacian embedding).

See also

layout_with_weighted_pmds(), layout_with_coarsened_pmds(), normalize_layout_coordinates(), ComputeLayout()

Examples

library(dplyr)
se <- ReadPNA_Seurat(minimal_pna_pxl_file()) %>%
  LoadCellGraphs(cells = colnames(.)[4], verbose = FALSE)
#> ✔ Created a <Seurat> object with 5 cells and 158 targeted surface proteins

cg <- CellGraphs(se)[[4]]
g <- cg@cellgraph

xyz <- layout_with_spectral(g) %>%
  as_tibble(.name_repair = ~ c("x", "y", "z"))

plotly::plot_ly(
  xyz,
  x = ~x, y = ~y, z = ~z,
  mode = "markers",
  type = "scatter3d",
  marker = list(size = 1)
)