STARGCN: Graph Convolutional Networks on Hypergraphs for Semi-Supervised Classification

Abstract

A graph is a data structure for representing the relationships between objects. Many graph algorithms were proposed and applied to meaningful real-life applications. However, many real-world networks are complex and go beyond pairwise relationships. A hypergraph, on the other hand, is a data structure that could directly model the complex relationships in which multiple objects engage. In this thesis, we present a graph convolutional network for effective semi-supervised learning on hypergraphs, named STARGCN. Using a graph neural network on star expansion, our method represents both nodes and hyperedges of a given hypergraph as vectors. To realize our method, we propose the following two strategies: (1) employing a graph neural network on a bipartite graph and (2) combining topological loss to fully exploit the bipartite graph. Through extensive experiments using five real-world hypergraphs, we show that STARGCN outperforms state-of-the-art methods.|그래프(graph) 자료구조는 객체와 객체간 상호작용을 나타내는 자료구조이며, 이를 이용한 다양한 그래프 알고리즘들이 여러 분야에서 상용되고 있다. 그러나 그래프는 두개의 객체간의 상호작용만을 모델링 할 수 있어 여러 객체들이 작용하는 실세계의 복잡한 상호작용을 표현하는데에 한계가 있다. 반면, 하이퍼그래프(hypergraph)는 복잡한 관계를 직접 모델링할 수 있는 자료구조이다. 이에 본 연구에서는 하이퍼그래프에서의 효과적인 준지도 학습을 위한 그래프 합성곱 신경망 기법인 STARGCN를 제안한다. 제안하는 기법은 스타 확장법에서의 그래프 합성곱 신경망(graph convolutional network on star expansion)을 바탕으로 주어진 하이퍼그래프의 노드들을 낮은 차원의 벡터들로 변환하고 이를 바탕으로 노드들을 분류한다. 이를 위해 우리는 (1) 주어진 하이퍼그래프를 이분 그래프(bipartite graph)로 모델링하고, 모델링된 이분그래프를 GNN에 활용하는 전략, 그리고 (2) topological loss를 결합하는 전략을 제안한다. 우리는 STARGCN의 효과를 검증하기 위해 5개의 실세계 하이퍼그래프에서 폭넓은 실험을 수행한다. 그 결과 STARGCN이 기존 하이퍼그래프에서의 임베딩 기법들에 비해 우수한 성능을 보이는 것을 확인한다.