Sequential sampling for correlated graph sampling

Abstract

Graph Convolutional Networks(GCNs) are successful models for learning graph structures and representations. However, real-world graphs are extremely large with numerous nodes and edges. As computational complexity increases exponentially with the depth of the GCNs layer, learning such real-world graphs are expensive. To mitigate this, previous works propose sampling methods that utilize few nodes to aggregate neighbor information. These graph sampling methods assume that the sampled nodes are independent, but this is an incorrect assumption for real-world graphs, as they are heavily correlated. To address this problem, we propose a sequential sampling method inspired by Monte Carlo - Markov Chain algorithm. We conduct the experiments on graph benchmark dataset: Cora, Citeseer and Pumbed. Experimental results show that our proposed algorithm outperforms the previous sampling methods.