Towards Scalable and Efficient Graph Structure Learning

In recent years, Graph Neural Networks (GNNs) have demonstrated remarkable capabilities in learning from graph-structured data. However, GNNs face challenges when dealing with imperfect graph structures, which often lead to performance degradation due to the underlying message propagation mechanism. In response to this issue, a class of data-centric techniques called Graph Structure Learning (GSL) has emerged, with a focus on improving the quality of graph structures. Our review of the existing GSL literature, combined with empirical studies, reveals two primary limitations: low scalability and low efficiency. To mitigate these limitations, we introduce Random Walk-based Graph Structure Learning (RWGSL), a new GSL method that utilizes random walk strategies and operates in a parameter-free manner. Extensive experiments demonstrate that Rwgsl consistently improves the classification performance of both vanilla GNNs and advanced GSL methods across various graph datasets, and Rwgsl can scale to extremely large graphs (e.g. Ogbn-Products) with acceptable time cost. In particular, the combination of Rwgsl and GCN significantly reduces the run time to approximately 5% of those observed in most GSL methods, while also achieving a superior classification accuracy. These findings validate the high scalability and robustness of Rwgsl.