Meaningful

Meaningful

Greeting :)

[그래프 AI]Graph Isomorphism Network(GIN)

Date:     Updated:

카테고리:

Graph Isomorphism Network(GIN)

What is the ‘Graph Isomorphism’?

1

Graph Isomorphism (그래프 동형)은 그래프 이론에서 두 개의 그래프가 노드 간의 연결 관계를 유지하면서 동일한 구조를 가지는지 판단하는 문제이다. 두 그래프가 Isomorphic하다는 것은 노드의 ordering차이로 인해 완전히 다르게 표현되지만 같은 구조를 가진다는 것을 말한다. 좀 더 수학적으로 접근하면, 두 그래프 \(G\)와 \(H\)가 있을 때, \(G\)를 \(H\)와 동일한 구조로 만들 수 있는 일대일 대응(mapping, bijection)이 존재한다면 두 그래프는 isomorphic하다고 한다.

그래프 동형 문제는 그래프의 구조적 동일성을 이해하는 데 중요하다. 예를 들어, 네트워크, 분자 구조, 소셜 네트워크 분석 등에서 구조적으로 유사한 객체를 찾는 것이 중요할 수 있다. 그래프 동형 문제의 계산 복잡도는 오랜 시간 동안 연구되어 왔으며, 현재까지도 P, NP, co-NP, NP-complete, NP-hard 등 어떤 복잡도 클래스에 속하는지 정확히 알려지지 않았다. (NP = Nondeterministic Polynomial time)

Weisfeiler-Lehman Test

Polynomial-time heuristic for the graph isomorphism problem.
Can (sometimes cannot) discriminates between two non-isomorphic graphs.
False positive may exists.

GIN은 위의 Weisfeiler-Lehman Test 사이의 유사성에 기반하여 만들어졌다. WN Test는 여러 종류의 Graph를 구별할 수 있는 효과적인 테스트 방법이다. GNN과 비슷하게, WN Test도 노드가 주어졌을 때, 이 노드의 이웃들의 feature를 벡터로 통합하여 node feature를 반복적으로 업데이트한다. WL Test의 경우 다른 노드의 이웃들을 다른 feature 벡터로 mapping하는 Injection Aggregation Update의 존재로 인해 강력한 효과를 지닌다.

1

예를 들어, 알라딘 서점과 스타벅스 커피는 사람 A의 이웃 Node이고, 이디야 커피는 사람 B의 이웃 노드라고 할 때, 사람 A와 B의 feature 벡터를 얻기 위해 GraphSAGE에서 제시한 Mean aggregation 과정을 진행해본다.

그렇다면 사람 A의 이웃 노드의 feature 벡터는 [0.5, 0.5, 0.5]가 될 것이고, 사람 B의 이웃 노드의 feature 벡터 또한 [0.5, 0.5, 0.5]가 될 것이다. 위 결과에 따르면 사람 A와 B의 이웃 feature 벡터는 똑 같은 형상을 하게 될 것이다. 이는 학습에 있어서 데이터 소실 혹은 왜곡이라는 문제로 귀결된다.

GIN 논문에서는 GNN의 Aggregation Scheme이 매우 expressive하고 그렇기에 Injective function을 모델링할 수 있다면 GNN 또한 WL Test처럼 강력한 Discriminative power를 지니게 될 것이라는 가정과 함께 시작한다.

GIN

GIN(Graph Isomorphism Network)은 그래프 데이터를 효과적으로 처리하기 위한 필요성에서 등장했다. 기존의 그래프 신경망, 특히 GCN이나 GraphSAGE는 그래프의 구조적 특성을 충분히 반영하지 못하거나, 그래프 동형성(graph isomorphism)을 잘 판별하지 못하는 한계가 있었다. 특히, 기존 GNN 모델들은 두 그래프가 동일한 구조를 가질 때 이를 잘 구별하지 못하는 문제가 있었다.

이러한 문제를 해결하기 위해, GIN은 그래프 동형성을 엄밀히 판단할 수 있는 능력을 강화한 모델로 제안되었다. GIN은 Weisfeiler-Lehman 그래프 동형성 테스트(Weisfeiler-Lehman test of isomorphism)와의 유사성을 바탕으로 설계되어, 그래프 구조를 더 정확하게 표현하고, 유사한 그래프를 구별하는 능력을 향상시키는 것을 목표로 한다.

1

1. GIN의 등장 배경

