Implicit Manifold Gaussian Process Regression

Summary

The curse of dimensionality demonstrates in Gaussian process models in that they’re default kernel choices that often depend on the Euclidean distance between 2 points. Euclidean distance is a poor metric especially in high-dimensional settings, where we expect data points to lie on an, often unknown, manifold. This paper combines findings from multiple precursor works in assembling a tool set to for Gaussian process regression with a Metern kernel, while implicitly inferring the underlying manifold structure.

Strengths

I believe that while the paper mostly combines existing theoretical results in manifold learning and numerical analysis, it presents a compelling, novel framework of tackling manifold learning with Gaussian process regression. The paper is largely self-sufficient: it tackles the complex problem of learning manifolds in the context of Gaussian process by proposing solutions to all facets of the problem: characterizing manifolds with graph Laplacian, gradient-based learning and scalability.

Weaknesses

I think the paper lacks a presentation of _how_ learning the manifold structure aids in the predictive performance of the rotated MNIST dataset. While one can clearly see _why_ the learning of an implicit manifold helps in predicting rotation angles for handwritten digit, as rotation expressly traverses around a nontrivial manifold, the benefits of this work go beyond simple improvements in prediction, but interpretability. While the authors did a very good job in demonstrating how the model correctly inferred the dumbbell-shaped manifold, I believe similar illustrations can also be done in the MNIST rotations.

Questions

None

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

4 excellent

Presentation

3 good

Contribution

3 good

Limitations

- I believe the presentation of the paper could be improved by a clear separation of predecessor works and original contribution: for example, Section 3.1 is almost solely composed of existing work except for the theoretical contribution of the Matern kernel convergence — an overall marginal contribution in the paper. - Table 3: “RMSE” in the table seems confusing for prediction of rotating angles. Is it so that the author is referring to the shortest arc as a metric for distance in rotations? - I believe that the paper could benefit from a illustration of what implicit manifold is learned from the rotated MNIST data: for example, a display of what the kernel values matrix looks like along the trajectory of a rotation compared to the Euclidean kernel matrix, or something else showing the geodesics of the points on the rotation trajectory.

Summary

Authors propose a novel methodology for doing GP regression which is able to learn the implicit structure from the data. This is particularly useful in high-dimensional problems, where the data lies on low-dimensional manifold. The proposed methods allows to learn the implicit manifold in a fully differentiable way, using nearest neighbour graph. The method is based on Matern GPs on manifolds and graphs (Borovitskiy, 2020, 2021). To approximate the eigenvalues of the Laplace-Beltrami operator on the implicit data manifold, authors use random walk normalized graph Laplacian (on KNN graph) weighted to overcome possible non-uniform sampling density. This work leverages efficient approximation to the KNN, sparse structure of the precision matrices, and RFF kernel approximation to be able to scale to large datasets. The model is tested on a synthetic dumbbell-shape manifold and on rotated MNIST data.

Strengths

This is, to the best of my knowledge, a novel methodology for GP regression. This work is build on solid foundation and the method is derived naturally from Matern GPs on manifolds and graphs. Authors cleverly use a variety of techniques to keep good scalability. In my opinion, the main contribution of this work is in the elegant assembly of the right methods, which gives a practically usable model for a well-known problem. The manuscript is written clearly and is easy to follow.

Weaknesses

Due to the incremental nature of the paper, it is not always clear what is a novel contribution of this work and what is a background from previous works (example, last paragraph of 2.1). The experiments are somewhat limited. The method is tested on one synthetic dataset and a few versions of rotated MNIST. In the MNIST dataset, however, the added rotation must be inducing a lot of structure. It would be beneficial to showcase the method on a real dateset where an implicit manifold is already existing in the data.

Questions

1. Could you please clarify on the following: There are no results on spectral convergence for KNN graphs independent of data sampling density. You use a weighing scheme to deal with non-uniform data sampling. You do not claim that it implies spectral convergence. How much of a problem is it, both theoretically and practically? Suggestions: 1. In figure 2, perhaps use different colours foe kernel and sample plots. 2. eq(11) I believe $\lambda_i$ should be $\lambda_l$?

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

4 excellent

Presentation

3 good

Contribution

3 good

Limitations

The limitations are adequately addressed.

Summary

The authors propose a methodology to extend Matern processes on implicit manifolds, which are modeled by $K$-NN graphs, and the kernel relies on the set of eigenvalues/vectors of the associated graph-Laplacian. An approximation of the eigenfunctions based on the eigenvectors is provided, which together with an additional trick allows to extend the process in the vicinity of the implicit manifold. The hyperparameters are learned in supervised and semi-supervised scenarios via a differentiable objective, and the performance is demonstrated in the experiments.

Strengths

- The technical part of the paper seems correct and sensible, but I have not checked the derivations in details. - The idea is a direct and relatively simple extension of previous work. - The results mainly due to the synthetic experiment seem convincing. - The paper in general is well-written.

Weaknesses

- The main drawback of graph-based methods is typically the construction of the graph and how well this recovers the actual structure of the underlying manifold. I suppose that the current method has the same limitation that is not clearly discussed/analyzed in the paper. - As the methodology applies to general manifolds, I would expect to see more empirical results. For example, some synthetic 3d surfaces and more complicated high-dimensional real-world datasets as the rotation of MNIST is closer to a synthetic experiment.

