CS224W - 05.Spectral Clustering

in Data on Graph


Spectral Clustering

  • ‘어떻게 Spectral Method를 이용해서 Community Detection을 할 것인가?’
    • Specral Method: Graph Adjacency Matrix의 Eigenvalue, Eigenvector를 계산하는 법 (선형대수)
  • 세 가지 Step
    • ⅰ. Preprocessing
      • 그래프를 Matrix representation으로 나타낸다.
    • ⅱ. Decomposition
      • Matrix로부터 Eigenvalue, Eigenvector를 계산해낸다.
      • 각 점들을 하나 이상의 Eigenvector들에 근거해 Low-dimension 공간으로 Mapping!
    • ⅲ. Grouping
      • 새로운 Representation에 근거하여, 각 점들을 두개 이상의 클러스터에 Assign!
  • 결국 Spectral Clustering도 Graph Partitioning인데, Spectral Clustering 전에 보다 근본적인 문제에 대한 궁금증이 생김
    • 그래프의 ‘좋은’ Partition이란 무엇이지?

    • 좋은 Partition을 ‘효율적으로’ ‘확인(Identify)’할 수 있는 방법은 없을까?

    • (첫번째 물음에 대해, 4강에서 ‘Modularity’를 떠올릴 수 있는데, ‘Modularity’는 Null Model과 Physics의 view였다면,
      이번 Chapter는 CS적인 최적화의 관점 → Approximation Guarantee와 얼마나 Network가 잘 working하는지에 대한 이야기를 하게 될 것)

    ‘좋은’ Partition이란?

    • Group 내의 connection 수를 Maximize, Group 간의 connection 수는 Minimize하는 Partition
    • 그렇다면, Group을 잘 ‘잘라야’ 할텐데, 이에 ‘Graph Cuts’라는 개념 출현
      gnn05-02
      • cut(A,B): 두 Sets를 얻기 위해 몇 개의 edges를 끊어야 하는가.

      gnn05-01

    • Objective Function을 ‘Edge Cut’에 대한 함수로 만든다.
      • Criterion1. Minimum-cut
        gnn05-03
        • 하지만 이 Criterion은 Externel cluster connection에만 집중한 나머지, internal cluster connectivity를 고려하지는 못함 (ex. Degenerate Case)
          gnn05-04
      • Criterion2. Conductance
        • Criterion1의 문제를 해결
        • 이 Criterion을 사용하면, 좀 더 Balanced한 Partition을 얻을 수 있다.

        • Φ(A,B): 각 그룹의 Density 대비 그룹간의 connectivity
          gnn05-05

          • vol(A), vol(B) 즉 각 그룹의 Size가 비슷할수록 분모의 값이 커질 것. (→ Φ값이 작아짐)
            (Conductance가 가능한 작기를 바라는 목적과 상통!)

    ‘효율적으로’ 좋은 Partition을 찾을 순 없을까?

    • Best Conductance 찾기는 NP-hard Problem!
    • (Guaranteed된) Approximation을 통해 해결하자.

Spectral Graph Partitioning

  • A: 무방향 그래프 G의 인접행렬

  • x (= (x1, x2, …, xn)): n개 노드들의 label 및 value를 담은 vector

  • A·x : 각 노드들의 neighbor들의 labels sum
    gnn05-06

    • A·__x__의 jth component: j번째 노드의 neighbor들의 x 값들의 합!

Spectral Graph Theory

  • Adjacency matrix A를 다음과 같이 Decompose할 수 있다.
    gnn05-07

    • Eigenvalue들을 오름차순으로 정리했을 때, 그에 대해 상응하는 Eigenvector들을 Spectrum이라고 하고
      그래프 G를 나타내는 함수의 Spectrum을 분석하는 것이 Spectral Graph Theory

    • Case1: d-Regular Graph
      • 그래프 G의 모든 노드들의 Degree가 d라면?
        • x = (1, 1, …, 1), λ=d
          (d가 A의 eigenvalue들 중 가장 큰 값)
    • Case2: Graph on 2-Components

      • 그래프 G가 연결되어있지 않고, d-regular인 두 개의 component로 나누어져 있다면?
        gnn05-08

      • 직관적으로, connected d-regular graph의 eigenvector는 (1,1, …, 1) 일 것.
      • Eigenvector들 간에는 orthogonal하기 때문에, eigenvector들의 component들은 양, 음수 모두를 갖게 될 것.
      • 두번째로 큰 Eigenvalue에 대응하는 Eigenvector에 대해, 양수인 node들은 같은 group으로, 음수인 node들을 또 다른 하나의 group으로 묶는다!

