CS224W - (12) Fast Neural Subgraph Matching and Counting
](https://i.imgur.com/VbdV6ye.png)
Introduction
Subgraph
서브그래프는 네트워크의 벽돌 같은 존재입니다. 서브그래프는 네트워크의 특성을 만들고 차별화하는 힘이 있죠. 많은 도메인에서 반복되는 구조적 구성 요소가 그래프의 기능이나 동작을 결정합니다.
서브그래프와 모티프(Subgraphs and Motifs)
그래프 $G = (V, E)$가 주어졌을 때 서브그래프를 정의하는 방법은 두 가지가 있습니다. 첫 번째로 노드 기반 서브그래프입니다. 전체 그래프에서 노드의 부분 집합과 그 부분 집합의 모든 엣지로 구성된 서브그래프는 다음의 성질을 갖습니다.
- $G^\prime = (V^\prime, E^\prime)$ 은 노드 기반 서브그래프일 때 다음 성질이 필요충분조건이다.
- $V^\prime \subseteq V$
- $E^\prime = \{ (u, v) \in E \mid u, v \in V^\prime \}$
- $G^\prime$는 $V^\prime$로부터 만들어진 서브그래프이다.
두 번째 방법은 엣지 기반 서브그래프입니다. 엣지의 부분 집합과 그 엣지를 구성하는 모든 노드로 구성된 서브그래프입니다. 엣지 기반 서브그래프는 다음 성질을 갖습니다.
- $G^\prime = (V^\prime, E^\prime)$은 엣지 기반 서브그래프일 때 다음 성질이 필요충분조건이다.
- $E^\prime \subseteq E$
- $V^\prime = \{ v \in V \mid (u, v) \in E^\prime \text{ for some } u \}$
서브그래프의 정의는 사실 도메인의 영향을 많이 받습니다. 화학에 대한 그래프라면 기능 그룹에 따른 노드 기반 서브그래프일 것이고, 지식 그래프라면 논리적 관계를 표현하는 엣지들이 중요하므로 엣지 기반 서브그래프일 수 있습니다.
만약 위 그림의 $G_1$과 $G_2$처럼 완전 다른 그래프에서 노드의 부분집합 $V^\prime$과 엣지의 부분집합 $E^\prime$이 나왔을 때 보통 $G_1$이 $G_2$에 포함된다고 말합니다.
Graph Isomorphism
Graph isomorphism 문제는 두 그래프가 완전히 같은 그래프인지를 묻는 문제입니다. 만약 $G_1 = (V_1, E_1)$과 $G_2 = (V_2, E_2)$가 isomorphic하다면 $(u, v) \in E_1 \iff (f(u), f(v)) \in E_2$ 를 만족하는 bijection $f: V_1 \to V_2$가 존재합니다. 이때 $f$를 isomorphism이라고 부릅니다.
하지만 graph isomorphism이 NP-hard인지, 이 문제를 풀기 위한 다항 알고리즘이 존재하는지 알 수 없습니다. Graph isomorphism은 서브그래프에도 적용할 수 있습니다. 만약 $G_2$의 서브그래프가 $G_1$과 isomorphic하다면 $G_2$는 $G_1$에 subgraph-isomorphic합니다. 이 경우 $G_1$은 당연히 $G_2$의 서브그래프가 됩니다. 그리고 노드 기반 또는 엣지 기반 서브그래프의 정의 중 하나를 사용할 수 있습니다. Subgraph-isomorphic 문제는 NP-hard에 속합니다.
All non-isomorphic, connected, undirected, graphs of size 4
All non-isomorphic, connected, directed, graphs of size 3
네트워크 모티프(Network Motifs)
Motifs
네트워크 모티프란 반복적이고 중요한 상호 연결 패턴을 의미합니다. 이 네트워크 모티프를 정의할 때 다음 세 가지 개념을 활용하는데요.
- 패턴: 노드 기반의 작은 서브그래프
- 반복: 높은 발생 빈도를 가지고 있음
- 유의성: (임의로 생성된 그래프 대비) 예상보다 자주 등장해야 함
모티프는 그래프에 있어서 매우 중요합니다. 우선 그래프가 어떻게 작동하는지 이해를 도우며, 그래프 데이터셋의 존재 여부에 기반한 예측을 생성하도록 도와줍니다. 다음의 예시를 살펴보겠습니다.
- Feed-forward loops: 뉴런 네트워크에서 주로 발견되며 “생물학적 노이즈”를 중화합니다.
- Parallel loops: 음식 관련 네트워크에서 발견됩니다.
- Single-input modules: 유전자 제어 네트워크에서 발견됩니다.
빈도
위에서 모티프를 정의할 때 빈도에 대한 내용이 많았습니다. 이제부터 서브그래프의 빈도에 대해서 알아보도록 하겠습니다. $G_Q$를 작은 그래프, $G_T$를 타겟 그래프 데이터셋으로 정의합니다. 그래프 레벨에서 서브그래프의 빈도에 대한 정의는 다음과 같습니다.
Example for graph-level subgraph frequency
$G_T$에서 $G_Q$의 빈도란 노드 $V_T$로 만들어지는 $G_T$의 서브 그래프가 $G_Q$에 isomorphic할 때 $G_T$의 노드 $V_T$의 고유 부분집합의 수
위에서 정의한 $G_Q$ 안에 있는 앵커 노드를 $v$로 두었을 때 노드 레벨에서 서브그래프의 빈도에 대한 정의는 다음과 같습니다.
Example for node-level subgraph frequency
$G_T$에 속하는 노드 $u$에 대해서 $G_T$의 서브그래프가 $G_Q$에 isomorphic하고, 이 isomorphism으로 노드 $u$가 노드 $v$에 매핑될 때 $G_T$ 에 속하는 노드 $u$의 개수
이때 $(G_Q, v)$를 앵커 노드 서브그래프(node-anchored subgraph) 라고 합니다. 이 방식의 정의는 이상치(outlier)에 강건합니다.
데이터셋이 여러 개의 그래프를 포함하고 있는 경우에는 데이터셋을 연결되어 있지 않은 여러 개의 그래프 컴포넌트로 구성된 하나의 큰 그래프 $G_T$로 취급하게 됩니다.
유의성
모티프를 정의할 때 사용하는 유의성을 정의하려면 일종의 영 모형(null model)이 필요합니다. 그래프에서는 임의로 생성되는 네트워크와 실제 네트워크를 비교하여 특정 서브그래프가 더 많이 등장하는지 확인을 하면 됩니다.
Three random graphs drawn from G5, 0.6
임의로 생성되는 네트워크로는 Erdös-Rényi (ER) 랜덤 그래프를 사용합니다. ER 그래프는 $G_{n, p}$로 보통 쓰는데, $n$ 개의 노드에 대해서 두 노드가 연결될 확률 $p$로 방향이 없는 그래프를 생성합니다.
Configuration model
다른 방법으로는 구성 모델(configuration model) 이 있습니다. 구성 모델은 주어진 degree sequence $k_1, \cdots, k_N$ 을 사용하여 랜덤 그래프를 생성합니다. 그림에서 볼 수 있다시피 노드가 주어지면 각 노드마다의 degree가 주어집니다. 각 노드를 임의로 쌍을 지어 그래프를 구성합니다. 구성 모델은 네트워크의 영 모델로 매우 유용한데, 실제 네트워크와 동일한 degree sequence를 가진 랜덤 네트워크를 비교할 수 있기 때문입니다.
Switching
또다른 방법으로는 스위칭(switching) 이 있습니다. 그래프 $G$가 주어졌을 때 스위칭 단계를 $Q \cdot |E|$ 번만큼 반복합니다. 여기서 $Q$는 상수이며, $|E|$는 엣지의 수입니다. 스위칭은 연결되어 있는 엣지 두 쌍을 무작위로 선택한 다음 각 엣지의 끝점을 서로 바꿉니다. 이 시행을 계속 반복하면 무작위로 재연결된 그래프를 얻을 수 있습니다. 하지만 동일한 node degree를 갖게 되죠. 스위칭을 수행할 때는 $Q$ 값을 적당히 크게 잡아줘야 올바른 무작위 그래프를 얻을 수 있습니다.
어떤 네트워크를 무작위 그래프와 비교하면 특정 모티프가 과하게 표현됩니다. 이런 모티프의 유의성을 계산하는 과정은 3단계에 걸쳐 이루어집니다.
- 주어진 그래프에서 모티프의 수를 센다.
- 주어진 그래프와 노드의 수가 비슷하거나, 엣지의 수가 비슷하거나, node degree가 비슷한 임의의 그래프를 생성하고 임의의 그래프의 모티프의 수를 센다.
- 각 모티프의 유의성을 통계적 방식으로 측정한다.
- 이때 Z-score를 사용합니다.
$Z_i$는 모티프 $i$ 에 대한 통계적 유의성을 의미합니다.
\[Z_i = \frac{N_i^\text{real} - \bar{N}_i^\text{rand}}{\text{std} (N_i^\text{rand})}\]- $N_i^\text{real}$: 그래프 $G^\text{real}$ 내 모티프 $i$의 수
- $\bar{N}_i^\text{rand}$: 랜덤 그래프 인스턴스 내 평균 모티프 $i$의 수
이를 이용하여 네트워크 유의성 프로파일(SP) 을 계산할 수 있습니다.
\[\text{SP}_i = \frac{Z_i}{\sqrt{\sum_j Z_j^2}}\]네트워크 유의성 프로파일은 Z-score의 정규화된 벡터이며 벡터의 차원은 모티프의 수에 따라 정해집니다. 네트워크 유의성 프로파일은 서브그래프의 상대적 유의성을 강조하는데 다양한 크기의 네트워크를 비교하는데 매우 중요합니다. 일반적으로 더 큰 그래프에서 Z-score의 값이 더 커집니다.
각 서브그래프에 대해서 Z-score는 서브그래프의 중요도를 분류할 수 있습니다. 만약 음수가 나왔다면 중요하지 않은, 양수가 나왔다면 중요한 서브그래프라는 의미입니다. 이를 통해 우리는 네트워크 유의성 프로파일을 만들 수 있고, 이는 각 서브그래프 종류에 대해 피처 벡터가 됩니다.
Network significance profile
위 그림에서 알 수 있듯이 서로 다른 도메인의 네트워크는 서로 다른 네트워크 유의성 프로파일을 가집니다. 따라서 이를 통해 해당 도메인의 고유한 특성을 파악할 수 있습니다.
지금까지 다룬 모티프의 대한 내용은 방향성 여부, 노드 특성 여부, 시간 관련 여부 등 네트워크의 특성에 따라 더 확장될 수 있습니다.
뉴럴 서브그래프 매칭(Neural Subgraph Matching)
모든 노드가 연결되어 있지 않을 수도 있는 매우 큰 그래프와 모든 노드가 연결되어 있는 쿼리 그래프가 있다고 가정해봅시다. 이 쿼리 그래프가 매우 큰 그래프의 서브그래프인걸 어떻게 알 수 있을까요? 보통 GNN을 사용하여 서브그래프 isomorphism을 예측합니다. 이때 임베딩 공간의 기하학적인 모양을 활용해 서브그래프의 isomorphism의 속성을 잡아냅니다.
서브그래프 매칭 태스크는 일종의 바이너리 예측입니다. 만약 쿼리가 타겟 그래프의 서브그래프와 isomorphic하면 True, 아니라면 False를 반환하는 문제입니다.
Overview of the Approach
이런 서브그래프 매칭에 뉴럴 네트워크를 활용할 수 있습니다. 서브그래프를 위한 뉴럴 아키텍처는 다음과 같습니다.
우선 쿼리 그래프와 타겟 그래프에서 앵커 노드(anchor node)의 임베딩이 같은지 확인합니다.
그 다음 각 앵커 노드에서 n-hop 이웃들의 임베딩과 GNN을 사용하여 두 앵커 노드의 이웃들이 서로 isomorphic한지 확인합니다. 타겟 그래프와 쿼리 그래프에서 각 노드에 대해 이웃을 임베딩하기 위해서는 다음 과정을 거칩니다. 우선 타겟 그래프에 대해서 앵커 노드로부터 $k$-hop 이웃을 찾습니다. 보통 BFS를 활용하여 찾을 수 있습니다. $k$는 하이퍼파라미터인데, 이 값이 클 수록 더 큰 모델이 됩니다. 쿼리 그래프에 대해서도 동일한 작업을 수행합니다. 그러면 GNN을 사용하여 이웃 노드를 임베딩할 수 있게 됩니다.
이렇게 앵커 노드를 활용하는 이유는 노드 레벨의 서브그래프 빈도의 정의와 연관이 있습니다. 노드 레벨의 서브그래프 빈도의 정의에서는 타겟 그래프의 노드 $u$와 쿼리 그래프의 노드 $v$ 사이의 isomorphism 매핑이 있으면 된다고 했는데, GNN을 활용하여 이 두 노드의 임베딩을 계산할 수 있습니다. 그러면 우리는 두 노드 사이의 매핑의 존재성 뿐만 아니라 두 노드가 동일한지도 확인할 수 있는거죠.
순서 임베딩 공간(Order Embedding Space)
임베딩을 통하여 서브그래프 여부를 판단하기 위해서 순서 임베딩 공간(order embedding space) 을 활용합니다. 어떤 그래프 $A$를 고차원 임베딩 공간의 $z_A$라는 점으로 매핑한다고 가정해보겠습니다. 이때 $z_A$가 모든 차원에서 음수가 아니면 우리는 partial ordering을 활용할 수 있습니다. 간단한 예제로 2차원 임베딩 공간에서 모든 임베딩이 모든 차원에서 음수가 아니라면 큰 그래프는 서브그래프보다 좌상단에 위치합니다. Partial ordering을 논할 때 만약 $a \preccurlyeq b$ 라면 $a$는 모든 차원에서 $b$보다 작거나 같은 값을 가집니다. 또한 이런 partial ordering으로 인해 전이성(transitivity)을 만족합니다.
\[a \preccurlyeq b \text{ and } b \preccurlyeq c \implies a \preccurlyeq c\]
위 그림에서 초록색 노드는 순서 임베딩 공간에서 모든 차원에 대해 작은 값을 갖지만 노란색 노드는 그렇지 않습니다. 따라서 query 1은 앵커 노드 $t$의 이웃의 서브그래프가 됩니다.
순서 임베딩 공간을 활용하는 이유는 이 공간에서 서브그래프 isomorphism 관계를 잘 나타낼 수 있기 때문입니다. 순서 임베딩 공간은 다음의 특징을 갖습니다.
- 전이성(Transitivity): 만약 $G_1$이 $G_2$의 서브그래프이고 $G_2$가 $G_3$의 서브그래프라면 $G_1$은 $G_3$의 서브그래프다.
- 반대칭성(Anti-symmetry): $G_1$이 $G_2$의 서브그래프이고 $G_2$가 $G_1$의 서브그래프라면 $G_1$은 $G_2$에 isomorphic하다.
- 교집합에 닫혀있음(Closure under intersection): 노드가 하나인 그래프는 모든 그래프의 서브그래프다.
Order constraint
우리는 GNN을 사용하여 이웃 노드를 임베딩하고 순서 임베딩 구조를 보존하도록 학습합니다. 그런데 여기에 사용하는 손실 함수는 어떤 것을 사용할까요? 여기서 사용할 손실 함수에서 가장 중요한건 순서 임베딩 구조를 보존하기 위한 제약 조건입니다. 우리는 순서 제약 조건(order constraint)을 설정하여 서브그래프의 성질이 순서 임베딩 공간에서 유지되도록 합니다.
Max-margin loss for GNN embeddings
GNN 임베딩은 최대 마진 손실 함수(max-margin loss) 를 최소화하도록 학습합니다. 이때 그래프 $G_q$와 $G_t$ 사이의 마진은 다음과 같이 정의합니다.
\[E(G_q, G_t) = \sum_{i=1}^D (\max(0, z_q[i] - z_t[i]))^2\]만약 어떤 $i$에 대해서 $z_q[i] > z_t[i]$ 라면 위 값은 0보다 커지고, 그 의미는 $G_q$가 $G_t$의 서브그래프가 아니란 뜻입니다.
- $G_q$가 $G_t$의 서브그래프일 때 $E(G_q, G_t) = 0$
- $G_q$가 $G_t$의 서브그래프가 아닐 때 $E(G_q, G_t) > 0$
뉴럴 서브그래프 매칭을 학습하기 위해서는 학습 데이터의 절반은 $G_q$가 $G_t$에 서브그래프인 데이터로, 나머지 절반은 서브그래프가 아닌 경우인 네거티브 데이터로 구성합니다.
$G_t$는 전체 데이터셋 $G$로부터 임의의 앵커 노드 $v$를 고르고 거리가 $K$인 모든 이웃 노드를 이용하여 구성합니다. 실제 서브그래프인 데이터는 $G_T$로부터 샘플링을 하는데 이때 BFS를 활용합니다.
- $S = \{ v \}, \; V = \emptyset$ 으로 초기화합니다.
- $N(S)$를 $S$의 모든 이웃 노드로 두고 매 단계마다 $N(S) \backslash V$에 있는 노드 중 10%를 샘플링하여 $S$에 넣습니다. 남은 노드는 $V$에 넣습니다.
- $K$ 단계 후에 앵커 노드 $q$로 만들어진 $S$ 기반의 서브그래프를 활용합니다.
네거티브 데이터는 $G_Q$로부터 노드나 엣지를를 추가하거나 제거하여 서브그래프가 아니도록 만들어서 사용합니다.
그리고 이 데이터를 이용하여 최대 마진 손실 함수를 최소화합니다. 네거티브 데이터에 대해서는 $\max(0, \alpha - E(G_q, G_t))$를 최소화하고 반대 경우에는 $E(G_q, G_t)$를 최소화합니다. 최대 마진 손실 함수는 임베딩을 점점 더 멀리 떨어뜨려 학습이 되는 현상을 방지할 수 있습니다.
학습 데이터는 매 반복마다 새로운 학습 데이터 쌍을 샘플링합니다. 그러면 매 반복마다 모델은 다른 서브그래프 예시를 참조하게 됩니다. 이 덕분에 성능도 좋아질 뿐만 아니라 오버피팅을 방지할 수 있습니다. BFS의 경우 그 깊이가 일종의 하이퍼파라미터가 됩니다. 깊게 탐색할 수록 성능은 좋아질 수 있지만 실행 시간이 길어집니다. 보통은 데이터셋에 따라서 설정하지만 일반적으론 3에서 5 정도로 설정합니다.
높은 빈도의 서브그래프 찾기
일반적으로 가장 빈도가 높은 $k$ 크기의 모티프를 찾는 문제는 다음 두 가지 어려운 포인트가 있습니다.
- $k$ 크기의 연결된 서브그래프를 나열하는 것
- 각 서브그래프 타입에서 발생 빈도를 세는 것
당장에 그래프에 특정 서브그래프가 존재하는지 확인하는 것만으로도 어려운 문제이기 때문에 위 두 포인트는 매우 어려운 문제가 됩니다. 실제로 서브그래프 isomorphism 문제는 NP-완전(NP-complete) 문제입니다. NP 집합에 속하는 결정 문제 중에서 가장 어려운 문제인거죠. 그리고 서브그래프의 크기가 증가할 수록 계산 시간은 기하급수적으로 증가합니다. 그래서 일반적으로 실현 가능한 모티프의 크기는 상대적으로 작습니다.
따라서 빈도 높은 서브그래프를 직접 셀 수는 없습니다. 조합 가능한 패턴의 수가 폭발적으로 늘어나고, 위에서 언급하였듯이 서브그래프 isomorphism 문제는 NP-완전이기 때문입니다. 하지만 여기에서 표현 학습(representation learning) 을 사용하면 이런 문제들을 조금 해결할 수 있습니다.
- $k$ 크기의 연결된 서브그래프를 나열하는 것
- 서브그래프를 다 셀 필요 없이 $k$ 크기의 서브그래프를 점진적으로 구성하면 됨
- 각 서브그래프 타입에서 발생 빈도를 세는 것
- 서브그래프의 빈도를 예측하기 위해 GNN을 사용
이제 이런 Frequent Motif Mining 문제를 해결하기 위해 다음의 설정을 합니다. 우선 타겟 그래프 $G_T$에 대해 서브그래프의 크기 $k$가 있습니다. 원하는 결과의 수는 $r$입니다. 우리가 원하는 것은 $k$개의 노드로 가능한 모든 그래프에서 $G_T$ 내에서 가장 빈도가 높은 $r$ 개의 그래프를 찾는 것입니다. 그래서 여기에서는 노드 레벨의 서브그래프 빈도 정의를 사용합니다.
SPMiner
SPMiner
SPMiner는 빈도 높은 모티프를 찾는 뉴럴 모델입니다. SPMiner는 $G_T$를 여러 서브그래프로 나눈 다음 각 서브그래프를 순서 임베딩 공간에 임베딩합니다. 순서 임베딩 공간에 임베딩하였기 때문에 서브그래프 $G_Q$의 빈도를 보다 빠르게 예측할 수 있게 됩니다.
$G_T$에서 앵커 노드의 이웃으로 구성된 서브그래프의 집합 $G_{N_i}$가 있을 때, 이 집합의 임베딩 $z_{N_i}$가 $z_Q \leq z_{N_i}$를 만족하는 $G_{N_i}$의 개수를 세서 $G_Q$ 의 빈도를 추정합니다. 순서 임베딩 공간이기 때문에 위 그림에서 빨간색으로 음영되어 있는 부분은 모두 $G_Q$를 포함하는 $G_T$의 서브그래프가 됩니다. 이런 서브그래프가 많을 수록 빈도 높은 모티프일 확률이 높겠죠.
SPMiner는 우선 $G_T$에서 시작 노드 $u$를 샘플링하는 것으로 시작합니다. 위 그림에서 음영 부분에 있는 점들은 모두 시작 노드를 포함하는 타겟 그래프의 서브그래프이기 때문에 거의 모든 서브그래프가 포함되어 있습니다.
이제 노드 $u$를 이웃 노드를 하나씩 추가하면서 음영 부분을 좁혀나갑니다. 이제 $k$ 단계 후에 음영된 부분에 들어가는 포인트의 수가 가장 많도록 해야 합니다.
원하는 크기의 모티프까지 도달했다면 작업을 종료합니다. 위 그림에선 크기가 12인 모티프에서 종료하였고, 위 그림에서 음영 부분에 있는 모든 서브그래프가 Step 12에 있는 모티프를 포함하고 있습니다.
각 단계에서 다음 노드를 정하는 방법은 서브그래프 $G$의 total violation을 사용합니다. $G$를 포함하지 않는 이웃의 수가 가장 적은 노드를 선택하는 것인데요. Total violation을 최소화하는 것은 빈도를 최대화하는 것과 똑같습니다. 이때 total violation의 계산은 탐욕 알고리즘(greedy algorithm)을 사용합니다.
실제 SPMiner는 전통적인 방식에 비해 실제 빈도 높은 모티프의 개수를 잘 추정합니다. 작은 모티프에 대한 실험 결과는 위 그림과 같습니다. 실제 큰 모티프에 대해서도 베이스라인 모델들보다 10배에서 100배 더 많은 모티프를 찾아냅니다.