Graphs Spectral Methods

The [[Ratio Cut]] Graph Cuts Cut For a subset of nodes $\mathcal A\subset \mathcal V$, the rest of nodes can be denoted as $\bar {\mathcal A} = \mathcal V \setminus \mathcal A$. In other words, $\mathcal A \cup \bar {\mathcal A} = \mathcal V$ and $\mathcal A \cap \bar {\mathcal A} = \emptyset$. That being said, the nodes can be partitioned into two subsets, $\mathcal A$ and $\bar {\mathcal A}$. The cut of this partition is defined as the total number of edges between them, $$ \operatorname{Cut} \left( \mathcal A, … is closely related to the [[Graph Laplacians]] Graph Laplacians Laplacian is a useful representation of graphs. The unnormalized Laplacian is $$ \mathbf L = \mathbf D - \mathbf A, $$ where $\mathbf A$ is the [[adjacency matrix]] Graph Adjacency Matrix A graph $\mathcal G$ can be represented with an adjacency matrix $\mathbf A$. There are some nice and clear examples on wikipedia1, for example, $$ \begin{pmatrix} 2 & 1 & 0 & 0 & 1 & 0\\ 1 & 0 & 1 & 0 & 1 & 0\\ 0 & 1 & 0 & 1 & 0 & 0\\ 0 & 0 & 1 & 0 & 1 & 1\\ 1 & 1 & 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 1 & 0 & 0 … .

Two Clusters

Given a vector $\mathbf a$,

$$ \mathbf a[u] = \begin{cases} \sqrt{ \frac{ \lvert \bar{\mathcal A} \rvert }{ \lvert \mathcal A \rvert } }, & u\in \mathcal A \\ -\sqrt{ \frac{ \lvert \mathcal A \rvert } { \lvert \bar{\mathcal A} \rvert }}, & u\in \bar{\mathcal A} \end{cases}. $$

Using $\mathbf a$, we have¹

$$ \mathbf a^T \mathbf L \mathbf a = \lvert \mathcal V \rvert \operatorname{RatioCut}(\mathcal A, \bar{\mathcal A}). $$

This result is useful as the Rayleigh-Ritz theorem tells us that $\mathbf a$ is the second smallest eigenvector of $\mathbf L$.

We can assign nodes to different groups based on $\mathbf a$.

• If $\mathbf a[u] \geq 0$, we know $u\in\mathcal A$;
• If $\mathbf a[u] \lt 0$, we know $u\in\bar{\mathcal A}$.

Multiple Clusters

Refer to chapter 2 of Hamilton2020¹.