- Rating
- 2
- Confidence
- 2
- Informativeness
- 3
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper revisits Laplacian Regularized Kernel Methods (LapKMs) for large-scale graphs. The authors propose LAPTOP, which uses ADMM to decompose LapKM into graph label smoothing and kernel ridge regression subproblems, together with Newton/APGD and block coordinate descent solvers to reduce memory usage. Experiments are conducted on six large-scale node classification datasets with four loss functions, reporting predictive performance, memory usage, training time, and inductive prediction results.
Critical strengths
-
A practically useful optimization framework for large-scale LapKM.
LAPTOP decouples the kernel matrix and graph Laplacian and retains a full kernel model without explicitly storing the full kernel matrix. Table 2 reports training on approximately 2.45 million nodes in Products with a peak GPU memory usage of 10.1 GB, showing that the method brings classical LapKM to a modern large-scale graph setting.
-
Broad experiments with competitive results.
The experiments cover six large-scale datasets, multiclass and multilabel tasks, and four loss functions. LAPTOP ranks among the top three on multiple datasets in Table 1, and the paper includes graph-regularization ablations, inductive prediction results, and convergence analyses. The authors also discuss the homophily assumption and limitations on heterophilous graphs.
Critical weaknesses
-
The background and related-work discussion is somewhat lengthy.
The Introduction and Related Work provide extensive background on the three graph-learning paradigms and large-scale kernel methods, some of which could be moved to the appendix. I suggest shortening this material and using the main-text space for the method intuition, experimental setup, and main results.
-
The baseline comparisons and ablations remain incomplete.
LAPTOP is tuned with a grid search, whereas some GNN/GT baselines use default configurations, and the experiments do not include simple graph-smoothing methods such as Correct and Smooth. Thus, the competitiveness claim in Table 1 would benefit from more fairly tuned baselines. It would also be useful to report results for different numbers of Nyström landmarks, in order to distinguish the contribution of the full kernel expansion from that of generic graph smoothing.
Questions for authors
-
Could the authors include fairly tuned strong GNN baselines and a simple feature predictor combined with Correct and Smooth or an equivalent graph-smoothing method? This would help clarify LAPTOP's competitiveness and additional value.
-
Could the authors report performance, runtime, memory usage, and optimization residuals for different numbers of Nyström landmarks? This would help separate the effects of low-rank representation, optimization accuracy, and hyperparameter selection.
Response to Reviewer tWsk
We thank you for recognizing the practical value of full-expansion LapKM and for suggesting more controlled baselines and a closer analysis of Nyström approximation. We have revised the paper accordingly and address each point below.
W1: Lengthy Introduction and Related Work
We condensed the three-paradigm background and large-scale kernel review while retaining the taxonomy needed to position LapTop. The released space is used for the new controlled baselines, efficiency measurements, and full-expansion analysis.
W2: Baseline Fairness and Missing C&S
We added the requested comparisons and detail the protocol and results in Q1.
W3: Incomplete Nyström Ablation
We completed the requested Nyström landmark ablation and report the accuracy, residual, runtime, and memory results in Q2.
Q1: Fairly Tuned GNNs and Feature Predictor + C&S
We added tuned GraphSAGE and two-stage MLP+C&S and KRR+C&S baselines. For these new baseline runs, we use the same raw features and splits, fixed search configurations, and validation-only selection. All final baseline results use five seeds.
LapTop outperforms both C&S variants and tuned GraphSAGE on all four multiclass datasets. These controlled comparisons show the additional value of joint graph-regularized training over post-hoc smoothing. The full comparison is provided in Table 1 of the updated manuscript.
Q2: Performance, Runtime, Memory, and Residuals across Nyström Landmarks
Figure 3 of the revised paper reports accuracy, PCG residual, runtime, and memory for Flickr (s=1000,4000,10000,22000) and Products (s=1000,4000,8000,12000). For each dataset, validation selection is performed at a fixed landmark count; the sweep then varies s with the selected model hyperparameters and PCG budget fixed. The sweep directly supports the value of full expansion. More landmarks improve accuracy on Products, but a large gap remains; on Flickr, accuracy decreases as s grows despite small PCG residuals. Meanwhile, the largest landmark models consume more memory than full expansion, although Nyström remains faster.
These results distinguish numerical accuracy within the approximate solver from closeness to the full LapKM optimum. The Nyström predictor remains restricted to the landmark span, so reducing PCG error cannot recover components outside that subspace. One possible explanation is that graph regularization uses kernel directions that are poorly represented by the landmark span; testing this spectral-alignment hypothesis is an interesting direction for future work.
The sweep therefore provides direct evidence for LapTop's design: retaining the full representer expansion preserves useful predictive components that a generic landmark subspace may miss, while LapTop makes this expansion tractable at scale.