acceptodds
Under review as a conference paper at ICLR 2027

Rethinking Large-scale Graph Learning with Laplacian Kernel Machines

Abstract

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.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Kernel methods, ADMM, Optimization, Graph Learning

Reviews

Among:
Shape:
1234this paper, Bottom 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.25 over 4 reviews, above 49% of the others.
Reviewer_tWskOpenReview ↗
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
  1. 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.

  2. 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
  1. 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.

  2. 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
  1. 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.

  2. 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.

1 comment
AuthorsOpenReview ↗

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.

DatasetLapTopMLP+C&SKRR+C&SGraphSAGE
Flickr53.3952.8351.5353.07
Products80.5680.1379.3578.29
Arxiv71.7570.3668.1971.58
Reddit95.9095.0993.2695.88

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,22000s=1000,4000,10000,22000) and Products (s=1000,4000,8000,12000s=1000,4000,8000,12000). For each dataset, validation selection is performed at a fixed landmark count; the sweep then varies ss 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 ss 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.

Reviewer_hraNOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

LAPTOP scales Laplacian Regularized Kernel Methods using the ADMM. Introducing u = Kα separates graph Laplacian label smoothing from kernel ridge regression. Block coordinate descent and truncated CG avoid storing the full kernel matrix while keeping the full representer expansion. Experiments compare several loss functions on six large graphs with graph-removal ablations and inductive inference tests.

Critical strengths
  1. The scalability result is significant. This paper provides a useful quality/resource trade-off.
  2. The ablation is clear. The graph-free comparisons keep the kernel and search space aligned. The inductive experiment applies the same smoothing to plain KRR and LAPTOP, helping separate training benefits from inference-time graph access.
Critical weaknesses
  1. The efficiency advantage over sampling-based GNNs is unclear. Table 1 includes GraphSAGE and GraphSAINT, but Table 2 omits their training time and peak memory. A comparison under the same hardware and comparable tuning budgets, including time to reach a common validation target, would help establish LAPTOP’s practical advantage over these scalable baselines.
  2. It lacks comparison with Correct and Smooth https://arxiv.org/abs/2010.13993
Questions for authors
  1. Can you compare with tuned GraphSAGE and Correct and Smooth under the same budget, separating training from selection cost?
1 comment
AuthorsOpenReview ↗

Response to Reviewer hraN

We thank you for highlighting the practical accuracy–resource trade-off and for encouraging a clearer comparison with tuned GraphSAGE and Correct & Smooth, including selection costs. We have revised the paper accordingly and address each point below.

W1: Efficiency Relative to Sampling-based GNNs

Table 2 now includes tuned GraphSAGE under the same hardware and profiling convention. On Products, LapTop achieves 80.56 accuracy with 10.1GB peak training memory, compared with 78.29 and 12.3GB for GraphSAGE. This gives LapTop a +2.27-point accuracy gain with 18% less memory, while retaining full-graph regularization without neighbor sampling. GraphSAGE remains faster to train (32 versus 173min), so the comparison identifies a clear accuracy–memory advantage rather than a uniform speed advantage. Polynormer reaches 83.82, but LapTop uses less than half its memory (10.1 versus 22.1GB) and trains in 173 rather than 443min.

W2: Missing Correct and Smooth Comparison

We added both MLP+C&S and KRR+C&S. LapTop outperforms both on all four multiclass datasets: Flickr 53.39 versus 52.83/51.53; Products 80.56 versus 80.13/79.35; Arxiv 71.75 versus 70.36/68.19; Reddit 95.90 versus 95.09/93.26. These results provide direct evidence for the value of joint graph-regularized training beyond post-hoc smoothing.

Q1: Comparable Budgets and Training versus Selection Cost

We separate final training from model selection. Table 2 reports the wall-clock time and peak memory of training the selected configuration. For selection, LapTop used approximately 20 Bayesian trials plus fixed configurations; GraphSAGE used a predefined 24-configuration search, with validation selection over completed runs; MLP and KRR used 8 and 4 base configurations, respectively, and each selected base predictor was reused across 12 C&S configurations. All selection was validation-only, followed by five final seeds.

We report configuration budgets rather than aggregate selection wall-times: the GraphSAGE search used CPU sampling, whereas its final Products training used a CUDA sampler, and LapTop's historical per-trial timings are unavailable. Mixing these measurements would not provide a like-for-like selection-cost comparison. Our efficiency comparison therefore concerns the selected model's accuracy, memory, and training time.

