Introduction and Problem Definition

Here we study the important class of spectral methods for understanding networks. Spectral clustering means, we will be using eigenvectors and eigenvalues of the matrix representations of the graphs.

The spectral clustering algorithms we explore generally consist of three basic stages

Pre-processing

Construct a matrix representation of the graph

Decomposition

Compute eigenvalues and eigenvectors of the matrix representation. And map each point to a lower-dimensional representation based on one or more eigenvectors.

Grouping

Assign points to two or more clusters, based on the new representation.

Problem Definition

Given an undirected graph $G(V,E)$ we need to be able to divide vertices into two disjoint groups A, B.

How can we define a good partition of $G$? And how can we efficiently identify such a partition.

Until now we defined things like modularity and such to identify the best partition with in a graph. Now we approach the same problem using a different criterion. Null models, modularity is a physics view of the partitioning problem, this will be a computer science view. Here we will have approximation guarantees of how well our methods work.

Graph Partitioning Criterion

Maximize the number of within-group connections and minimize the number of between-group connections.

Lets define the graph partitioning objective as a function as the edge cut of the partition. Cut is the set of edges with one endpoint in each group.

$cut(A,B)=\sum _{i\in A,j\in B}{w}_{ij}$

If we define the criterion as Minimum-cut ${\mathrm{argmin}}_{A,B}cut(A,B)$, there will be some edge cases where dangling nodes will consider themselves as a different group when there are much better partitioning of the graphs available. It only considers external cluster connections but not internal more non obvious wrt cut cluster connectivity.

