일단 적고보자

AAAI 24. [Paper]
Aritra Bhowmick, Mert Kosan, Zexi Huang, Ambuj Singh, Sourav Medya
New York University, University of California,University of Illinois
20 Dec 2023

그래프 클러스터링은 네트워크 분석에서 중요한 문제로 소셜네트워크, 생물학적 시스템, 컴퓨터 비전, 추천 시스템 등에서 사용된다. 그래프 클러스터링의 최종 목표는 다른 클러스터와의 구별은 유지하면서 비슷한 특징이나 기능을 하는 노드를 묶는 것이다.

Node attributes

기존 연구에서 그래프 클러스터링은 네트워크의 구조적 연결인 토폴로지에 의존해 진행되었다. 대표적인 방법으로 Modularity를 극대화하는 방법(논문리뷰) 을 이용했지만 최근 연구들에 의하면 노드의 추가적인 정보인 node attributes를 클러스터링에 활용하는게 중요하다는 사실이 알려졌다. node attribue를 사용하면 노드와 관련된 추가정보와 contextual insight도 제공한다. 이를 통해 클러스터링 정확도를 높일 수 있다.

GNN-based clustering

최근에는 GNN에 기반한 그래프 클러스터링 방법들이 많이 연구되고 있다고 한다. 여기선 총 3가지 사례를 언급한다.

  • MGAE : 손상된 노드를 marginalize해, 그래프 인코더로 representation learning을 진행
  • Graph AutoEncoder : 그래프의 latent representation을 학습해 클러스터링 효율 개선
  • Contrastive Learning : 최근에 클러스터링 효율성을 높이기 위해 도입됨

Neural modularity maximization

딥러닝기반 Modularity 최적화를 수행한 연구들에 대해 소개한다. 그래프 클러스트링이 어떻게 발전해왔는지에 대해 나열하고 있다.

  1. Yang et al. (2016) : graph autoencoder를 활용한 nonlinear reconstruction을 제안
  2. Wu et al. (2020) : adjacency matrix를 이용한 spatial proximity matrix를 사용한 기법을 제안. spacial eigenvactor를 활용한 modularity 최적화를 진행
  3. Mandaglio, Amelio, Tagarelli (2018) : modularity metric를 활용한 커뮤니티 탐지 및 그래프 클러스터링 수행
  4. Choong, Liu, Murata (2018) & Bhatia, Rani (2018) : 사전에 정의되지 않은 커뮤니티 구조 없이도 클러스터링을 수행하는 방법을 제시, 각각 VAE와 모듈러리티를 최적화하는 방식으로 진행
  5. Sun et al. (2021) : GNN을 활용해 modularity와 attribute similarity를 동시에 최적화하는 방법을 제안
  6. DMoN (Tsitsulin et al., 2023) : cluster assignment를 인코딩하고, modularity 기반의 목적함수로 최적화함

contributions

위의 연구에서는 입력으로 클러스터의 수를 요구하지 않았거나 노드의 속성를 최대한 활용하지 않았다. 예를 들어 pairwise membership 같은 추가적인 노드 레벨 정보를 활용하지 않았다. 그래서 이를 극복하기 위해 해당 논문에서는 사전에 클러스터의 갯수를 정의할 필요가 없고, 노드의 부가적인 정보를 활용하는 harness graph repressentation learning 방법을 사용한 Deep Graph Cluster (DGCLUSTER)를 제안한다. 구체적인 기여는 다음과 같다.

  1. DGCLUSTER : Modularity를 극대화하는 방식으로, Pairwise (Soft) Memberships을 통한 그래프 클러스터링 문제 해결. 그래프의 크기에 따른 선형적인 복잡도를 가진것도 특징
  2. Handling Unknown Number of Clusters and Auxiliary Information : 클러스터 수를 사전에 알 필요 없으며, flexible loss function을 통해 다양한 보조 정보를 활용 가능
  3. Extensive Empirical Evaluation : 7개의 데이터셋에서 4가지 평가항목에 대해 평가를 진행. 대부분의 항목에서 SOTA에 비해 유의미한 성능향상을 보임.

Problem Definition

