Graph Sampling for Scalable and Expressive Graph Neural Networks on Homophilic Graphs
This addresses scalability issues for GNNs on large homophilic graphs, but it is incremental as it builds on existing transferability methods.
The paper tackled the problem of GNN scalability by proposing a graph sampling algorithm that leverages feature homophily to preserve graph structure, resulting in improved performance in preserving Laplacian trace and GNN transferability compared to random sampling on citation networks.
Graph Neural Networks (GNNs) excel in many graph machine learning tasks but face challenges when scaling to large networks. GNN transferability allows training on smaller graphs and applying the model to larger ones, but existing methods often rely on random subsampling, leading to disconnected subgraphs and reduced model expressivity. We propose a novel graph sampling algorithm that leverages feature homophily to preserve graph structure. By minimizing the trace of the data correlation matrix, our method better preserves the graph Laplacian trace -- a proxy for the graph connectivity -- than random sampling, while achieving lower complexity than spectral methods. Experiments on citation networks show improved performance in preserving Laplacian trace and GNN transferability compared to random sampling.