程序代写代做代考 C graph algorithm decision tree Sep 2020

Sep 2020
Algorithms for Machine Learning
Lecture 2: Graph Visualisation and Clustering
Thomas Sauerwald
University of Cambridge, Department of Computer Science email: thomas.sauerwald@cl.cam.ac.uk

Outline
Introduction to Spectral Graph Theory
Graph Spectra and Graph Structure
Graph Clustering
Applications: Image Segmentation and Clustering Migration Networks
Graph Visualisation and Spectral Clustering Introduction to Spectral Graph Theory 2

Landscape of Machine Learning Algorithms
Training Set provided initially
Supervised Learning
Classification, regression: logistic regr., SVM, decision tree, neural network, naive Bayes, Perceptron, kNN, Boosting
Online/Reinforcement Learning
Weighted-Majority, Multiplicative-Update. control learning: Markov Decision Processes, temporal difference
Unsupervised Learning
Clustering: spectral, hierarchical, k-means. Principal Component Analysis, Singular value Decomposition
Predict unseen data
Feedback after Decisions
Maximise Reward
No Training Set
Extract Knowledge
Graph Visualisation and Spectral Clustering Introduction to Spectral Graph Theory
3

Origin of Graph Theory
Source: Wikipedia
Seven Bridges at Königsberg 1737
Graph Visualisation and Spectral Clustering Introduction to Spectral Graph Theory 4

Origin of Graph Theory
Source: Wikipedia Source: Wikipedia
Seven Bridges at Königsberg 1737 Leonhard Euler (1707-1783)
Is there a tour which crosses each bridge exactly once?
Graph Visualisation and Spectral Clustering Introduction to Spectral Graph Theory 4

Origin of Graph Theory
A
B C
D
Source: Wikipedia
Seven Bridges at Königsberg 1737
Source: Wikipedia Leonhard Euler (1707-1783)
Is there a tour which crosses each bridge exactly once?
Graph Visualisation and Spectral Clustering Introduction to Spectral Graph Theory 4

Origin of Graph Theory
A
B C
D
Source: Wikipedia
Seven Bridges at Königsberg 1737
Source: Wikipedia Leonhard Euler (1707-1783)
A Is there a tour which crosses each bridge exactly once?
BD
C
Graph Visualisation and Spectral Clustering Introduction to Spectral Graph Theory 4

Graphs Nowadays: Clustering
Graph Visualisation and Spectral Clustering Introduction to Spectral Graph Theory 5

Graphs Nowadays: Clustering
Goal: Use spectrum of graphs (unstructured data) to extract clustering (communitites) or other structural information.
Graph Visualisation and Spectral Clustering Introduction to Spectral Graph Theory 5

Graph clustering (applications)
Applications of graph clustering
Community detection
Group webpages according to their topics
Find proteins performing the same function within a cell Image segmentation
Identify bottlenecks in a network
…
Graph Visualisation and Spectral Clustering Introduction to Spectral Graph Theory 6

Graph clustering (applications)
Applications of graph clustering
Community detection
Group webpages according to their topics
Find proteins performing the same function within a cell Image segmentation
Identify bottlenecks in a network
…
Unsupervised learning method
(there is no ground truth (usually), and we cannot learn from mistakes!)
Graph Visualisation and Spectral Clustering Introduction to Spectral Graph Theory 6

Graph clustering (applications)
Applications of graph clustering
Community detection
Group webpages according to their topics
Find proteins performing the same function within a cell Image segmentation
Identify bottlenecks in a network
…
Unsupervised learning method
(there is no ground truth (usually), and we cannot learn from mistakes!)
Different formalisations for different applications
Graph Visualisation and Spectral Clustering Introduction to Spectral Graph Theory 6

Graphs and matrices
Graphs
Matrices
0 1 0 1 1 0 1 0
 0 1 0 1
1010
1
2
43
Graph Visualisation and Spectral Clustering
Introduction to Spectral Graph Theory 7

Graphs and matrices
Graphs
Matrices
0 1 0 1 1 0 1 0
 0 1 0 1
