Graph Fourier MMD for signals on data graphs
Authors: Sam Leone
Alexander Tong
Guillaume Huguet
Guy Wolf
Smita Krishnaswamy
Venue: Submitted to ICLR 2023 (2023)
Keywords: Optimal transport
Data Geometry
Graph Signal Processing

Abstract:  While numerous methods have been proposed for computing distances between probability distributions in Euclidean space, relatively little attention has been given to computing such distances for distributions on graphs. However, there has been a marked increase in data that either lies on graph (such as protein interaction networks) or can be modeled as a graph (single cell data), particularly in the biomedical sciences. Thus, it becomes important to find ways to compare signals defined on such graphs. Here, we propose Graph Fourier MMD (GFMMD), a novel a distance between distributions, or non-negative signals on graphs. GFMMD is defined via an optimal witness function that is both smooth on the graph and maximizes difference in expectation between the pair of distributions on the graph. We find an analytical solution to this optimization problem as well as an embedding of distributions that results from this method.  We also prove several properties of this method including scale invariance and applicability to disconnected graphs. We showcase it on graph benchmark datasets as well on single cell RNA-sequencing data analysis. In the latter, we use the GFMMD-based gene embeddings to find meaningful gene clusters. We also propose a novel type of score for gene selection called {\em gene localization score} which helps select genes for cellular state space characterization.

Under review as a conference paper at ICLR 2023
GRAPH FOURIER MMD FOR SIGNALS ON GRAPHS
Anonymous authors Paper under double-blind review
ABSTRACT
While numerous methods have been proposed for computing distances between probability distributions in Euclidean space, relatively little attention has been given to computing such distances for distributions on graphs. However, there has been marked increase in data that either lies on graph (such as protein inter- action networks) or can be modeled as a graph (single cell data), particularly in the biomedical sciences. Thus, it becomes important find ways to compare sig- nals defined on such graphs. Here, we propose Graph Fourier MMD (GFMMD), a novel distance between distributions and signals on graphs. GFMMD defined via an optimal witness function that is both smooth on the graph and maximizes difference in expectation between the pair of distributions on the graph. We find an analytical solution to this optimization problem as well as an embedding of dis- tributions that results from this method. We also prove several properties of this method including scale invariance and applicability to disconnected graphs. We showcase it on graph benchmark datasets as well on single cell RNA-sequencing data analysis. In the latter, we use the GFMMD-bar -bssed gene embeddings find meaningful gene clusters. We also propose a novel type of score for gene selec- tion called gene localization score which helps select genes for cellular state space characterization.
INTRODUCTION
With the advent of high dimensional, high throughput data in fields ranging from biology, to finance, to physics, it becomes important to develop methods to perform high dimensional statistics in this sphere. In particular, the analysis of signals (or features in the data) and their pattern of spread through the landscape of data poses challenge. If the signals act as functions on low dimensional space like R 3 it is possible to visualize them to gain a sense of the data. But what if these signals act on higher dimensional space like R9000 This could easily be the case in practice when set of observations carries many variables, such as single-cell data. In order to handle data like this, one useful assumption has been that the data lies intrinsically in lower- diver-dimensional manifold M, ie., the Manifold hypothesis. This hypothesis has motivated low -iw-dmmnniional embedding algorithms such spectral clustering (Ng al. 2001), 1SNE (van der Maaten & Hinton 2008), diffusion maps (Coifman & Lafon 2006), and PHATE (Moon et al., (011). In such algorithms, the data is first converted an affinity graph, found by first computing distances between data points, and then affinities using a kernel function on the distances. This allows us to represent high dimensional data in simpler form. Here, we use this representation signals on such high dimensional data graphs called Graph Fourier Maximum Mean Diserepancy (GFMMD). Note, that GFMMD can also work on signals that naturally arise from graph or network structures, i.e., features of people in social interaction graphs.
propose a distance between distributions or
Thus far while GNNs and other methods have focused on organizing and classifying nodes, there has been little focus on organizing the variables / signals themselves on these abstract spaces. For instance, in many measurements or sensors whose structure can be modelled as a graph, there is a need to understand the relationship between measured features. One example that arises in biology is that of single cell data. Here the cellular manifold can be modelled as a nearest neighbors graph, and each cell has measurements of thousands of genes, and there is great deal of interest in under- standing the relationships between genes and how and whether their expression is localized to parts of the cellular manifold.

---

Under review as a conference paper at ICLR 2023
Here address the question of how to organize and compare signals on graphs in such way that accounts for geometric structure on their underlying space. In particular, given a weighted graph g (V,E, w) and set of functions {fi); on the vertices: f. V + R. how can structure and analyze these signals? We will first consider the case when fs is a probability mass function and extend the framework arbitrary signals. This has very natural applications many modern datasets. To illustrate this, we focus on the application of embedding set of genes on a graph of cells, as created from single cell RNA-sequencing data, and also in measuring whether the expression of a gene is localized (i.e., characteristic of a subpopulation of cells) or global like house-keeping gene.
We present a new distance that belongs to the family of integral probability metrics (Sriperumbudur jet al. 2012). Integral Probability Metrics (IPM) are distances between probability distributions that are characterized by witness function that maximizes the discrepancy between distributions expectation. The Maximum Mean Discrepancy (MMD) (Gretton et al., (012) distances are a popular class of IPMs, they assume further structure in the space of witness functions, requiring that they come from a reproducing kernel Hilbert space.
Our notion of MMD, that we call Graph Fourier MMD (GFMMD), is distance between signals on a data graph that is found by analytically solving for an optimal witness function. Furthermore, through the use of Chebyshev polynomials (Mason & Handscomb 2002). GFMMD can be com- puted rapidly, and has a closed-form solution. We demonstrate its potential on toy datasets as well as single cell data, where
it to identify gene modules.
Our main contributions are as follows: 1) We define Graph Fourier MMD as a distance between signals on arbitrary graphs, and prove that it is both integrable probability metric and maximum mean discrepancy. 2) We derive an exact analytical solution for GFMMD which can be approxi- mated in (n n + m²)) time calculate all pairwise-distanee is the number of vertices of the graph and m is the number of signals. 3) We derive feature map for GFMMD that allows for efficient embeddings and dimensionality reduction. 4) We provide an efficient Chebyshev approximation method for computing GFMMD among a set of signals. 5) We showcase application of GFMMD to single cell SeNuueequnn data.
between distributions, where n
1.1 RELATED WORK
Spectral methods, such as (Coifman & Lafon 2006; Belkin & Niyogi 2003 Bronstein & Bronstein, 2010), define an embedding of the nodes of graph using the eigendecompostion of graph operator the graph's 's spectral properties
(Laplacian diffusion operator). Similar to these methods, to define an embedding of signals on the graph, and we show that this embedding preserve an MMD distance between signals.
The closest related work is that of Diffusion EMD Tong et al. (202)) which involves diffusion graph signals to different scales using a diffusion operator (similar to that of a diffusion map Coif- man & Lafon| (2006)) to create multiscale density estimates of the data. Then Diffusion EMD computes weighted 7.* distance between the multiscale density estimates of different signals. While this method is faster than most primal methods for EMD computation, it can be inaccurate unless the graph is significantly large.
Earlier methods that have been proposed for empirical estimations of high dimensional EMD include the Sinkhorn method Cuturi (2013), which involves Sinkhorn iterations (repeated normalization) of a joint probability distribution to converge at distribution that describes a valid transport plan, i.e. whose marginals agree with the two empirical distributions. The authors of (Solomon et al., 2013) Huguet et al. 2022) extent the Sinkhorn algorithm to graphs with a heat-geodesic ground distance. Their algorithm can be computed efficiently for two signals on a sparse graphs, but does not provide an embedding of signals.
In (Le et al. 2022 2019 Essid & Solomon 2018), 3) the authors consider the EMD between distribu- tions defined node to another. The authors (Le et al. [022] 2019) provide a closed-form solution that relies on graph shortest path distance. In this setting, there is sparse approximation to diffusion distances in terms of graph shortest path. We consider a different problem where the edges of the graph are affinities.
distance graph, that is the edge weights define the cost of moving mass from one
2

