Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper addresses the settings of self-supervised learning, providing a new perspective on Laplacian regularization by restricting the solution to a reproducing kernel Hilbert space. They show this formulation leads to new efficient empirical estimates, and demonstrate their approach out-performs the classical graph Laplacian regularization, both in terms of accuracy and computational complexity.     

main_review: The authors provide an interesting new solution to semi-supervised learning, by casting the classical Laplacian regularization typically used into an RKHS perspective. They provide both convergence rates as well as a practical algorithm for their new approach.  
My main concern with this paper is that it is ~40 page journal paper trying to squeeze into a dense 9 page conference paper + appendix. As such, the flow of the paper is hard to follow and useful insights and mathematical background that would be of use to the general reader are buried in the appendix, as are experimental results that are more interesting than those presented in the main text. For example, given the limited page length, is Figure 2 essential to the main text? Figures 4 and 5 in the appendix would be more important to demonstrate the performance of the approach.   

My second concern is the motivation. The authors claim the graph-based Laplacian is a technique that does not scale well with the dimension. In the text they clarify this statement in 2 places, once in lines 156-157 regarding the scaling of the convergence of the estimator of the graph Laplcian and once in the experimental results in setting the bandwidth of the Gaussian kernel. In practice, regularization with the graph Laplacian has been demonstrated successfully in a broad range of applications with high dimensional data: matrix factorization, convex clustering, dictionary learning, recommender system, data imputation, dimensionality reduction, etc., such that this theoretical concern seems of limited practical implications.  

In this context, how dependent are the experimental results on the kernel bandwidth used for the graph Laplacian? In practice, the bandwidth of the Gaussian kernel is typically set in a data-driven manner, such as the median distance of k-nearest neighbors of all points, or using an adaptive bandwidth such as self-tuning bandwidth (Zelnik-Manor and Perona), or multiple other possibilities. The bandwidth used by the author does not seem to depend in any way on the scale of the data itself. 

The experiments themselves are synthetic and limited, mostly proof of concept, and more extensive experiments would be required to adopt the author’s approach which the authors state is their goal (I understand this is beyond the scope of the paper).

The paper doesn’t mention recent literature on RKHS in the graph signal processing field for data reconstruction, LMS solutions and spectral filtering:  
* SEMI-PARAMETRIC GRAPH KERNEL-BASED RECONSTRUCTION† Vassilis N. Ioannidis, Athanasios N. Nikolakopoulos, and Georgios B. Giannakis
* Kernel-based Reconstruction of Graph Signals Daniel Romero, Meng Ma, Georgios B. Giannakis
* Adaptive Graph Filters in Reproducing Kernel Hilbert Spaces: Design and Performance Analysis, V. R. M. Elias, V. C. Gogineni, W. A. Martins and S. Werner
Additional missing references:
* Semi-supervised learning on Riemannian manifolds, M Belkin, P Niyogi -
* Regularization and semi-supervised learning on large graphs, M Belkin, I Matveeva, P Niyogi 



limitations_and_societal_impact: These were addressed in the appendix and not in the main text.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: The paper proposes a novel Laplacian regularization method for semi-supervised learning that incorporates an additional penalty term that constraints the learned function to be in a smaller, smoother, RKHS. They characterize their approach via a spectral filtering perspective, provided an approximation that improves the computational complexity in the generalized eigendecomposition, and provided a convergence rate bound under several assumptions that they clearly identified. 
main_review: I believe that semi-supervised learning and Laplacian regularization are significant problems of broad interest. 

The exposition is clear, and the paper is well organized and well motivated. The technical/mathematical parts of the paper are well written and a pleasure to read. 

The authors provided ample background information and motivated their problem clearly, proposed their regularization method, provided different characterizations of their method, and provided a computational approximation that offers a big speedup in computing the eigendecomposition. They outlined their assumptions clearly and provided statistical guarantees. 

This is a good quality theory/methods paper. 

Several comments: 
1. In figure 3b (the subfigure on the right), the computational complexity of small kernel and graph based Laplacian appear to be similar (with the graph-based laplacian appear to be slightly faster than the small kernel)....perhaps in that figure the dimension is not high enough? I would expect that the proposed method with the approximation proposed should scale better computationally than naive Laplacian regularization as dimension scales higher. If so perhaps this can be illustrated with a plot of computational complexity comparison of said methods as you try different dimensions along the x axis? 

2. Optimality of bounds: I understand that lower bounds are difficult to show (I certainly don't expect a lower bound to be included in the revision of this paper), but I wonder whether the authors have anything to say about the optimality of their statistical guarantees. Perhaps an easier way to give evidence of how tight their upper bound is is to do some simple simulations under very ideal settings and plot the empirical results along with your bound to show that your bounds are perhaps not (too) loose. 

3. Simulations: I understand that this is largely a theory/methods paper, but I do think more simulations/experiments could help make the case more compelling. For one, you mentioned the limitation of the work of El Alaoui et al in part of your motivation but did not provide comparisons against their methods in simulations/experiments. 

* A side note is that there is a typo in your reference : Your reference [1] contains only El Alaoui, but the actual paper has many more authors. 

limitations_and_societal_impact: Since this is mainly a math/theoretical paper, I don't believe any potential negative societal impact is applicable here.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper considers the problem of semi-supervised learning using Laplacian regularization. The authors use principles and methods from RKHS to mitigate issues with the curse of dimensionality. 
main_review: The paper appears to be original and is tackling an important problem. The experiments seem correct and support the authors' claim.

My main complaint is that the paper is highly technical. While technical papers are welcomed at NeurIPS, I think it could be made a bit more accessible to the general NeurIPS community. As it stands, it seems the paper will be mostly of interest to those who are deeply in this field. Perhaps some of the technical results could be summarized better with details left for the supplementary material and more experiments moved to the main paper.
limitations_and_societal_impact: Yes
review_title: null

Meta-review: The paper received positive reviews. However, only 3 out of 4 reviewers submitted a review, and therefore the AC very carefully read the paper on their own. They do share the positive impressions of the reviewers regarding novelty and they also think that for somebody familiar with the topic this paper is very accessible, while for others it is certainly a hard read. Their major concern regarding the paper is Assumption 1, which unfortunately has not been seen as an issue during the review/rebuttal phase. The main problem they see with Assumption 1 is that it is very restrictive, in fact much more restrictive than a usual source condition, as it explicitly assumes that the target function can be expressed by a finite number of eigenfunctions of the Laplacian, whereas "normal" source conditions are usually phrased in terms of an essentially polynomial decay of the Fourier coefficients. Even worse, the main result, Theorem 1, does not specify the dependence on the number of required eigenfunctions, and a quick look at the appendix did not resolve this issue. As a consequence, the AC views the main result, Theorem 1, as rather premature.

These concerns were discussed with the reviewers and SAC, and it was concluded that this paper should nonetheless be accepted. 1) the authors are attacking a problem of interest to the community; 2) they have some new non-trivial results; 3) the writing is good. The only concern is that the assumption made is not as nice as one might like. 
Decision: Accept (Poster)