Reviewer_jZZLOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The authors consider Laplacian regularized kernel methods (LapKMs) for graph-based semi-supervised learning problems, under large-scale setting. The authors identify the optimization gap for LapKMs approach, then propose LapTop by leveraging ADMM to decompose the considered problem into graph Laplacian label smoothing (uu-step) and kernel ridge regression (KRR) (α\alpha-step) subproblems. For the uu-step, the authors consider inexact Newton methods for smooth loss, and accelerated proximal gradient descent (APGD) for prox-friendly loss. For α\alpha-step, the authors propose to use block coordinate descents (BCD) (Zhang and Lai, 2025) for full kernel in large-scale KRR. The authors illustrate advantages of the proposed approaches on 6 benchmark graph datasets.

Critical strengths
  • The authors propose a practical ADMM framework to scale LapKMs for large-scale settings. The proposed approach decouples the considered problems into two graph smoothing and kernel regression subprolems.

  • The proposed method outperforms LapKMs (LapSVM-Primal) a large margin even solving the same problem; and its performances are also comparative with other GNN approaches.

Critical weaknesses
  • The ability to work with the full kernel in KRR is mainly based on (Zhang and Lai, 2025), which may limit the novelty of the proposed approach.

  • It is better to consider a trivial two-stage baseline: base predictor (e.g., label propagation), then post-processing graph smoothing, to highlight advantages of the proposed joint ADMM.

  • It is unclear whether efforts for hyperparameter tuning of the proposed approach and baselines are similar. It is better to compare their performances under comparable budget for hyperparameter tuning.

  • It is better to have ablation study on ρ\rho and bb.

  • Both subproblems are approximated with uncleared error tolerance. How does it affect ADMM convergence?

Questions for authors
  • Are there any reported experiments where GNN and graph transformers are tuned per dataset with a budget comparable to the proposed approach with grid?

  • In Table 1, for Flickr dataset, could the authors explain how the proposed approaches outperform LapKM a large margin? Do they solve the same optimization problem?

  • How does hyperparameter ρ\rho affect the 2 subproblems? and how does hyperparameter bb affect?

  • Could you specify under what conditions for subproblems (inexact approximation) which can guarantee convergence for LapTop in practice?

  • Please also report results of other baselines (GNN/graph transformer), besides Polynormer in Table 2.

2 comments
AuthorsOpenReview ↗

Response to Reviewer jZZL — Part 1/2

We thank you for the careful assessment of LapTop's optimization and for the specific suggestions on baselines, tuning, and inexact convergence. We address each point below.

W1: Contribution and Novelty

We emphasize that our contribution is the problem-specific decomposition, rather than a generic application of ADMM or BCD. Introducing u=Kαu=K\alpha avoids directly solving the coupled KLKKLK system while retaining the full representer expansion. It separates LapKM into graph Laplacian smoothing and kernel ridge regression, allowing well-established solvers to be applied where the original coupled formulation was computationally intractable. The matched Flickr comparison illustrates the improvement in solution quality enabled by this decomposition: under the same squared-hinge objective and full expansion, LapTop attains J=20.314J=20.314, compared with 124.750124.750 for LapSVM$^2$ (see Q2 for details). To our knowledge, this is the first demonstration of full-expansion LapKM with squared, hinge, squared-hinge, and logistic losses on million-node graphs (on Products, LapTop trains on 2.45 million nodes using 10.1GB memory). By resolving this optimization bottleneck within a single-GPU memory budget, LapTop clarifies where LapKMs remain effective on modern graph-learning tasks. Therefore, the novelty lies in the reformulation that unlocks this scale and loss flexibility, not in claiming ADMM or BCD as new algorithms.

W2: Missing Two-stage Baselines

We added MLP+C&S and KRR+C&S. For these new baseline runs, we use the same raw features and splits, with validation-only selection. LapTop outperforms both on all four multiclass datasets, showing that joint graph-regularized training adds value beyond smoothing an independently trained predictor. The full comparison appears in Table 1 in the revised manuscript.

W3: Comparable Hyperparameter Tuning

Please see Q1.

W4: Effects of ρ\rho and bb

Please see Q3.

W5: Inexact Subproblems and Convergence

Please see Q4.

Q1: Comparable Tuning Budgets