기존의 GNN 모델들은 그래프 데이터를 처리할 때 비동형(non-isomorphic) 그래프를 제대로 구별하지 못하는 문제가 있었다. 이는 GNN의 집계 함수(aggregation function)가 노드 이웃의 정보를 충분히 잘 포착하지 못해 발생하는 문제였다. 이러한 한계를 극복하기 위해 GIN은 그래프 동형성 테스트에서 사용되는 Weisfeiler-Lehman(WL) 테스트의 강력함을 반영한 구조로 설계되었다.

2. GIN의 구조와 작동 방식

GIN은 그래프의 노드 특징을 업데이트하는 과정을 통해 그래프의 표현을 학습한다. GIN은 집계 함수(Aggregation Function)로 sum을 사용한다. 노드의 특징을 갱신할 때 주변 노드의 특징을 합(sum)으로 집계한다. 기존 GNN 모델들이 평균(mean)이나 최대값(max)을 사용하여 집계할 때 발생하는 정보 손실 문제를 해결하기 위해, GIN은 노드 이웃의 전체 멀티셋(multiset)을 포착할 수 있도록 합(sum) 함수를 사용한다. 이는 그래프의 구조를 더 정확하게 반영할 수 있게 해준다.

GIN은 각 노드의 특징을 갱신할 때 다층 퍼셉트론(MLP, Multi-Layer Perceptron)을 사용한다. MLP는 충분히 큰 hidden dimensionality와 적절한 activation function을 갖는 1-hidden layer 구조로, 임의의 연속형 함수를 근사할 수 있다. 이로 인해 GIN은 그래프 구조의 복잡한 패턴을 효과적으로 학습할 수 있다.

1

  • 노드 특징 갱신 수식: GIN의 노드 특징 갱신 수식은 다음과 같다
$$h_v^{(k)} = \text{MLP}^{(k)}\left( (1 + \epsilon^{(k)}) \cdot h_v^{(k-1)} + \sum_{u \in \mathcal{N}(v)} h_u^{(k-1)} \right)$$
  • \(h_v^{(k)}\): k번째 레이어에서 노드 \(v\)의 특징 벡터
  • \(\mathcal{N}(v)\): 노드 \(v\)의 이웃 노드 집합
  • \(\text{MLP}^{(k)}\): k번째 레이어에서의 다층 퍼셉트론(Multi-Layer Perceptron)
  • \(\epsilon^{(k)}\): 학습 가능한 파라미터 또는 고정된 스칼라 값

1

GIN의 핵심 내용은 간단하다. 충분히 큰 Hidden Dimensionality와 적절한 activation function을 갖는 1-hidden layer MLP는 일정 수준의 정확도로 어떠한 연속형 함수도 근사할 수 있다는 것이 본 이론의 내용이다. 최초의 반복에서 만약 Input feature가 One-hot 인코딩이면 그들의 합 또한 Injective 할 것이기 때문에 sum 연산 이전에 MLP가 필요하지는 않다. 만약 one-hot 인코딩이 되어 있지 않거나 연속형 변수가 중간에 포함된다면 MLP가 필요하다.

3. GIN의 학습과 표현력

  • 초기 입력 특징이 One-hot 인코딩일 경우: 만약 입력 특징이 One-hot 인코딩이면, 노드의 특징 벡터들이 각기 다른 값을 가지게 되므로, 이 단계에서는 MLP가 필요하지 않다. 이는 노드의 특징이 고유한 벡터로 표현되기 때문이다.
  • 연속형 변수 포함 시: 입력이 연속형 변수이거나 One-hot 인코딩이 아닌 경우에는 MLP가 필요하다. MLP는 입력 특징을 적절히 변환하여 그래프의 복잡한 구조를 학습할 수 있게 해준다.

4. GIN의 장점

  • 그래프 표현의 강력함: GIN은 WL 테스트와 유사한 방식으로 그래프의 구조적 특징을 포착하여, 비동형 그래프를 효과적으로 구별할 수 있다.
  • 학습 유연성: 학습 가능한 파라미터 \(\epsilon^{(k)}\)를 도입하여, 각 레이어에서의 특징 업데이트를 더욱 유연하게 만들어 준다.
  • 다양한 그래프 구조 학습: GIN은 노드 이웃의 정보를 합(sum)으로 집계함으로써, 그래프 구조의 다양한 패턴을 효과적으로 학습할 수 있다.

따라서, GIN은 그래프 데이터의 복잡한 구조적 특성을 효과적으로 반영하고, 그래프 동형성 문제를 해결하는 데 강력한 성능을 발휘하는 모델로 평가된다.

Reference

Blog: Graph Isomorphism Networks 리뷰
GIN: How to Design the Most Powerful Graph Neural Network

Graph 카테고리 내 다른 글 보러가기

댓글 남기기

최근 글 10 개 :)