---

Under review as a conference paper at ICLR 2023
Among methods for MMD, the most common method has been sampling based method that also forms a 2-sample Kernel test based on defining a kernel between empirical observations Gretton et al. 2012)) Note that semantically this takes distances between point clouds themselves by mod- eling them as a data graph with vertices as points. We define a method of taking signals which arbitrary graph,
point cloud otherwise, and demonstrate its effectiveness both when the graph lies in a metric space and when adjacencies are binary. We compare our method GFMMD all three of these methods.
generalizes
PRELIMINARIES
Integral probability metries IPMs (Müller 1997 Sriperumbudur et al. 2012) constitute a fam- ily of distances between probability distributions. They are often used when dealing with em- pirical samples (datasets) sampled from a continuous space. In contrast, the alternative class of o-divergences (such as KL-divergence) is often less useful as measure between empirical sam- ples with poor behavior when the domains do not overlap. In contrast to d--divergences, integral probability metrics are defined over a metric space, this allows for reasonable distance between distributions with non-overlapping support.
Definition 1. Given a metric space (X, d), a family F of measurable, duuncit on X, and two measures P and Q on X, the IPM between P and Q is defined as
(F(P,Q) sup - EQ().
fEF
Here, F is family of "witness function" since it emphasizes the differences between P and Q, choosing a certain F determines the IPMs.
Maximum Mean Discrepancy H is Reproducing Kernel Hilbert Space (RKHS) of functions xc), on X' (equipped with norm (l)))) then the IPM corresponding to F = {f I| I 1} is a kernel Maximum Mean Discrepancy (Gretton al. (012). Numerous distances between distributions IPMs, given a suitable choice of F. For example, the Wasserstein distance is an IPM where F corresponds to the family of Lipschitz functions.
Computing MMDs in practice could be difficult. Algorithms like Kernel MMD rely on the fact that kernels induce such RKHS, and vice-versa. can be shown that, for given positive definite kernel k X' x X + R. there exists RKHS H. in which, Vf E H. f(x) = (f. k(z, ,)H So in particular, (k(y. -), k<xx,
k(x.8) y)-
Definition 2. Let k(.,,) be a positive definite kernel and H is the Hilbert space in which (f,k(z, ") fxx) for all f E H. The mean embedding of probability distribution P is de- fined as [k<p( )), and the Maximum Mean Discrepancy between P and Q is defined to be (MD(P,Q) sup 51 [F(() RQ(s)-
As consequence of the Cauchy-Schwarz Schwarz inequality. it can be shown that MMD(P, Q) = =|ıp [ollæ 1l Kernel MMD (Gretton et al. 2012) works by estimating the norm the RKHS with the empirical mean embeddings defined by the kernel k(.,,)
||rp -uell
x(X,')++ E KOY,Y') - XXX
R(X,)). X-PY-Q
Y.-O
Example 2.1. X and Y Q are two point clouds of size m and n, we can approximate the distance MM Q) by approximating the expectations with empirical means
m
m
n
n
m
Σ
(x)) + nln
k(y,, My)
k(a,,
m(m
mI
Note that, in practice this quantity often computed by random sampling with replacement from the point clouds X and Y

---

Under review as a conference paper at ICLR 2023
Wasserstein Distance The Earth Mover's Distance (EMD), also known the I-Wasserstein dis- tance, is a distance between probability distributions designed to measure the least amount of "work" it takes to move mass from one distribution to another. Formally, we given two distributions P and Q on a measure space (Ω, Jo) and a distance d X' x X' + R. Most commonly, Q might be a Riemann manifold, Rd, or in case, finite graph. We define the space of couplings of P and Q, denoted I1(P, Q) to be the set of joint probability distributions whose marginals are equal to P and Q.
Definition 3. The 1- 1-Wasserstein Distance between P and Q is defined be:
W(P.Q) - min =ET((P.)) / Jxxx ((r,)))(,,)))
The supremizing joint distribution π would then be called the optimal transport plan. In the case that 92 is finite (say of size n). [I, Q) could be thought of the set of n x matrices for which m1 = P,1 = Q. Then we could represent distances in a ri x n matrix D, and the EMD is given by min, D. Typical solutions to EMD in its primal form are found using linear programming. A well known theorem in the study of optimal transport is the Kantorovich- Rubbinsttn Duality, which provides an equivalent expression for the Wasserstein Distance based on the dual optimization. Let- ting |lfl| s1 symbolize the condition that f obeys a 1-Lipschitz constraint: in other words, that for all I. X, (f(x) f(y) S d(x, y)-
form
Theorem 1.
The EMD is an IPM with F the space of I-Lipschitz,function
W(P,Q) = sup (f( - EQ(
Illl
We refer to Dudley (018) for a proof of the previous theorem. Intuitively, we can think of suitable functions being varying slowly over X. The I-Lipschitz constraint prevents witness functions from behaving too erratically over the space. Then calculating the Wasserstein distance is equivalent solving the above linear program. In the discrete case, we trying to maximize (J, P) () subject to (ʃ(a) - s(b)] s d(a,) b) for all a, b E V.
The Graph Laplacian For weighted graph = (V,E, E, w) vertices, we have number of associated matrices. The first of which is an adjacency affimity matrix A for which, given vertices and b. A (a, b) w(a, b); for our purposes, we assume w(a, b) 2 0. In the case when V belongs to a metric space (X' d), we have an associated distance matrix M for which M(a, b) = d(a, b) for all 6 E V. Oftentimes, the affinity matrix A is generated by a nonlinear kernel function k(-) so that A(a b) = k(M (a, b)). For our purposes, if A is generated in this way, we will call G affinity graph. There also a diagonal degree matrix for which D a) EbEV w(a, b). Finally, we define the combinatorial Laplacian L = D - A. It can be shown that for any function on the vertices f. Lf E(amer w(a (f())))
positive semi- definiee with spectrum ()x, 1/s )/= (such that A; is nondecreasing in i). In fact, the dimension of L's 's kernel is equal to the number of connected components of G. In particular, L1 = O, where the all I's vector. If G is fully connected, then 1 spans the kernel of L. Since L is positive semi- definite, it diagonalizable with an orthonormal set of eigenvectors, so we may write = WATT where A diag do A1 >1...>am An-1) and v = (v/p 8/1 ... 11) Then the Graph Fourier Transform of a function f V- + R is defined as f f= TT Similarly, for any function : {A+}s + RR we can define the graph filter H : f En= ((A)) = Uh(A)4" f. As matter of notation, the L refers to the Moore- Penroee inverse of L and L-1/2 is defined as V -1/2gTT where -1/2 is obtained by taking the elementwise reciprocal square roots of positive entries of A, and leaving the zeros is.
From this identity, it's clear that
3 METHODS
In the following, with present definitions and theorems for arbitrary probability distributions P and Q. but our theory can be extended to any real bounded signals, the expectations would be replaced by the integrals w.r.t. a finite (signed) measure.
4

---

Under review as a conference paper at ICLR 2023
3.1 GRAPH FOURIER MMD AS AN OPTIMIZATION
For Graph Fourier MMD in a metric space, we are given a finite affinity graph 9 = (V,E,d) on a metric space (X, d). We are also given two probability distributions P,Q - R (where each node comes with a given probability). If we were to take the I-Wasserstein distance between P and Q. the dual form would yield:
W(P. Q) max(s, P Q) subject to
d(a, d(a, ((()) s Va
Now, we will augment the above constraint. Instead, we impose the new relaxed constraint that L(o,)E No.by= (f(a) - f(b)² < T for some threshold T. Note that if w(a, b) 1/d(a, b)². then this condition is equivalent to fTL < T. The constraint f S T is valid for any way of calculating the affinity and result in a closed-form solution. It as a similar interpretation than the I-Lipschitz as quantifies the smoothness of a signal on a graph with respect the affinities. For example, if we assume that our data lies on a manifold, we can choose a different level of affinity, such as w(a, b) = cxp(-d(a, b)2//20* ) to penalize transport over larger global distances. Thus, we define our distance between P and Q only in terms of L. In the following, we only assume that the affinities are nonnegative.
Definition 4. Let 9 (V, w) be a finite graph with Laplacian L and P.Q be two bounded probability distributions on V. For T E IR+,, the Graph Fourier MMD between P and Q is
GFMMD Q) A max
Tp(s) - (f(s).
Note that this definition holds for any construction of a positive semi-definite Laplacian matrix L and chosen T.
Theorem 2. Let G, L, be as defined in Definition Fand let G be fully connected. Then, any two bounded probability distributions P and Q defined on V. GFMMD(P, Q) = vT 2 Q)1 where || is the lg norm in R..
Proof. P and Q can be viewed vectors indexed over V so that, for any function ʃ V R. (f) - E²(s) = (P - J) Additionally, note that for any function f, we can write f= fi + fz. where fi is orthogonal
the 1 vector (so fi E C(L)) and fz ker(L) the kernel of L. Since ker(L) is 1. we have f2 = cl for some C E R. Then, Ep(f) - Ef(
Er(fi) - (f)
(f(
Ro( = (fi - (f) + (cl) + (cl)
= Er(s))
Bo(fi) + cl cl (f) BQ(fi). Thus, for any such f, it can be assumed, without loss of generality, that f T
G disconnected, we can still assume that f ker(L), but this is more technical and will be omitted for now (see Theorem I.I.I). In particular, it can be assumed that LL f where L is the pseudo-inverse of L. Note f Lf < T if and only if [L à fl I VT. Thus, we can rewrite the optimization as max(P Q, 7TL VT
L.å f) where the maximum is over {f L fl < 1). Doing a change of variables of L f to x, then from the Cauchy Schwarz
Inequality, we have GFMMD(P, Q) VT /T (L (P Q). x) = VT }(P Q)Il as desired.
Note that the assumption that & is connected was key to this proof. These concerns addressed in Theorems A. and Corollary 1.2 Since P-Q ş C(L) if and only if ((P-Q). I(Cx)) = 0 for all connected components kt, this condition can be easily checked in practice. GFMMD possesses a set of convenient properties. Namely, we have a representation in terms of an explicit feature map L 2, So to compute pairwise distances, it is sufficient to apply the feature map and then take Euclidean distances. Also, the distance value is bona fide distance (particularly an MMD), and is also preserved under certain graph manipulations. These are the results of Lemmas 3 and E
Lemma 3. (i) GFMMD(-..) defines a valid distance on the probability distributions acting on V. Furthermoe, (ii) GFMMDg(PP Q) is Maximum Mean Discrepancy with explicit feature map VTL-1.
Proof. For (i), note that L L- Q) is linear. By the usual nonnegativity of lengths, GFMMD(P, V L-t 2 0, so GFMMD(:-)) is nonnegative. Furthermore,
5

---

Under review as a conference paper at ICLR 2023
note that GFMMD(P, Q) if and only if = L. But since P and Q sum to L, -- as
injectively on the set of functions orthogonal to its kernel, so P = Q. Thus, GFMMD (P. () 2 0, with equality if and only if P Q. Finally, the triangle incquality holds, since for arbitrary prob-
ability densities P.Q, R. GFMMD(P,
VTIL--L - L =11 S
-
R| +
VTIL- L- equality in f.. Thus, GFMMID is valid distance acting probability distributions. For (ii), by definition, an MMD y between P and Q takes the form (P.Q) = =sup [l [f( (f),
+ R|] = GFMMD(P, R) + GFMMD(Q, R) follows from the usual triangle in-
where H is some Hilbert Space and {f [Ifll S 1) corresponds to the unit ball. we define a
Hilbert space on & with (z, you 7 FL y, follows that [f Il I 1 corresponds L' < T.
Thus, GFMMD(..)) possesses the form of a valid MMD. Therefore, this distance is also an IPM. 0
Note that if we choose our parameter T in such way that it is proportional to the total degree of the graph, we may rescale our affinities however we like without affecting the underlying distance. This is the claim of Lemma 4
Lemma 4. If = (V,E,w) and g' = (V,E, cw) are finite, fully connected graphs with c E R and T is chosen to be proportional to the total degree of the graph, then GFMMDg(P,Q) GFMMDg Q). In other words, Graph Fourier MMD is scale invariant.
Proof. This follows from the fact that a matrix scales inversely with its pseudo-inverse. If is proportional to the total graph degree T x E. D(a, a), then we define T = k E, D(a,a), a). In particular, if L, L' are the Laplacians of g and G', then all of the following hold: L cL,T
L, T" L'
LL_ so (T) | (P- Q)I = VTIIL) Q)l-- And we conclude GFMMDg (P,Q)
k eT cf. Also note (L') (cL)
QII = VCT 1L
GFMMDg (P.Q)
nice corollary of Lemma that if our affinities satisfy w(a, b)/d(a, b) g(c) for some function g of c. then GFMMD is invariant under rescaling of distances well. For instance, by doubling all points V. the GFMMD between two distributions remains the same. Moreover, we were to choose encode each vertex of G the Kronecker delta 6a, then the corresponding embeddings for each vertex would be familiar. In fact, the best k-dimensional representation (by multidimen- sional scaling) of the vertices will coincide almost exactly with Hall's ' Spectral Graph Drawing (Hall) 1970). which uses the first & nontrivial eigenvectors to represent vertices using coordinates T This is made formal by Theorem 5 which proof is presented the Appendix.
Theorem 5. Xf = (ōv is a family of Kronecker-delta functions centered at each vertex of G, then the k-dimensional embedding which best preserves the distances between signals in X is equivalent up to rescaling to Hall's 's Spectral Graph Drawing of the Graph G in k-dimensions.
3.2 COMPUTATIONAL COMPLEXITY AND SPEEDUP
Computation of exact GFMMD is O(n²) as it requires computing the pseudo-inverse of L. The space complexity is On²²) for since it requires representation of the full distance matrix. However, with some minor modifications we can greatly reduce the time and memory requirements in the particular case where the graph G is sparse i.e. EE| = Onn log n). In such cases, we present an On log n) algorithm for the computation of GFMMD which is substantially faster than naive im- plementations based on a Chebyshev polynomial approximation the filter Algorithm I as well KNN kernel. The steps for an arbitrary graph are the same, but with W provided.

---

Under review as a conference paper at ICLR 2023
Algorithm 1 GFMMD in Metric Space
Input: A set of n points X C RR m probability distributions f; X + R in an n x m matrix F, and a kernel function l X
R
Output: An m X n embedding matrix E in which |, E,yl GFMMD fy). M and distance matrix which M GFMMD((i.
Create a thresholded K-Nearest Neighbor graph & over X with On log n) edges Wij t k(X,, XX)) for all (i.j) E
L - D W. where D the matrix whose diagonal is the row sums W. E; < L f either by Chebyshev approximation of the filter ((A) = X
My E; Ejll for all i, E [n]
return M, E
This gives a total fine grained time complexity of ((k) +-)nn log kynm log m) and space com- plexity of On log m-) space. Here, f is the order of the Chebyshev polynomial, 1 is the thresh- old for number of nearest-neighhors in constructing G. and h/ the number of nearest-distributions we' d like to calculate. More simply, for fixed Chebyshev order, and number of neighbors, the time to estimate distances between all distributions is On log n + nm²).
4 EMPIRICAL RESULTS & APPLICATIONS
In experiments, signals always nonnegative and normalized to be interpreted as probability distributions. However, while Graph Fourier MMD is developed in the case in which and Q are regarded as signals representing probability distributions, we may take distances between any two bounded signals P and Q shared graph via GFMMD(P, Q) 112 Q)
4.1 IDENTIFYING DISTRIBUTIONS ON THE SWISS ROLL
In this experiment, generate random point clouds centered at points on the swiss roll. More specifically, we sample = 100 points on the swiss roll ø1, . Fn and rotate the coordinates into 10-dimensional space. Then, around each of these points, we generate a point cloud d, of size m = 100 points from multivariate normal distribution centered at a;. The result is nm points in 18 For each i E [n]. we have known geodesic distance between x; and Zy.- Across the different measures, we can see how well the distance between the point clouds d, and d, compares to the geodesic distance between their corresponding centers I; and Zy. We generate a common data graph with nm vertices and consider a family
probability distributions pa(x)) = m 1 E de) We compare the distributions using: 1) computation of earth Mover's Distance between point clouds in ambient space, 2) Sinkhorn algorithm (Cuturi) 2013). 3) Diffusion EMD (Tong et al.] [2021), 4) Kernel MMD (Gretton al. 2012) between all pairs Ps: Py via random sampling (20 points from each distribution with replacement). 5) Graph Fourier MMD between Pi, Pj. using both the exact
calculation and approximation via Chebyshev polynomials. Results are shown in Table [
Graaue Trail Datanca
Iesand DACANA
Figure 1: Left: first two PCs of the embeddings E from Algorithm D. colored by the coordinate of the corresponding center along the curved direction of the swiss roll. Right: Geodesic distance between centers vs. corresponding distance between distributions
By plotting true geodesic distance between centers against distance by each of these methods, we can assess the corresponding method accuracy. On the left of Figure Tis EMD, where the oscillatory pattern illustrates its ineffectiveness at calculating distances between distributions Euclidean distance between points on the swiss roll has periodic behavior in curvature. Diffusion EMD and Kernel MMD effective taking distances between points initially, but fail to discern
graphs, since
7

---

Under review as a conference paper at ICLR 2023
Method
Spearman-p
10-NN time (s)
All-pairs time(s)
DiffusionEMD
0,584 = 0.017
2.171 0.265
3.341 + 0.333
Exact
0.253 + 0.022
26.881 + 1.104
26.881 + 1.104
Sinkhorn
0.250 + 0.022
54.346 + 17.576
54,346 = 17.576
0.509 + 0.021
5.016 0.237
5.016 0.237
Graph MMD (Exact)
0,613 + 0.019
139,453 + 16.790
139,468 = 16.794
Graph MMD (Chebyshev, 8)
0.606 = 0.024
0.619 0.057
0.641 0.056
Graph MMD (Chebyshev, 64)
0.593 = 0.021
1.155 = 0.035
1.163 + 0.035
Graph MMD (Chebyshev, 512)
0.612 + 0.018
6.249 2.896
6.258 2.895
Graph MMD (Chehyshev, 4096)
0.612 + 0.018
48.138 + 1.184
48.159 + 1.182
Table 1:
Comparison of runtime and Spearman-p correlation to ground truth manifold distances between distributions with mean = standard deviation over 10 seeds for 100 distributions of 100 points each on a swiss roll manifold. The exact Graph MMD is most performant but requires a disen-decomposttion. The Chebyshev approximated Graph MMD (Chebyshev, t) is extremely fast and almost as performant at even lower orders I.
between higher and higher distances. Graph Fourier MMD, on the other hand, has a far more clear linear correlation, which levels off much slower. If instead of taking the distances in the embedded space between distributions, we could take the embeddings and project them to a low dimensional space by running PCA on the matrix VTL-1/22 where X = =d1 d2... dn]. We would therefore obtain the best lower dimensional linear embedding in which distances between distributions approximates their distance according to Graph Fourier MMD. By taking the first two PCs of the embedding and coloring by the curvature coordinate of corresponding distribution center, we find that we are highly effective at capturing geometry of the underlying manifold.
4.2 SINGLE CELL ANALYSIS WITH GFMMD
To demonstrate the utility of Graph Fourier MMD for biological analysis, we leverage publicly available single-cell RNA sequencing dataset of CD8-positive cells (Zheng et al. 2017). CD8- positive T cells are adaptive immune cells known to be critical for mediating immune response in infection, cancer, and other diseases. This dataset consists 9,167 cells with 1,991 highly variable genes each cell. Then we apply Algorithm T with the adaptive Gaussian Kernel (Moon et al,, 2019) between datapoints, to compute GFMMD between genes, resulting in an 1991 x 1991 matrix of distances. Here viewed each gene distribution nearest neighbor cell graph. We also obtain E which is an 1991 x 9167 matrix containing an explicit feature map or embedding of the genes. In Figure A we visualize the gene embedding using both PCA and PHATE (Moon et al./ 2019). We find that clusters 0- 9 in from the gene embedding, show characteristic expression on the cellular embedding in Figure BB. In other words, the subplots in Figure 2 represent a PHATE map of the cells in this dataset, and when we highlight the expression of gene clusters on the cells we see that these clusters have localized expression on the cellular manifold.
To interpret these gene clusters for biological significance, we amalyzed the gene set enrichment of clusters 6 and with Enrichr (Chen al.) 2013), which show high expression in opposite ends of the cellular manifold (see Figure 2 Enrichr shows that cluster 7 has strong enrichment for signatures of naive T cell becoming activatied with mitosis and T cell activation signatures being significant. On the other hand, cluster 6 shows strong enrichment for effector CD8 T cell, with signatures of cytotoxic activity and inflammatory signaling (interferon gamma). Thus, these genes can be used to characterize the cellular manifold as following trajectory from naive effector CD8 T cells. We compare these to gene clusters derived from DiffusionEMMD, as well as to a more standard method of gene selection in biology: differential expression of genes in different areas of cellular state space based on a Wilcoxon rank sum test between the two manually curated cell clusters from Zheng et al. (017). The gene clusters 4 and 8 from DiffusionEMI that were most enriched on the opposite ends of the manifold consisted of 6 genes and 11 genes, which resulted in no enrichment for the above signatures. These genes upregulated based on the Wilcoxon rank sum test give much less clear picture of the cellular state space, with the same annotations scoring much lower.
8

---

Under review as a conference paper at ICLR 2023
Outtring Gens Space
C.
Elidor Signnaess
the harkwo
Combined Goore
Nakee Skyakures
B.
Bae Duile?
Peetive lng delee
Toll adiiaiion
Combined
Figure 2:
Embeddings genes datasct from Zheng et al. (017 computed by the GFMMD
gorithm, visualized with PCA and PHATE (Moon et al. 2019). colored by results of K-mcans clustering. B.
Embeddings of cells from Zheng et al. (2017) visualized with PHATE. Each plot is colored by the average from Enrichr (Chen
expression of genes in the marked cluster over cells. C. C
To thet Lackeaak
Sat tooaleed
at 2013) on T-cell relevant annotations, between GFM
$7.96
expression-based gene sets.
Local Genes A novel type of analysis en- abled by GFMMD is a search for localized sig- nals. Often, researchers in the single cell field search highly variable genes, but we posit that genes that have localized expression lar manifolds can be used to characterize salient cellular subtypes. We propose measure of gene locality by GFMMD between the gene signal and a uniform distribution on the graph.
Density
cellu-
10
10'
Localization
We visualize the 1st, 10th, 100th, and 1500th most local genes the cell graph. In- deed, we find the expected behavior. Density plots for localization scores, comparing housekeeping genes and naive CD8+ T cell signature. The naive gene signatures given by the red curve and Housekeeping gene signatures by the gray.
Figure 3:
Definition 5. The gene localization score, s of gene described by distribution P on the cel- lular data graph as: s(p) GFMMD(PP U).
Here, U = = on the same vertex set.
Theorem 6. The localization score 8 can be computed s(p) GFMMD(P,U)
| PII-
Proof. Since 1 the kernel of L (and thus L ), we have GFMMD(P,U) = P
[L PII.
Based on this score, in Figure 3 we visualize first most local gene, 10th most local gene, and 20th most local. Here, we compare localization scores between housekeeping genes and the gene signature for naive CD8+ T cells. Housekeeping genes are expressed highly in many systems, but are not known to have a function that contributes strongly to cell-cell variation for T cells Eisenberg & Levanon| (2003); Wang et al.) (2021): de Jonge al. (2077). By contrast, cells enriched for the naive CD8+ T cell signature are a subset of T cells along the T cell differentiation axis. We show that the localization score is order of magnitude higher for the naive gene signature versus the housekeeping signature Figure validating our intuition about localized genes.
5 CONCLUSION
In this paper we have introduced Graph Fourier MMD, framework for taking distances between signals on graphs and generating embeddings in which these distances hold. We have shown its intuitive performance in both the Riemannian and abstract graphical setting for known distributions. as well as its advantage in speed, and ability to capture global properties of the underlying data manifold compared alternative methods like Earth Mover's Distance and Diffusion EMD. Its rapidity makes particularly useful for high dimensional datasets, such as single cell data, where have showed its ability capture the natural trajectories of gene expression.

---

Under review as a conference paper at ICLR 2023
REPRODUCIBILITY
In the experiments, the main libraries which were used were Pygsp to generate, store, and manipulate graphs. This includes key functions such as filter, which we use for both the exact and Chebyshev ap- proximated version of Graph Fourier MMD. This library includes the toy datasets which were used, including the grid graph (section 4), Minnesota graph, and Bunny graph. Source code for imple- mentation of Graph Fourier MMD and the swiss roll experiment (section 4.1) is located GitHub ppppensccinnce//rrappa Paaprr/Graaaa-uiier-r-rrr Bouurer--MMDSSC
For the biological experiments, at https//anonymous.. calculated using k-nearest neighbors upon centering and normalizing the cell-cell affinities data matrix of gene expression in each cell.
REFERENCES
Mikhail Belkin and Partha Niyogi. Laplacian eigenmaps for dimensionality reduction and data representation. Neural computation, (5(6):133-11399 2003.
Michael M Bronstein and Alexander M Bronstein. Shape recognition with spectral distances. IEEE Transactions Pattern Analysis and Machine Intelligence, (3(5):1665-107) 2010.
Edward Y Chen, Christopher M Tan, Yan Kou, Qiaonan Duan, Zichen Wang, Gabriela Vaz Meirelles, Neil R Clark, and Avi Ma' ayan. Enrichr: interactive and collaborative HTML5 gene list enrichment analysis tool. BMC Bioinformatics, 14(1):128, April 2013.
Ronald R Coifman and Stéphane Lafon. Diffusion maps. Applied and computational harmonic analysis, 21(1):5-30, 2006.
Marco Cuturi. Sinkhorn distances: Lightspeed computation of optimal transport. Advances in neural information processing systems, 26, 2013.
Hendrik M de Jonge, Rudolf S N Fehrmann, Eveline $ M de Bont, Robert M W Hofstra, Frans Gerbens, Willem A Kamps, Elisabeth G de Vries, Ate G J van der Zee, Gerard J te Meer- man, and Arja ter Elst. Evidence based selection of housekeeping genes. PLoS One, 2(9):e898, September 2007.
Richard M Dudley. Real analysis and probability. CRC Press, 2018.
Eli Eisenberg and Erez Y Levanon. Human housekeeping genes compact. Trends Genet., 19(7): 362-365, July 2003.
Montacer Essid and Justin Solomon. Quadratically regularized optimal transport on graphs. SIAM Journal on Scientific Computing, 40(4):A1961-A1986 2018.
Arthur Gretton, Karsten M Borgwardt, Malte Rasch, Bernhard Schölkopf, and Alexander Smola. A kernel two-sample test. The Journal of Machine Learning Research, 13(1):723-773, 2012.
Kenneth M Hall. An r-dimensional quadratic placement algorithm. Management science, 17(3): 219-229, 1970.
Guillaume Huguet, Alexander Tong. María Ramos Zapatero, Guy Wolf, and Smita Krish- naswamy. Geodesic sinkhorn: optimal transport for high-dimensional datasets. arXiv preprint arXiv:2211.00805 2022.
Tam Le, Makoto Yamada, Kenji Fukumizu, and Marco Cuturi. Tree-sliced variants of wasserstein distances. Advances in neural information processing systems, 32, 2019.
Tam Le, Truyen Nguyen, Dinh Phung, and Viet Anh Nguyen. Sobolev transport: A scalable metric for probability measures with graph metrics. In International Conference on Artificial Intelligence and Statistics, pp. 9844-9868. PMLR, 2022.
John C Mason and David C Handscomb. Chebyshev polynomials. Chapman and Hall/CRC, 2002.
10

---

Under review as a conference paper at ICLR 2023
Kevin R. Moon, David van Dijk, Zheng Wang. Scott Gigante, Daniel B. Burkhardt, William S. Chen, Kristina Yim. Antonia van den Elzen, Matthew Hir,, Ronald R. Coifman, Natalia B. Ivanova, Guy Wolf, and Smita Krishnaswamy. Visualizing structure and transitions in nigh-dimensional biological data. Nature Biotechnology, 37(11))1442-1444 1482-1492, December 2019.
Alfred Müller. Integral probability metries and their generating classes of functions. Advances in Applied Probability, 29()):299992 1997.
Andrew Ng, Michael Jordan, and Yair Weiss. On spectral clustering: Analysis and an algorithm.
Advances in neural information processing systems, 14, 2001.
Justin Solomon, Fernando De Goes, Gabriel Peyré, Marco Cuturi, Adrian Butscher, Andy Nguyen, Tao Du, and Leonidas Guibas. Convolutional wasserstein distances: Efficient optimal transporta- tion on geometric domains. ACM Transactions on Graphics (ToG), 34(4):1-11, 2015.
Bharath K Sriperumbudur, Kenji Fukumizu, Arthur Gretton, Bernhard Schölkopf, and Gert RG Lanckriet. On the empirical estimation of integral probability metrics. Electronic Journal of Statistics, 6: 6:1550-10 1590,15992000 2012.
Alexander Y Tong, Guillaume Huguet, Amine Natik, Kincaid MacDonald, Manik Kuchroo, Ronald Coifman, Guy Wolf, and Smita Krishnaswamy. Diffusion earth mover's distance and distribution embeddings. In International Conference Machine Learning, pp. 10336- 10346. PMLR, 2021.
Laurens van der Maaten and Geoffrey Hinton. Visualizing high nigh-dimensional data using t-SNE. Journal of Machine Learning Research, 9:2579-2605, 2008
Xiliang Wang, Yao He, Qiming Zhang, Xianwen Ren, and Zemin Zhang. Direct comparative anal- yses of 10X genomics chromium and smart-seq2. Genomics Proteomics Bioinformatics, 19(2): 253-266, April 2021.
Grace X Y Zheng, Jessica M Terry, Phillip Belgrader, Paul Ryvkin, Zachary W Bent, Ryan Wilson, Solongo B Ziraldo, Tobias D Wheeler, Gcoff P McDermott, Junjie Zhu, Mark T Gregory, Joe Shuga, Luz Montesclaros, Jason G Underwood, Donald A Masquelier, Stefanic Nishimura, Michael Schnall-Levin, Paul W Wyatt, Christopher M Hindson, Rajiv Bharadwaj. Alexander Wong, Kevin D Ness, Lan W Beppu, H Joachim Deeg, Christopher McFarland, Keith R Loeb, William J Valente, Nolan G Ericson, Emily A Stevens, Jerald P Radich, Tarjei S Mikkelsen, Benjamin J Hindson, and Jason H Bielas. Massively parallel digital transcriptional profiling of single cells. Nat. Commun., 8( 8(1):14049, January 2017.
A APPENDIX
A.1 PROOF OF STATED RESULTS
A.1.1 PROOF THEOREM A.I.I
Theorem Let C(L) be the column space of L. Then P & C(L) if and only there exists a connected component C' of G such that Exec P Eiec Q. Furthermore, if d is distance acting when
on V and L is constructed so that w(a.b) = 0 when d(a, b) co, then W (P,, Q)
P - Q & C(L).
Proof. Note that if C.... Cm are the connected components of G, then the kernel of L is spanned by the mutually orthogonal vectors I(C1} ..CC)...I(C.)). I(C2). First, if there exists a connected component C₃ such that Eaec, P(a) # Eaec, Q(a), then,
[.C)). Q) 20 00
And we are done: P - Q has nonzero component in the kernel L. On the other hand, if L has a nonzero projection in the kernel of I., this will be witnessed by some function in the basis. Thus, one

---

Under review as a conference paper at ICLR 2023
of our basis functions [[Ck} } (for some k) will satisfy -P)))) # 0, so looking the corresponding
connected component Ck.
Σ aECk
P(a)
P(a) + Σ Q(a)
RECk
Giving us the other direction.
For the second part of the proof, assume V lie in some metric space with distance d between vertices, and we define the Wasserstein metric (PP, Q) by this distance. Also II be the set matrices и which satisfy m1 P. 1 Q and D be the distance matrix defined by D over V. now claim that, supposing L is generated by an affinity w such that w(a, b) = 0 if and only if d(a. b) = oc, that if P and Q possess the above property, then ((P, Q) oo. Indeed, note that the set of transport plans is enclosed in a finite-dimen dintessiinnion polytope and is thus a compact set. So we may consider the transport plan 7- Suppose that W Q) is finite. Then for all a, such that and belong to different connected components of the graph, 7(a b) = O, or else W(P, Q) 2 7a, b)d(a, b) = oc. Additionally, without loss of generality, there exists a C& for which Eaeo, P(a) Eneo, Q(a). But since 7 marginals are /' and Q, it should be that,
Σ Σ E P(a) oEC₁
b(, Σ E (a, aEC2 bECz
DEV
Likewise,
Σ Q(a== Σ Σ (a, acC
acC₁ dEC,
But Eeec, P(a) # Enso, Q(a), which contradicts our assumption that W(P.Q) < co.
A.1.2 PROOF OF COROLLARY
Corollary For a possibly disconnected graph 9 as defined,
VT I Q)Il if PP
GFMMD(P,
otherwise.
Proof. We repeat the same argument before. First, if P Q is not in the column space of L,, it has nonzero component in the kernel of L. Then, we conclude by Theorem A.I.I that P and Q have different amounts of mass is connected component Ct. Then let f cd( We then have that, EI([(C+)) Eg (I(Ck + O. So in particular, (f) (f) = - C for some nonzero number C. And since al C } in the kernel of L, Lf = Therefore, GFMMD(P, Q) 2 a C. Letting - oc, we know GFMMD( (P, Q) = co. For the other direction, if E C(L), then LL f f. and the remainder of the proof is the same as that of Theorem 2
A.1.3 PROOF OF THEBREM 5
Theorem 5 If X {ō. hiv is family of Kronecker-delta functions centered at each vertex of G. then the k-dimensional embedding which best preserves the distances between signals in X is equivalent up to rescaling to Hall's Spectral Graph Drawing of the Graph G in k-dimensions.
Proof. Note that X, the data matrix of Kronecker Deltas, is equal to the n-dimenssinal iden- tity. So VTL- X = VTL- hence the best k-dimensional embedding of VTL-+ (respect- ing the 1,2 norm between columns) will be equivalent to Principal Component Analysis (P.C...). Since L 1
0. L- --p's columns are mean-centered, its covariance matrix of VTL-1 is T T L TL-
12

---

Under review as a conference paper at ICLR 2023
Since its columns and rows already mean centered. And thus P.C.A. will select the eigenvectors of L corresponding to the kth largest eigenvalues. Note that these are precisely given by 1/1, 2/2..0%k
with associated eigenvalues in L given by A ... Letting A& di 11/2 ... ...xx" 1/2 and V (1/1 ... vkk) P.C.A. would embed vTL
as,
= V = (I& 0₂- (I&AA On-k) v" A
So our embedding of distributions would be given by A₂ A.T. On the other hand, Hall's Spectral Graph Drawing would embed the graph g simply as W since it chooses the first & nontrivial eigenvectors of L. Thus, coordinates in each embedding the same up to the rescaling by eigen- values.
A.2 GRID GRAPH
Grid Graph First, consider a 16 16 grid graph (vertices given by ( si.gse We can construct a signal P by placing a Dirac 6(8.4) on the vertex (8,4) and then diffusing it with a heat filter (using time
16). Q is generated likewise, but by applying heat filter to (8,)422)) and diffusing for each j = 0, 1, 2. The result are two modes: P on the left, and Q moving along the right. The distributions are visualized in the top row, and the witness function their difference in the bottom row of figure 4
And of course, the corresponding distances between P and the Q's (per the order presented above) are increasing in the distances between the appropriate centers.
(Wimans Function
[Witness Funciion
(Nitoees Furction!
(Vitnesa Function)
Figure 4: Top row: the distributions and Q. where the signal P stays fixed but the vertex which Q is centered shifts to the right. Corresponding distances between distributions appear in the title, and the relevant centers of P and are highlighted. Bottom row: corresponding witness functions f to the difference between P and Q.
A.3 DIFFUSING SIGNALS ON THE BUNNY GRAPH
One very simple sanity check of a measure of spread to verify that the more we diffuse a Dirac, the lower the distance the uniform. Indeed, if we begin with the Bunny graph (from pygsp's built in library) and diffuse the Dirac 81,00 (1400 was chosen for visual appeal) for scales T 22t 24, 28 and 2 (using heat filter), find that the corresponding measures of spread 40.5, 26.9, 21.5, and 9.76. The signals are visualized below:
2
29
Figure 5: The signal 01400 diffused to levels 1,6 62 and 6 using heat filter.
13

---

Under review as a conference paper at ICLR 2023
A.4 BIMODAL SIGNALS
We can take the earlier signals from the grid graph (each pair of P and Q for translations of Q) and combine them into signal [ + Q). This forms family of bimodal signals for which the two modes spread. Accordingly, in the example above, the distance to the uniform is given by 11.14, 8.66, 6.13, and 6.09.
A.5 LOCALIZATION ON THE MINNESOTA GRAPH
A.5.1 EXAMPLE: MINNESOTA GRAPH (BINARIZED)
A final sanity check for measure of closeness the uniform would be to begin with density which puts all its mass on one vertex. Then, put equal mass on that vertex and its neighbors. then the neighbors of neighbors, etc. More specifically, let Nx(i,j) = EEKL E [k] A > 0}, or N& (i 1 there
path of length < k from to j}. Then we can consider multiplying this by Dirac, say du to get family of signals. Using k = 1, 44 42, 43, we have a family of distributions proportional to No N200, N300, and N400- Again, we can visualize the activated vertices in yellow:
Figure 6: The zeroth vertex's neighbors, then neighbors of neighbors, etc. for order 1, 4, 16, and 64 neighbors. The corresponding distances to the uniform are given in the title.
A.6 EXAMPLE: MINNESOTA GRAPH (SMOOTH WAVES)
A similar example we can consider is a similar class of signals which "spread" across the graph, but rather than activating neighbors, simply diffusing the signal from a given start vertex. Here, choose the same start vertex, and run heat diffusion at times 7 2", 24 28, and 2
Figure 7: Visualization the diffusions of the signal dn times 20,24 25,25, and 212 The corre- sponding distances to the uniform are given above.
14


Reviews:
[{"review_id": "d6KP9Chu6o", "reviewer": "Reviewer_3iNi", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors propose a new distance between distributions (or non-negative signals) on graphs, namely Graph Fourier MMD. The authors also prove its scale invariance and applicability to disconnected graphs. The authors evaluate the proposed distance for gene clusters.", "summary_of_the_review": "The proposed method has some potential. However, it is better in case the authors elaborate the proposed approaches with more details and improve the experiments.", "strength_and_weaknesses": "Strength:\n+ The authors prove a new distance, namely Graph Fourier MMD for distributions on graphs\n\nWeaknesses:\n+ It is not clear the advantages of the proposed distance over existing ones in the literatures for distributions on a graph. \n+ The empirical advantages of the proposed method are unclear.  (e.g., no baselines about distances for distributions on graphs on the single cell analysis?, it is unclear why it is important to measure the correlation with the exact EMD?)\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "KdiTQkW8MN", "reviewer": "Reviewer_tGJZ", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This article introduces a distance between probability distributions on a graph. It is defined as the distance in the RKHS of the embedding of these distributions according to a kernel defined by the pseudo-inverse of the Laplacian of the graph. ", "summary_of_the_review": "Here are my detailed comments: \n\n- Litterature review and competing methods:\n\nMy main reproach concerning this article is that it is not complete enough and that the literature review on the subject is too light. The article lacks comparisons with many existing methods which are very similar to the proposed method. In this context the sentence \"relatively little attention has been given to computing such distances for distributions on graphs\" is very misleading. \n\nOn the one hand, all the literature on spectral embedding methods, or more generally on harmonic analysis on graphs, is almost not mentioned in the article. However, this is exactly what is proposed by the authors to compare signals on graphs seen as probability distributions. Indeed Theorem 2. simply tells us that the chosen metric corresponds exactly to computing the Euclidean distance between the spectral embeddings of the signals. From a shape point of view, many works have already addressed the issue (e.g. [1, 2]) and others have tried to generalize these approaches for the case of signals on different graphs e.g. [3]. In this context, lernel embedding of signals based on the Laplacian is far from being new. From an OT persepective there is also a lot of litterature on the exact same problem that is not mentionned e.g. [4-6] (even for signals on different graphs e.g. [7-10]). In light of these various works, the proposed method is quite incremental. I think it is necessary to position the approach well with respect to the spectral and other transport variants that already exist, without omitting them, and to compare with them. \n\n- Justification of the approach: \n\nI also find that talking about Wasserstein distance to define the GFMMD metric is rather clumsy, even a bit forced. Indeed the authors artificially start from the distance of $W_1$ and relax the constraints, going from a Lipschitz constraint to a constraint on the sum. The justification given is \"This condition is more robust to noise than the corresponding 1-Lipschitz constraint, and results in a closed-form solution\". The second sentence is indeed correct but the first one lacks justification. Moreover, to define GFMMD there is no need for the Wasserstein distance. It is enough to define the discrete kernel $K = L^{-}$ and to consider the MMD associated to this kernel (as illustrated in Theorem 6.). Going through the Wasserstein distance instead of presenting the simple definition of GFMMD with the explicit kernel reinforces the unclear side of the paper. \n\nMore importantly, there is a real confusion between \"signals on graphs\" and \"probability distributions on graphs\". Indeed, the way it is written, $GFMMD(P,Q) = \\|L^{-\\frac{1}{2}}(P-Q)\\|$ implies that the method cannot take into account signals on the graph. Indeed \"$P$ is a probability distribution on the vertices/nodes\": thus it is simply a histogram (say the graph have two nodes $1, 2$ then $P$ is for example $(1/2, 1/2)$). So $\\|L^{-\\frac{1}{2}}(P-Q)\\|_{2}$ is simply the $\\ell_2$ distance between the histograms reweighted by the Laplacian, and there is no signal here: unless $P$ is defined as $(f(1), f(2), \\cdots , f(n))$ where $f(i) \\in \\mathbb{R}$ is the value of the signal at the node $i$. But in this case $P$ is not a probability distribution anymore since $f(i)$ can be negative: it is a signed measure. This confusion is also supported by the next point.\n\n- About \"Empirical Results \\& Applications\":\n\nThe first paragraph of this part is indeed quite surprising: I have the impression that the authors confuse \"negative signals $P$ and $Q$\" with \"negative measures/distributions $P$ and $Q$\". In the first case there is no problem to consider the MMD/Wass between two probability distributions associated to signals which can take negative values (one can easily compute the MMD or Wass distance between $\\frac{1}{2} \\delta_{-1} + \\frac{1}{2} \\delta_{-2}$ and $\\frac{1}{2} \\delta_{1} + \\frac{1}{2} \\delta_{12}$). In this case, why mention the fact that we have to normalize? In the second case, $P$ and $Q$ are indeed no longer probability distributions and the framework/formalism must be changed. \n\nI have trouble seeing the point of the grid graph experiment: what is exaclty this \"witness function\"? The distance $D$ is, I guess the GFMMD, right? What this example shows is that the GFMMD increases when the $2$ signal moves away from the $1$ signal on the graph, right? \n\nI am not really convinced by the experiment 4.1 which tries to show that GFMMD is a good measure of similarity between distributions on the graph. The example is quite artificial and the results are really noisy, it is hard to understand why one method is really better than the others (for example Diffusion EMD vs GFMMD) \n\n- Other comments: \n\nOverall I find that the Figure 1, 2 and 5 are really hard to read. I think it is important to make the titles and figures larger.\n\nThe article about the package \"python optimal transport\" should be quoted instead of just mentioning it in a sentence. Similarly references Chebyshev polynomials applied to filter approximation on graphs are missing (e.g. [11]). \n\nThe \"Hall's Spectral Graph Drawing of the Graph G in k-dimensions\" is not properly defined in the article and there are no references, so we don't really understand what Theorem 7 is about.\n\nI think the writing of the article could be improved. In particular, the first three pages contain a lot of definitions that I think are not really useful and could be removed to discuss many more important points like the links with the different spectral approaches or to discuss other transport approaches for signals on graphs.\n\nRefs: \n[1] Michael M. Bronstein, Alexander M. Bronstein. Shape recognition with spectral distances. IEEE TRANS. PAMI 2010.\n\n[2] Rustamov, Raif M. Laplace-Beltrami Eigenfunctions for Deformation Invariant Shape Representation. Proceedings of the Fifth Eurographics Symposium on Geometry Processing. 2007\n\n[3] Saurabh Verma, Zhi-Li Zhang. Hunt For The Unique, Stable, Sparse And Fast Feature Learning On Graphs. NeurIPS 2017.\n\n[4] Montacer Essid, Justin Solomon. Quadratically-Regularized Optimal Transport on Graphs. SIAM J. SCI. COMPUT. 2018\n\n[5] Tam Le, Truyen Nguyen, Dinh Phung, Viet Anh Nguyen. Sobolev Transport: A Scalable Metric for Probability Measures with Graph Metrics. AISTATS 2022.\n\n[6] Le, T., Yamada, M., Fukumizu, K., and Cuturi, M. Tree-sliced variants of Wasserstein distances. NeurIPS 2019\n\n[7] Nikolentzos, G., Meladianos, P., and Vazirgiannis, M. Matching node embeddings for graph similarity. In Proceedings of the Thirty-First AAAI Conference on Artificial\nIntelligence, February 4-9, 2017, San Francisco, California, USA., pp. 2429–2435, 2017.\n\n[8] Titouan Vayer, Laetitia Chapel, Rémi Flamary, Romain Tavenard, Nicolas Courty. Optimal Transport for structured data with application on graphs. ICML 2019\n\n[9] A. Barbe, M. Sebban, P. Gon¸calves, P. Borgnat and R. Gribonval. Graph Diffusion Wasserstein Distances. ECML 2020.\n\n[10] Hongteng Xu, Dixin Luo, Hongyuan Zha et Lawrence Carin Duke. Gromov-Wasserstein Learning for Graph Matching and Node Embedding. ICML 2019\n\n[11] D. I. Shuman, S. K. Narang, P. Frossard, A. Ortega, and P. Vandergheynst. The emerging field of signal\nprocessing on graphs: Extending high-dimensional data analysis to networks and other irregular domains.\nIEEE Signal Processing Magazine, 30(3):83–98, 2013.", "strength_and_weaknesses": "The idea of this distance is simple and seems quite natural. The advantage is that it is reasonably simple to calculate. However, my overall impression of the article is that it doesn't seem mature enough to be published yet, and many points are unclear.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "KZ3VW407zLm", "reviewer": "Reviewer_SH8k", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The article defines a measure of Maximum Mean Discrepancy (MMD) for Graph Fourier features. it discusses how one could use the Laplacian of a graph suited to multivariate data so as to compute a GF-MMD. Some empirical results and applications are shown in an extensive numerical section. ", "summary_of_the_review": "My appreciation is borderline for acceptation; I put currently marginally under the acceptance threshold. \n\nThe weaknesses in the presentation and on some insights should be corrected by the authors. ", "strength_and_weaknesses": "Strength\n\n- The proposed method, as summarized by Definition 4 and Theorem 2, is an interesting approach to design a distance between two multivariate distributions. \n\n- there are some interesting numerical experiments in Section 5 that provide a correct grasp of the potentialities of the work.\n\n- the article is mostly clear and well written.\n\nWeaknesses\n\n1- Some points shoud be better stated: the initial result in 3.1 assumes a distance function $d(a,b)$ between all pairs of nodes yet the author suggest just before Def 4 and again afterwards to use instead an affinity graph between nodes instead of $1/d^2$. Is this affinity graph truncated or sparsified) in some way ? Or is it intended to gave a weighted full graph ?\n\n2- Also: Algorithm 1 takes $X$ as an input and never is considered the more general (and interesting) situation where $X$  and $\\mathcal{G}$ which is not a k-NN graphs over $X$. Would the method be amenable to such a more general situation ?\nAnd, if not, is the performance of the method only a conequence of the approximation of some manifold where the data points lie thanks to the k-NN graph ? Could topologies more varied than ones derived from data on swiss roll be considered ?\n\n3- Can you challenge my impression that, in 4.1, the works merely rely on the possibility to approximate the structure (manifolds) thanks to k-NN ? If that so, what is actually the difference as compared to Laplacian embedding methods ?\n\n4- I don't understand why most of A.1 is not in the main text, while discussion about disconnected graphs (half or page 5, including Theorem 5 and the corollary) could safely be postponed to appendix, as there is almost no practical usage of working on disconnected graphs without preprocessing by connected components.\n\n5- Some references are missing: to Hall's spectral drawing ; to references about Chebyshev polynomial approximation for graph filters ; in 4.1 when listing the various methods for comparisons \n\nNotes / questions:\n\n- MMD should be \"translated\" in the introduction\n\n- I am not confident that the lifting approach described at the beginning of 4 will not have major impact. Has this point been studied more ?\n\n- for the grid graph and Fig 1, how are chosen the diffusion times ?\n\n- The aspects about Gene Locality is not clear for me (but maybe it's because it's a field that I know less).\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "E5M-ENO8Uzi", "reviewer": "Reviewer_yZp1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes a way to define a metric (called GFMMD) for non-negative graph signals in a way to account for geometric structure. It comes from by mimicing the so-called Integral Probability Metrics, particularly 1-Wasserstein distance for discrete distributions. GFMMD can be computed rapidly (relying on approximation to L^{-1/2}) and in closed-form.  From this closed-form solution, an embedding can be defined.  This newly defined distance has been applied in several empirical examples. It seems certain benefits can achieve.", "summary_of_the_review": "The idea in the paper is simple but interesting. It emphasizes the importance of L^{-1/2}f although the paper did not go further in this direction. Overall the paper is well presented. More interesting applications are desired.", "strength_and_weaknesses": "Strength\n\n1. The origin of the question has been clearly described.\n\n2. Propose a new distance as specified in Definition 4.   \n\n3. The theoretical analysis and derivation of solution are solid.\n\nWeakness\n\n1. The experimental examples are not very significant. This reflects the fact or question how this theory can benefit in wide learning scenarios. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject