[딥러닝 with Python] GIN 알아보기(Graph Isomorphism Network)

 

이번에는 기존에 알아본 GNN개념과 더불어 GIN이라는 방법론에 대해서 알아보고자 합니다.

[개념정리] 그래프 신경망(Graph Neural Network / GNN) (1)

[개념정리] 그래프 신경망(Graph Neural Network / GNN) (1)

[개념정리] 그래프 신경망(Graph Neural Network / GNN) (2)

[개념정리] 그래프 신경망(Graph Neural Network / GNN) (2)

[개념정리] 그래프 신경망(Graph Neural Network / GNN) (3)

[개념정리] 그래프 신경망(Graph Neural Network / GNN) (3)

[개념정리] Graph SAGE란? Graph SAmple & aggreGatE)

[개념정리] Graph SAGE란? Graph SAmple & aggreGatE)

 

 

 

Graph Neural Network(GNN)는 그래프 구조 데이터를 처리하는 강력한 신경망 모델입니다. (서로 다른 그래프를 구분하는 Graph Classification에 효과적인 모델입니다)

 

그러나 대부분 초기 GNN 모델들은 그래프의 동형성(Graph Isomorphism)을 효과적으로 구분하는 능력이 부족하여 정보 손실이 발생할 수 있는데요

 

이에 착안하여 나온 모델이 Graph Isomorphism Network, GIN입니다. 

 

GIN은 Weisfelier-Lehman Gaph Isomorphism Test(WL Test)와 밀접한 연관을 가진 모델인데요.

 

이번 포스팅에서는 GIN이 무엇인지에 대해서 알아보고자합니다.

 

 

[이번 포스팅은 GIN을 제안한 논문 " HOW POWERFUL ARE GRAPH NEURAL NETWORKS? "( Keyulu Xu et al, ICLR 2019)을 바탕으로 작성했습니다.]

 

1. GIN이란? 

- GIN은 WL Test의 아이디어를 신경망 구조로 변형하여 그래프의 표현 학습(Representation Learning)을 강화한 모델입니다.

 

- 기존의 GNN들은 가중합(Weighted Sum)을 통해 노드의 특성을 업데이트하지만, 이 방식은 그래프의 동형성(Isomorphism)을 충분히 반영하지 못하는데요.

 

 

 

1) 그래프의 동형성(Graph Isomorphism)

- 그래프의 동형성이란, 단순히 노드의 이름이나 라벨이 다를 뿐, 구조적으로 동일한 그래프라는 것을 의미하는 용어입니다.

 

- 즉, 두 그래프 G1과 G2가 동형이라면, 노드들 간의 연결 관계가 동일하며 노드의 이름을 변경해도 두 그래프의 형상이 변하지 않는 것을 의미합니다. 이를 수식적으로 정리해보면 아래와 같습니다.

 * 여기서 정점은 Node(또는 Vertex)와 같은 말입니다.

 

- 즉, Node 간의 연결 관계(Adjacency Structure)가 보존되어야 두 그래프가 동형이다라고 할 수 있는 것입니다. 아래 그림의 Graph1과 2는 동형(Isomorphic) / 3과 4는 비동형(Non-Isomorphic)의 예제를 시각화 해본 것입니다.

 

 

 

2) 그래프의 동형성 판별을 위한 WL Test

- 두 그래프가 동형인지 아닌지를 판별하기 위한 대표적인 방법은 WL Test입니다.

 

- WL Test는 그래프의 노드 정보를 반복적으로 업데이트하면서 그래프의 구조를 판별하는 방법을 말합니다. 

 

- WL Test의 핵심 아이디어는 각 노드의 이웃 정보(Neighborhood Information)를 기반으로 새로운 레이블을 생성하면서 점진적으로 그래프의 구조를 판별한다는 것입니다. 이를 단계별로 표현해보면 다음과 같습니다.

 

- 이를 수식적으로 표현해보면 다음과 같습니다.

 

 

- 즉, 이 과정을 거치면서 전달과정이 반복될수록 그래프의 구조적인 차이가 발생하게 됩니다.

 

 

 

 

