[Study]Chapter 12. Frequent Subgraph Mining with GNNs
해당 내용은 개인적으로 정리한 내용임으로 틀린 부분이 있을 수 있습니다.
해당 챕터에서는 그래프의 특정한 패턴이나 부분 그래프를 나타내는 모티프의 식별 및 빈도를 파악하는 것을 이야기합니다.
그래프는 부분 그래프의 블럭들로 이루어져 있어 네트워크를 특징화하고 판별할 수 있는 힘이 있습니다. 많은 도메인에서 이러한 반복되는 구조적 요소들은 그래프의 특성을 결정합니다.
I. Subgraphs and motifs
네트워크를 구성하는 블록을 정의하는 도메인 특성에 의존하며 아래와 같이 두가지 공식이 있습니다.
- node-induced subgraph : 특정 노드 집합을 받아 해당 노드와 그에 연결된 edge들로 구성된 그래프
- edge-induced subgraph : 특정 edge들의 집합을 받아 상호작용하는 모든 node들로 구성된 그래프
Figure 1 : original graph에서 나온 서브 그래프 G1과 G2에서 나온 예제를 보면 G1은 G2에 포함되어\(_{contained-in}\)있다고 표현가능합니다.
1. Graph Isomorphism
Graph isomorphism은 두 그래프가 동일한치 확인하는 문제로 G1 = (V1, E1), G2 = (V2, E2)가 주어졌을때, 전단사 \(f : V_1 \rightarrow V_2\) 가 존재하면 isomorphic이라고 합니다.
Figure 2 : (좌) Isomorphic (우) Not Isomorphic
이러한 isomorphism인지 아는것은 NP-hard의 문제로 알지못합니다. Figure 1에서 G2의 부분그래프가 G1과 isomorphic하다는 것을 subgraph-isomorhpic이라 하고, 이러한 문제도 마찬가지로 NP-hard의 문제입니다.
2. Network Motifs
네트워크에서는 상호연관되어있는 중요한 패턴이 반복되어 나타나는데 이를 아래와 같이 정의할 수 있습니다.
- 패턴 : 작은 서브 그래프
- 반복 : 빈도
- 중요한 : 기대 빈도 보다 많음
이러한 Motifs가 왜 필요한가?
그래프의 작동하는 방식을 이해하는 것과 데이터셋에서 존재 유무에 기반한 예측을 도와줍니다.
Figure 4 : 그래프의 작동방식을 이해하는 예로 Feed-forward loops, parrallel loops, single-input modules 등이 있습니다.
3. subgraph frequency
목표 그래프 $G_T$이고, $G_Q$를 작은 그래프로 두자.
Graph-Level Frequency$G_Q$와 isomorphic한 $G_T$ 노드들의 부분집합 수
Figure 5 : Graph-Level Frequency
Node-Level Frequency$G_Q$와 isomorphic한 $G_T$ 부분집합이면서 anchor node v로 isomorphism하게 매핑이되는 $G_T$ 노드들의 수
Figure 6 : Node-Level Frequency, ($G_Q$, v)는 node-anchored 부분그래프로 불리고 이는 이상치에 robust한 특성을 가진다
4. motif significance
중요도를 정의할때 비교가능한 랜덤 그래프인 null-model(point의 comparison)이 필요합니다. Figure 7처럼 우측 무작위 network보다 좌측의 실세계의 서브그래프는 기능적인 중요도를 가집니다.
Figure 7 : (좌) 실세계 그래프 (우) null-model
실제 그래프와 랜덤그래프의 motifs를 비교하여 네트워크를 표현합니다.
- motifs를 count한다
- 랜덤 그래프를 유사한 통계치를 가지고 생성한다.
- 통계적인 측정치를 사용하여 각 motif가 얼마나 중요한지 평가한다(Z-score)
\[G_{n,p}\]5. Erdős–Rényi(ER) random graphs
무작위 무방향 그래프에서 n개의 노드에서 각 edge가 나타날 확률 p를 가진다.
6. Configuration model
Configuration Model은 차수 순서가 주어졌을때 랜덤그래프를 생성하는 모델로 실제 네트워크의 degree sequence와 비교하기 유용합니다.
Figure 8 : configuration model
위에서 보았던 Figure 7의 바퀴살\(_{spokes}\)의 대안으로 switching이 존재한다.
아래와 같은 방법을 통해 랜덤 그래프를 생성합니다.
- 주어진 그래프 G에서 시작하여 $Q\cdot \vert E\vert$ 번 반복
- endpoint({A\rightarrow B, C\rightarrow D} \Rightarrow {A\rightarrow D,C\rightarrow B})를 교환한다.
- 교환되는 edge는 multiple edge가 없거나 self-edge가 생성된 경우만 가능
- 결과로 같은 node degree를 가지는 무작위 그래프의 edge를 재배정한다.
7. Network siignificance profile(SP)
motif i의 통계적인 중요도를 수집하는 Z-score($Z_i$)로 아래와 같이 표현됩니다.
\[\begin{array}{ll} Z_i = (N_i^{real} - \bar{N}_i^{rand})/ std(N_i^{rand})\\ N_i^{real}\text{ : 실그래프의 #(motif i),} \\ \bar{N}_i^{rand} \text{ : 랜덤 그래프 인스턴스의 평균 #(motifs i)} \end{array}\]SP 는 정규화된 Z-score의 벡터로 아래와 같이 표현됩니다.
\[SP_i=Z_i / \sqrt{\sum_j Z_j^2}\]SP 차원은 모티프의 수에 의존하고, 이러한 SP는 부분그래프의 중요도에 관련하여 강조하며 다른 크기의 네트워크를 비교할때 중요합니다. 일반적으로는 큰 그래프에서 높은 Z-score를 나타납니다.
음수는 부분 그래프가 부족하게 나타나고 있는 것이고, 양수는 해당 그래프가 많이 있는 것을 의미합니다. 이러한 SP는 모든 서브그래프의 타입을 차원으로 빈도 값을 가지는 특징 벡터가 됩니다. 따라서, 랜덤그래프를 가지고 다른 그래프들의 profile을 비교합니다.
Figure 9 : Example significance profile
II. Neural Subgraph Representations
subgraph matching은 말그대로 쿼리 그래프가 목표 그래프의 서브그래프인지 확인하는 것을 말합니다.
Figure 10 : Subgraph Matching
우리는 이러한 Subgraph Matching Task가 subgraph-isomorphic을 통해 NP-hard임을 알고 있습니다. 따라서, GNN을 사용해 임베딩 공간에서 기하학적 형태를 이용하여 부분그래프의 isomorphsim의 속성을 수집해 부분 그래프가 isomorphism임을 예측합니다.
이러한 과정은 이진 분류를 고려하며 isomorphic 유무로 진행합니다.
Figure 11 : 쿼리의 Anchor 노드의 계산 그래프와 목표의 Anchor 노드의 계산 그래프를 GNN을 통해 임베딩하여 분류함.
부분 그래프의 신경 Architecture
- node-anchored 정의를 사용한다.
- node-anchored의 이웃을 가지고 사용한다.
- GNN을 이용하여 u와 v의 표현을 얻는다. node u의 이웃들이 노드 v의 이웃들과 isomorphic한지 예측한다.
왜 anchor인가?
GNN을 이용하여 각 노드(u,v)의 임베딩을 계산할 수 있습니다. 이는 u의 이웃과 v의 이웃들의 부분그래프(계산그래프)가 isomorphic함을 임베딩을 활용하여 결정할 수 있다는 것을 의미합니다.
1. order embedding space
Figure 12 : 임베딩을 비교할때 초록색 점이 빨간색 점보다 작지만 황색점은 빨간색 점보다 작지않음을 알 수 있다. 쿼리 1은 t 이웃의 부분집합을 나타낸다.
그래프 A를 point $Z_A$의 고차원의 임베딩 공간으로 매핑하면 $Z_A$는 모든 차원에서 non-negative하게 된다. 이를 통해 부분적인 순위를 수집하게\(_{transitivity}\) 한다. 여기서 Figure 12에서 초록색 점이 빨간색 점보다 작거나 같음을 이용해 해당 임베딩이 빨간색 점의 임베딩보다 작거나 같음을 모든 좌표에서 나타내는 정보를 의미합니다. 따라서, 2차원의 order embedding 공간에서 부분그래프는 상위 그래프에서 왼쪽아래에 위치하게 됩니다.
왜 임베딩 공간을 정렬(order)하는가?
부분집합의 isomorphc 관계는 해당 임베딩 공간에서 잘 임베딩됩니다.
Figure 13 : Transitivity, Anti-symmetry, Closure under intersection example
아래 속성들은 해당 임베딩 공간에서의 특성입니다.
Transitivity
ex. G1이 G2의 부분그래프일때 G2는 G3의 부분그래프이면 G1은 G3의 부분그래프이다.
Anti-symmetry
ex. G2가 G1의 부분그래프이고, G1이 G2의 부분그래프이면 G1은 G2에 isomorphic이다.
Closure under intersection
ex. 1개 노드의 trivial graph는 모든 그래프의 부분 그래프이다.
2. Order Constraint
위와 같은 GNN을 사용하여 Order embedding space를 학습하기 위해서는 부분그래프의 관계를 반영하는 order embedding이 학습되어야 합니다. 따라서, Order constraint는 이러한 속성을 특정해 이에 기반하여 loss 함수를 아래와 같이 디자인해야합니다.
Figure 14 : 각 임베딩의 관계를 반영하는 order constraint에 기반하여 디자인된 loss
이러한 max-margin loss를 최소화하는 방향으로 GNN 임베딩은 학습이 됩니다.
\[E(G_q, G_t)=\sum^{D}_{i=1}(max(0, z_q[i]-z_t[i]))^2\]위와 같이 쿼리 그래프와 목표 그래프의 margin을 정의하여 $E(G_q, G_t)=0$이면 부분그래프이고, E(G_q, G_t) > 0 면 부분 그래프가 아님을 나타냅니다.
Max-margin loss
쿼리가 목표의 부분집합인 정답일 때는 각 임베딩의 margin인 $E(G_q, G_t)$를 최소화하는 방향으로 그렇지 않을때는 $max(0, \alpha - E(G_q, G_t))$를 최소화하는 방향으로 이러한 Max-margin loss는 모델이 임베딩을 계속 떨어뜨리는 퇴화된 전략을 학습하는 것을 방지합니다. 즉, 모델의 임베딩이 지나치게 분산되지 않고 일정 간격을 유지하도록 제한합니다.
3. Training
그래프 G에서 학습할 쿼리 그래프와 목표 그래프를 생성할 필요가 있습니다. 목표 그래프에서 무작위 anchor 노드 v를 선택하고 K 거리를 가진 모든 노드를 G에서 가져옵니다. 이렇게 가져온 노드들을 BFS 샘플링을 통해 쿼리 그래프를 얻고, 샘플은 목표 그래프의 부분 그래프에서 가져옵니다.
Figure 15 : BFS sampling
- \(S=\{v\}, V=\emptyset\)를 초기화한다.
- N(S)를 S의 노드들의 모든 이웃으로 두고, 모든 단계에서 10%의 노드의 표본을 뽑아 N(S)의 노드를 남김.
- K 반복 후 S의 q anchor에서 발생한 부분 그래프 G를 얻음.
- 부정 샘플은 노드 또는 edge를 더하거나 제거함으로써 부분그래프가 아닌 쿼리 그래프를 얻음
이러한 샘플링 방법은 추출 가능한 부분그래프의 수가 Training 단계에서 반복을 할때마다 새로운 학습 쌍이 기하급수적으로 증가하기 때문에 모델이 다른 예제를 보게되어 과적합을 피하고 능력이 향상됩니다.
이러한 샘플링은 실행 시간과 수행능력의 trade-off 관계의 하이퍼파라미터입니다.
III. 3. Mining Frequent Motifs
k 크기의 가장 빈번한 motifs 를 찾을때, 아래의 두가지 문제를 해결해야합니다.
- 연결된 k 크기의 부분 그래프를 나열
- 각 부분그래프의 type의 발생 수를 센다.
Figure 16 : (좌) 가능한 N 크기의 motifs 나열 (우) 그래프에서 해당 motif으 빈도 확인
그래프의 존재하는 부분그래프를 모두 아는것은 NP-hard이고, 부분 그래프의 크기(유용한 크기는 3~7)가 증가함에따라 계산 시간도 지수적으로 증가합니다.
따라서, 표현학습이 위 문제에서 부분그래프를 아는 것을 GNN을 통한 예측으로 해결하고, 크기의 지수적인 폭발을 검색 공간을 조직하는 것으로 해결이 가능합니다.
1. SPMiner
SPMiner는 frequent motifs를 정의하는 신경 모델입니다.
핵심은 입력된 목표 그래프를 이웃들로 분해하고, 이웃들을 order 임베딩 공간으로 임베드하여 주어진 쿼리 부분그래프의 빈도를 빠르게 찾는 것 입니다.
Figure 17 : SPMiner, 각 노드를 계산그래프로 만들어 Order 임베딩 공간으로 임베드하여 증가하는 패턴의 부분 그래프 빈도를 계산합니다.
특정 노드를 중심으로하는 부분그래프 집합($G_{N_i}$)이 주어졌을때, 쿼리 그래프가 얼마나 자주 나타나는지 $G_{N_i}$의 빈도를 계산하여 추정합니다.
Figure 18 : 빨간점은 Motif의 임베딩으로 빨간색으로 표시된 영역안의 노란 점들은 부분그래프의 임베딩들로 매우 빠르게 빈도를 계산할 수 있습니다.
Figure 19 : SPMiner search process
SPMiner 검색 절차
- 목표 그래프에서 시작 노드 u를 무작위로 선택하여 u를 포함하는 motif S를 형성합니다.
- 반복적으로 motif S에서 u 주변의 노드를 선택하고 S에 추가해 성장시킵니다.
- 충분한 motif size에 도달하면, S에서 발생한 부분그래프를 얻게 됩니다.
음영된 영역의 각 점은 motif 패턴을 포함한 부분그래프를 표현합니다. 모든 그래프는 사소한 부분 그래프(노드 하나)를 포함한다. 이웃 노드를 더함으로써 motif를 성장시켜 해당 임베딩은 빨간점으로 표현합니다. 목표는 k step 이후에 빨간색으로 음영된 영역의 벡터 수를 최대화하는것 입니다. 즉, 음영된 영역의 임베딩 벡터들은 빨간색 벡터의 상위 그래프들로 해당 영역의 벡터가 많아질수록 해당 motif가 더 빈번하게 나타내는 것으로 더 중요한 패턴으로 해석될 수 있습니다.
각 단계에 추가할 노드는 탐욕적인 전략(heuristic)을 활용하여 모든 각 단계에서 total violation이 가장 작은 노드를 더한다. total violation은 Figure 19에서 음영으로 표시되지 않은 벡터들의 수를 가지고 측정한다.
Small Motifs
Figure 20 : Small Motifs, SPMiner는 Ground truth에 더 가깝게 식별합니다.
Large Motifs
Figure 21 : Large Motifs, SPMiner는 baseline(Rand-esu)보다 10-100x배 더 잘 식별합니다.