1010
Eigenvalues Eigenvectors Inverse Determinant Matrix-powers . . .
1
2
43
Connectivity Bipartiteness Graph partitioning Number of triangles Graph isomorphism Max-flow
…
Graph Visualisation and Spectral Clustering
Introduction to Spectral Graph Theory 7

Adjacency matrix
Adjacency matrix
Let G = (V,E) be an undirected graph.
The adjacency matrix of G is the n by n matrix A defined as
􏱢1 if{u,v}∈E Au,v = 0 otherwise.
Graph Visualisation and Spectral Clustering Introduction to Spectral Graph Theory 8

Adjacency matrix
Adjacency matrix
Let G = (V,E) be an undirected graph.
The adjacency matrix of G is the n by n matrix A defined as
􏱢1 if{u,v}∈E Au,v = 0 otherwise.
12
0 1 0 1 A=1 0 1 0 0 1 0 1
1010 The sum of elements in each row/column i equals the degree of the
43
Properties of A:
corresponding vertex i, deg(i)
Since G is undirected, A is symmetric
Graph Visualisation and Spectral Clustering Introduction to Spectral Graph Theory 8

Eigenvalues and Graph Spectrum of A Eigenvalues and eigenvectors
Let M ∈ Rn×n, λ ∈ C is an eigenvalue of M if and only if there exists
x ∈Rn \{0}suchthat
We call x an eigenvector of M corresponding to the eigenvalue λ.
We say that G is d-regular if every degree is d, i.e., every vertex has exactly d connections.
Graph Spectrum
Let A be the adjacency matrix of a d-regular graph G with n vertices. Then, A has n real eigenvalues λ1 ≤ ··· ≤ λn and n corresponding orthonormal eigenvectors f1, . . . , fn. These eigenvalues associated with their multiplicities constitute the spectrum of G.
Mx = λx.
Graph Visualisation and Spectral Clustering Introduction to Spectral Graph Theory 9

Exercise 1
What are the Eigenvalues and Eigenvectors of this Graph?
Graph Visualisation and Spectral Clustering Introduction to Spectral Graph Theory 10

Exercise 1
What are the Eigenvalues and Eigenvectors of this Graph?
1
23
0 1 1 A=1 0 1
110
Graph Visualisation and Spectral Clustering
Introduction to Spectral Graph Theory 10

Laplacian matrix
Laplacian matrix
Let G = (V , E ) be a d -regular undirected graph. The (normalised) Lapla- cian matrix of G is the n by n matrix L defined as
L = I − 1 A, d
where I is the n × n identity matrix. 12
43
1 −1/2 0 −1/2 L = −1/2 1 −1/2 0  0 −1/2 1 −1/2
−1/2 0 −1/2 1
Graph Visualisation and Spectral Clustering
Introduction to Spectral Graph Theory
11

Laplacian matrix
Laplacian matrix
Let G = (V , E ) be a d -regular undirected graph. The (normalised) Lapla- cian matrix of G is the n by n matrix L defined as
L = I − 1 A, d
where I is the n × n identity matrix. 12
1 −1/2 0 −1/2 L = −1/2 1 −1/2 0  0 −1/2 1 −1/2
−1/2 0 −1/2 The sum of elements in each row/column equals zero
L is symmetric
Graph Visualisation and Spectral Clustering Introduction to Spectral Graph Theory
1
43
Properties of L:
11

Exercise 2
Can you find a relation between the spectrum (= set of eigenvalues & eigenvectors) of the Adjacency Matrix A and the Laplacian Matrix L?
Graph Visualisation and Spectral Clustering Introduction to Spectral Graph Theory 12

Exercise 2
Can you find a relation between the spectrum (= set of eigenvalues & eigenvectors) of the Adjacency Matrix A and the Laplacian Matrix L?
Hint: Use L = I − 1 A. d
Graph Visualisation and Spectral Clustering Introduction to Spectral Graph Theory 12

