Review: Summary questions of the last lecture

Review: Summary questions of the last lecture

What is the meaning of eigenvalues and eigenvectors of Laplacian?

What is the meaning of the multiplicity of eigenvalue 0 of Laplacian?

What is the meaning of the smoothness of an eigenvector?

How to get the eigen-spectrum of Laplacian of the complete graph?

What is the relation btw Laplacian and random walks on undirected graphs?

Review: Summary questions of the last lecture

What is the meaning of eigenvalues and eigenvectors of Laplacian?

→ Frequencies and its corresponding graph signals that a graph can have.

A signal 𝒇 can be written as graph Fourier series:

𝒇^𝑇𝒖_𝑘 = ෍

𝒊

𝑓መ_𝑖𝒖_𝑖^𝑇𝒖_𝑘 = መ𝑓_𝑘 = 𝒖_𝑘^𝑇𝒇 𝒇 = ෍

𝒊

𝑓መ_𝑖𝒖_𝑖 ෠𝒇 =

𝑓መ_𝟏

… 𝑓መ_𝑵

=

𝒖₁^𝑇

… 𝒖_𝑁^𝑇

𝒇

Spatial domain: 𝒇

෠𝒇 = 𝑼^𝑇𝒇

Decompose signal 𝑓

Spectral domain: ෠𝒇 Reconstruct signal 𝒇

Design GCN in spectral domain Design GCN in spectral domain

Review: Summary questions of the last lecture

What is the meaning of the multiplicity of eigenvalue 0 of Laplacian?

→ The number of connected components in a graph.

𝑣₃

𝑣₂

𝑣₇

𝑣₅ 𝑣₆

𝑣₄ 𝑣₈ 𝑣₁

2 − 1 − 1 0 0 0 0 0

−1 2 − 1 0 0 0 0 0

−1 − 1 3 − 1 0 0 0 0

0 0 − 1 1 0 0 0 0

0 0 0 0 1 0 − 1 0

0 0 0 0 0 2 − 1 − 1 0 0 0 0 − 1 − 1 3 − 1 𝑳_𝟏

𝑳_𝟐

[Intuitive Proof]

Letting two eigenvectors be 𝒖₁ = [ 1 1 1 1 0 0 0 0]^𝑇, 𝒖₂ = [ 0 0 0 0 1 1 1 1]^𝑇. Then

𝑳𝒖₁ = 0𝒖₁, 𝑳𝒖₂ = 0𝒖₂. Thus

(0, 𝒖₁) and (0, 𝒖₂) are eigenpairs.

The multiplicity of eigenvalue 0 of 𝐿 equals to 2.

Review: Summary questions of the last lecture

What is the meaning of the smoothness of an eigenvector?

→ The smoothness of a eigenvector is its eigenvalue (frequency).

𝑆_𝐺 𝒇 = 𝒇^𝑇𝑳𝒇 = 𝒇^𝑇𝑼𝚲𝑼^𝑻𝒇 = 𝜶^𝑻𝚲𝜶 = 𝜶 _𝚲^𝟐 = ෍

𝟏≤𝒊≤𝑵

𝜆_𝒊𝛼_𝒊^𝟐, 𝜶 = 𝑼^𝑻𝒇

Spectral coordinate (unique vector) of eigenvector 𝒖_𝑘: 𝜶_𝑘= 𝑼^𝑇𝒖_𝑘 = 𝒆_𝑘. 𝑆_𝐺 𝒖_𝑘 = 𝒖_𝑘^𝑇𝑳𝒖_𝑘 = 𝒖_𝑘^𝑇𝑼𝚲𝑼^𝑇𝒖_𝑘 = 𝒆_𝑘^𝑇𝚲𝒆_𝑘 = 𝒆_{𝑘 𝚲}^𝟐 = ෍

1≤𝑖≤𝑁

𝜆_𝑖𝑒_𝑘,𝑖² = 𝜆_𝑘

Review: Summary questions of the last lecture

How to get the eigen-spectrum of Laplacian of the complete graph?