Questions

Q1. Lines 98-100: Is there any reference that plugging in Eq. 3 the graph Laplacian and the Gaussian noise gives a Matern process on the graph? Q2. Why the dimension of the implicit manifold (graph) is 0? I suppose that the underlying manifold has some dimensionality. I think that there are approaches relying on graphs that try to estimate this dimensionality. Q3. How sensitive is the method with respect to the graph construction? In particular, how the number of neighbors $K$ influences the result? Can this be estimated somehow e.g. by cross-validation? Q4. How the method behaves if there are more than one connected components in the dataset? Q5. Lines 144-150: The graph Laplacian converges to the Laplace-Beltrami (in terms of eigenvalues/vectors/functions) for $K$-NN graphs as long as the data distribution is uniform on the manifold? While for non-uniform distributions such a convergence result does not exist? Q6. Lines 177-179: I think that here the gist is unclear. Q7. Which Nyström method is used? Q8. Fig 3. I think it is interesting to see the actual eigenvector on the data (e.g. color the points) and how this correlates to the extended version. Q9. Eq. 11 the eigenvalue should be probably $\lambda_l$ and not $\lambda_j$?

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

2 fair

Presentation

3 good

Contribution

3 good

Limitations

The authors do not discuss the limitations of their work, and in particular, the construction of the graph which I think is critical for the performance of the model. The methodology that is propose does not have a direct negative societal impact.

Summary

This work extends the reach of Matern Gaussian processes to additionally learning the implicit low-dimensional (unknown) manifold the data lives on - the existence of such a manifold is suggested by the manifold hypothesis. The theory draws from existing Laplacian Matern Gaussian processes (Borovitskiy et al., 2020). The model they propose is differentiable wrt all model and geometry hypers. It is able to scale to thousands of data points by leveraging the sparse structure of Mather precision matrices. They provide a way to extend predictions to the whole R^{d} space by reverting to a Euclidean GP away from the manifold. The experimental evaluation shows support for the implicit manifold Gaussian process.

Strengths

- The end-to-end differentiability where the kernel hyperparameters along with those that parameterise the underlying geometry can be learnt simultaneously using a single objective. - Scalability is achieved as the precision matrix corresponding to the KNN implied graph is sparse. - The semi-supervsied case is interesting where a large amount of unlabelled data is leveraged to infer the underlying geometry of the manifold through a weighted nearest neighbour graph. All these points contribute to the quality and significance of the work.

Weaknesses

- The exposition could benefit from an algorithm style pseudocode for the training and prediction steps, it should start with the interpretation of the data as a graph, computation of the elements needed for the Matern kernel etc - as I am a bit confused about the order of the steps. - While the details are all there in section 3.2, I think there need to be separate sections for construction of the matern kernel on graph nodes, computing the dependencies ie. the eigenpairs of the graph Laplacian, computing the kernel on arbitrary vectors in R^{d}, computing the predictive posterior. - I dont understand this line - pls explain or rewrite. Basically, why dont you just say how do you compute dim(M)? Essentially, from the theoretical results of Section 3.1 we borrow a particular weighting scheme, aiming to cancel out the possibly non-uniform density, and a specific choice of the graph Laplacian (the random walk normalized one).

Questions

- The final predictive distribution is a mixture of Gaussians - one is the canonical Euclidean posterior predictive with SE-ARD kernel and the other is the geometry aware kernel underlying the same canonical posterior predictive equations? - What is the order of the steps in training - the log marginal likelihood depends entails the precision matrix which depends on the eigenpairs, but you say in line 206 that they are computed after the hyperparameters are found, these are mentioned in line 216 - is the \hat{\kappa} the number of neighbours of the KNN graph?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

I think authors should devote a paragraph to this. I don't see limitations discussed anywhere.

Post-rebuttal comment

I thank the author for their detailed response, and I maintain the same score assessment but slightly decrease my confidence level as I realize my lack of expertise in manifold learning algorithms such as diffusion maps. I mainly have 1 question regarding the rebuttal PDF: the author added a 3d manifold example in the figure, but I did not see an explanation (it's possible that I missed it in your responses to other reviewers). Could you please clarify what message you meant to convey by this figure?

Post-rebuttal comment

I would like to thank the authors for their responses and the additional demonstrations. Regarding the graph construction, I agree that having more data implies that $K$ becomes a less critical parameter, but instead, I believe that the bandwidth of the kernel becomes critical for capturing well the structure of the underlying manifold with the graph. Anyways, this is a classic issue in graph construction, and the current papers focus on a different problem. I also agree that the manifold assumption does not hold in many of the real-world datasets. I recommend the authors include in the updated paper 3D demonstrations, potentially showing the eigenvectors together with the extended version (e.g. in Fig.3 ), and also discussing clearly the limitations of the proposed approach. As other reviewers mentioned, the novelty of the paper is somewhat limited in the sense that it combines previous approaches in a practical way. Overall and in light of the other reviews with there being a consensus for acceptance, I increase my score and vote for borderline acceptance.

Post rebuttal comment

I would like thank the authors for their response and clarifications. I am happy to support this work and raise my confidence score to a 4 and keep my overall score intact at 6. I would urge the authors to restructure section 3.2, clarify the training algorithm and ensure that all the parameters are described before being used in equations, for example \hat{\kappa}.