기본 표현 정리

  • $G = (V,E)$ : undirected unweighted Graph
  • $V = {v_1, v_2, v_3, \dots}$ : n개의 nodes들의 집합
  • $E = {e_{ij} = (v_i,v_j)}$ : m개의 edge의 집합
  • $A = [A_{ij} \in R_+^{n\times n}]$ : $A_{ij}$가 i와 j 사이의 edge가 있으면 1 없으면 0인 adjacency matrix(인접행렬)
  • $d_i = \sum_j a_{ij}$ : 노드 i에 연결된 edge의 차수
  • $X_0 \in \mathbb{R}^{n \times r}$ : 노드의 추가적인 feature(attribute), r : 각 노드에 연결된 attribute 차원

Graph clustering

우리가 지금 하려는 목적은 그래프의 노드를 클러스터로 묶는 겁니다. 여기서 그래프 클러스터링은 노드를 k개의 클러스터로 묶는걸 의미하며 이걸 수식으로 나타내면 다음과 같습니다. ${V_i}_{i=1}^k, V_i \cap V_j = \emptyset \quad \text{(i ≠ j)}$. 즉 이렇게 되면 같은 클러스터에 있는 노드들 끼리는 다른 클러스터의 노드의 연결보다 더 촘촘해야한다. 여기에 해당 논문에서는 기존 연구와 다르게 그래프의 topology 뿐만 아니라 노드의 attribute도 클러스터링 과정에 포함시킨다 한다.

그래프 클러스터링 퀄리티의 지표로 다음과 같은 것들이 있다고 한다.

  1. Conductance
  2. nomalized cut-ratio
  3. modularity 이중에서 가장 널리 사용되는 metric은 modularity라고 한다.

Modularity

Modularity를 극대화시키는 방법을 통해 그래프 클러스터링 Newman 에 의해 처음 제안되었다고 한다. 해당 방법은 Topolog기반으로무작위로 edge가 분포되었을때랑 비교합니다. 수식은 다음과 같습니다.

\[Q = \frac{1}{2m} \sum_{ij} \left(A_{ij} - \frac{d_i d_j}{2m}\right) \delta(c_i, c_j)\]

Modularity의 값은 $-\frac{1}{2}$부터 1까지입니다. 이 값은 0에 가까울 수록 커뮤니티의 edge가 랜덤 분포를 따른다는 것이고, 높은값일수록 클러스터 구조를 가질 가능성이 높다.

\[Q = \frac{1}{2m} \sum_{ij} B \odot M = \frac{1}{2m} \text{Tr}(BM^T) = \frac{1}{2m} \text{Tr}(BM)\]
  • $\odot$ : Element-wise Multiplication(요소별 곱)
  • Tr : 행렬의 대각선 원소의 합
  • M : n x n의 대칭행렬, 같은 클러스에 있는지 여부를 나타내는 행렬

이는 다음과 같은 행렬곱의 형태로 나타낼 수도 있다.

여기서 큰 Q의 값은 중요한 클러스터 구조를 의미합니다. 그래서 좋은 클러스터 구조를 찾기 위해서 modularity를 최적화해야합니다. 근데 modularity를 최적화하는건 NP-Hard 문제이기에 spectral relaxation and 그리디 알고리즘과 같은 테크닉을 이용해 사용한다.

Goal

해당 논문에서는 Modularity를 극대화하는 방식으로 그래프 클러스터링을 진행한다. 이 방식을 통해 클러스터 수를 사전에 알 필요 없이 클러스터링이 가능해진다. 또한 graph represent learning을 사용해 구조적인 정보와 비 구조적인 정보를 모두 활용할 수 있게 됩니다. 그리고 실험을 통해 4가지 지표(Modularity, Conductance, NMI, F1 Score)를 통해 그래프 클러스터링의 품질을 평가하려고 한다.

DGCLUSTER

해당 논문에서는 그래프 구조와 노드 attribute에 기반한 Deep Graph Clustering을 진행하는 완전 미분 가능한 방법을 제안합니다. 해당 방법은 사전에 커뮤니티의 수를 정의할 필요도 없습니다. 여기서는 GNN을 통해 노드 임베딩을 진행하고 그 임베딩을 바탕으로 Similarity를 계산해 Modularity를 최적화 하는 방식을 사용합니다. 구체적인 절차는 다음과 같습니다.

  1. 노드 임베딩 생성 : GNN을 통해 노드 임베딩을 얻고 추가적인 변형을 통해 효과적인 클러스터링을 진행
  2. 유사도 기반의 모듈러리티 평가 : 노드 임베딩간 유사도를 계산하고, 이를 soft community pairwise membership으로 간주
  3. Objectives : 위의 membership을 기반으로 클러스터링 objective function을 구축, GNN의 모든 파라미터를 미분 가능한 방식으로 학습 시킴
  4. Final clustering : 최종적으로 GNN 노드 임베딩을 통해 커뮤니티 관계를 계산합니다.

