Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper proposes a new local descriptor on sampled data, which quantifies the local recurrence properties of a random walk. This corresponds to a notion of curvature: random walks diffuse rapidly in regions that are negatively curved (such as branching trees), and stay more concentrated in regions of positive curvature (such as boundaries).

strengths_and_weaknesses: This paper is original and well-written. It addresses an interesting topic in data sciences: what are the local descriptors that we can define (and understand!) on high-dimensional datasets.

Up to and including Section 3.1, this paper is truly excellent: the authors introduce their ideas clearly, with an appropriate level of details. I appreciate the fact that the authors included relevant references to concepts and theorems in the mathematical literature. An unfortunate trend at NeurIPS/ICML is to provide truncated overviews of the literature in pure mathematics in order to present classical ideas as “novel”: the diligent work of the authors should be rewarded.

Overall, I believe that this paper builds a very nice  bridge between modern geometry and machine learning applications. It introduces inspiring ideas in a way that is easy to digest by the NeurIPS community.

Please note, however, that I have some reservations about the content of pages 6 to 9:

- I do not understand why the authors decided to rely on a black-box neural network to estimate a local quadratic fit to the input point cloud. This method is intrinsically less reliable and interpretable than a simpler estimator, and goes against the clean mathematical definition of the proposed diffusion curvature. Couldn’t the authors have simply relied on a least-square formulation? Even if we add an L1 regularization term as in Eq. (3), it seems clear that we could compute a decent quadratic fit to the input point cloud by solving a small convex optimization problem with respect to Q. In 2022, this is easy to do using e.g. the “cvxpy" library.

- One of the main motivations that is proposed by the authors for their method is that it allows one to estimate the Hessian of a neural network. A discussion of alternative methods and approximations would have been appreciated.

