GRAHIES: Multi-scale graph representation learning with latent hierarchical structure

Abstract

A wide variety of deep neural network models for graph-structured data have been proposed to solve tasks like node/graph classification and link prediction. By effectively learning low-dimensional embeddings of graph nodes, they have shown state-of-the-art performance. However, most existing models learn node embeddings by exploring flat information propagation across the edges within the local neighborhood of each node. We argue that incorporating hierarchical node embeddings can capture the inherently hierarchical topological features of many realistic graphs such as social networks, biological network and World Wide Web. In this paper we propose GRAHIES, a general framework for graph neural networks to learn node representations that preserve hierarchical graph information at higher-orders. GRAHIES adaptively learns a multi-level hierarchical structure of the input graph, which consists of successively coarser (smaller) graphs that preserve the global structure of the original graphs at different levels. By combining the graph representations from different levels of the graph hierarchy, the final node representation captures the inherent global hierarchical structure of the original graph. Our experiments show that applying GRAHIES's hierarchical paradigm yields improved accuracy for existing graph neural networks on the node classification tasks.