이제 이 4단계를 순서대로 자세히 알아보자

Node embeddings using GNN

GNN은 그래프의 구조와 노드의 attribute 정보를 결합한 노드 임베딩을 생성하는 기법이다. 여기서 GNN의 핵심 요소는 Message Passing으로 이웃 노드로부터 정보를 받아 자신의 임베딩을 지속적으로 업데이트한다.

해당 논문에서는 노드 임베딩을 만들기 위해 GCN(Graph Convolutional Network)을 사용한다. 여기서 메시지 패싱 규칙은 다음과 같다.

\[X^{(l+1)} = \sigma(\tilde{A} X^{(l)} W^{(l)})\]
  • $\tilde{A}$ : 정규화된 인접행렬, $\tilde{A} = D^{-1/2} A D^{1/2}$
  • $D$ : 노드의 Degree 행렬
  • $X^{(l)}$ : l 번째 레이어의 임베딩 출력
  • $W^{(l)}$ : l 번째 행렬의 학습가능한 가중치 행렬
  • $\sigma$ : 활성화 함수
\[SELU(x) = \begin{cases} \beta x & \text{if } x \geq 0 \\ \beta \alpha (e^x - 1) & \text{otherwise} \end{cases}\]

활성화 함수로는 더 나은 수렴을 위해 SELU를 사용하며, 파라미터는 β ≈ 1.05, α ≈ 1.67

Transformation of the embeddings

  • GNN에서 나온 최종 임베딩의 출력 : $X = X^L = [X_1, \cdots, X_n]^T$
    • $X = X^L$ : 마지막 레이어의 출력이 최종 임베딩 행렬의 형태임
    • $X = [X_1, \cdots, X_n]^T$ : 임베딩 벡터를 모아놓은 행렬이 최종 임베딩 행렬의 형태임을 나타냄

그 이후 나온 최종 임베딩에 변환을 취해줌

  1. $X_i \leftarrow \frac{X_i}{\sum_j X_{ij}}$ : 정규화, tanh에 큰값이 들어갈 때 vanishing gradient를 막기 위해
  2. $X_i \leftarrow \tanh(X_i)$ : tanh 활성화
  3. $X_i \leftarrow X_i^{\circ 2}$ : 요소별 곱
  4. $X_i \leftarrow \frac{X_i}{|X_i|_2}$ : L2 정규화, 코사인 유사도 계산량을 줄이기 위해 dot pruduct로 단순화해서 사용함.

이렇게 하면 최종 임베딩은 양의 공간에 Surface of the Unit Sphere의 형태로 나타내게 됨

Modularity via embedding similarity

pairwise node similarity를 이용해서 Modularity를 계산하는 방법에 대해 기술한다. 여기서 M은 binary matrix로 j와 j가 같은 클러스터에 속하는지를 통해 나타낸다. 이를 수식으로 나타내면 다음과 같다.

\[M_{ij} = \delta(c_i, c_j) = \begin{cases} 1 & \text{if } c_i = c_j \\ 0 & \text{otherwise} \end{cases}\]

또한 해당 행렬은 transitivity 성질을 갖는다. 즉 $\delta(c_u, c_v) = 1$ 그리고 $\delta(c_v, c_w) = 1$ 면 $\delta(c_u, c_w) = 1$이고, 동일한 클러스터 내의 노드끼리는 항상 연결이 된다는게 보장된다.

여기서 Q를 극대화하는 최적의 M을 찾는건 NP-Hard문제라고 했다. 따라서 M을 soft pairwise community membership matrix로 바꿔서 사용한다.

