GIN : How Powerful GNN ? (2019)
WHY GNN IS BETTER THAN WL?
K-dimensional Weisfeiler-Lehman Alogrithm 은 의 coloring 을 반복적으로 수행한 것을 의미하며, 1-dimensional WL alogrithm 은 CR(Color Refinement) 를 의미한다. 복합적인 확경에서 발생하는 문제를 제외하고, 그래프 동형 문제를 푸는데 효율적인 방법이며, LINK PREDICTION 문제에 처음 적용된 딥러닝 방법론이다.
graph coloring 문제는 NP-Hard 한 문제이며, 이는 다항시간 안에 계산할 수 없음을 의미한다.
1-dimensional WL Algorithm
1차원의 WL 알고리즘은 Naive Vertex Refinement 또는 Color Refinement, Naive Vertex Classification 이라고 불린다. 몇번의 반복 끝에, 두 그래프의 노드 LABEL 이 다를 경우, non-isomorphic 하다고 결정할 수 있다. 하지만, 그래프의 동형성을 결정하는 도구 중 하나로 사용할 뿐 유일한 방법은 아니다.
GNN 은 Node 별 Vector Embedding 을 출력 결과로 내놓는다. 또한 GNN 은 서로 다른 그래프를 다른 임베딩 차원에 표현할 수 있는 능력을 가지고 있다. 즉, 그래프 동형 문제를 해결할 수 있따는 의미를 나타낸다. 따라서 본 논문에서는 GNN 을 Weisfeiler-Lehman(WL) graph isomorphism test 보다 강하다고 말한다.
Graph Isomorphism
(정리) A 는 GNN 이며 A 는 그래프를 d 차원의 벡터로 매핑을 수행할때, WL test 가 그래프가 동형이 아니라고 판단한 것을 아니라고 판단한다. 제약조건은 다음과 같다.
neighbour aggregation : GNN 은 이웃한 노드의 정보를 모으고 이 정보와 자신의 이전상태를 기반으로 자신을 업데이트 한다. 이를 수식으로 나타내면 다음과 같다. 이웃한 노드의 정보들은 중복을 허용하며, 매핑할 때는 일대일 함수 (단사함수)하여야 한다. 일대일함수란, 집합 X 의 임의의 원소 일때, 가 다르다는 것을 의미하며, 일대일 대응은 일대일 함수의 의미를 더해 공역과 치역이 같을 때를 의미한다. 여기서는 일대일 함수이다.
graph-level readout functions : 모든 노드의 피처들을 구해진 다음에 SUM 혹은 MEAN 을 통해서 Node의 임베딩을 합치는 것을 의미하며 이 또한 일대일 함이어야 한다.
GIN (Graph Isomorphism Network)
GIN 은 일대일 함수(injective) 를 찾았다. 다음이 일대일함수라는 것은 논문 Appendix 에 있는 증명을 찾아본다.
따라서 위 함수가 일대일 함수로 증명이 되었기 때문에 다음 식은 permutation invariant 하다. 즉, permutation (순서) 즉 벡터의 순서와 상관없이 같은 값이 출력된다.
따라서, 우리는 신경망을 사용하여 을 학습한다. 그리하면, GIN 은 노드를 다음과 같이 업데이트 한다.
f는 압축하는 함수이다. 원핫 벡터 또는 N-digit으로 표현된 수보다 더 작다.
Universal Approximation Theorem 이란 1개의 Layer 를 가진 Neural Network 로 어떠한 함수도 근사시킬 수 있다는 것이다.
Last updated
