[cs224w] Frequent Subgraph Mining with GNNs

 

1️⃣  12강 복습 

---

 

🔹 Main Topic : Subgraph Mining - Identifying and Counting Motfits in Networks 

 

• Subgraph 와 motifs 는 그래프 구조에 대한 인사이트를 얻게 해주는 요소이다. 

• 특정 그래프들 사이에서 Subgraph Isomorphism 관계에 있는지 예측하는 Task 에 대해 신경망을 활용한다. 

• Subgraph 관계를 판별하는 방법 : Order embedding 

 

 

🔹 Subgraph and Motifs

 

• Building Blocks of Networks → Subgraph (=Mofits) 는 네트워크의 function 이나 behavior 과 같은 요소를 결정한다. 이를 통해 그래프가 어떻게 작동하는지 알 수 있고, 그래프 형태에 따라 예측을 진행할 수 있다. 

 

     👉 특정 mofits 가 전체 그래프에서 얼마나 빈번하게 (recurring) 나타나는지, 얼마나 중요한지에 (significant) 집중 

 

 

mofits 은 우리가 특정하게 보고싶은 subgraph 형태를 의미

 

 

• Graph Isomorphism : 두 그래프가 주어졌을 때, identical 한지 판별하는 것 

 

 

• Subgraph Isomorphism : G1 과 G2 는 구조적으로 동일한 subgraph 부분이 존재한다. 

 

 

• Subgraph Frequency : subgraph 의 빈도를 세는 방식의 접근에는 Graph-level , Node-level, Multiple graphs 가 있다. 

 

   👉 Graph - level 

 

   👉 Node - level 

 

node anchor 를 기준으로 살펴봄

 

   👉 Multiple graphs

 

 

 

 

• Subgraph Significance : subgraph 의 중요도를 판단하기 위해, 랜덤하게 생성된 그래프 네트워크에서 mofit 빈도보다 real network 의 mofit 빈도가 더 많을 것이라는 가정을 도입해 실험한다. 

 

   👉 Random graph 를 생성하는 방법 : ER, Configuration model, Switching

   👉 실제 그래프와 랜덤하게 생성된 그래프에서 각 motif 가 얼마나 중요도를 가지는지 Z-score 를 사용해 평가한다. 

 

 

 

 

🔹 Subgraph Matching 

 

• Query 그래프가 Target 그래프의 subgraph isomorphism 인지 확인하는 Task → Use GNN and embedding space 

 

① node anchor 를 정의하여 임베딩을 비교 

 

 

 

② anchor node 의 주변 이웃 노드들을 살펴봄

n-hop 내에 있는 이웃노드들의 임베딩을 비교

 

 

• Order embedding Space : 임베딩 공간에서 두 그래프 중 하나가 다른 하나의 좌하단에 위치하면, 서브그래프라 볼 수 있다. 

 

 

  👉 Loss function : max-margin loss 

 

값이 0이면 Gq가 Gt 의 subgraph

 

 

 

🔹 Finding Frequent subgraphs

 

• 자주 등장하는 mofit 을 찾기 → Representation learning 을 통해 임베딩 공간 내에서 GNN 을 활용 

 

 

 

 

 

 

 

 

 

2️⃣  gSpan 

---

 

• algorithm for Mining frequent subgraphs 

• Supports undirected graphs

• DFS Lexicographic order : use lexicographic order (사전식 순서) embedding and explore depth-first search (DFS) method 

 

 

(b) and (d) are isomorphic

 

 

DFS 방법을 통해 subgraph 를 찾는 과정

 

 

• Using chemical compound datasets, it finds the common chemical compound substructures 

 

이전에 제안된 FSG 모델보다, gSpan 이 훨씬 더 빠른 속도를 보이고 있음