Eigenvalues and Graph Spectrum of L
Eigenvalues and eigenvectors
Let M ∈ Rn×n, λ ∈ C is an eigenvalue of M if and only if there exists
x ∈Rn \{0}suchthat
We call x an eigenvector of M corresponding to the eigenvalue λ.
Graph Spectrum
Let L be the Laplacian matrix of a d-regular graph G with n vertices. Then, L has n real eigenvalues λ1 ≤ ··· ≤ λn and n corresponding orthonormal eigenvectors f1, . . . , fn.
Mx = λx.
Graph Visualisation and Spectral Clustering Introduction to Spectral Graph Theory 13

A Min-Max Characterisation of Eigenvalues and Eigenvectors
Courant-Fischer min-max formula
Let M be an n by n symmetric matrix with eigenvalues λ1 ≤ ··· ≤ λn. Then,
x(i)T Mx(i)
λk= min max T . x(1),…,x(k)∈Rn\{0}, i∈{1,…,k} x(i) x(i)
x(i)⊥x(j)
The eigenvectors corresponding to λ1 , λ2 , . . . , λk minimise such expres-
sion.
Graph Visualisation and Spectral Clustering Introduction to Spectral Graph Theory
14

A Min-Max Characterisation of Eigenvalues and Eigenvectors
Courant-Fischer min-max formula
Let M be an n by n symmetric matrix with eigenvalues λ1 ≤ ··· ≤ λn. Then,
x(i)T Mx(i)
λk= min max T . x(1),…,x(k)∈Rn\{0}, i∈{1,…,k} x(i) x(i)
x(i)⊥x(j)
The eigenvectors corresponding to λ1 , λ2 , . . . , λk minimise such expres-
sion.
xTMx x∈Rn\{0} xTx
λ1= min
minimised by an eigenvector f1 for λ1
Graph Visualisation and Spectral Clustering Introduction to Spectral Graph Theory
14

A Min-Max Characterisation of Eigenvalues and Eigenvectors
Courant-Fischer min-max formula
Let M be an n by n symmetric matrix with eigenvalues λ1 ≤ ··· ≤ λn. Then,
x(i)T Mx(i)
λk= min max T . x(1),…,x(k)∈Rn\{0}, i∈{1,…,k} x(i) x(i)
x(i)⊥x(j)
The eigenvectors corresponding to λ1 , λ2 , . . . , λk minimise such expres-
sion.
λ1= min x∈Rn\{0} xT x
λ2= min x⊥f1∈Rn\{0} xT x
minimised by f2
Introduction to Spectral Graph Theory 14
xTMx xTMx
minimised by an eigenvector f1 for λ1 Graph Visualisation and Spectral Clustering

A Min-Max Characterisation of Eigenvalues and Eigenvectors
Courant-Fischer min-max formula
Let M be an n by n symmetric matrix with eigenvalues λ1 ≤ ··· ≤ λn. Then,
x(i)T Mx(i)
λk= min max T . x(1),…,x(k)∈Rn\{0}, i∈{1,…,k} x(i) x(i)
x(i)⊥x(j)
The eigenvectors corresponding to λ1 , λ2 , . . . , λk minimise such expres-
sion.
xTMx x⊥f1∈Rn\{0} xT x
λ2= min minimised by f2
xTMx x∈Rn\{0} xTx
λ1= min
minimised by an eigenvector f1 for λ1
Graph Visualisation and Spectral Clustering Introduction to Spectral Graph Theory
14

Quadratic forms of the Laplacian
Lemma
Let L be the Laplacian matrix of a d-regular graph G = (V,E) with n vertices. For any x ∈ Rn,
T 􏱣 (xu−xv)2 xLx= d.
{u,v}∈E
Graph Visualisation and Spectral Clustering Introduction to Spectral Graph Theory 15

Quadratic forms of the Laplacian
Lemma
Let L be the Laplacian matrix of a d-regular graph G = (V,E) with n vertices. For any x ∈ Rn,
Proof:
T 􏱣 (xu−xv)2 xLx= d.
{u,v}∈E
TT􏱠1􏱡T1T
x Lx=x I−dA x=x x−dx Ax
=􏱣xu2−2 􏱣 xuxv
u∈V
d
{u,v}∈E
= 1 􏱣 ( x u2 + x v2 − 2 x u x v )
􏱣 (xu−xv)2 =d.
d
{u,v}∈E
{u,v}∈E
Graph Visualisation and Spectral Clustering Introduction to Spectral Graph Theory 15