여기서 이제 새로운 similarity $f_{sim}(X_u, X_v)$를 정의한다. 이 값은 0과 1사이의 값이며, 높은 값일 수록 두 노드 간의 관계가 더 강하다는 것을 의미한다. 많은 방법으로 유사도를 계산할 수 있지만 여기서는 코사인 유사도를 이용한다. 여기서 기존의 M은 0과 1 사이의 값을 통해 연산을 해야하지만, 임베딩 변환 후 내적을 함으로서 병렬처리가 가능해짐. 수식으로 나타내면 다음과 같음. $f_{sim}(X_u, X_v) = \cos(X_u, X_v) = X_u^T X_v$

Objective function

여기서는 Community Structure Quality Measure와 Local Auxilary Information에 기반해서 클러스터링을 할 수 있는 objective function을 소개한다.

Modularity optimization

제일 첫번째로 Modularity 최적화로 주요한 objective function이 된다.

\[L_1 = -\tilde{Q} = -\frac{1}{2m} \text{Tr}(B X X^T)\]

첫번째 손실함수는 다음과 같이 이루어진다. 위의 Mudularity식에서 마지막에 $M$이 $XX^T$로 바뀐것을 알 수 있다. 여기서 Q의 값을 극대화 하기위해 $L_1$을 최소화 하는 방식으로 학습을 진행한다.

Auxiliary information loss

추가적인 local information을 활용해 클러스터링의 flexibility를 높인다. 이러한 정보는 반지도 학습과 구조기반 그래프 분할을 통해 얻는다.

우선 Local Information이 무엇인지 정의한다. 총 2가지가 존재한다. 첫번째는

\[S\subseteq V\]

으로 그래프에서 로컬 정보가 주어진 노드들의 부분집합이다. 즉 그래프의 일부 노드에만 클러스터 레이블이 존재할때 레이블이 있는 노드들의 집합이다. 두번째는

\[H \in \mathbb{R}^{|S| \times |S|}\]

으로 $H_{ij}$은 노드 i와 j간의 Pairwise Membership, 즉 같은 클러스터에 속하는지 여부를 나타낸다.

\[H_{ij} = \begin{cases} 1 & \text{if } c_i = c_j \\ 0 & \text{otherwise} \end{cases}\]

H의 경우 노드가 같은 클러스터에 속해있는지 여부를 나타내므로 위 수식과 같이 나타낼 수 있다. 그리고 만약 H를 원핫 인코딩 된 행렬을 통해서 나타낸다면

\[C \in \mathbb{R}^{|S| \times p}\]

(p는 전체 클러스터의 수) 다음과 같이 나타낼 수 있고, H를 다시한번 C의 꼴로 하여 아래와 같이 나타낼 수 있다.

\[H = C C^T\]

만약 클러스터에 대한 라벨이 없다면 Louvain 알고리즘과 같은 그래프 분할 알고리즘을 이용하여, 가상의 레이블을 생성할 수도 있다.

\[L_2 = \frac{1}{|S|^2} \|H - X_S X_S^T\|_F^2\]
  • $X_S$ : 노드 집합 S에 대한 임베딩 부분 행렬
  • $H$ : Pairwise Information Matrix
  • $|\cdot|_F$ : Frobenius 노름(Frobenius Norm), 행렬 원소 간의 차이의 제곱 합(Squared Error)을 나타냄.

이제 보조 정보 손실함수 $L_2$를 정의하자. 이 손실함수의 목적은 H와 $X_S X_S^T$의 차이를 최소화하는데 있다. 즉 노드임베딩으로 계산된 유사도가 실제 정보와 일치되도록 학습시키는 것이다 .

\[L_2 = \frac{1}{|S|} \sum_{p_{ij} \in S} (1 - \langle X_i, X_j \rangle)^2\]
  • $p_{ij}$ : 동일한 커뮤니티에 속하는 노드쌍
  • $\langle X_i, X_j \rangle$ : 두 노드 간의 내적(유사도)

만약 개별 노드의 레이블이 아닌 pairwise membership만 주어질 경우 다음과 같은 L2를 정의 할 수 도 있다.

\(L = L1 + λL2\) 그리고 최종적으로 나오는 objective function은 다음과 같은 형태가 되며 λ는 하이퍼 파리머터로 두 손실 간의 균형을 조절하게 된다.

Cluster Node Embedding

해당 부분에서는 soft pairwise membership을 이용해 하드 클러스터 분할을 진행하는 방법에 대해 기술한다.