→ The 1-st eigen-pair is (0, 𝟏_𝑁) and compute the second eigen-pair of which eigenvector is orthogonal to 1-st eigenvector. The remaining ones can be computed to be orthogonal to the previous ones.

If 𝒖 ≠ 𝟎 and 𝒖 ⊥ 𝟏_𝑵 ⇒ σ_𝑖 𝑢_𝑖 = 0 . To get the other eigenvalues, we compute (𝑳_𝑲𝑵𝒖)₁and divide by 𝑢₁ (letting 𝑢₁≠ 0).

(𝑳_𝑲𝑵𝒖)₁ = (𝑁 − 1)𝑢₁ − ෍

2≤𝑖≤𝑁

𝑢_𝑖 = 𝑁𝑢₁

→ (0, 𝟏_𝑁), (𝑁, 1 − 1 0 … 0 ^𝑇), …

Review: Summary questions of the last lecture

What is the relation btw Laplacian and random walks on undirected graphs?

→ The random walks is a stochastic process with a transition probability 𝑝_𝑖𝑗 =

𝑤_𝑖𝑗

𝑑_𝑖 between node 𝑖 and 𝑗 of a graph with a Laplacian 𝐿 = 𝐷 − 𝑊.

Transition matrix: 𝑷 = 𝑝_𝑖𝑗 = 𝑫⁻¹𝑾 (notice 𝑳_𝑟𝑤 = 𝐈 − 𝑷).

Unique stationary distribution 𝝅 = 𝜋₁, … , 𝜋_𝑁 where 𝜋_𝑖 = ^𝑑𝑖

𝑣𝑜𝑙 𝑽 .

← 𝑣𝑜𝑙 𝑮 = 𝑣𝑜𝑙 𝑽 = 𝑣𝑜𝑙 𝑾 ≜ σ_𝑖 𝑑_𝑖 = σ_𝑖𝑗 𝑤_𝑖𝑗. 𝝅 = ^𝟏𝑇𝑾

𝑣𝑜𝑙(𝑾) verifies 𝝅𝑷 = 𝝅 as 𝝅𝑷 = 𝟏^𝑇𝑾𝑷

𝑣𝑜𝑙(𝑾) = 𝟏^𝑇𝑫𝑷

𝑣𝑜𝑙(𝑾) = 𝟏^𝑇𝑫𝑫⁻¹𝑾

𝑣𝑜𝑙(𝑾) = 𝟏^𝑇𝑾

𝑣𝑜𝑙(𝑾) = 𝝅.

Spectral Clustering

𝑐𝑢𝑡 𝑨, 𝑩 = 1

2 𝒇 ^𝑻 𝑳𝒇

𝑣₃

𝑣₂

𝑣₅ 𝑣₆

𝑣₄ 𝑣₈ 𝑣₁

𝒇 =

1

−1

−1 1

−1

Application of Graphs for ML: Clustering

Spectral Clustering: Cuts on graphs

Spectral Clustering: Cuts on graphs

Defining the cut objective we get the clustering!

Spectral Clustering: Cuts on graphs

MinCut: 𝑐𝑢𝑡 𝑨, 𝑩 = σ_{𝑖∈𝑨,𝑗∈𝑩} 𝑤_𝑖𝑗 Are we done?

Spectral Clustering: Balanced Cuts

MinCut

RatioCut

Let’s balance the cuts!

NormalizedCut

𝐶𝑢𝑡 𝑨, 𝑩 = σ_{𝑖∈𝑨,𝑗∈𝑩} 𝑤_𝑖𝑗 s.t. 𝑨 = 𝑩

𝑅𝐶𝑢𝑡 𝑨, 𝑩 = ෍

𝑖∈𝑨,𝑗∈𝑩

𝑤_𝑖𝑗 1

𝑨 + 1 𝑩

𝑁𝐶𝑢𝑡 𝑨, 𝑩 = ෍

𝑖∈𝑨,𝑗∈𝑩

𝑤_𝑖𝑗 1

𝑣𝑜𝑙(𝑨) + 1 𝑣𝑜𝑙(𝑩)

Spectral Clustering: Balanced Cuts