Matrix Representations

  • Anxn: Adjacency Matrix
    gnn05-09
    • 대칭행렬
    • n개의 real eigenvalues
    • eigenvector의 component들 역시 실수값을 가지며, eigenvector들 간에는 orthogonal

  • Dnxn: Degree Matrix
    gnn05-10

  • Lnxn: Laplacian Matrix
    • L = D-A
      gnn05-11
    • Laplacian Matrix의 Rowsum = 0

    • 생각해볼 수 있는 Trivial Eigenpair: Eigenvector (1,1,…,1) with eigenvalue 0

    • Eigenvalue: 0이상의 실수

    • Eigenvector: 모두 실수값들을 가짐

    • Laplacian Matrix가 지니는 성질
      gnn05-12

      • Laplacian Matrix로 무엇을 할 수 있나?
        -> Laplacian Matrix의 2nd Largest Eigenvalue는, 그래프 내 node들을 partition할 때, node들간의 거리 합의 최소값!
        (이 말인즉슨, 2nd Largest Eigenvalue에 대응하는 2nd Eigenvector들을 바탕으로 0보다 큰 값을 하나의 그룹으로, 0보다 작은 값을 다른 한 그룹으로 partition 할 때가 최상의 partition이 된다는 것)

        • 이는, 다음의 사실을 이용한 것.
          gnn05-13

          M의 자리에 L(Laplacian Matrix)을 넣으면, 이 식은 다음과 같이 변형됨
          gnn05-14

          • eigenvector의 성질에 따르면 분모는 1이 되고, 이는 곧 분자를 최소화하겠다는 것과 동치.
          • 2nd eigenvector에서 0보다 작은값은 왼쪽으로, 큰 값은 오른쪽으로 모아서 cross edge들을 최대한 줄이는 optimize problem이며,
            이 optimize solution은 λ2
            gnn05-15
  • 다시 Optimal cut을 찾는 문제로 돌아와서,
    • Fiedler는 1973년에 다음과 같은 방법을 제시
      gnn05-16
      • 바로 앞의 사고와 굉장히 유사한 사고

    • Rayleigh Theorem (또다른 Classical Theory)
      gnn05-17

      • 이런 사고들이 왜 중요한가?
        ∵ 이런 종류의 Graph Laplacian의 Spectral Clustering은 Near Optimal Solution을 주기 때문.

Spectral Partitioning Algorithm

  • 결론적으로, Spectral Partitioning하는 과정은 다음과 같다.

  • 1) Pre-processing
    • 그래프 G로부터 Laplacian matrix L을 만든다.
  • 2) Decomposition
    • L로부터 eigenvalue λ와 eigenvector x 를 얻는다.
  • 3) Grouping
    • 이 때 2nd smallest eigenvalue λ2에 상응하는 eigenvector x2 를 보고, 0보다 작은 값들을 하나의 partition으로, 0보다 큰 값들을 다른 partition으로 묶는다.
      gnn05-18
  • 어떻게 k개의 cluster로 그래프를 partition 할까?
    • 접근1: Recursive bi-partitioning
      gnn05-19
    • 접근2: Cluster multiple eigenvectros
      gnn05-20
      • x2, x3에서 이미 cluster는 distinguished되었고, 이들을 종합적으로 생각할 수 있음.

      • 너무 많은 eigenvector들을 고려해야될 필요는 없다.

      • k-way normalized cut (k-way conductance based cut)을 통해 optimal cut을 근사할 수 있다.

      • Eigengap을 이용해서 k를 선택할 수도 있음.
        • Eigengap: 연속된 두 eigenvalue 값들 간의 차이
        • 가장 stable한 clustering은 일반적으로 eigengap Δk를 최대화하는 값 k에서 달성
          gnn05-21

Motif-Based Spectral Clustering

  • Pattern에 근거하여 clustering을 하고 싶다면? gnn05-22

    • Idea: 다른 Motif는 다른 Modular structure를 나타낸다!
      gnn05-23

  • Edge cut의 Criterion으로서 Conductance를 사용했던 것처럼
    Motif cut의 Criterion으로서도 Conductance를 한 번 사용해보겠다.

    gnn05-24

    • 예시
      gnn05-25

    • Minimal motif conductance를 찾는 문제는 (Edge cut conductance와 마찬가지로) NP-Hard문제이기 때문에, Approximation!
      -> Solution: Motif Spectral Clustering

  • 3 Steps
    • 1) Pre-Processing
      • 그래프 G로부터 관심있는 Motif M을 적용한 Weighted graph W^(M)을 만든다.
        gnn05-26
    • 2) Decomposition
      • Weighted graph에 대한 Laplacian Matrix를 만든다!
      • Laplacian Matrix에 대해 Do standard Spectral clustering!
    • 3) Grouping
      • Standard Spectral Clustering과 같은 방식으로 grouping 판단! (2nd eigenvector에 근거하여 cluster 결정!)
      • 다만 여기서는 0을 기준으로 나누는 것이 아니라, Sweep Procedure로!
        • 노드를 eigenvector components 들의 값에 따라 sorting하고, Motif conductance가 최소가 되는 조합을 찾는다.
          gnn05-27
          • 해당 조합이 near optimal이라는 사실은 수학적으로 증명되어 있음. (By Motif Cheeger Inequality)
  • Motif-Based Spectral Clustering 적용 예시 (먹이사슬 문제)
    Nodes: 생태계 내 종들, Edges: 천적관계

    • ‘다른 motif는 다른 먹이사슬 관계를 나타낸다.’는 Ideation 하에, 먹이사슬을 가장 잘 설명하는 Motif를 찾으려 함
      gnn05-28

    • 3 모티프를 거친 후, 각 모티프들에 대해 Motif Conductance를 Plotting 해보면 다음과 같은 결과를 얻게 됨
      gnn05-29
      • Motif M6이 Significance를 갖고 있다고 말할 수 있음.
        반면 M5, M8에 대해서는 Profile plot에서 어떠한 good cut을 찾을 수가 없음.
        -> Network는 Motif M6에 근거하여 Organize 되어 있다!
    • 실제로 이 예시의 모티프를 따르는 Cluster는 정확도 84% 정도의 좋은 성능을 보여줌
    • M6의 천적관계 instance들은 다음과 같이 나타남.
      gnn05-30

References

CS224W: Spectral Clustering