Your concern is whether LapTop benefits from more tuning. We added dataset-specific GraphSAGE tuning and clarified each search. LapTop uses approximately 20 Bayesian trials plus additional fixed configurations rather than enumerating the full 16×1616\times16 grid. GraphSAGE uses a predefined 24-configuration search, with validation selection over completed runs. C&S uses separate searches for its two stages: 8 MLP or 4 KRR base configurations, followed by 12 smoothing configurations. GraphSAGE therefore receives a comparable selection budget, and both stages of C&S are tuned.

The model selection uses validation performance only, and test labels are never used for tuning. Five final seeds are run after selection. Figure 4 also suggests a practical way to simplify LapTop's search: a moderate ρ∈[4,16]\rho\in[4,16] works well, while the tested block sizes and inner budgets have little effect on validation accuracy. The search can therefore focus on cLc_L and cMc_M, which control the labeled-data fit and graph-regularization strength, respectively.

Q2: Flickr Comparison with LapSVM$^2$

Yes. We evaluated the predictors in two loss-specific pairs with a common offline implementation of the corresponding LapKM objective. Both pairs use the same RBF kernel, symmetric graph Laplacian, splits, and cL=128,cM=16c_L=128,c_M=16. The SVM$^2$ pair uses squared hinge and directly compares two solvers for the same full-expansion problem. The MSE pair uses squared loss; LapRLS-NyPCG retains its landmark restriction (s=22,000s=22{,}000). Here, RR, GG, and LL are the RKHS norm, manifold regularization, and labeled-loss terms, and J=R+G+LJ=R+G+L.

LossMethodRRGGLLJJVal. (%)Test (%)
SVM$^2$LapTop-SVM$^2$2.6497.8499.81620.31453.9153.84
SVM$^2$LapSVM$^2$0.0005137.12487.626124.75046.1646.07
MSELapTop-RLS2.5388.9349.82321.29553.9253.94
MSELapRLS-NyPCG2.88715.24856.70474.84038.7444.34

In both pairs, LapTop attains a substantially lower JJ, with the largest reduction in the labeled-loss term: LL decreases from 87.626 to 9.816 for SVM$^2$ and from 56.704 to 9.823 for MSE. Thus, the baseline predictors leave much more labeled-data error at the same regularization strengths. For LapSVM$^2$, the near-zero RKHS term is offset by much larger graph and labeled-loss terms; a small RR alone therefore does not imply a better objective. The lower objectives coincide with higher validation and test accuracies. The SVM$^2$ pair rules out a landmark-subspace explanation and directly links the Flickr accuracy gap to optimization quality, while the MSE pair also includes the representation effect of the landmark restriction.

Continued in Part 2: Q3–Q5.

AuthorsOpenReview ↗

Response to Reviewer jZZL — Part 2/2

Q3: Mechanisms and Effects of ρ\rho and bb

We added controlled ablation studies of ρ\rho and bb in Figure 4 of the revised manuscript. The penalty ρ\rho controls agreement between uu and KαK\alpha. A larger ρ\rho strengthens the quadratic term in the uu-step, but weakens the I/ρI/\rho ridge in the α\alpha-step and makes that system more ill-conditioned. Figure 4(a) shows that moderate ρ=4\rho=4–16 performs well. At ρ=256\rho=256, the primal residual decreases further, but validation accuracy drops to 41.03: smaller feasibility error alone does not imply better prediction. The block size bb controls how many kernel coefficients are updated together. Larger blocks offer more parallelism but require O(b2)O(b^2) storage for the block system. Across b=256b=256–8192, Figure 4(b) shows validation accuracy within 52.95–53.16, indicating low sensitivity in the tested range.

Q4: Conditions for Inexact-subproblem Convergence