𝑅𝐶𝑢𝑡 𝑨, 𝑩, 𝑪, … = 𝐶𝑢𝑡 𝑨, 𝑩, 𝑪, … 1

𝑨 + 1

𝑩 + 1

𝑪 + … 𝑁𝐶𝑢𝑡 𝑨, 𝑩, 𝑪, … = 𝐶𝑢𝑡 𝑨, 𝑩, 𝑪, … 1

𝑣𝑜𝑙(𝑨) + 1

𝑣𝑜𝑙(𝑩) + 1

𝑣𝑜𝑙(𝑪) + … Easily generalizable to 𝑘 ≥ 2.

Can we compute this? 𝐶𝑢𝑡, 𝑅𝐶𝑢𝑡 and 𝑁𝐶𝑢𝑡 are NP hard.

Approximate! (Relaxation)

𝐶𝑢𝑡 𝑨, 𝑩 = σ_{𝑖∈𝑨,𝑗∈𝑩}𝑤_𝑖𝑗 s.t. 𝑨 = 𝑩 = 𝑪

Spectral Clustering: Relaxing Balanced Cuts

Laplacian formulation for simple balanced cuts for 2 sets

What is the cut value with this definition?

Graph function 𝒇 for cluster membership: 𝑓_𝑖 = ቊ 1 𝑖𝑓 𝑣_𝑖 ∈ 𝑨

−1 𝑖𝑓 𝑣_𝑖 ∈ 𝑩 min𝑨,𝑩 𝐶𝑢𝑡 𝑨, 𝑩 subject to 𝑨 = 𝑩

𝐶𝑢𝑡 𝑨, 𝑩 = ෍

𝑖∈𝑨,𝑗∈𝑩

𝑤_𝑖𝑗 = 1

4 ෍

𝑖∈𝑨,𝑗∈𝑩

𝑤_𝑖𝑗 (𝑓_𝑖 − 𝑓_𝑗)² = 1

2 𝒇^𝑇𝑳𝒇 What is the relationship with the smoothness of a graph function?

Spectral Clustering: Relaxing Balanced Cuts

Optimization formulation for spectral clustering Constraints:

𝑨 = 𝑩 ↔ σ_𝒊 𝑓_𝑖 = 0 ↔ 𝒇^𝑇𝟏_𝑵 = 0 ↔ 𝒇 ⊥ 𝟏_𝑵

𝐦𝐢𝐧𝒇 𝒇^𝑇𝑳𝒇 subject to 𝑓_𝑖 = ±1, 𝒇^𝑇𝟏_𝑵 = 0, 𝒇 = 𝑵 Objective:

𝐶𝑢𝑡 𝑨, 𝑩 = ෍

𝑖∈𝑨,𝑗∈𝑩

𝑤_𝑖𝑗 = 1

4 ෍

𝑖∈𝑨,𝑗∈𝑩

𝑤_𝑖𝑗 (𝑓_𝑖 − 𝑓_𝑗)² = 1

2 𝒇^𝑇𝑳𝒇

Still NP hard (∵ 𝑓_𝑖 = ±1, nonconvex). → relax even further!

𝑓_𝑖 = ±1 → 𝑓_𝑖∈ 𝑅 or 0 ≤ 𝑓_𝑖≤ 1

Spectral Clustering: Relaxing Balanced Cuts

Optimization formulation for spectral clustering

𝐦𝐢𝐧𝒇 𝒇^𝑇𝑳𝒇 subject to 𝑓_𝑖∈ 𝑅, 𝒇^𝑇𝟏_𝑵 = 0, 𝒇 = 𝑵

Rayleigh-Ritz theorem

If 𝜆₁ ≤ … ≤ 𝜆_𝑁 are the eigenvalues of real symmetric 𝑳, then 𝜆₁ = 𝐦𝐢𝐧

𝒙≠𝟎

𝒙^𝑇𝑳𝒙

𝒙^𝑇𝒙 = 𝐦𝐢𝐧

𝒙^𝑇𝒙=𝟏 𝒙^𝑇𝑳𝒙 𝜆_𝑁 = 𝐦𝐚𝐱

