spectral embedding

[[concept]]

Spectral Embedding

Suppose we are given a diagonalizable adjacency matrix $A$ for a graph with nodes partitioned into $C$ classes. Suppose we know the assignments for some of the nodes $T \subset Vertices$ . Let $V_{c}$ be the top $C$ eigenvectors of $A$ .

Finding the spectral embedding amounts to solving the problem$$\min_{f} \sum_{i \in T} \mathbb{1}(f(A){i} = y)$$ where $f$ comes from our hypothesis class ${f : f (A) = σ (V_{c} W), W \in R^{C \times C}}$ and $σ$ is a predetermined pointwise nonlinearity.

Notes

This can be thought of as an FC-NN on the $C$ -dimensional embeddings $u_{1}, \dots, u_{n}$ of the nodes of the graph into feature space.

in practice, a surrogate is usually used for the 0-1 loss
to find the optimal $f$ ie the optimal $W$ , we solve using gradient descent methods
this is the semi-supervised version of spectral clustering (clustering assigns communities to all nodes, embedding assigns communities to nodes with unknown community)
^definition

Spectral Embedding Problem

$min_{f} \sum_{i \in T} 1 (f (A)_{i} = y_{i}), f \in {f (A) = σ (V_{c} W), W \in R^{C \times C}}$

^problem

Mentions

File
feature-aware spectral embeddings
sometimes spectral algorithms fail
spectral clustering
2025-02-10 graphs lecture 6
2025-02-12 graphs lecture 7