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.
그래프 컨볼루션 네트워크(GCN)은 그래프의 구조와 표현을 학습하는 성공적인 모델이다. 하지만, 실제세계의 그래프들은 수 많은 노드와 엣지를 가지고 있다. 따라서 그래프 컨볼루션 네트워크의 계산 복잡도는 모델의 레이어의 개수가 늘어남에 따라 기하급수적으로 증가한다. 이를 해결하기 위해서 일부의 노드만 사용해 이웃 노드의 정보를 배우는 그래프 샘플링 방법론들이 제시됐다. 이러한 그래프 샘플링 방법론들은 샘플된 노드들 이 서로 독립임을 가정하지만, 실제 세계의 그래프들은 샘플된 노드들 사이에 상관관계가 존재한다. 따라서 이를 반영하기 위해 우리는 몬테카를로 마르코프체인(MCMC) 방법론에서 영감을 얻은 순차적인 샘플링 방법 을 제시한다. 또한 그래프 벤치마크 데이터셋인 Cora, Citeseer, Pumbed 로 진행한 실험 결과를 통해 논문에서 제시한 방법론이 다른 샘플링 기법들과 비교했을때 우수하다는 점을 보인다.