𝒙≠𝟎

𝒙^𝑇𝑳𝒙

𝒙^𝑇𝒙 = 𝐦𝐚𝐱

𝒙^𝑇𝒙=𝟏 𝒙^𝑇𝑳𝒙

𝒙^𝑇𝑳𝒙

𝒙^𝑇𝒙 is Rayleigh quotient How can we use it?

Proof:

Derivative yields 𝑳𝒙 = 𝜆𝒙

Spectral Clustering: Relaxing Balanced Cuts

Optimization formulation for spectral clustering

𝐦𝐢𝐧𝒇 𝒇^𝑇𝑳𝒇 subject to 𝑓_𝑖∈ 𝑅, 𝒇 ⊥ 𝟏_𝑵, 𝒇 = 𝑵 Generalized Rayleigh-Ritz theorem (Courant-Fischer-Weyl) If 𝜆₁ ≤ … ≤ 𝜆_𝑁 are the eigenvalues of real symmetric 𝑳, and

𝒖₁, … , 𝒖_𝑁 the corresponding orthogonal eigenvectors, for 𝑘 = 1, … , 𝑁 − 1 𝜆_𝑘+1 = 𝐦𝐢𝐧

𝒙≠𝟎, 𝒙⊥𝒖₁,…,𝒖_𝑘

𝒙^𝑇𝑳𝒙

𝒙^𝑇𝒙 = 𝐦𝐢𝐧

𝒙^𝑇𝒙=𝟏, 𝒙⊥𝒖₁,…,𝒖_𝒌 𝒙^𝑇𝑳𝒙 𝜆_𝑁−𝑘 = 𝐦𝐚𝐱

𝒙≠𝟎, 𝒙⊥𝒖_{𝑁−𝑘+1},…,𝒖_𝑁

𝒙^𝑇𝑳𝒙

𝒙^𝑇𝒙 = 𝐦𝐚𝐱

𝒙^𝑇𝒙=𝟏, 𝒙⊥𝒖_{𝑁−𝑘+1},…,𝒖_𝑁 𝒙^𝑇𝑳𝒙

The solution becomes the second eigenvector which can be obtain by 𝑘 = 1.

Spectral Clustering: Relaxing Balanced Cuts

Optimization formulation for spectral clustering

𝐦𝐢𝐧𝒇 𝒇^𝑇𝑳𝒇 subject to 𝑓_𝑖∈ 𝑅, 𝒇 ⊥ 𝟏_𝑵, 𝒇 = 𝑵

The solution

𝜆₂ = 𝐦𝐢𝐧

𝒙^𝑇𝒙=𝟏, 𝒙⊥𝒖₁ 𝒙^𝑇𝑳𝒙, where 𝒖₁ = 𝟏_𝑵 for 𝜆₁ = 0

→ second eigenvector 𝒙 of 𝑳

Since the elements in 𝒙 are not integer and 𝒙 = 𝟏, 𝒇 can be obtained by 𝑓_𝑖 = ቊ 1 𝑖𝑓 𝑥_𝑖 ≥ 0

−1 𝑖𝑓 𝑥_𝑖 < 0 → 𝒇 = 𝑵 → 𝐴 = 𝐵 𝑓_𝑖∈ {1, −1}

Spectral Clustering: Approximating RatioCut

RatioCut

Define graph function 𝒇 for cluster membership of RatioCut: ^𝑓_𝑖 ^{= ൞}

𝑩

𝑨 𝑖𝑓 𝑣_𝑖 ∈ 𝑨

− ^𝑨

𝑩 𝑖𝑓 𝑣_𝑖 ∈ 𝑩

min𝑨,𝑩 𝑅𝐶𝑢𝑡 𝑨, 𝑩 = min

𝑨,𝑩 ෍

𝑖∈𝑨,𝑗∈𝑩

𝑤_𝑖𝑗 1

𝑨 + 1 𝑩

𝒇^𝑇𝑳𝒇 = 1

2 ෍

𝑖,𝑗

𝑤_𝑖𝑗 (𝑓_𝑖 − 𝑓_𝑗)²= 𝑨 + 𝑩 𝑅𝐶𝑢𝑡 𝑨, 𝑩 Since 𝑨 + 𝑩 is constant, min

𝑨,𝑩 𝑅𝐶𝑢𝑡 𝑨, 𝑩 = min

𝒇 𝒇^𝑇𝑳𝒇, subject to 𝑓_𝑖 ∈ ^𝑩

𝑨 , − ^𝑨

𝑩

𝑨 = 𝑩

Spectral Clustering: Approximating RatioCut

Optimization formulation for RatioCut (same with balanced mincut) 𝐦𝐢𝐧𝒇 𝒇^𝑇𝑳𝒇 subject to, 𝑓_𝑖 ∈ 𝑅, 𝒇 = 𝑵

𝑠. 𝑡. 𝑓_𝑖 =

𝑩

𝑨 𝑖𝑓 𝑣_𝑖 ∈ 𝑨

− 𝑨

𝑩 𝑖𝑓 𝑣_𝑖 ∈ 𝑩

min𝑨,𝑩 𝑅𝐶𝑢𝑡 𝑨, 𝑩 = min

𝑨,𝑩 𝒇^𝑇𝑳𝒇

𝒇 ^𝟐 = σ_𝑖 𝑓_𝑖² = 𝑨 ^𝑩

𝑨 + 𝑩 ^𝑨

𝑩 = 𝑨 + 𝑩 = 𝑵 → not sufficient for 𝑓_𝑖∈ ^𝑩

𝑨 , − ^𝑨

𝑩

𝑨 = 𝑩 𝒇^𝑇𝑳𝒇 ≠ 𝑨 + 𝑩 ෍

𝑖∈𝑨,𝑗∈𝑩

𝑤_𝑖𝑗 1

𝑨 + 1 𝑩

Spectral Clustering: Approximating RatioCut

Optimization formulation for RatioCut (same with balanced Mincut) 𝐦𝐢𝐧𝒇 𝒇^𝑇𝑳𝒇 subject to 𝑓_𝑖∈ 𝑅, 𝒇 ⊥ 𝟏_𝑵, 𝒇 = 𝑵

𝑨 = 𝑩 → ෍

𝑖

𝑓_𝑖 = 0 ↔ 𝒇 ⊥ 𝟏_𝑵

Optimization formulation for RatioCut (same with balanced mincut) 𝐦𝐢𝐧𝒇 𝒇^𝑇𝑳𝒇 subject to 𝑓_𝑖∈ 𝑅, 𝒇 = 𝑵

Spectral Clustering: Approximating RatioCut

The solution

𝜆₂ = 𝐦𝐢𝐧

𝒙^𝑇𝒙=𝟏, 𝒙⊥𝒖₁ 𝒙^𝑇𝑳𝒙, where 𝒖₁ = 𝟏_𝑵 for 𝜆₁ = 0.

→ second eigenvector 𝒙 of 𝑳

Since the elements in 𝒙 are not integer and 𝒙 = 𝟏, 𝒇 can be obtained by

𝑓_𝑖 =

𝑩

𝑨 𝑖𝑓 𝑥_𝑖 ≥ 0

− 𝑨

𝑩 𝑖𝑓 𝑥_𝑖 < 0

→ 𝒇 = 𝑵

𝑨 = 𝑩 𝒇^𝑇𝑳𝒇 ≠ 𝑨 + 𝑩 ෍

𝑖∈𝑨,𝑗∈𝑩

𝑤_𝑖𝑗 1

𝑨 + 1 𝑩

Spectral Clustering: Approximating NormalizedCut

NormalizedCut

Balancing the clusters by considering the degrees of nodes Define graph function 𝒇 for cluster membership of NCut: ^𝑓_𝑖 ^{= ൞}

𝑣𝑜𝑙(𝑩)

𝑣𝑜𝑙(𝑨) 𝑖𝑓 𝑣_𝑖 ∈ 𝑨

− ^{𝑣𝑜𝑙(𝑨)}

𝑣𝑜𝑙(𝑩) 𝑖𝑓 𝑣_𝑖 ∈ 𝑩