Visualising a Graph
Question: How can we visualize a complicated object like an unknown graph with many vertices in low-dimensional space?
Graph Visualisation and Spectral Clustering Introduction to Spectral Graph Theory 16

Visualising a Graph
Question: How can we visualize a complicated object like an unknown graph with many vertices in low-dimensional space?
A Larger Example
Algorithms and ML: Examples of Spectral Clustering 3
Graph Visualisation and Spectral Clustering
Introduction to Spectral Graph Theory 16

Visualising a Graph
Question: How can we visualize a complicated object like an unknown graph with many vertices in low-dimensional space?
A Larger Example
Embedding onto Line Coordinates given by x
Algorithms and ML: Examples of Spectral Clustering 3
Graph Visualisation and Spectral Clustering
Introduction to Spectral Graph Theory 16

Visualising a Graph
Question: How can we visualize a complicated object like an unknown graph with many vertices in low-dimensional space?
A Larger Example
Embedding onto Line Coordinates given by x
Algorithms and ML: Examples of Spectral Clustering 3
Graph Visualisation and Spectral Clustering
Introduction to Spectral Graph Theory
16
Algorithms and ML: Examples of Spectral Clustering
5

Visualising a Graph
Question: How can we visualize a complicated object like an unknown graph with many vertices in low-dimensional space?
A Larger Example
Embedding onto Line Coordinates given by x
Algorithms and ML: Examples of Spectral Clustering
3
1 􏱦{u,v}∈E(xu−xv)2 λ2 = · min
d x∈Rn ∥x∥2 x ̸=0,x ⊥1
The values in the vector x indicate how similar/dissimilar vertices are. Edges between dissimilar vertices are penalised quadratically.
Algorithms and ML: Examples of Spectral Clustering
5
Graph Visualisation and Spectral Clustering Introduction to Spectral Graph Theory
16

A Simplified Clustering Problem
Partition the graph into connected components so that any pair of ver- tices in the same component is connected, but vertices in different com- ponents are not.
Graph Visualisation and Spectral Clustering Graph Spectra and Graph Structure 18

Exercise Question 3
What are the Eigenvectors with Eigenvalue 0 of L?
Hint: Try to find vectors that reflect the connected components.
Graph Visualisation and Spectral Clustering Graph Spectra and Graph Structure 19

Exercise Question 3
What are the Eigenvectors with Eigenvalue 0 of L?
Hint: Try to find vectors that reflect the connected components.
145
2376
0 1 1 0 0 0 0 1 0 1 0 0 0 0 1 1 0 0 0 0 0
A=0 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 0 0 1 0 1
0001010
Graph Visualisation and Spectral Clustering
Graph Spectra and Graph Structure 19

Exercise Question 3
What are the Eigenvectors with Eigenvalue 0 of L?
Hint: Try to find vectors that reflect the connected components.
145
0 1 1 0 0 0 0 1 0 1 0 0 0 0 1 1 0 0 0 0 0
A=0 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 0 0 1 0 1
0001010
1 −1 −1 0 0 0 0 22
2 3
7 6
−1 1 −1 0 0 0 0 22 
−1 −1 1 0 0 0 0 22 11
L=0001−0−
 2 2
0 0 0 −1 1 −1 0 22
0 0 0 0 −1 1 −1 1212
Graph Visualisation and Spectral Clustering
0 0 0 −2 0 −2 1 Graph Spectra and Graph Structure 19

Graph clustering
Partition the graph into pieces (clusters) so that vertices in the same piece have, on average, more connections among each other than with vertices in other clusters
Graph Visualisation and Spectral Clustering Graph Clustering 21

Edge Expansion
Edge Expansion
Let G = (V,E) be a d-regular graph and ∅ ̸= S ⊂ V. The edge expansion (conductance) of S is
φ(S) := |E(S, V \ S)| d · |S|
Moreover, the edge expansion (conductance) of the graph G is φ(G) := min φ(S)
S⊆V : 1≤|S|≤V /2
φ(S) = 5 589
2 1
7
4
6
3
φ(G) ∈ [0, 1] and φ(G) = 0 iff G is disconnected
Graph Visualisation and Spectral Clustering
Graph Clustering 22

