# Spectral Graph Theory

## Prerequisites
- SVD, properties of eigenvalues and eigenvectors of symmetric matrices: [Overview](https://towardsdatascience.com/the-properties-and-application-of-symmetric-matrice-1dc3f183de5a)
- Positive semi-definite matrices: [Wiki](https://en.wikipedia.org/wiki/Definite_matrix)
- Familiarity with un-directed graphs, adjacency matrices and degree matrices
- Connected components of a graph: [Overview](https://www.geeksforgeeks.org/connected-components-in-an-undirected-graph/)

## A really good and concise introduction of SGT
- https://www.cl.cam.ac.uk/~lc647/drafts/Spectral_Graph_Theory.pdf

## Graph Laplacian (L)
A square matrix `L = D - A` where,
- `D` = degree matrix, a diagonal matrix where `D[i,i] = degree of node i`
- `A` = adjacency matrix where `A[i,j] = similarity between nodes i and j = A[j,i] for undirected graph`
- `D` can be created from `A` by `D = np.diagflat(A.sum(axis=-1, keepdims=True))`

## Some obvious properties of `L`
- it is symmetric
- sum of every row and column is `0`
- diagonal elements are non-negative whereas non-diagonal elements are non-positive
- it does not contain any information about self-loops (edges with the same source and target vertices)

## Some less obvious but highly useful properties
- L is positive semi-definite.
- In other words $x^TLx \ge 0 \space \forall \space x$
- This means that all eigenvalues are non-negative and all eigenvectors are orthogonal to each other
- Since the sum of all rows is zero, the sum of all column vectors of L is a zero-vector.
- In other words $L.\overrightarrow{1} = \overrightarrow{0} = 0.\overrightarrow{1}$
- Thus $\overrightarrow{1}$ is an eigenvector of `L` with eigenvalue `0`
- Since all eigenvalues are non-negative, `0` is the smallest eigenvalue of `L`
- Consider an eigenvector $\overrightarrow{v} \ne \overrightarrow{1}$ of `L`
- Since all eigenvectors are orthogonal to each other, we have $\overrightarrow{v}.\overrightarrow{1} = 0$ which means $\Sigma_i v_i = 0 \text{ where } v_i \text{ are scalar components of } v$
- This means that some values of `v` are positive and some are negative
- This can be interpreted as partitioning of nodes into two groups: one corresponding to positive values and one corresponding to negative values

## Relationship between connected components of a graph and eigenvalues
- Let's name the eigenvalues of `L`: $\lambda_1 \ge \lambda_2 \ge \lambda_3 \ge ... \lambda_n=0$
- If the number of connected components is 1 i.e. the entire graph is connected then $\lambda_{n-1} \gt 0$
- If the number of connected components is 2 then $\lambda_{n} = \lambda_{n-1} = 0 \text{ and } \lambda_{n-2} \gt 0$
- In general, if the number of connected components is k then $\lambda_n = \lambda_{n-1} = \lambda_{n-2} = ... = \lambda_{n-k+1} = 0 \text{ and } \lambda_{n-k} \gt 0$
- An important thing to note is that
- as a fully connected graph moves closer to a graph with two connected components, $\lambda_{n-1}$ moves closer to `0`
- thus, the smaller the value of $\lambda_{n-1}$, the more disconnected the graph is: this can be used to determine how similar the nodes in a graph are

## Relationship between eigenvalues and optimization (minimization) of $x^TLx \text{ where } \lVert x \rVert = 1$

For this section, we use $u$ to denote a unit vector. The eigenvector corresponding to the eigenvalue $\lambda_{i}$ is denoted by $\overrightarrow{\lambda_{i}}$

- $argmin_u \space u^TLu = \overrightarrow{\lambda_{n}} = \overrightarrow{1}$ and $min_u \space u^TLu = \lambda_{n}$ i.e the smallest eigenvalue/eigenvector pair
- $argmin_{u \perp \overrightarrow{\lambda_{n}}} \space u^TLu = \overrightarrow{\lambda_{n-1}}$ and $min_{u \perp \overrightarrow{\lambda_{n}}} \space u^TLu = \lambda_{n-1}$ i.e the second smallest eigenvalue/eigenvector pair
- $argmin_{u \perp \overrightarrow{\lambda_{n}}, \overrightarrow{\lambda_{n-1}}} \space u^TLu = \overrightarrow{\lambda_{n-2}}$ and $min_{u \perp \overrightarrow{\lambda_{n}}, \overrightarrow{\lambda_{n-1}}} \space u^TLu = \lambda_{n-2}$ i.e. the third smallest eigenvalue/eigenvector pair
- ... and so on

Thus when you think of the second smallest eigenvector, you should think of it as the vector that minimizes $u^TLu$ subject to the condition that $u^T \perp \overrightarrow{1}$.

Now we focus on the expression $u^TLu$. Note that $u_i$ are scalars of the unit vector $u$. Then we have:

$u^TLu = \Sigma_{edge \space ij} \text{ (weight of edge ij) . } (u_i - u_j)^2$

Since we want to minimize $u^TLu, \space u_i \text{ and } u_j$ must be small when weight of edge `ij` is big.
Now if $\text{(weight of edge ij)} \propto \text{ (similarity of vertices i and j) }$then similar vertices i and j will have similar values of the second smallest eigenvector $\lambda_{n-1} \space: u_i \text{ & } u_j$ respectively.

###### tags: `math`