A concrete requirement is to control the suboptimality of each augmented subproblem, rather than only the number of inner iterations. Both computational subproblems in LapTop are strongly convex: the uu-step contains ρI\rho I, and the α\alpha-step potential ϕk\phi_k has Hessian K+I/ρ⪰ρ−1IK+I/\rho\succeq\rho^{-1}I. Their residuals therefore bound the distance to the corresponding exact subproblem solution. For example, for smooth uu-step losses with objective HukH_u^k, ∥u~k+1−u⋆k+1∥≤ρ−1∥∇Huk(u~k+1)∥,∥α~k+1−α⋆k+1∥≤ρ∥∇ϕk(α~k+1)∥.\lVert\widetilde{u}^{k+1}-u_\star^{k+1}\rVert\leq\rho^{-1}\lVert\nabla H_u^k(\widetilde{u}^{k+1})\rVert,\qquad \lVert\widetilde{\alpha}^{k+1}-\alpha_\star^{k+1}\rVert\leq\rho\lVert\nabla\phi_k(\widetilde{\alpha}^{k+1})\rVert. Define eku=u~k+1−u⋆k+1e_k^u=\widetilde{u}^{k+1}-u_\star^{k+1} and ekα=α~k+1−α⋆k+1e_k^\alpha=\widetilde{\alpha}^{k+1}-\alpha_\star^{k+1}. Under the standard assumptions of Eckstein and Bertsekas (1992), one sufficient condition for convergence to an optimal primal-dual solution of LapKM is ∑k=0∞(∥eku∥2+∥ekα∥2)<∞.\sum_{k=0}^{\infty}\left(\lVert e_k^u\rVert_2+\lVert e_k^\alpha\rVert_2\right)<\infty. In words, the total subproblem error over all outer iterations must be finite. If the two residuals above are bounded by τu,k\tau_{u,k} and τα,k\tau_{\alpha,k}, the residual bounds give a direct stopping rule: ∑k=0∞(ρ−1τu,k+ρτα,k)<∞.\sum_{k=0}^{\infty}\left(\rho^{-1}\tau_{u,k}+\rho\tau_{\alpha,k}\right)<\infty. This condition ensures the required summable solution errors and hence the same convergence guarantee. For nonsmooth uu-step losses, the gradient residual is replaced by an appropriate KKT or subgradient residual. Relative-error and subgradient-based conditions provide alternative sufficient rules (Eckstein and Yao, 2018). As a constructive example of how the sufficient condition can be met, consider a linear system Akx=bkA_kx=b_k with TCG residual rk=bk−Akxkr_k=b_k-A_kx_k. One suitable stopping rule at outer iteration kk is ∥rk∥2≤min⁡(0.25∥bk∥2,C(k+1)2),C>0.\lVert r_k\rVert_2 \leq\min\left(0.25\lVert b_k\rVert_2,\frac{C}{(k+1)^2}\right),\quad C>0. The second bound gives ∥rk∥2≤C/(k+1)2\lVert r_k\rVert_2\leq C/(k+1)^2, so the residual sequence is summable. Applying such absolute-residual schedules to the two subproblems satisfies the sufficient condition above. The 0.250.25 relative-residual cap also maintains a clear accuracy target during early iterations. For the fixed-budget implementation used in the paper, Figure 4 shows stable validation across TBCD=100T_{\rm BCD}=100–3000 and TCG=5T_{\rm CG}=5–500, while Figure 5 shows decreasing objective and feasibility residuals. These results show that stable training does not require aggressive inner solves.

Q5: Additional GNN/GT Efficiency Baselines

Table 2 now includes tuned GraphSAGE alongside Polynormer and the LapKM solvers. On Products, LapTop achieves 80.56 accuracy with 10.1GB memory and 173min training. GraphSAGE is faster at 32min and reaches 78.29 with 12.3GB; Polynormer reaches 83.82 with 22.1GB and 443min. LapTop thus combines higher accuracy than tuned GraphSAGE with lower memory, while using less than half Polynormer's memory.

Reviewer_T5JJOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper revisits Laplacian regularized kernel methods for graph semi-supervised learning, arguing their long-standing scalability issue stems from an optimization gap . It proposes LAPTOP, a tailored ADMM-based framework to decouple the coupled kernel and graph Laplacian into two tractable subproblems. Experiments on six large-scale datasets show LAPTOP delivers competitive performance against strong GNN baselines.

Critical strengths
  1. The paper attributes the long-standing scalability bottleneck of Laplacian kernel machines to an optimization gap caused by the coupled kernel matrix and graph Laplacian. And unlike low-rank approximations that substantially erode the benefit of graph regularization, the proposed ADMM framework decouples the original problem into graph label smoothing and kernel ridge regression. Combined with a memory-efficient BCD solver, it enables full kernel expansion on million-node graphs on a single consumer-grade GPU.

  2. This work fills the performance reference gap of the regularizer-side paradigm at scale. It demonstrates that well-optimized classical kernel methods can compete with strong deep graph baselines with lower memory cost, offering a principled complementary perspective to the community.

