H₂C₂GCN: Heterogeneous and Hierarchical Cross-Context Graph Convolution Network

Abstract

Given attributed graphs, how can we accurately classify them using both topological structures and node features? Graph classification is a crucial task in data mining, especially in the bioinformatics domain where a chemical compound is represented as a graph of attributed compounds. Although there are existing methods like graph kernels or truncated random walks for graph classification, they do not give good accuracy since they consider features present at a single resolution, i.e., nodes or subgraphs. Such single resolution features result in a biased view of the graph's context, which is nearsighted or too wide, failing to capture comprehensive properties of each graph. In this paper, we propose H₂C₂GCN (Heterogeneous and Hierarchical Cross-context Graph Convolution Network), an accurate end-to-end framework for graph classification. Given multiple input graphs, H₂C₂GCN generates a multi-resolution tree that connects the given graphs by cross-context edges. It gives a unified view of multiple graphs considering both node features and topological structures. We propose a novel hierarchical graph convolutional network to extract the representation of each graph. Extensive experiments on real-world datasets show that H₂C₂GCN provides the state-of-the-art accuracy for graph classification.

어떻게 구조적 특성과 노드의 레이블을 활용하여 속성 그래프를 분류 할 수 있을까? 그래프 분류는 데이터 마이닝 분야에서 중대한 과제로 여겨진다, 특히나 생물 정보 영역에서 화학 물질들이 속성 그래프로 표현되어 있는 경우에는 더욱 중요하다. 그러나 기존 연구들은 그래프 커널 방식이나 무작위 행보 방식을 사용하여, 그래프 내에 하나의 해상도 (노드 또는 부분그래프) 에 한정되어서 특징들을 고려한다. 이와 같이 하나의 해상도에 집중하여 특징을 고려할 경우 그래프 전체에 대한 편향된 시선으로 바라볼 수밖에 없다. 즉, 그래프들에 대하여 좁게 또는 넓게 바라보므로 그래프 간의 특징을 구분하는데 큰 어려움이 있다.

이 논문에서는 그래프 분류에 종단 간 학습이 가능한 H₂C₂GCN (Heterogeneous and Hierarchical Cross-context Graph Convolution Network)를 제안한다. 다수의 속성 그래프가 주어졌을 시, H₂C₂GCN는 다수의 해상도를 지닌 교차 문맥 간선이 이어진 트리를 만든다. 이를 통하여 다수의 그래프 간의 노드 레이블 및 구조적 특성의 견해를 담을 수 있다. 만들어진 트리에서 그래프 합성곱 신경망을 사용하여 하여 각 그래프의 임베딩을 추출하게 된다. 실험을 생물 정보 데이터에 대하여 평가를 하여 H₂C₂GCN가 기존 방법들에 비하여 높은 정확도를 가지는 것을 확인할 수 있다.