대규모 그래프 노드 분류를 위한 효율적이고 확장 가능한 그래랕 볼(Granular-ball) 그래프 축소 방법

Efficient and Scalable Granular-ball Graph Coarsening Method for Large-scale Graph Node Classification

그래프 컨볼루션 네트워크(GCN)는 그래프 데이터 작업에 효과적으로 적용될 수 있는 모델로, 성공적으로 활용되어 왔습니다. 그러나 대규모 그래프 데이터셋의 경우, 특히 그래프 내 컨볼루션 레이어 수가 많은 경우, GCN은 여전히 높은 계산 비용이라는 과제를 안고 있습니다. 현재, 이러한 문제점을 완화하기 위해 다양한 샘플링 기법 또는 그래프 축소 기법을 사용하는 고급 방법들이 많이 개발되었습니다. 그러나 이러한 방법 중 일부는 그래프 구조 내의 다중-레벨 정보를 고려하지 않으며, 일부 축소 방법의 시간 복잡도는 여전히 상대적으로 높습니다. 이러한 문제점들을 해결하기 위해, 본 논문에서는 기존 연구를 바탕으로, 대규모 그래프 노드 분류를 위한 효율적이고 확장 가능한 그래랕 볼 그래프 축소 방법이라는 새로운 프레임워크를 제안합니다. 구체적으로, 이 방법은 먼저 다중-레벨 그래랕 볼 그래프 축소 알고리즘을 사용하여 원래 그래프를 축소하고, 여러 개의 부분 그래프를 얻습니다. 이 단계의 시간 복잡도는 선형이며, 기존 그래프 축소 방법보다 훨씬 낮습니다. 그런 다음, 이러한 그래랕 볼로 구성된 부분 그래프를 무작위로 샘플링하여 GCN 학습을 위한 미니배치를 구성합니다. 제안하는 알고리즘은 원래 그래프의 규모를 적응적으로 크게 줄여 GCN의 학습 효율성과 확장성을 향상시킵니다. 마지막으로, 여러 데이터셋에 대한 노드 분류 실험 결과는 본 논문에서 제안하는 방법이 우수한 성능을 보임을 입증합니다. 코드 및 관련 정보는 https://anonymous.4open.science/r/1-141D/ 에서 확인할 수 있습니다.

Graph Convolutional Network (GCN) is a model that can effectively handle graph data tasks and has been successfully applied. However, for large-scale graph datasets, GCN still faces the challenge of high computational overhead, especially when the number of convolutional layers in the graph is large. Currently, there are many advanced methods that use various sampling techniques or graph coarsening techniques to alleviate the inconvenience caused during training. However, among these methods, some ignore the multi-granularity information in the graph structure, and the time complexity of some coarsening methods is still relatively high. In response to these issues, based on our previous work, in this paper, we propose a new framework called Efficient and Scalable Granular-ball Graph Coarsening Method for Large-scale Graph Node Classification. Specifically, this method first uses a multi-granularity granular-ball graph coarsening algorithm to coarsen the original graph to obtain many subgraphs. The time complexity of this stage is linear and much lower than that of the exiting graph coarsening methods. Then, subgraphs composed of these granular-balls are randomly sampled to form minibatches for training GCN. Our algorithm can adaptively and significantly reduce the scale of the original graph, thereby enhancing the training efficiency and scalability of GCN. Ultimately, the experimental results of node classification on multiple datasets demonstrate that the method proposed in this paper exhibits superior performance. The code is available at https://anonymous.4open.science/r/1-141D/.