Edge Expansion
Edge Expansion
Let G = (V,E) be a d-regular graph and ∅ ̸= S ⊂ V. The edge expansion (conductance) of S is
φ(S) := |E(S, V \ S)| d · |S|
Moreover, the edge expansion (conductance) of the graph G is φ(G) := min φ(S)
S⊆V : 1≤|S|≤V /2
φ(S) = 5 589
7 4
φ(G) ∈ [0, 1] and φ(G) = 0 iff G is disconnected
6 If G is a complete graph, then |E(S, V \ S)| = |S| · (n − |S|) and
φ(G) ≈ 1/2.
Graph Clustering 22
2
1 3
Graph Visualisation and Spectral Clustering

Edge Expansion
Edge Expansion
Let G = (V,E) be a d-regular graph and ∅ ̸= S ⊂ V. The edge expansion (conductance) of S is
φ(S) := |E(S, V \ S)| d · |S|
Moreover, the edge expansion (conductance) of the graph G is φ(G) := min φ(S)
S⊆V : 1≤|S|≤V /2 NP-hard to compute!
φ(S) = 5 589
7 4
φ(G) ∈ [0, 1] and φ(G) = 0 iff G is disconnected
6 If G is a complete graph, then |E(S, V \ S)| = |S| · (n − |S|) and
φ(G) ≈ 1/2.
Graph Clustering 22
2
1 3
Graph Visualisation and Spectral Clustering

λ2 versus Expansion (1/2)
G is disconnected
Graph Visualisation and Spectral Clustering Graph Clustering 23

λ2 versus Expansion (1/2)
145
2376
G is disconnected
Graph Visualisation and Spectral Clustering Graph Clustering 23

λ2 versus Expansion (1/2)
145
2376
φ(G) = 0 ⇔ G is disconnected
Graph Visualisation and Spectral Clustering Graph Clustering 23

λ2 versus Expansion (1/2)
145
2376
φ(G) = 0 ⇔ G is disconnected ⇔ λ2(G) = 0
Graph Visualisation and Spectral Clustering Graph Clustering
23

λ2 versus Expansion (1/2)
145
2376
φ(G) = 0 ⇔ G is disconnected ⇔ λ2(G) = 0 What is the relationship between φ(G)
and λ2(G) for connected graphs?
Graph Visualisation and Spectral Clustering Graph Clustering 23

λ2 versus Expansion (2/2) 1D Grid
2D Grid
3D Grid
λ2 ∼n−2 φ ∼ n−1
λ2 ∼n−1 φ ∼ n−1/2
λ2 ∼n−2/3 φ ∼ n−1/3
Graph Visualisation and Spectral Clustering
Graph Clustering
24

λ2 versus Expansion (2/2) 1D Grid
2D Grid
3D Grid
λ2 ∼n−2 φ ∼ n−1
Hypercube
λ2 ∼n−1 φ ∼ n−1/2
Random Graph (Expanders)
λ2 ∼n−2/3 φ ∼ n−1/3
Binary Tree
λ2 ∼ (logn)−1 φ ∼ (log n)−1
λ2 = Θ(1) φ = Θ(1)
λ2 ∼ n−1 φ ∼ n−1
Graph Visualisation and Spectral Clustering
Graph Clustering
24

Relating λ2 and Edge Expansion Cheeger’s inequality
Let G be a d-regular graph and λ1 ≤ ··· ≤ λn be the eigenvalues of its Laplacian matrix. Then,
λ2 ≤ φ(G) ≤ 􏱤2λ2. 2
Graph Visualisation and Spectral Clustering Graph Clustering 25

Relating λ2 and Edge Expansion Cheeger’s inequality
Let G be a d-regular graph and λ1 ≤ ··· ≤ λn be the eigenvalues of its Laplacian matrix. Then,
λ2 ≤ φ(G) ≤ 􏱤2λ2. 2
Spectral partitioning:
1. Compute the eigenvector x corresponding to λ2
2. Ordertheverticessothatx1 ≤x2 ≤···≤xn (embedV onR)
3. Tryalln−1sweepcutsoftheform({1,2,…,k},{k+1,…,n}) and return the one with smallest expansion
Graph Visualisation and Spectral Clustering Graph Clustering 25

