Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: The authors propose the intrinsic sliced Wasserstein (ISW) distances for collections of probability measures. The ISW is a variant of sliced Wasserstein (SW) which exploits the closed-form solution of optimal transport on 1-dimensional space. The authors propose to use the eigenfunctions to project supports into 1-dimensional space and use corresponding eigenvalues as its weights.

ISW is Hilbert embeddable which allows to reformulate testing problems over collections of probability measures to traditional ones in Hilbert space. The authors demonstrate it for hypothesis testing via resampling based test and testing by p-value combination (from coordinate-wise tests).

strengths_and_weaknesses: Strengths
+ The authors propose a novel intrinsic sliced Wasserstein (ISW) for collections of probability measures by leveraging eigenfunctions for 1-dimensional projection and eigenvalues as weights.
+ The paper is easy to follow.
+ The authors derive hypothesis testing in the Hilbert for collections of probability measures problems under ISW.

Weaknesses
+ The ideas to use eigenfunctions and eigenvalues for sliced Wasserstein are interesting. However, the authors have not demonstrated the advantages of the proposed approach over other approaches (e.g., sliced-Wasserstein, general sliced-Wasserstein, tree-sliced-Wasserstein or the recent Sobolev transport – a variant of optimal transport on graphs. Note that all these approaches are Hilbert embeddable as the proposed method) in theory and/or experiments.
+ The authors should discuss the complexity of the proposed intrinsic sliced Wasserstein (and report time consumption in experiments)

questions: + The proposed ISW is a variant of sliced-Wasserstein (SW) by leveraging the eigenfunctions and eigenvalues (closely related to SW, GSW, TSW as in line 68-80; and the recent Sobolev transport – a variant of optimal transport for measures supported on graphs). The authors should compare them in experiments.
+ The motivation of using eigenfunctions (for slicing) is too vague (the authors only give a short discussion in line 179-182). I think the authors should describe its advantage rigorously in theory and/or experiments.

Some other concerns are as follow:
+ What is the relation between T in Equ. (2.1) and in Proposition 1?
+ For Proposition 6, is it hold for any kernel used in MMD? Please specify it.
+ In Proposition 8, why can one assume that C is finite? (it is not clear whether the bound is useful in Proposition 8 without this assumption)
+ For line 266-269, how to choose L, D’ to obtain infinitesimally small error estimation (e.g., to obtain error less than epsilon)?
+ For experiments, the authors should discuss the results, e.g., how to choose L, D’ (in Figure 2b) follow the results in Section 3.2 and Section 4?   

Minor:
+ In line 193-194, \eta^0 maps to H^0, but D is a norm on H’?

limitations: + The authors have not discussed the limitations of their works clearly in the text. (as mentioned in the checklist).
+ The authors have not discussed the potential negative societal impacts of their work as in the checklist.
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: It is well-known that the Wasserstein distance between two 1D measures can be computed easily. Hence, a common approach in a higher dimensional Euclidean space $\mathbb{R}^d$ consists in _slicing_ the space (formally, projecting on 1D subspaces), compute the distances on the slices, and integrating to retrieve a proper distance between the input measures. 

This work proposes to adapt this idea in the context of measures supported on a (compact) manifold $\mathcal{M}$. The key idea is to rely on the Laplacian-Beltrami operator on the manifold, which provides a collection of maps $\phi_\ell : \mathcal{M} \to \mathbb{R},\ \ell \in \mathbb{N}$ (eigenvectors of the operator), which can be used to push-forward the measures we want to compare to $\mathbb{R}$. Namely, they introduce 
$$ISW_2(\mu,\nu) = \sum_\ell \alpha(\lambda_\ell) W_2(\phi_\ell \mu, \phi_\ell \nu), $$
where $\lambda_\ell$ is the eigenvalue of the Laplacian operator, $\alpha$ is some weighting function. 

Authors then prove that $ISW_2$ defines a metric (under mild assumptions), the key aspect being that it induces a universal kernel which yields the separation property $ISW_2(\mu,\nu) = 0 \Rightarrow \mu = \nu$ (other properties are mostly straightforward). 