기존에는 pairwise node similarity matrix를 이용해 직접 클러스터링 알고리즘을 적용하였다. 대표적으로 Affinity Propagation 알고리즘이 있다. 하지만 해당 방법은 계산적으로 제한이 많이 됨. 그렇기에 여기서 저자가 제안한 방법은 기존에 임베딩에 했던 $L_2$ 정규화를 한 것을 이용한다. 해당 정규화를 통해 $|X_u|_2 = 1, \quad |X_v|_2 = 1$ 특성이 생긴다.

\[\|X_u - X_v\|_2^2 = \|X_u\|_2^2 + \|X_v\|_2^2 - 2 \|X_u\|_2 \|X_v\|_2 \cos(X_u, X_v)\]

코사인 유사도와 유클리드 사이의 관계를 다음과 같이 나타낼수 있고, L2 정규화 조건을 적용하면

\(\|X_u - X_v\|_2^2 = 2(1 - \cos(X_u, X_v))\) 다음과 같이 나타낼 수 있다. 이는 코사인 유사도가 1에 가까울수록 임베딩이 유사하다는 것을 의미하며, 유클리드거리는 0에 가까울 수록 유사함을 의미. 이를통해 코사인 유사도 계산 없이 유클리드 거리 계산만으로 클러스터링이 가능해짐.

여기에 저자는 Balanced Iterative Reducing and Clustering using Hierarchies (BIRCH) 알고리즘을 도입한다. 해당 알고리즘은 클러스터 수를 사전에 설정할 필요가 없으며, 데이터 포인트를 cluster feature tree로 변환한 후 최종 클러스터링을 수행한다.

Complexity analysis

여기서 해당 알고리즘에대한 복잡도를 계산한다. 구체적인 전개 과정은 생략하고 L1의 복잡도는 $O(k^2 n)$ L2의 복잡도는 $O(p^2 n)$이다. 따라서 전체 모델의 전체 복잡도는 $O(k^2 n + p^2 n)$이며 $k, p \ll n$ 일때 그래프의 크기에 대해 선형적으로 확장이 가능해진다. (여거서 파라미터 k : 임베딩 차원, p : 보조 정보의 차원)

Experimental Results

실험 요약 7개의 데이터셋 에 대해 4가지 평가 지표(graph conductance, modularity, NMI (Normalized Mutual Information), and F1 score)로 평가를 진행  또한 주요 평가항목으로 다음과 같은게 있음

  1. DGCLUSTER 성능이 다양한 GNN 아키텍처에도 일관되게 적용되는지
  2. Auxiliary Information 추가의 영향을 평가
  3. 추가적인 정규화 항이 모델에 미치는 영향
  4. DGCLUSTER가 데이터셋 별 감지된 커뮤니티 수

총 7개의 데이터셋이 사용됐으며 테마는 3가지임. 해당 데이터셋에 대한 정보는 위 표와 같음(V: 노드 수, E : edge 수, X : Feature 벡터의 차원, Y : 클러스터 수)

  1. Citation Networks : 논문간 인용 네트워크 3개
  2. Co-Purchase Networks : 동시에 구매된 제품에 대한 네트워크 2개
  3. Co-Authorship Networks : 공동 연구에 대한 네트워크 2개

그리고 2023년에 진행된 DMoN 연구와 동일한 Baseline setting을 통해 일관된 비교를 진행함. 기존의 10개의 알고리즘과 성능을 비교해 성능이 얼마나 개선됐는지를 평가함

  1. SBM (Stochastic Block Model) (Peixoto, 2014)
  2. k-means + DeepWalk (Perozzi, Al-Rfou, and Skiena, 2014)
  3. k-means(DGI) (Velicković et al., 2018)
  4. AGC (Attributed Graph Clustering) (Zhang et al., 2019)
  5. DAEGC (Deep Attributed Embedded Graph Clustering) (Wang et al., 2019)
  6. SDCN (Structural Deep Clustering Network) (Bo et al., 2020)
  7. NOCD (Neural Overlapping Community Detection) (Shchur and Günnemann, 2019)
  8. DiffPool (Differentiable Pooling) (Ying et al., 2018a)
  9. MinCutPool (Bianchi, Grattarola, and Alippi, 2020)
  10. Ortho (Bianchi, Grattarola, and Alippi, 2020)