Relating λ2 and Edge Expansion Cheeger’s inequality
Let G be a d-regular graph and λ1 ≤ ··· ≤ λn be the eigenvalues of its Laplacian matrix. Then,
λ2 ≤ φ(G) ≤ 􏱤2λ2. 2
Spectral partitioning:
1. Compute the eigenvector x corresponding to λ2
2. Ordertheverticessothatx1 ≤x2 ≤···≤xn (embedV onR)
3. Tryalln−1sweepcutsoftheform({1,2,…,k},{k+1,…,n}) and return the one with smallest expansion
It returns S ⊂ V such that φ(S) ≤ √2λ2 ≤ 2􏱤φ(G)
Graph Visualisation and Spectral Clustering Graph Clustering 25

Relating λ2 and Edge Expansion Cheeger’s inequality
Let G be a d-regular graph and λ1 ≤ ··· ≤ λn be the eigenvalues of its Laplacian matrix. Then,
λ2 ≤ φ(G) ≤ 􏱤2λ2. 2
Spectral partitioning:
1. Compute the eigenvector x corresponding to λ2
2. Ordertheverticessothatx1 ≤x2 ≤···≤xn (embedV onR)
3. Tryalln−1sweepcutsoftheform({1,2,…,k},{k+1,…,n}) and return the one with smallest expansion
It returns S ⊂ V such that φ(S) ≤ √2λ2 ≤ 2􏱤φ(G)
no constant factor worst-case guarantee, but usually works well in
practice (see examples later!)
Graph Visualisation and Spectral Clustering Graph Clustering 25

Relating λ2 and Edge Expansion Cheeger’s inequality
Let G be a d-regular graph and λ1 ≤ ··· ≤ λn be the eigenvalues of its Laplacian matrix. Then,
λ2 ≤ φ(G) ≤ 􏱤2λ2. 2
Spectral partitioning:
1. Compute the eigenvector x corresponding to λ2
2. Ordertheverticessothatx1 ≤x2 ≤···≤xn (embedV onR)
3. Tryalln−1sweepcutsoftheform({1,2,…,k},{k+1,…,n}) and return the one with smallest expansion
It returns S ⊂ V such that φ(S) ≤ √2λ2 ≤ 2􏱤φ(G)
no constant factor worst-case guarantee, but usually works well in
practice (see examples later!)
can be implemented in O(|E| log |E|) time
Graph Visualisation and Spectral Clustering Graph Clustering 25

Extensions of what we covered here
We have worked with a relatively simple version of the clustering problem.
Graph Visualisation and Spectral Clustering Graph Clustering 26

Extensions of what we covered here
We have worked with a relatively simple version of the clustering problem. What if G is not d-regular?
need to work with normalised Laplacian matrix L, Li,j = √ 1 , if deg(i )·deg(j )
{i, j} ∈ E(G), Li,i = 1 and Li,i = 0 otherwise
need to work with generalised version of edge-expansion φ: let vol(S) := 􏱦u∈S deg(u) and then
|E(S,V \S)| φ(G) := min .
S⊆V : 1≤vol(S)≤|E| vol(S)
What if we want to find k > 2 clusters?
use a recursive approach: first partition into two clusters, and then try to
partition any of the two clusters further etc. 􏱧 hierarchical clustering “High-OrderCheegerInequality”(quitetricky):lookatλ2,…,λk andthe associated eigenvectors
Graph Visualisation and Spectral Clustering Graph Clustering 26

Similarity graph
Given X = {x1,…,xn} ∈ Rd, construct G = (V,E,w): xi ∈X􏱥→vi ∈V
E = 􏱞 V2 􏱟
􏱠 ∥x−x∥2􏱡
w (vi , vj ) = exp − i j (Gaussian similarity function)
2σ2
Graph Visualisation and Spectral Clustering Applications: Image Segmentation and Clustering Migration Networks 28