min𝑨,𝑩 𝑁𝐶𝑢𝑡 𝑨, 𝑩 = min

𝑨,𝑩 ෍

𝑖∈𝑨,𝑗∈𝑩

𝑤_𝑖𝑗 1

𝑣𝑜𝑙(𝑨) + 1 𝑣𝑜𝑙(𝑩)

min𝐴,𝐵 𝒇^𝑇𝑳𝒇 = 𝑣𝑜𝑙 𝒱 𝑁𝐶𝑢𝑡 𝑨, 𝑩 , 𝑓_𝑖 ∈ 𝑣𝑜𝑙(𝑩)

𝑣𝑜𝑙(𝑨) , − 𝑣𝑜𝑙(𝑨) 𝑣𝑜𝑙(𝑩) 𝒇^𝑇𝑳𝒇 = ෍

𝑖,𝑗

𝑤_𝑖𝑗 𝑣𝑜𝑙(𝑩)

𝑣𝑜𝑙(𝑨) + 𝑣𝑜𝑙(𝑨) 𝑣𝑜𝑙(𝑩)

2

= ෍

𝑖,𝑗

𝑤_𝑖𝑗 𝑣𝑜𝑙 𝑩 + 𝑣𝑜𝑙(𝑨) 𝑣𝑜𝑙(𝑨) 𝑣𝑜𝑙(𝑩)

2

𝑣𝑜𝑙 𝑩 = 𝑣𝑜𝑙(𝑨)

Spectral Clustering: Approximating NormalizedCut

NormalizedCut

Define graph function 𝒇 for cluster membership of NCut: ^𝑓_𝑖 ^{= ൞}

𝑣𝑜𝑙(𝑩)

𝑣𝑜𝑙(𝑨) 𝑖𝑓 𝑣_𝑖 ∈ 𝑨

− ^{𝑣𝑜𝑙(𝑨)}

𝑣𝑜𝑙(𝑩) 𝑖𝑓 𝑣_𝑖 ∈ 𝑩

min𝑨,𝑩 𝑁𝐶𝑢𝑡 𝑨, 𝑩 = min

𝑨,𝑩 ෍

𝑖∈𝑨,𝑗∈𝑩

𝑤_𝑖𝑗 1

𝑣𝑜𝑙(𝑨) + 1 𝑣𝑜𝑙(𝑩)

(𝑫𝒇)^𝑇𝟏_𝑁 = 0, 𝒇^𝑇𝑫𝒇 = 𝑣𝑜𝑙 𝒱 Necessary condition for 𝑓_𝑖 ∈ ^{𝑣𝑜𝑙(𝑩)}

𝑣𝑜𝑙(𝑨) , − ^{𝑣𝑜𝑙(𝑨)}

𝑣𝑜𝑙(𝑩)

Spectral Clustering: Approximating NormalizedCut

Optimization formulation for NormalizedCut

𝐦𝐢𝐧𝒇 𝒇^𝑇𝑳𝒇 subject to 𝑓_𝑖∈ 𝑅, 𝑫𝒇 ⊥ 𝟏_𝑵, 𝒇^𝑇𝑫𝒇 = 𝑣𝑜𝑙 𝒱 NormalizedCut

Define graph function 𝒇 for cluster membership of NCut: ^𝑓_𝑖 ^{= ൞}

𝑣𝑜𝑙(𝑩)

𝑣𝑜𝑙(𝑨) 𝑖𝑓 𝑣_𝑖 ∈ 𝑨

− ^{𝑣𝑜𝑙(𝑨)}

𝑣𝑜𝑙(𝑩) 𝑖𝑓 𝑣_𝑖 ∈ 𝑩

min𝑨,𝑩 𝑁𝐶𝑢𝑡 𝑨, 𝑩 = min

𝑨,𝑩 ෍

𝑖∈𝑨,𝑗∈𝑩

𝑤_𝑖𝑗 1

𝑣𝑜𝑙(𝑨) + 1 𝑣𝑜𝑙(𝑩)