Critical weaknesses
  1. Though the proposed framework is effective, its methodological novelty is limited. It builds upon established ADMM splitting and existing solvers, including BCD which has been applied to large-scale kernel ridge regression previously. The contribution mainly lies in integrating these techniques for LapKM.

  2. The experimental evaluation covers large-scale datasets, yet several critical dimensions remain under-explored. (1) The work lacks systematic tests across diverse label rates. Most datasets adopt relatively high label fractions, leaving its performance under challenging low-label regimes unclear; (2) Inductive evaluation is only validated on two datasets and several baselines, which is insufficient to support general conclusions for inductive graph learning.

Questions for authors
  1. Could the authors provide supplementary experimental results addressing the missing diverse label-rate settings and inductive evaluation?

  2. Could the authors include sensitivity analysis for kernel function selection, to disentangle performance gains from the ADMM framework versus the choice of kernel?

  3. Some baseline results are adopted from original publications while others are re-run by the authors, leading to inconsistent experimental protocols. Could the authors clarify this practice? Would the relative performance gaps change if all baselines were evaluated under a unified setup?

  4. The paper mainly compares training memory and runtime among LapKM variants but does not include GNN baselines in these efficiency benchmarks. And could the authors further provide inference-time computational costs of LAPTOP and compare them against the GNN and graph Transformer baselines?

2 comments
AuthorsOpenReview ↗

Response to Reviewer T5JJ — Part 1/2

We thank you for recognizing the value of making full-expansion LapKMs practical at scale, and for the constructive suggestions on label rates, inductive evaluation, kernel sensitivity, and efficiency. We address each point below.

W1: Methodological Contribution and Novelty

LapTop makes full-expansion LapKMs practical at scale and provides a competitive regularizer-side reference on modern graph benchmarks. The problem-specific ADMM decoupling supports four convex losses and trains on 2.45 million Products nodes with 10.1GB memory. In the revised benchmark, LapTop ranks among the top three methods on every dataset. These results show where full-expansion LapKMs remain competitive and what computational costs they incur when trained on a single consumer-grade GPU.

W2: Label-rate and Inductive Coverage

We address the requested additional label-rate and inductive evaluation in Q1.

Q1: Label Rates and Additional Inductive Evaluation

Label rates. We conducted a response-only Flickr comparison at 0.1%, 1%, and 5% labels, using matched label subsets and three subset seeds. Test accuracies (%) are:

Label rateLabelsLapTopGraphSAGEMLP+C&SLaplacianPoisson
0.1%8920.11±2.9031.2±4.8316.6±1.828.2±2.0917.5±0.36
1%89220.97±0.6932.3±6.8625.8±0.818.7±2.3824.8±1.31
5%446225.03±1.4333.7±3.8430.5±1.0522.4±3.0027.9±1.33

LapTop achieves higher mean accuracy than Laplacian propagation at all three rates and, at 0.1%, higher means than Poisson learning and MLP+C&S. GraphSAGE achieves the strongest results in this sparse-label study. Building on the scalability enabled by LapTop, extending LapKM research to sparse supervision through objectives such as Poisson-learning-inspired formulations is a natural direction for future work.

Inductive evaluation. LapTop's representer expansion predicts new nodes without their edges; when the test graph is available, one optional smoothing step can be applied without retraining. In addition to the Products/Arxiv study, we conducted a response-only Flickr comparison using the same uu-step for both base predictors:

MethodGraph-free+ one uu-step
MLP47.0250.45
LapTop46.4250.90

The same smoothing step improves LapTop by 4.48 points and MLP by 3.43 points, with LapTop reaching a slightly higher final accuracy. As additional graph-aware references, GraphSAGE reaches 51.1 and MLP+C&S reaches 52.9 using its standard correction-and-smoothing pipeline.

Q2: Kernel-function Sensitivity

ADMM changes the optimization method rather than the kernel representation. For each kernel, we compare plain KRR and LapTop with the same kernel and otherwise matched settings. The validation gains are +8.2, +3.2, and +2.7 points for Gaussian/RBF, Matern-0.5, and Arc-cos order-0 kernels, respectively. Thus, each gain is measured within a fixed representation, and its consistency across kernels shows that the graph-regularization benefit is not specific to one kernel choice.

To examine the optimization contribution separately, we compare LapTop and LapSVM$^2$ under the same squared-hinge objective, RBF kernel, and full expansion. LapTop attains a lower common objective, 20.314 versus 124.750. This matched comparison shows that the framework improves the solution obtained for a fixed model, rather than benefiting only from a different kernel.