Similarity graph
Given X = {x1,…,xn} ∈ Rd, construct G = (V,E,w): xi ∈X􏱥→vi ∈V
E = 􏱞 V2 􏱟
􏱠 ∥x−x∥2􏱡
w (vi , vj ) = exp − i j (Gaussian similarity function)
2σ2
w(vi,vj) is large if xi is close to xj
Remarks:
value of σ ≥ 0 depends on the application (choose it by trial and error, usually σ ∈ (0.05, 10))
large σ if, on average, pairwise nearest neighbours are far apart
Graph Visualisation and Spectral Clustering Applications: Image Segmentation and Clustering Migration Networks 28

Similarity graph
Given X = {x1,…,xn} ∈ Rd, construct G = (V,E,w): xi ∈X􏱥→vi ∈V
E = 􏱞 V2 􏱟
􏱠 ∥x−x∥2􏱡
w (vi , vj ) = exp − i j (Gaussian similarity function)
2σ2
w(vi,vj) is large if xi is close to xj
Remarks:
value of σ ≥ 0 depends on the application (choose it by trial and error, usually σ ∈ (0.05, 10))
large σ if, on average, pairwise nearest neighbours are far apart Problem: Since G is complete, from Θ(dn) to Θ(n2) space.
Graph Visualisation and Spectral Clustering Applications: Image Segmentation and Clustering Migration Networks 28

Similarity graph
Given X = {x1,…,xn} ∈ Rd, construct G = (V,E,w): xi ∈X􏱥→vi ∈V
E = 􏱞 V2 􏱟
􏱠 ∥x−x∥2􏱡
w (vi , vj ) = exp − i j (Gaussian similarity function)
2σ2
w(vi,vj) is large if xi is close to xj
Remarks:
value of σ ≥ 0 depends on the application (choose it by trial and error, usually σ ∈ (0.05, 10))
large σ if, on average, pairwise nearest neighbours are far apart Problem: Since G is complete, from Θ(dn) to Θ(n2) space.
Possible solution: r-nearest neighbour graph (vi ∼ vj iff xj is one of the r-nearest neighbours of xi or vice versa)
Graph Visualisation and Spectral Clustering Applications: Image Segmentation and Clustering Migration Networks 28

Similarity graph
Given X = {x1,…,xn} ∈ Rd, construct G = (V,E,w): xi ∈X􏱥→vi ∈V
E = 􏱞 V2 􏱟
􏱠 ∥x−x∥2􏱡
w (vi , vj ) = exp − i j (Gaussian similarity function)
2σ2
w(vi,vj) is large if xi is close to xj
Remarks:
value of σ ≥ 0 depends on the application (choose it by trial and error, usually σ ∈ (0.05, 10))
large σ if, on average, pairwise nearest neighbours are far apart Problem: Since G is complete, from Θ(dn) to Θ(n2) space.
Possible solution: r-nearest neighbour graph (vi ∼ vj iff xj is one of the r-nearest neighbours of xi or vice versa)
From geometric to graph clustering!
Graph Visualisation and Spectral Clustering Applications: Image Segmentation and Clustering Migration Networks 28

Example
Graph Visualisation and Spectral Clustering Applications: Image Segmentation and Clustering Migration Networks 29

Example
Similarity graph: Gaussian with σ = 0.1. Only edges with weight ≥ 0.01 shown.
Graph Visualisation and Spectral Clustering Applications: Image Segmentation and Clustering Migration Networks 29

Example
Similarity graph: Gaussian with σ = 0.1. Only edges with weight ≥ 0.01 shown.
Spectral partitioning (variant for non-regular graphs)
1. Compute the eigenvector x corresponding to λ2 and y = D−1/2x.
2. Ordertheverticessothaty1 ≤y2 ≤···≤yn
3. Choose“sweep”cut({1,2,…,i},{i+1,…,n})withsmallestconductance
Graph Visualisation and Spectral Clustering Applications: Image Segmentation and Clustering Migration Networks 29

Image segmentation
Goal: identify different objects in an image
Graph Visualisation and Spectral Clustering Applications: Image Segmentation and Clustering Migration Networks 30

Image segmentation
Goal: identify different objects in an image
Construct similarity graph as follows:
A pixel p is characterised by its position in the image and by its RGB value map pixel p in position (x,y) to a vector vp = (x,y,r,g,b)
construct similarity graph as explained earlier
Graph Visualisation and Spectral Clustering Applications: Image Segmentation and Clustering Migration Networks 30

Image segmentation
Goal: identify different objects in an image
Construct similarity graph as follows:
A pixel p is characterised by its position in the image and by its RGB value map pixel p in position (x,y) to a vector vp = (x,y,r,g,b)
construct similarity graph as explained earlier
Original image
Graph Visualisation and Spectral Clustering Applications: Image Segmentation and Clustering Migration Networks 30

Image segmentation
Goal: identify different objects in an image
Construct similarity graph as follows:
A pixel p is characterised by its position in the image and by its RGB value map pixel p in position (x,y) to a vector vp = (x,y,r,g,b)
construct similarity graph as explained earlier
Original image Output SC (Gaussian, σ = 10)
Graph Visualisation and Spectral Clustering Applications: Image Segmentation and Clustering Migration Networks 30

Practical Guide: How to pick the right parameters
If k is unknown:
small λk means there exist k sparsely connected subsets in the graph
large λk+1 means these k subsets have “good” inner-connectivity properties
=⇒ choose smallest k so that the spectral gap λk +1 − λk is “large” For example, ⃗λ = (0,0.20,0.22,0.43,0.45,…) =⇒ k = 3.
Or ⃗λ = (0,0.17,0.37,0.39,0.41,…) =⇒ k = 2.
Data represented by vectors. k is known, but need to construct a similarity graph and choose the right parameters.
For example, for the Gaussian similarity function we need to choose σ. Strategy: try σ ∈ {0.01,0.02,0.04,…,10,20,…} and choose σ
maximising λk +1 − λk .
Graph Visualisation and Spectral Clustering Applications: Image Segmentation and Clustering Migration Networks 31

Clustering Challenges
graphs can be very large
graphs could change over time (temporal graphs) graphs may not be completely observable clusters may overlap
more than 2 clusters
graphs may be directed
Graph Visualisation and Spectral Clustering Applications: Image Segmentation and Clustering Migration Networks 32

Clustering on Directed Graphs (1/3)
The (complex-valued) Hermitian Adjacency Matrix H defined as
i if {u,v} ∈ E Hu,v =−i if{u,v}∈E
0 otherwise.
Define a normalised Hermitian Laplacian L, which has real eigenvalues
with complex, orthonormal eigenvectors
Graph Visualisation and Spectral Clustering Applications: Image Segmentation and Clustering Migration Networks 33

Clustering on Directed Graphs (2/3)
pairs of clusters with the highest imbalance in the direction of edges are highlighted
most edges connect nodes in the green cluster to nodes in the red one ⇒ people tend to move from rural to urban countries
Graph Visualisation and Spectral Clustering Applications: Image Segmentation and Clustering Migration Networks 34

Clustering on Directed Graphs (3/3)
Graph Visualisation and Spectral Clustering Applications: Image Segmentation and Clustering Migration Networks 35

References
Fan R.K. Chung.
Graph Theory in the Information Age.
Notices of the AMS, vol. 57, no. 6, pages 726–732, 2010.
Fan R.K. Chung.
Spectral Graph Theory.
Volume 92 of CBMS Regional Conference Series in Mathematics, 1997.
Mihai Cucuringu, Huan Li, He Sun and Luca Zanetti.
Hermitian matrices for clustering directed graphs: insights and applications.
The 23rd International Conference on Artificial Intelligence and Statistics AISTATS 2020
Daniel Spielman
Chapter 16, Spectral Graph Theory
Combinatorial Scientific Computing
Luca Trevisan.
Lectures Notes on Expansion, Sparsest Cut, and Spectral Graph Theory, 2014. http:eecs.berkeley.edu/~luca/books/expanders.pdf
Graph Visualisation and Spectral Clustering Applications: Image Segmentation and Clustering Migration Networks 36

Related Posts