Conductance [Shi-Malik '97]

Conductance is defined as connectivity between groups relative to the density of each group.

$\varphi (A,B)=\frac{cut(A,B)}{min(vol(A),vol(B))}$

Volume is total weighted degree of the nodes in a group. We want the conductance to be as small as possible, and its small when the volume of the both groups is as big as possible. And we use minimum volume in a way to force both groups to be as big as possible. Intuitively we want to split the graph into two similar sized groups such that the cut is small. Conductance produces much more balanced partitions, unlike using just Cut. And computing the best conductance cut is NP-hard.

Spectral Graph Theory

Spectral graph partitioning that gives us an approximation guarantee to find the cut that optimizes conductance .

Let $A$ be the adjacency matrix of undirected graph $G$ and $x$ a vector in ${\mathcal{R}}^n$ with components $(x_1,\cdots x_n)$. We can think of it as a label or a value respective to each node in $G$. Every node $i$ has it's own corresponding $x_i$

And now $y=A.x$

$\left(\begin{array}{ccc}{a}_{11}& \cdots & a_{1n}\\ ⋮& \ddots & ⋮\\ a_{n1}& \cdots & a_{nn}\end{array}\right).\left(\begin{array}{c}{x}_1\\ ⋮\\ x_n\end{array}\right)=\left(\begin{array}{c}{y}_1\\ ⋮\\ y_n\end{array}\right)$

$y_i=\sum _{j=1}n{A}_{ij}{x}_j=\sum _{(i,j)\in E}{x}_j$

When we multiply our adjacency matrix with $x$, we get another vector $y$ whose elements at a position $i$ is just sum of all the corresponding $x$ values of nodes that have an edge to node $i$. Entry $y_i$ is sum of labels $x_j$ of neighbors of $i$.

Eigenvectors and Eigenvalues of a matrix $A$ are defined as the solution to the equation $A.x=\lambda .x$. Where $x$ is our eigenvector and lambda our eigenvalue. Multiplying a matrix with a vector results in scaling the original vector and rotates it. When you multiply a matrix with one of its eigenvectors, it just scales the vector and does not rotate it. And it scales it by eigenvalue amount. For any matrix there are some favoured vectors/directions and when the matrix acts upon these favoured vectors, it just scales the vector with no rotation. If we consider the maximum eigenvalue of a matrix A and its acted upon by the corresponding eigenvector, the result will be the maximum, no other vector when acted upon by this matrix will get as stretched as this eigenvector.

If we consider a eigenvector and corresponding eigenvalue of our adjacency matrix, with each element in the eigenvector labeling each node. And when we the sum all the x values of neighbours of node $i$ we get a scaled version of $x_i$. $y_i$ is essentially eigenvalue times $x_i$ even though its sum of neighbouring x values of node i.

Spectral Graph Theory is branch of applied mathematics, that analyses the spectrum of a matrix representing $G$. Where spectrum represents the Eigenvectors $x^{(i)}$ of a graph, ordered by its magnitude of their corresponding eigenvalues $\Lambda =\{{\lambda }_1,{\lambda }_2,\cdots {\lambda }_n\}$ where ${\lambda }_1\le {\lambda }_2\le \cdots \le {\lambda }_n$

Example: d-Regular Graph.

For a connected graph $G$ with all $d$-degree nodes, $G$ is called $d$-regular.

Consider the vector $x=[1,1,\cdots 1]$. If we multiple the Adjacency matrix of a $d$-regular matrix with the vector $x$ we will just be getting $d.x$. As its a d-regular all nodes will be having d neighbor. And $A.x$ at $i$ is just sum of $x$ values of node $i$. As multiplying $A$ with $x$ is giving us a scaled $x$ by times $d$, we consider $x$ here is an eigenvector and $d$ corresponding eigenvalue.

$$\begin{gathered} x=[1,1,\cdots 1] \\ A.x=[d,d,\cdots d]=\lambda .x \\ \text{with }\lambda =d \end{gathered}$$

Turns out for a $d$-regular graph, $d$ is the largest eigenvalue and $[1,1,\cdots 1]$ the corresponding eigenvector.

TODO: proof of the above statement in pdf

Example: Graph on 2 Components

Consider a Graph $G$ with two $d$-regular disconnected components. What are some eigenvectors.

Suppose $A$ and $B$ are the components and lets consider $x$ with all 1s on $A$ and 0s on $B$.

$$\begin{gathered} x^{\prime }=[\underset{|A|}{1,\cdots ,1},\underset{|B|}{0,\cdots ,0}{]}^T\text{ then }A.x^{\prime }=[d,\cdots ,d,0,\cdots ,0{]}^T \\ {x}^{\prime \prime }=[0,\cdots ,0,1,\cdots ,1{]}^T\text{ then }A.x^{\prime \prime }=[0,\cdots ,0,d,\cdots ,d{]}^T \end{gathered}$$

Both vectors corresponding $\lambda =d$

Hence for a graph with two $d$-regular disconnected components ${\lambda }_n={\lambda }_{n-1}$. The two largest eigenvalues are the same. We found an eigenvector of multiplicity 2, meaning two eigenvectors correspond to the same eigenvalue. Intuitively if a graph has multiple connected components, the multiplicity of the largest eigenvalue tells us number of connected components it has.

From this intuition, consider a graph that almost has two connected components, the largest eigenvalue and the second largest eigenvalue will be very close to each other. ${\lambda }_n-{\lambda }_{n-1}\approx 0$. The second largest eigenvalue will tell us what nodes should be in component $A$ and what nodes should be in component $B$

Eigenvectors are orthogonal, hence if the $d$-regular graph is connected then we already know that $x_n=[1,\cdots ,1]$ is the eigenvector corresponding the largest eigenvalue. This implies $x_{n-1}$ must sum to zero. Because $x_n.x_{n-1}=0\to {\sum }_i{x}_n[i].x_{n-1}[i]={\sum }_i{x}_{n-1}[i]=0$

$x_{n-1}$ "splits" the nodes into two groups, nodes with $x_{n-1}>0$ and $x_{n-1}<0$. So in principle we could look at the eigenvector of the 2nd largest eigenvalue and declare nodes with positive label in $A$ and negative label in $B$.

Matrix Representations

Adjacency matrix($A$)

size $n\times n$ with $a_{ij}=1$ if edge between $i$ and $j$, for a undirected graph $A$ is symmetric, has $n$ real eigenvalues and eigenvectors are real-valued and orthogonal.

$A=\left(\begin{array}{cccccc}0& 1& 1& 0& 1& 0\\ 1& 0& 1& 0& 0& 0\\ 1& 1& 0& 1& 1& 0\\ 0& 0& 1& 0& 1& 1\\ 1& 0& 0& 1& 0& 1\\ 0& 0& 0& 1& 1& 0\end{array}\right)$

Degree matrix($D$)

Diagonal Matrix of size $n\times n$, $D=[d_{ii}],d_{ii}=$ degree of the node $i$

$D=\left(\begin{array}{cccccc}3& 0& 0& 0& 0& 0\\ 0& 2& 0& 0& 0& 0\\ 0& 0& 3& 0& 0& 0\\ 0& 0& 0& 3& 0& 0\\ 0& 0& 0& 0& 3& 0\\ 0& 0& 0& 0& 0& 2\end{array}\right)$

Laplacian matrix($L$)

Laplacian matrix is defined as $L=D-A$, your degree matrix minus the adjacency matrix. -1 where ever there is an edge and positive degrees wherever there is an edge. $n\times n$ size symmetric matrix.

$L=\left(\begin{array}{cccccc}3& -1& -1& 0& -1& 0\\ -1& 2& -1& 0& 0& 0\\ -1& -1& 3& -1& 0& 0\\ 0& 0& -1& 3& -1& -1\\ -1& 0& 0& -1& 3& -1\\ 0& 0& 0& -1& -1& 2\end{array}\right)$

Trivial eigenpair in case of a laplacian matrix is $x=[1,\cdots ,1]$ then $L.x=0$ and so $\lambda ={\lambda }_1=0$

The smallest eigenvalue is 0, unlike in case of adjacency matrix, the eigenvalue corresponding to $[1,\cdots ,1]$ is the largest.

Also eigenvalues of $L$ are non-negative real numbers. And eigenvectors are all real and are always orthogonal.

TODO: Proof for the laplacian matrix properties above mentioned is in the pdf.

${\lambda }_2$ as an Optimization Problem

For any symmetric matrix M:

${\lambda }_2=\underset{x:x^T{w}_1=0}{\min }\frac{x^{T}Mx}{x^{T}x}$ where $w_1$ is eigenvector corresponding to ${\lambda }_1$

TODO: Proof of this is in the pdf

In our case $M$ is $L$, to figure out the meaning of $\min x^{T}Lx$ on $G$

$$\begin{gathered} x^{T}Lx={\sum }_{i,j=1}^n{L}_{ij}{x}_i{x}_j \\ ={\sum }_{i,j=1}^n(D_{ij}-A_{ij})x_i{x}_j \\ ={\sum }_i{D}_{ii}{x}_i^2-{\sum }_{(i,j)\in E}2x_i{x}_j \\ ={\sum }_{(i,j)\in E}(x_i^2+x_j^2-2x_i{x}_j) \\ ={\sum }_{(i,j)\in E}(x_i-x_j{)}^2 \end{gathered}$$

As eigenvectors are unit vectors we have ${\sum }_i{x}_i^2=1$

and x is orthogonal to 1st eigenvector $[1,\cdots ,1]$ thus: ${\sum }_i{x}_i.1={\sum }_i{x}_i=0$

From the above 3 equations we have

${\lambda }_2=\underset{x:\sum x_i=0}{\min }\frac{{\sum }_{(i,j)\in E}(x_i-x_j{)}^2}{{\sum }_i{x}_i^2}=\underset{x:\sum x_i=0}{\min }\sum _{(i,j)\in E}(x_i-x_j{)}^2$

We want to assign values $x_i$ to nodes $i$ such that few edges cross 0. We want $x_i$ and $x_j$ to subtract each other. From the equation for ${\lambda }_2$ above, we have the constraints that all the node labels should sum up to zero, so intuitively half of nodes will be in one cluster, and the other half will be in the other cluster. And to minimize the term ${\sum }_{(i,j)\in E}(x_i-x_j{)}^2$ the edges crossing the clusters have to as few as possible. And the Edges within the clusters will result in a small value for ${\sum }_{(i,j)\in E}(x_i-x_j{)}^2$ anyway.

The image below is for intuition, as we have node labels from the second eigenvector on x-axis and the corresponding nodes in red. The edges between the two clusters have to minimum to minimize the term ${\sum }_{(i,j)\in E}(x_i-x_j{)}^2$

Eigenvector that corresponds to ${\lambda }_2$ is our magical vector that puts nodes in one or the other cluster.

Find Optimal Cut [Fiedler '73]

This is an optimal cut algorithm from 73, where we express the partition of graph into two components $A$, $B$ as a vector $y$ like below.

$y_i=\{\begin{array}{ll}+1& \text{ if }i\in A\\ -1& \text{ if }i\in B\end{array}$

We also enforce that $|A|=|B|\to {\sum }_i{y}_i=0$, equivalent to being orthogonal to the trivial eigenvector $[1,\cdots ,1]$

He proves that we can minimize the cut of the partition by finding a vector $y$ that minimizes:

$\underset{y\in \{-1,+1{\}}^n}{\mathrm{argmin}}f(y)=\sum _{(i,j)\in E}(y_i-y_j{)}^2$

This equation looks almost the same as we got when we were using ${\lambda }_2$ for clustering into components. Only difference is $y$ here can only take +1 or -1, unlike in the eigenvalue case, where it can assume any real number following the constraints mentioned above.

Rayleigh Theorem

$\underset{y\in {\Re }^n;{\sum }_i{y}_i=0;{\sum }_i{y}_i^2=1}{\min }f(y)=\sum _{(i,j)\in E}(y_i-y_j{)}^2=y^{T}Ly$

Rayleigh Theorem states that

• ${\lambda }_2={\min }_{y}f(y)$ The minimum value of $f(y)$ is given by the second smallest eigenvalue ${\lambda }_2$ of the Laplacian matrix $L$
• $x{\mathrm{argmin}}_{y}f(y)$ The optimal solution for $y$ is given by the eigenvector $x$ corresponding to ${\lambda }_2$ referred to as Fielder Vector.
• And we can use the sign $x_i$ to determine cluster assignment of node $i$.

There is a proof where you can show this type of spectral clustering of graph laplacian will give us near optimal solution. There is an approximation guarantee of the spectral clustering: Spectral clustering finds a cut that has at most twice the conductance as the optimal one of conductance $\beta$

Suppose there is a partition of $G$ into $A$ and $B$ where $|A|\le |B|$, such that the conductance of the cut (A,B) is $\beta$ then ${\lambda }_2\le \beta$.

TODO: The proof for this is in the PDF

Solving for ${\lambda }_2$ is essentially minimizing the sum of the squared differences between the coordinates(eigenvector labels) of nodes. with the condition that sum is zero and square sum is 1

Spectral Partitioning Algorithm

Preprocessing

Build the laplacian matrix $L$ from adjacency matrix

Eigenvalue decomposition

find the eigenvalues $\lambda$ and eigenvectors $x$ of $L$. Map vertices to corresponding components of $x_2$

Grouping

Sort components of reduced 1-d vector of node labels. Identify clusters by splitting the sorted vector in two. You can choose the splitting point at median or simply 0, or you can choose to minimize the normalized cut by sweeping over ordering of nodes induced by the eigenvector.

In the above image you can see after you build the laplacian matrix of the graph with two obvious clusters, and get the $x_2$ and assign them to the respective nodes, sort them and plot the ranks of the node on x-axis and its $x_2$ value on the y axis. You can see the clusters emerging.

In the above image if you do spectral clustering on a graph with 4 obvious clusters, and you do the same plot on the second eigenvector $x_2$, you see 4 step pattern emerge.

In the above image we show the plots of 1st and 3rd component plots for the same cluster above.

k-Way Spectral Clustering

Given a graph, how do we make use of the eigen components of the graph laplacian?

Two approaches

• recursive bi-partitioning[Hagen '92]
• cluster multiple eigenvectors[Shi-Malik '00]

Recursive Bi-partitioning

Recursive bi-partitioning involves, partitioning the cluster into two components using the second component $x_2$. And then consider each cluster into its own graph and find its own second component and repeat. This is a bit inefficient and unstable and cluster count will have to be a power of 2.

Cluster multiple eigenvectors

Cluster multiple eigenvectors, involves, building a reduced space from multiple eigenvectors. Each node is now represented by k components of the first k eigenvectors. We then cluster these nodes based on their k-dimensional representation using k-means and etc. This is the recommended approach and more common in recent papers. This method can be used to approximate optimal k-way normalized cut. Emphasizes cohesive clusters, increases the unevenness in the distribution of the data. Associations between similar points are amplified, associations between dissimilar points are attenuated. The data begins to "approximate a clustering". Multiple eigenvectors prevent instability due to information loss.

We make use of Eigengap, the difference between two consecutive eigenvalues, to choose k. Most stable clustering is generally give by the value $k$ that maximizes eigengap ${\Delta }_k=|{\lambda }_k-{\lambda }_{k-1}|$. You plot the eigenvalues, and when pick $k$ where it seems like the plot drops.

Motif-Based Spectral Clustering

Could you come up and cluster the network based on the motifs. We want to detect communities based on network motifs. Give a motif M and Graph G, We identify clusters in the network where M occurs a lot. Different motifs reveal different clustering structures.

We need analogues to cut, volume and conductance in case of motifs and they are defined like below.

Motifs cut: Number of motifs that get cut

Volume $vo{l}_M(S)$ = number of instances of end points of a motif are there in a given set s

Motif conductance $\varphi (S)$ = $\frac{\text{motifs cut}}{vo{l}_M(S)}$

In the image above the motif cut is 1 and volume 10, because the number of motif endpoints in set s, three triangles and the cut motif has one endpoint in $S$.

Similar to edge clustering where finding the optimal cut that minimizes conductance is NP-hard, finding a cut that optimizes the motif-conductance is also NP-hard. But we can use similar spectral clustering techniques with slight changes to get an approximate optimal motif clustering.

Motif Spectral Clustering

Given a motif $M$ and a graph $G$, find a set of nodes $S$ that minimizes motif conductance.

Preprocessing:

From graph $G$ and Motif $M$. We get a new weighted graph $W^{(M)}$. $W_{ij}^{(M)}$ is the number of times edge (i, j) participates in motif M

In the above picture, in the weighted graph, the edge weight of nodes 8 and 9 is 2 because in the graph G that (8,9) edge participates in two instances of the motif. And the edge weight of nodes 7, 9 is zero as there are no instances of edge (9,7) participating in the motif M. The weighted graph we build is also an undirected graph.

Decomposition

We apply standard spectral clustering on weighted graph $W^M$ finds clusters of low motif conductance.

Compute Fiedler vector $x$ associated with ${\lambda }_2$ of the laplacian of $L^{(M)}$

$L^{(M)}=D^{(M)}-W^{(M)}$

Compute: $L^{(M)}={\lambda }_{2}x$

Use x to identify communities.

Grouping

We sort the nodes by their values in $x$, Let $S_r=\{x_1,\cdots ,x_r\}$ and compute the motif conductance of each $S_r$. We select the optimal cut by doing this sweeping procedure. In the above image we see that $S_5$ had the optimal conductance, so we finalize the cut to be of the nodes $\{1\cdots 5\}$

We generalized community detection to higher-order structures. Motif conductance admits a motif Cheeger inequality. Simple, fast and scalable.

Other partitioning methods

METIS

Heuristic but works really well in practice.

Graclus

Based on kernel k-means

Louvain

Based on Modularity Optimization

Clique percorlation method

For finding overlapping clusters

Chapters

1. Introduction, Structure of Graphs
2. Properties of Networks and Random Graph Models
3. Motifs and Structural Roles in Networks
4. Community Structure in Networks
5. Spectral Clustering
6. Message Passing and Node Classification
7. Graph Representation Learning
8. Graph Neural Networks
9. Graph Neural Networks - Pytorch Geometric
10. Deep Generative Models for Graphs
11. Link Analysis: PageRank
12. Network Effects and Cascading Behaviour
13. Probabilistic Contagion and Models of Influence
14. Influence Maximization in Networks
15. Outbreak Detection in Networks
16. Network Evolution
17. Reasoning over Knowledge Graphs
18. Limitations of Graph Neural Networks
19. Applications of Graph Neural Networks