Once this distance is introduced, authors provide some approximation results for practical computations (e.g. we do not have access to all the $(\phi_\ell)_\ell$ and similarly just a sampling of the (projected) measures. Afterward, as this metric is _Hilbertian_, meaning that the metric space $(P(X), ISW_2)$ isometrically embeds in a Hilbert space, they design a two-sample-test between distribution supported on $P(X)$ whenever $X$ is a compact manifold. 
They showcase the relevance of their approach in different numerical experiments. 

(note : $\phi \mu$ denotes the pushforward for $\mu$ by $\phi$ here, hashtag not used due to rendering issues.)
strengths_and_weaknesses: # Originality

Using the Laplace-Beltrami operator as a way to build a "canonical" way to slice measures supported on a manifold feels pretty satisfying and is a novel idea to the best of my knowledge. 
On the other hand, one could argue that once the idea of using the Laplace-Beltrami operator to slice the measures has been introduced, most of the work (aside from the experimental section) is essentially an adaptation of standard techniques in two-sample-tests literature.

# Clarity

The paper was overall well-written. It motivates the need to consider that our measures are supported on manifold in a convincing manner (e.g. on a circle for daily event records) and aside from few paragraphs (see below), it is fairly easy to read. 

# Significance

I think this paper provides a new interesting approach that may motivate further practical developments of Optimal Transport for measures supported on non-flat domain. 

# Quality

I think this is a competent paper which introduces a new idea that may be of interest for the Optimal Transport community. 
questions: # Questions

1. In the Chicago data experiment, why is the manifold/graph structure "crucial" as stated in the Caption of Figure 4 in the appendix ? i guess that we can reasonably assume that this graph is planar in which case we can consider the measures are supported on $\mathbb{R}^2$. As far as I can tell, there is no comparison between $ISW_2$ and $W_2^{\mathbb{R}^2}$ (or a standard sliced-$W_2$, so that one has a kernel embedding and can run a two-sample-test here).
2. Related to the comparison between the $ISW_2$ and the usual Sliced-Wasserstein (assuming our manifold is embedded in $\mathbb{R}^n$, what is the computational burden in terms of running time related to the computation of $ISW_2$ vs $SW_2$ (in situations where we do not have access to the $\phi_\ell$ and $\lambda_\ell$ in close form)? I think a proper comparison of the benefits of using $ISW_2$ instead of a naive $SW_2$ is worth of interest. 

# Minor remarks and suggestions

- I think there are few typos in the Proof of Proposition 3 (some $\mathcal{H}$ should be $\mathcal{H}^0$, or $\eta$ should be $\eta^0$).
- The proof of Theorem 1 in the appendix could be enhanced (with some more precise quote of the results used in the aforementioned references). E.g. what precise statement in [17] and [12] yield the implication $\alpha(\lambda_\ell) > 0 \Rightarrow$ the kernel is universal hence characteristic? Right now, it is cumbersome to properly check the proof. A similar comment holds for other proofs as well (e.g. the proof of Theorem 2 is quite expeditious).
- In think the quantitative results mentioned in section 4.1 and detailed in the appendix should actually be mentioned in section 3.2 directly. Indeed, when reading section 3.2 at first, one may be worried by the lack of quantitative assertion there. 
- line 325 : inite-->finite (typo). 
limitations: Few limitations of the work should be discussed further. 

I did not identify ethical concern specific to this work.
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: Consider the set of probability measures on some manifold. The authors propose a new distance on this set, that behaves in some way like the sliced Wasserstein distance. This distance is defined as the weighted average of the Wasserstein distance between the pushforwards of the two measures by the eigenfunctions of the Laplace-Beltrami operator on the manifold. Some properties of this distance are given, and the distance is then used in the two-sample testing problem, where each sample is a sample of iid probability measures on a given manifold. Some numerical illustrations of the two-sample tests are then given.
strengths_and_weaknesses: Sliced Wasserstein (SW) distances have been originally proposed as computationally cheap versions of the Wasserstein distance on the Euclidean space $\mathbb{R}^D$. The idea of the original SW is the following: instead of computing the Wasserstein distance between two measures in high dimension, let us look at a certain number of "projections" of the measures on lines in $\mathbb{R}^D$; then one can compute efficiently a distance between the two measures by averaging the distance between the projections.  This paper proposes a very reasonable generalization of this idea, called the Intrinsic SW (ISW) when the support of the measure is a manifold or a graph: as lines are no longer defined, the distance is defined as an average of "projections" along the eigenvalues of the Laplace-Beltrami operator, that should describe the geometry of the manifold (and therefore replace the lines in $\mathbb{R}^D$).

The paper focuses on the notion of ''Hilbert embeddability'' to justify the use of this distance. This means that their distance $ISW(\mu,\nu)$ is actually equal to $\|\eta(\mu)-\eta(\nu)\|_H $ for some feature map $\eta$ and some Hilbert space $H$. However, the authors seemed to have miss a key link with kernel methods. Indeed, the feature map $\eta$ defines a kernel on the space $P(X)$ of probability measures on $X$ (through $k(\mu,\nu) = <\eta(\mu),\eta(\nu)>_H$), and the method they propose for the two-sample tests is the kernel two-sample test method from Gretton & al. The authors seemed to have understand partially the connection, as their proofs are adaptations of the ones from Gretton & al, but the authors have missed that they could actually directly used the results from Gretton & al, without any adaptation. 

There are other concepts defined in the paper that can be rephrased in the more standard language of kernels:
- a Hilbert centroid (def. 1) is a kernel mean embedding. 
- T(P,Q) (eq 2.1) is actually the MMD associated with the kernel on P(X) given by the intrinsic sliced Wasserstein distance.
- Most proofs corresponding to Section 4.1 can be removed: it suffices to check that the assumptions given in Gretton & al are satisfied for the kernel given by the intrinsic SW distance.

Other comments:
- The intrinsic SW distance depends on the choice of a weight function (describing the importance given to each eigenvector). Having to tune such an important hyperparameter is clearly a drawback of this distance compared to the Sliced Wasserstein distance.
- Notation in Prop.9 (in the Appendix) are extra confusing: when defining the eigenvectors of some operator (that are defined on some Hilbert space H), the variable "x" is used, whereas x was used before to note an element of the underlying manifold. As we also consider eigenvectors on the manifold, this created a lot of confusion at first.

On my grade: I put 4 so far, as I believe the link with kernel methods is not made very clear in the paper, whereas it is central to the approach proposed. I could improve my grade if this link is made more explicit (e.g. say explicitly that the test IS a kernel two-sample test and that $T(P,Q)$ IS a MMD), and if proofs are significantly shortened by using Gretton & al.'s theorems directly. Please tell me if I am missing something and if this test is not a kernel two-sample test.


questions: On the implementation:
In a lot of situations, the measures at stake will be atomic, of the form $\mu_i= \sum a_i \delta_{x_i}$. Then, it looks like the most efficient way to compute the ISW distance is to compute $\phi_k(x_i)$ for every eigenfunction $\phi_k$, and then compute the 1D matching between two 1D atomic distributions (that is we do the same as for the classical sliced Wasserstein distance). Why is this approach not at all proposed in the paper? 

On the numerical illustrations:
The authors test their procedures against other reasonable testing procedures, but not against the one that appears to be the most standard in their situation, that would be a two-sample test based on the Wasserstein distance. (that is we reject if $W_2(\mu_n,\nu_n)>\alpha$, and we accept otherwise). CLTs for empirical Wasserstein distances could probably be used to obtain asymptotic confidence levels on such a test, or one could use bootstrap or other approaches. Is there a reason for which this was not implemented (at least for synthetic experiments where the number of observations is reasonably small, so that W2 should be easy to compute)?
limitations: Yes.
review_title: null

Meta-review: metareview: In this paper, the authors propose the intrinsic sliced Wasserstein distances and a Hypothesis testing framework for the proposed measure. The idea of using eigenfunctions and eigenvalues for sliced Wasserstein is interesting. The authors addressed a part of the concerns raised by the reviewers. However, the advantage over the existing methods (sliced Wasserstein distances and MMDs) is unclear. Thus, it needs a major revision and cannot be accepted with the current version. I encourage the authors to revise the paper based on the reviewer's comments and resubmit it to a future venue.
confidence: Certain
Decision: Reject