성능 평가 요소는 다음과 같다.

  1. Modularity (Q) (Newman, 2006b) : 가장 주된 성능 평가 요소, 무작위 연결과 비교해 커뮤니티 연결강도를 비교하며 높을 수록 좋음
  2. Conductance (C) (Yang and Leskovec, 2012) : 그래프에서 커뮤니티 외부로 나가는 edge 비율을 측정. 낮을수록 좋음
  3. Normalized Mutual Information (NMI) : 클러스터 할당이 실제 노드 레이블과 일치도를 평가하며 높을수록 좋음
  4. F1 Score : pairwise membership과 클러스터 기반으로 계산하며, 계산복잡도가 높아 1000개만 샘플링해 계산하고, 높을수록 좋음.

실험 설정은 다음과 같다

  • GCN 설정
    • 히든 레이어 수 : 2
    • 히든 레이어 노드 수 : 256, 128
    • 출력 차원 : 64
  • 학습 설정
    • optimizer : Adam
    • Learning rate : 0.001
    • 에폭: 300
    • 하이퍼 파라미터 $\lambda$ : 다양하게 사용
    • 10번의 반복 실험 후 평균 성능으로 평가

해당 table을 보면 모든 데이터셋에서 기존 방법과 비교했을 때 비슷하거나 더 우수한 성능을 보이는 것을 알 수 있다. 여기서 굵은글씨는 첫번째, 밑줄은 두번째로 좋은 성능을 보인 방법이다.

해당 table도 마찬가지로 NMI와 F1-score에 대한 결과를 볼 수 있다. 여기서는 하이퍼 파라미터 $\lambda$값에따라 더 좋은 성능을 보인다는 것을 알 수 있다. 특히 위 데이터 셋중에서 Co-purchase와 Co-authorship 네트워크에서는 모든 지표에서 우수한 성능을 보인것을 볼 수 있다.

이제 위에서 말한 주된 평가항목 4개에 대한 결과이다.

Robustness on Different Base GNNs

DGCLUSTER가 다양한 GNN 아키텍처에 대한 Robustness를 평가함. 이때 위 결과를 통해서 GNN 모델에 크게 영향을 미치지 않는다는 것을 알 수 있었음. 총 4가지 모델 (GCN, GAT, GIN , GraphSAGE)에 대해 실험을 했을 때 GNN 모델에 대해 크게 영향을 받지 않으며 일관된 성능을 보였다. GAT는 Q를 GraphSAGE는 C와 F1 score에 좀 더 좋은 성능을 보였으며, GIN은 전반적인 성능 저하가 있었다.

Auxiliary Information Effect

이제 하이퍼 파라미터 값인 $\lambda$의 값을 조절함에 따라 어떠한 변화가 있는지를 테스트 하였다. 이때 위 표를 보면 $\lambda$값이 증가하면 Q는 점점 감소하는데, 이는 당연히 Q는 그래프 구조에만 의존하기 때문이다. 하지만 NMI를 보면 $\lambda$값이 점점 높아짐에 따라 상당히 증가하는 것을 볼 수 있다.

Additional Regularization

\[\alpha \left( \frac{1}{n^2} \sum_{ij} \langle X_i, X_j \rangle \right)^2 = \alpha \| \bar{X} \|_2^4\]
  • $\bar{X}$ : 노드 임베딩의 평균
  • $\alpha$ : 조정가능한 하이퍼 파라미터

다음과 같은 정규화 식을 넣었을때의 성능 차이를 확인해본다. 이는 단순 클러스터링, 즉 모든 노드가 하나의 클러스터에 속하는 상황을 회피하기 위해 넣었다고 한다. 하지만 위 표를 보다 싶이 영향을 거의 미치지 않는다는 것을 알 수 있다. 하지만 잠재적인 단순 클러스터링을 방지할 수 있는 효과가 생긴다.

Number of Communities

마지막으로 커뮤니티 수에 대한 평가를 진행한다. 다양한 $\lambda$값과 데이터셋에 대해 커뮤니티수를 확인해본다. 여기서 $\lambda$에 값에 따라 커뮤니티 수가 변동될 순 있지만, 다양한 데이터셋에서 일관적인 성능을 보여준다.

You may also enjoy