Generalization of Graph Neural Networks through the Lens of Probabilistic Inference

Abstract

Graph Neural Network (GNN) is an effective framework for representation learning of graphs. However, despite GNNs revolutionizing graph representation learning, there is limited understanding of their generalization performance. Graph Neural Network (GNN) can process various graph structures where each graph has different connectivity but explaining how GNN generalize across out-of-distribution inputs is still challenging. In this thesis, we deal with the problem of computing marginal probabilities given a probabilistic graphical models. We assume that underlying graph structure of training data plays a key role in extrapolation to out-of-distribution inputs. For experiment, we vary graph size, topology and interaction strength between nodes in training data to see how they affect generalization performance of GNN. We find that (1) GNN trained on a fixed size and various graph structure generalizes to graph sets which determined by graph properties, especially unique degree distribution of training data; (2) even if the size of graph is different, it is not a fundamental limiting factor in generalization of GNNs when the average node degree remains invariant across training and test distributions; (3) despite the size-invariant generalization, training GNNs on graphs of high degree (and of large size consequently) is not trivial; thus additional operations such as skip-connection and attention mechanisms are required for the ease of training. (4) neural inference by GNNs outperforms algorithmic inferences especially when the pairwise potentials are strong, which naturally makes the inference problem harder.| 그래프 신경망(Graph Neural Network)은 그래프의 표현 학습을 위한 효과적인 프레임워크이다. 그러나 그래프 신경망이 그래프 표현 학습을 혁신했음에도 불구하고 일반화 성능에 대한 이해는 제한적이다. 그래프 신경망은 서로 다른 연결성을 갖는 다양한 그래프 구조를 처리할 수 있지만, 그래프 신경망이 학습 분포 외 입력에서 일반화하는 방법을 설명하는 것은 여전히 어려운 문제이다. 본 학위논문은 주어진 확률 그래프 모델에 대해서 marginal probability를 계산하는 문제를 다루며, 학습 데이터의 기본 그래프 구조가 분포 외 입력에 대한 일반화에 중요한 역할을 한다고 가정했다. 학습 데이터의 그래프 구조가 그래프 신경망의 일반화 성능에 어떤 영향을 미치는지 보기 위해 학습 데이터의 그래프 크기, 위상 및 상호 작용 강도를 변화시킨다. 본 학위논문은 실험을 통해 중요한 실험적 결과를 확인하였다. (1) 고정된 크기와 다양한 그래프 구조에 대해 훈련된 그래프 신경망이 그래프 구조적 특성, 특히 학습 데이터의 평균 unique degree distribution에 의해 결정되는 그래프 집합에 일반화가 용이하다는 것을 발견했다. (2) 그래프의 크기가 다르더라도, 학습 및 테스트 데이터의 평균 unique degree distribution이 유사하다면 그래프 신경망 일반화의 근본적인 제한 인자가 아니다. (3) 크기 불변 일반화에도 불구하고, 높은 차수를 가지는 그래프(그리고 결과적으로 큰 크기의) 대한 그래프 신경망 학습은 용이하지 않다. 훈련의 용이성을 위해 skip-connection 및 attention 메커니즘과 같은 추가적인 연산이 필요하다. (4) 그래프 신경망에 의한 추론은 특히 pairwise potential이 강할 때 알고리즘 추론을 능가하며, 이는 알고리즘에 의한 추론 문제를 더 어렵게 만든다.