3) 기존 GNN의 Node 업데이트 방식의 문제점 : 동형성 파악 문제

 

 

- 그렇다면 왜 이러한 아이디어를 생각하게 되었을까요? 그건 바로 기존의 GNN에서 노드를 업데이트할때 사용되는 Aggregation함수의 표현력이 부족하기 때문입니다. 보통 Sum, Mean, Max 를 사용해서 주변 노드들의 업데이트 된 정보들을 Aggregation하는데요. 

 

 

* 위 그림에서 보듯 Sum Aggregator는 모든 정보를 유지하는데 셋 중에서 가장 뛰어난 표현력을 가지지만 mean이나 max는 정보가 더 축약되고 소실되어 서로 다른 그래프를 구분하는데 뛰어나지 못합니다. 이는 아래 그림을 보면 더 확실하게 알 수 있는데요

 

 

*  위 그림에서 보는 것처럼 서로 다른 그래프이지만, a)는 Mean과 Max의 경우 v와 v'에 대한 노드 업데이트 시 서로 다른 두 그래프의 차이를 보이지 못하고, b) Max의 경우에도 빨간색만 택하기에 차이가 없으며, c) 의 경우에도 mean과 max 모두 차이를 보이지 못합니다.

 

 

 

4) GIN

 

- GIN은 위에서 알아본 WL Test를 활용해 기존 GNN의 노드 업데이트 문제에 대한 새로운 해법을 제안하는 방법론입니다.

 

- WL Test에서 Hash 함수를 통해 그래프의 동형성을 구분한 것에서 착안하여, GIN에서는 이 개념을 차용한 Sum Aggregation 후 MLP 라는 방법으로 노드의 정보를 업데이트합니다.

 

- 즉, WL Test가 그래프의 서브트리 구조를 구별하는 방식이 GIN의 동작 원리와 일맥상통하다고 볼수 있으며, 이를 통해 그래프의 동형성을 잘 판별할 수 있게 됩니다. 

 

- GIN의 노드 업데이트 공식은 다음과 같습니다.

 

 

- 이를 통해서 GIN은 기존 GNN과는 다르게

1) Sum Aggregation과 MLP를 통해서 단순 가중합이 아닌 직접적인 특성 합산을 통해 정보 손실을 방지하고

2) 기존 GNN이 선형 변환 이후 활성화함수(ReLU등)을 활용하였지만, GIN은 MLP를 활용해 보다 풍부한 비선형 변환을 가능하게 했고

3) WL Test의 개념을 가져왔기에, 그래프의 동형성을 효과적으로 구별할 수 있습니다.

 

 

 

 

2. GIN을 통한 Graph Classification

- 이러한 동형성을 파악하는 능력 덕분에 GIN은 Graph Classification에서 다른 GNN(GCN, Graph SAGE 등)보다 우수한 능력을 발휘할 수 있는 가능성이 있습니다.

 

 

 

- 아래 결과는 각 데이터셋에 대한 Baseline 및 GIN의 Graph Classification에 대한 결과 입니다. 

 

 

사용된 데이터 셋은 아래와 같습니다.

 

✔ IMDB-B, IMDB-M → 소셜 네트워크 데이터셋 (노드: 영화, 엣지: 배우 간 연결)
✔ RDT-B, RDT-M5K → 레딧(Reddit) 데이터셋 (노드: 포스트, 엣지: 상호작용)
✔ COLLAB → 협업 네트워크 데이터셋
✔ MUTAG, PROTEINS, PTC, NCI1 → 화학 및 생물학적 그래프 데이터셋 (노드: 원자, 단백질 등)

 

 

( 여기서 GIN은 Sum-MLP로 표현되며 이는 GIN에서 Sum으로 이웃 노드들의 특성을 모두 더해서 Aggregation한 뒤 MLP를 통해 비선형 변환을 수행하기 때문에 이렇게 명명되었습니다)

 

 

- 결과적으로 해당 데이터셋에 대해서 기존의 GCN이나 GAT보다 강력한 그래프 분류 능력을 보여주었다고 볼 수 있습니다.