- As far as I can tell, the authors do not discuss the scalability of their method. Since the proposed method relies on the computation of the first eigenvectors of a large N-by-N (normalized) kernel matrix, this is an important point. Could the authors explain why Eq. (1) is necessary? Couldn’t the authors simply iterate the application of a (normalized) Gaussian kernel matrix to simulate diffusion?
  I assume that the authors could be interested by recent papers and codes on diffusion or kernel matrices, such as "Fast geometric learning with symbolic matrices", Feydy et al., that was presented at NeurIPS 2020 (with a relevant example on eigendecompositions at: http://kernel-operations.io/keops/_auto_tutorials/backends/plot_scipy.html) or the work of Nicholas Sharp (https://nmwsharp.com/) on the vector Heat method and Diffusion networks.

- I would have appreciated some more details on the proposed experiments (e.g. better legends for the figures). Currently, it is hard to see them as anything more than toy examples: this could be fine for a theoretical paper, but there is certainly room for improvement here. For instance, the authors could illustrate the difference between their notion of curvature and other alternatives (discussed in Section 2.2) to highlight different behaviours, or discuss the influence of the choice of their kernel matrix (i.e. of the underlying random walk). This would be relevant for practitioners, in a context where the “best” local metric for a given dataset is often not known.

questions: Please refer to the questions above on implementation choices.
limitations: N/A
review_title: null

final_score: rating: 3: Reject: For instance, a paper with technical flaws, weak evaluation, inadequate reproducibility and incompletely addressed ethical considerations.
review_content: summary: The paper formulates a discretized scalar curvature for graph and point cloud data, using the diffusion rate of a random walk started at the query point. This is tested on toy cases, and on single-cell data, showing its basic efficacy and correlation with Gaussian curvature (in the toy cases).

Additionally, it considers a procedure for Hessian estimation using diffusion maps to perform dimensionality reduction. In particular, they first train a neural network to estimate Hessians from quadrics of various degrees. Next, given a local optimum, they tack on the label dimension and put it through a diffusion map for the embedding, and apply the neural network. This was tested on synthetic data from a high-dimensional hypersphere, giving again, some evidence of efficacy.
strengths_and_weaknesses: Strengths:

- The method is certainly novel, and the Hessian optimization method tackles a problem of importance.
- I quite liked Figure 2, which succinctly summarized their Hessian estimation method.

Weaknesses:

- The scalar curvature quantity and the Hessian estimation method are only loosely related. Either one is not really necessary for the other. The linking concept is that of diffusion maps.
- The effectiveness of the Hessian optimization method is never tested on a real dataset, in the proposed application, as some measure of how well a local minimum might generalize (question 4 below). 
- I think the method overlooks the challenges presented by the potential high dimensionality of the weight space. See question 1 below.
- The experimental comparisons are relatively weak, with no competing methods considered for either concept.
- There was no test for robustness to kernel parameters (see question 3).
questions: 1. How do you deal with the problem that the dimensions of your input data far outweigh your output label? This would seem to suggest that it would be easy for this information to get washed out in the embedding, and you might simply end up measuring curvature of the input.
2. It's repeatedly mentioned that sampling around the minima is a method of dimensionality reduction. I'm not sure I understand why this is the case. It seems to me that if you randomly perturb about a point in $R^{|W|}$ where $|W|$ is the dimension of the weight space, then you are still generating a random sample from a full-dimensional ball.
3. In practice, many diffusion maps methods are quite sensitive to the kernel choice when building a graph from a dataset. Did you find that your method was robust to changes in some of those parameters (e.g. $\alpha$)?
4. Did you test whether your estimated Hessians and their spectra actually gave information on how robust a local optimum was?
limitations: I think the method presents an interesting idea, but the exploration is lacking, and with a lack of strong experimental evidence, I'm not clear that its assumptions are valid. Most of my questions above reference my doubts and potential pitfalls I see for the method.

I would recommend that further work be done on experimental validation be done to address these concerns, if the paper is not accepted.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: The paper presents a technique to estimate local curvatures on point clouds using diffusion maps. The proposed metric, diffusion curvature, is quadratic in nature and resembles the gaussian curvature, in terms of discriminatively. The authors demonstrate its usability for estimating local curvatures on high (and low)-dimensional data and hessians of a neural network loss. The underlying idea is simple: the diffusion curvature measures the divergence in a local neighbourhood wrt to a ball of a constant radius. It can be computed on a point cloud of any dimension. 
strengths_and_weaknesses: Strengths:

1. The proposed diffusion curvature is simple yet sufficiently novel, to my best knowledge.
2. In general, the paper reads well. The main idea is made sufficiently clear.


Weakness:
1. As seen in figure 3, the proposed  diffusion curvature is more discriminative than gaussian one. Perhaps, it should also be compared with mean curvature as it is more discriminative than the gaussian one, especially in the flat regions. Is there any reason why comparison with mean curvature was ignored?
2. It is unclear how the diffusion curvature handle the noisy data. Given its discriminative power, it seems that diffusion curvature will be more affected by the noise in data as compared to the gaussian curvature. Repeating the hessian estimation (figure 3) with varied levels of noise in the data is important to understand how unstable the proposed metric is.
3. The experimental section is missing a practical use-case. A possible use-case could be the use of this metric to correct noisy 3D data obtained through various 3D sensors such as Kinect.


questions: Please address the points raised in the weakness section.
limitations: yes
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper introduces a new measure of the local curvature of a point cloud sampled from an underlying manifold: the so-called diffusion curvature. This measure uses the framework of diffusion maps and random walks. More precisely, the idea is to use random walks to capture the relative spreading of geodesics. Actually, a random walker is more likely to return to its starting point in a region where geodesic paths converge, i.e. in a region of positive curvature than negative curvature. The authors demonstrate by experiments that their notion of curvature scattering can be related to the Gaussian one.

Using a diffusion map, the authors also propose a way to locally approximate the Hessian associated with the loss function of a neural network for a given data set. This second-order approximation allows quantifying the (local) minima and thus quantifying their generalizability. Intuitively, the authors claim that flat minima generalize better than sharp minima. This estimation is done using a neural network: CurveNet.

The experiments are conducted on simulated data, which allows, in particular, the comparison with Gaussian curvature, and single-cell data.
strengths_and_weaknesses: I appreciated the efforts of the authors to give geometric insights, especially in dimension 2 (see section 3.1), throughout their paper. In general, the article is pleasant to read and well constructed. 

In my opinion, one of the main limitations of this work concerns the sampling of points (also by the authors' admission, line 175). This point is not discussed here, and I wonder how this notion of diffusion curvature behaves in very high dimensions.

On the other hand, as much as the article is well worked, there is a lot of redrafting of supplementary material to be done. Several times in the article, the authors refer to it, but without specifying which part of the appendix. Moreover, the different sections are never put in context, and their titles are not explicit. I have the feeling that the authors have cut and pasted pieces of their articles to fit into the 9-pages limit without trying to recontextualize the different paragraphs. In the end, it makes this supplementary material difficult to follow.
questions: Here are some minor comments and suggestions:
* _l41:_ “the minima” Which one?  Which function?  Uniqueness?
* _l69:_ $\lVert.\rVert_1$ is not defined.
* _l77:_ Maybe add a sentence to justify why $\lambda_1=1$?
* _l88 (and the next times):_ Which annex?
* _Section 2.3_: Revise this paragraph to better motivate the introduction of the Hessian that arrives without context. Maybe write the paragraph the other way around and start talking about the generalizability of minima? Just a suggestion!
* _l129:_ No need to redefine the sphere.
* _l130:_ $K$ is not defined.
* _Theorem 1:_ The same notation ($B(p,r)$) is used to define two different objects.
* _Figure 1:_ The article does not refer to Figure 1.
* _l254:_ “sample $n$ points” According to which law?
limitations: This work is theoretical and has no short-term societal impact.
review_title: null

Meta-review: metareview: This paper uses diffusion maps to measure curvature from point cloud data and includes some theoretical analysis as well as preliminary experiments demonstrating the value of the curvature measure.

The paper benefited from detailed discussion among a number of experts that gave it thorough consideration.  While the reviewers did not totally converge to a unanimous "accept" decision, the AC views their detailed/thoughtful discussion as a *positive* sign that the work will spark discussion and interest at the NeurIPS conference.  Other than limited experimental evaluation, it seems the main negative aspects of the work (mostly raised by reviewer 4SQF) are debatable in terms of whether they truly invalidate the research paper.

Overall, the AC recommends accepting this paper, especially since OpenReview will show the thoughtful discussion between the reviewers and authors.
confidence: Less certain
Decision: Accept