𝒇^𝑇𝑳𝒇 = 𝑣𝑜𝑙 𝒱 𝑁𝐶𝑢𝑡 𝑨, 𝑩 , (𝑫𝒇)^𝑇𝟏_𝑁 = 0, 𝒇^𝑇𝑫𝒇 = 𝑣𝑜𝑙 𝒱 ,

Spectral Clustering: Approximating NormalizedCut

Optimization formulation for NormalizedCut

𝐦𝐢𝐧𝒇 𝒇^𝑇𝑳𝒇 subject to 𝑓_𝑖∈ 𝑅, 𝑫𝒇 ⊥ 𝟏_𝑵, 𝒇^𝑇𝑫𝒇 = 𝑣𝑜𝑙 𝒱

Can we apply Rayleigh-Ritz now? Define 𝒉 = 𝑫^𝟏/𝟐𝒇 Optimization formulation for NormalizedCut

𝐦𝐢𝐧𝒉 𝒉^𝑇𝑫^−1/2𝑳𝑫^−𝟏/𝟐𝒉 subject to ℎ_𝑖∈ 𝑅, 𝒉 ⊥ 𝒖_{𝟏,𝑳𝒔𝒚𝒎}, 𝒉^𝑇𝒉 = 𝑣𝑜𝑙 𝒱

𝐦𝐢𝐧𝒉 𝒉^𝑇𝑳_𝒔𝒚𝒎𝒉 subject to ℎ_𝑖∈ 𝑅, 𝒉 ⊥ 𝒖_{𝟏,𝑳𝒔𝒚𝒎}, 𝒉 = 𝑣𝑜𝑙 𝒱

Spectral Clustering: Approximating NormalizedCut

Optimization formulation for NormalizedCut

Solution by Rayleigh-Ritz? 𝒉 = 𝒖_{𝟐,𝑳𝒔𝒚𝒎}, 𝒇 = 𝑫^−𝟏/𝟐𝒉 𝐦𝐢𝐧𝒉 𝒉^𝑇𝑳_𝒔𝒚𝒎𝒉 subject to ℎ_𝑖∈ 𝑅, 𝒉 ⊥ 𝒖_{𝟏,𝑳𝒔𝒚𝒎}, 𝒉 = 𝑣𝑜𝑙 𝒱

𝑓_𝑖 ←

𝑣𝑜𝑙(𝑩)

𝑣𝑜𝑙(𝑨) 𝑖𝑓 ℎ_𝑖 ≥ 0

− 𝑣𝑜𝑙(𝑨)

𝑣𝑜𝑙(𝑩) 𝑖𝑓 ℎ_𝑖 < 0

↔ 𝒇^𝑇𝑫𝒇 = 𝑣𝑜𝑙 𝒱 → 𝑣𝑜𝑙 𝑨 = 𝑣𝑜𝑙(𝑩)

→ eigenvector of 𝑳_𝒓𝒘

→ 𝐿𝑢 = 𝜆𝐷𝑢

Spectral Clustering: Bibliography

 Random Work: M. Meila et al. “A random walks view of spectral

segmentation”. In: International Conference on Artificial Intelligence and Statistics (2001)

 𝑳_𝒔𝒚𝒎: Andrew Y Ng, Michael I Jordan, and Yair Weiss. “On spectral clustering: Analysis and an algorithm”. In: Neural Information

Processing Systems. 2001

 𝑳_𝒓𝒎: J Shi and J Malik. “Normalized Cuts and Image Segmentation”. In:

IEEE Transactions on Pattern Analysis and Machine Intelligence 22 (2000), pp. 888–905

 Things can go wrong with the relaxation: Daniel A. Spielman and Shang H. Teng. “Spectral partitioning works: Planar graphs and finite element meshes”. In: Linear Algebra and Its Applications 421 (2007), pp. 284–

305

Summary questions of Lecture

 Explain the meaning of Spectral Clustering in one sentence. Why spectral?

 What is represented by the solution of Laplacian formulation relaxing Balanced Graph cut problem?

 What does the solution of MinCut problem mean?

 What does the solution of NormalizedCut problem mean?