Q3: Published Results and Unified Baseline Protocol

The revised appendix identifies published entries separately from our runs. The new GraphSAGE, MLP+C&S, and KRR+C&S comparisons use the same raw features and splits, frozen configurations, validation-only selection, and five final seeds. LapTop outperforms both C&S variants and tuned GraphSAGE on Flickr, Products, Arxiv, and Reddit. These controlled results, rather than mixed-source leaderboard entries, support our competitiveness claim.

Continued in Part 2: Q4 on efficiency and inference cost.

AuthorsOpenReview ↗

Response to Reviewer T5JJ — Part 2/2

Q4: GNN Efficiency and Inference Cost

Table 2 now includes tuned GraphSAGE. On Products, LapTop achieves 80.56 with 10.1GB and 173min, compared with 78.29, 12.3GB, and 32min for GraphSAGE and 83.82, 22.1GB, and 443min for Polynormer. GraphSAGE trains faster, while LapTop achieves 2.27 points higher accuracy with lower training memory. Polynormer achieves the highest accuracy, but requires substantially more training time and memory. We additionally profile inference for the selected configurations on the same RTX 4090, using two warm-up runs and the mean of three CUDA-synchronized runs. Training, preprocessing, and setup are excluded. Saved weights are loaded when available; otherwise, the same dense computation is profiled with initialized parameters. For C&S, peak memory is the larger measured value across the base and smoothing stages.

For LapTop, graph-free KαK\alpha prediction and one optional uu-step are timed separately. Blocked kernel matrix–vector products avoid materializing the full test–train kernel matrix, although the full expansion still evaluates all train–test kernel pairs.

DatasetMethodBase/KαK\alpha (s)Post-processing/uu-step (s)Total (s)Peak GPU (GB)
FlickrLapTop0.2543.5643.8183.26
FlickrGraphSAGE0.129--0.1294.65
FlickrMLP+C&S0.0240.0420.0661.11
FlickrKRR+C&S0.1100.0460.1561.23
FlickrPolynormer0.378--0.3782.04
ProductsLapTop304.8759.676314.55110.05
ProductsGraphSAGE32.401--32.40115.15
ProductsMLP+C&S0.0644.7934.8579.82
ProductsKRR+C&S32.6964.78037.4769.04
ProductsPolynormer36.996--36.9962.88

Training scalability does not automatically imply low inference latency. LapTop retains all training nodes in its predictor, so graph-free prediction evaluates all train–test kernel pairs. The measurements show this cost directly. On Products, the full expansion accounts for 304.875 seconds of the 314.551-second total. On Flickr, the optional uu-step instead dominates.

The tables therefore address different practical questions. Table 2 shows that LapTop achieves competitive accuracy and memory usage when training at million-node scale. The inference table measures the cost of using the resulting predictor. For latency-critical applications, lightweight graph predictors are preferable. LapTop makes full-expansion LapKM training feasible at this scale.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of the Revised Manuscript and Responses

We thank all reviewers and the AC for their constructive feedback. This short note summarizes our revisions; detailed answers to each specific concern are provided in the corresponding reviewer threads.

LapTop’s central contribution is a problem-specific decomposition that makes full-expansion LapKMs trainable at million-node scale. This enables us to assess both the accuracy these models can achieve and the computational costs of retaining the full expansion.

The revised manuscript provides three main pieces of evidence:

  • Controlled baselines: C&S baselines have been added. LapTop ranks among the top three on all six benchmarks, and outperforms tuned GraphSAGE, MLP+C&S, and KRR+C&S on Flickr, Products, Arxiv, and Reddit.
  • Better LapKM solutions: We compare matched predictor pairs using a shared implementation of the corresponding LapKM objective. LapTop achieves both higher test accuracy and substantially lower objective values than LapSVM² under squared hinge and LapRLS-NyPCG under squared loss.
  • Value of full expansion: Nyström landmark sweeps show that small PCG residuals do not necessarily translate into better prediction, while the largest landmark models consume more memory than LapTop.

Additional studies clarify inference costs, label-rate behavior, inductive prediction, and convergence with inexact subproblem solves. Together, these additions strengthen the empirical evidence and clarify the scope of our claims.

We hope the revised manuscript and responses address the reviewers’ concerns, and we welcome further questions.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.