Adaptive Graph Coarsening for Efficient GNN Training
This addresses scalability issues in GNN training for large real-world graphs, offering a novel approach that adapts to learning tasks rather than relying on preprocessing, though it is incremental in combining existing techniques like clustering with GNN training.
The paper tackles the challenge of training graph neural networks (GNNs) on large graphs by proposing an adaptive graph coarsening method that merges nodes via K-means clustering during training, achieving improved efficiency and adaptability, particularly for heterophilic data, as validated on node classification datasets.
We propose an adaptive graph coarsening method to jointly learn graph neural network (GNN) parameters and merge nodes via K-means clustering during training. As real-world graphs grow larger, processing them directly becomes increasingly challenging and sometimes infeasible. Tailoring algorithms to large-scale data may sacrifice performance, so we instead consider graph reduction to decrease the amount of data used during training. In particular, we propose a method to simultaneously train a GNN and coarsen its graph by partitioning nodes via K-means clustering based on their embeddings. Unlike past graph coarsening works, our approach allows us to merge nodes during training. Not only does this preclude coarsening as a preprocessing step, but our node clusters can adapt to the learning task instead of relying solely on graph connectivity and features. Thus, our method is amenable to scenarios that are challenging for other methods, such as heterophilic data. We validate our approach on both homophilic and heterophilic node classification datasets. We further visualize relationships between node embeddings and their corresponding clusters to illustrate that our coarsened graph adapts to the learning task during training.