Graphs Spectral Methods

#Graph #Basics #Statistics

The Ratio Cut Graph Cuts Cut For a subset of nodes $\mathcal A\subset \mathcal V$, with the rest of nodes $\bar {\mathcal A} = \mathcal V \setminus \mathcal A$. For $k$ such subsets of nodes, $\mathcal A_1, \cdots, $\mathcal A_k$, the cut is the total number of edges between $\mathcal A$ and $\bar{\mathcal A}$ 1, $$ \operatorname{Cut} \left( \mathcal A_1, \cdots, $\mathcal A_k \right) = \frac{1}{2} \sum_{k=1}^K \lvert (u, v)\in \mathcal E: u\in \mathcal A_k, v\in \bar{\mathcal A_k} \rvert. $$ For smaller cut value, the … 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}. $$

We have

  • $\sum_{u\in\mathcal V} \mathbf a[u] = 0$, and
  • $\lVert{\mathbf a}\rVert = \lvert \mathcal V \rvert$.

Using $\mathbf a$, we have1

$$ \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 Hamilton20201.


  1. Hamilton2020 Hamilton WL. Graph Representation Learning. Morgan & Claypool Publishers; 2020. pp. 1–159. doi:10.2200/S01045ED1V01Y202009AIM046  ↩︎

Published: by ;

L Ma (2021). 'Graphs Spectral Methods', Datumorphism, 09 April. Available at: https://datumorphism.leima.is/wiki/graph/basics/graph-spectral-methods/.

Current Ref:

  • wiki/graph/basics/graph-spectral-methods.md