Rethinking Large-scale Graph Learning with Laplacian Kernel Machines

Graph-based semi-supervised learning (SSL) leverages the relational structure among samples to exploit both labeled and unlabeled data. Existing approaches differ in where the graph enters the learning problem. Among them, Laplacian Regularized Kernel Methods (LapKMs), which inject the graph as a regularizer on the predictor, are renowned for rigorous theory, yet have been overlooked for a long time due to the scalability bottleneck. This paper argues that the long-standing stagnation of LapKMs arises from an *optimization* gap rather than a model deficiency: the coupling of the kernel matrix and the graph Laplacian induces prohibitive computation and numerical instability. We propose LapTop, a **T**ractable **op**timization scheme for large-scale **Lap**KM, which reformulates LapKM via a tailored Alternating Direction Method of Multipliers (ADMM) and decouples it into two well-structured subproblems, i.e., graph Laplacian label smoothing and kernel ridge regression. Together with a memory-efficient block coordinate descent solver, LapTop trains *exact* kernel models on million-node graphs using a single consumer-grade GPU, and supports more diverse loss functions than the existing LapKMs. Experiments on six large-scale benchmarks show that LapTop ranks within the top three against strong graph neural network (GNN) and graph Transformer baselines on all datasets, with less than half the memory of the strongest baseline. Our results call for a re-examination of LapKMs as a principled complement to deep graph learning.