Scalable Sobolev IPM for Probability Measures on a Graph

Dear Reviewer Qz8Z,

Thank you for your valuable feedback. Below are the answers for your questions and comments.

(1) [...]choice of graph structure (not justified)[...]not explain why these specific graph structures were chosen. Different graph structures (e.g., random geometric graphs, small-world graphs) may impact computational performance[...]

[...]over-reliance on fixed graph structures [...]choice of graph structure seems not justified[...]not explain why these specific graph structures were chosen and has no discussion on how graph structure impacts Sobolev IPM performance[...]crucial to (Sobolev IPM)[...]

→ In this work, we study Sobolev IPM for probability measures supported on a given graph (line 11–13). As in line 1481–1284 (Appendix C.3), much as Sobolev transport (Le et al., 2022), we assume that the graph metric space (i.e., the graph structure) is given. We will clarify it.

Our proposed regularized Sobolev IPM can be applied for probability measures supported on any given graph $\mathbb{G}$ such that $\mathbb{G}$ is connected, undirected, physical graph with positive edge length, and $\mathbb{G}$ satisfies the uniqueness property of the shortest paths (as in line 90-103). Furthermore, as in Remark 3.6 (181-189), the regularized Sobolev IPM can be also applied for non-physical graph $\mathbb{G}$ for the discrete case as in Theorem 3.5 (line 165-179).

In our experiments, we consider graphs $\mathbb{G}$_Log, $\mathbb{G}$_Sqrt as in Le et al. (2022) (line 326–327). We agree that there are many different approaches for document classification and TDA tasks. However, it is not the goal of our empirical studies. As in line 299-306, our experiments aim to illustrate the fast computation of the regularized Sobolev IPM, and show preliminary evidences on its advantages compared to other popular transport approaches (e.g., optimal transport and Sobolev transport) for probability measures on a given graph under the same settings.

(2) [...] (advantages) on fast closed-form computation, the paper presents empirical runtime comparisons, but does not provide a theoretical complexity analysis of its method, for example, on graph size $|V|$ and $|E|$[...]

→ Besides the preprocessing with computational complexity $\mathcal{O}(|E| + |V| \log |V|)$ (line 262-267), from Equ. (10) in Theorem 3.5, the computational complexity of the regularized Sobolev IPM is trivially linear to the number of edges in $E$ of graph $\mathbb{G}$, i.e., $\mathcal{O}(|E|)$.

Moreover, by exploiting the sparsity property, we further reduce its computational complexity into $\mathcal{O}(|E_{\mu, \nu}|)$ (line 205-216). We will clarify it.

(3) [...]proves equivalence with the $1$-Wasserstein distance when the graph is a tree[...]not fully explore relations for $p>1$. No theoretical guarantees on whether the regularized Sobolev IPM behaves similarly to higher-order Wasserstein distances.[...]

→ We do acknowledge it (line 233-243). For $p=1$, regularized Sobolev IPM is equal to $1$-Wasserstein (Prop. 4.5). For $p > 1$, to our knowledge, their relation is an open problem (line 233-235), but $p$-order regularized Sobolev IPM is lower bounded by $1$-Wasserstein (Prop. 4.6).

We respectfully clarify that our goal for the behavior of the regularized Sobolev IPM is similar to the original Sobolev IPM (Theorem 2), but NOT the $p$-Wasserstein. We agree that for $p>1$, the regularized Sobolev IPM and $p$-Wasserstein can behave differently. We believe that it should not be considered as the weakness for the regularized Sobolev IPM.

(4) [...]equivalence result (Theorem 4.2) only provides upper and lower bounds[...]not analyze the gap between standard Sobolev IPM and the regularized version[...]

→ We agree that in Theorem 4.2, we show that the regularized Sobolev IPM is equivalent to the original Sobolev IPM, but not their gap. However, from Theorem 4.2, one can obtain the upper/lower bounds on the ratio between regularized Sobolev IPM and original Sobolev IPM.

We further emphasize that our approach aims neither to derive a tight bound for the gap nor to provide a sharp approximation for the challenging optimization problem (Equ. (4)) of the original Sobolev IPM. Our purpose is in a different direction. More precisely, we instead propose a novel regularization for Sobolev IPM which yields an equivalent metric to the original Sobolev IPM, and a closed-form expression for a fast computation. Note that, to our knowledge, there are no efficient algorithms to compute Sobolev IPM effectively yet. We believe that each approach has its own merits.

Concluding remarks. We would be grateful if you could let us know whether our clarifications and answers address the raised concerns. If so, we kindly ask that you consider increasing your rating. We are also pleased to discuss any other questions you may have.

Dear Reviewer FFqa,

Thank you for your valuable feedback. Below are the answers for your questions and comments.

(1) [...]Limited Justification for General Graphs[...]claimed to work on graphs, its theoretical analysis and experiments are only carried out on trees[...] (not for) general graphs, where the shortest-path structure may not be unique[...]

[...]discuss the potential applications of TW/ST or regularized ST to general graphs?[...]

→ We respectfully disagree. We clarify that the regularized Sobolev transport can be applied for probability measures on any given graph $\mathbb{G}$ such that $\mathbb{G}$ is connected, undirected, physical graph with positive edge length, and graph $\mathbb{G}$ satisfies the uniqueness property of the shortest paths (as in line 90-103). We emphasize that there is no requirement that the given graph $\mathbb{G}$ is a tree. Furthermore, as in Remark 3.6 (181-189), the regularized Sobolev IPM can be also applied for non-physical graph $\mathbb{G}$ for the discrete case as in Theorem 3.5 (line 165-179).

For the uniqueness property of the shortest paths, we clarify that it does NOT require that there is only one path connecting between two nodes $x, y \in \mathbb{G}$ (or the given graph should be a tree). In fact, there may exist multiple different paths with various path lengths, connecting these two nodes. The uniqueness property of the shortest paths only requires that the shortest path between root node $z_0$ and arbitrary node $x$ to be unique (i.e., no multiple shortest paths between them; and there is no problem for existing multiple different paths connecting them). Please see line 1467-1480 (Appendix C.3) for the further discussion.

Note that a graph is called geodetic if for every pair of nodes the shortest path between them is unique. Thus, geodetic graphs are special examples satisfying the uniqueness property of the shortest paths (i.e., geodetic graphs are not necessarily trees). Please see Fig. 1 in Le et al. (2022) for an example of such geodetic graphs. Moreover, in our experiments, graph $\mathbb{G}$_Log has $M$ nodes and at least $(M \log M)$ edges; and graph $\mathbb{G}$_Sqrt has $M$ nodes and at least $M^{3/2}$ edges. Thus, these graphs are obviously not trees. We will clarify it.

(2) [...]Scalability Claim Relative to Existing Closed-Form Solutions[...]highlights scalability (key advantage), but (TW/ST) already have closed-form solutions[...] (unclear) significant computational benefits beyond[...]

→ We clarify that our goal is NOT to scale up the computation of either TW or ST, but the Sobolev IPM for probability measures on a given graph.

In this work, we study Sobolev IPM for probability measures supported in a given graph (line 10-13). To our knowledge, there are no efficient algorithmic approaches to compute Sobolev IPM effectively, which hinders its practical applications (line 19-22). Please see Equ. (4) for the challenging optimization problem of the Sobolev IPM.

We propose a novel regularization for Sobolev IPM in Equ. (8) in Def. 3.3 (line 131-139), which yields a closed-form for a fast computation (Theorem 3.5, line 165-179). This paves a way for applying Sobolev IPM in applications, especially large-scale settings.

In our experiments, the performances of regularized Sobolev IPM kernels compare favorably with those of ST, OT, TW kernels (line 371-375). Furthermore, note that TW can only use a partial graph information (line 292-294), i.e., tree information sampled from the given graph.

(3) [...]Evaluation on Embeddings Instead of Direct Graph Metrics[...]designed for probability measures on graphs[...] (experiments) relies on embedding-based representations (e.g., word embeddings for documents, persistence diagrams for TDA)[...]whether the metric truly captures graph-based probability measure discrepancies or if the improvement is due to embeddings[...]

→ We agree that there are many different approaches for document classification and TDA tasks. However, it is not the goal of our empirical studies.

We clarify that as in line 299-306, our experiments aim to illustrate the fast computation of the regularized Sobolev IPM, and show preliminary evidences on its advantages compared to other popular transport approaches (e.g., OT, ST) for probability measures on a given graph under the same settings.

More concretely, in our experiments, we consider graphs $\mathbb{G}$_Log, $\mathbb{G}$_Sqrt as in Le et al. (2022) (line 326–327), and evaluate for regularized Sobolev IPM, OT, ST to compare probability measures supported on these given graphs under the same settings.

Concluding remarks. We would be grateful if you could let us know whether our clarifications and answers address the raised concerns. If so, we kindly ask that you consider increasing your rating. We are also pleased to discuss any other questions you may have.

Dear Reviewer XuWp,

Thank you for your valuable feedback. Below are the answers for your questions and comments.

(1) [...]pseudo algorithm (Theorem 3.5)[...] (compute in practice)[...] (preprocessing) is dense and not too informative[...]

→ We respectfully clarify that the preprocessing is necessary to compute the regularized Sobolev IPM efficiently (i.e., precompute $\gamma_e$ and $\beta_e$ for each edge $e$ in graph $\mathbb{G}$).

As in line 206-208, following Le et al., 2022, each support $x$ in measure $\mu$ contributes its mass to $\mu(\gamma_e)$ if and only if edge $e$ is in the shortest path between root $z_0$ and $x$. Therefore, for each edge $e$, it is simple to obtain $\mu(\gamma_e)$, $\nu(\gamma_e)$ by checking the precomputed shortest paths between root $z_0$ and each support in $\mu$, $\nu$ respectively. Additionally, $\beta_e$ is precomputed. Hence, it is straightforward to implement Equ. (10) in Theorem 3.5. We will clarify it.

We will follow your suggestion to add the pseudo-code for the computation in Equ. (10).

(2) [...]example where you can validate (Theorem 4.2)[...]

→ We respectfully clarify that the findings in Theorem 4.2 are theoretically and rigorously proved in Appendix A.5. As in Theorem 4.2, for any nonnegative Borel measure $\lambda$ on graph $\mathbb{G}$ and for $1 \le p < \infty$, the $p$-order regularized Sobolev IPM is equivalent to the original $p$-order Sobolev IPM.

To our knowledge, there are no efficient algorithmic approaches to compute Sobolev IPM (Equ. (4), line 140-142) effectively yet.

(3) [...]Theorem 4.2 and other derivations seem related to the weighted sobolev norm and the analysis (Peyre, 2018)[...]

→ To our knowledge, our theoretical findings are essentially different from the results in Peyre (2018).

We study the Sobolev IPM for probability measures supported on a given graph. The Sobolev IPM (Equ. (4)) constrains a critic function within the unit ball defined by the Sobolev norm (Equ. (3), line 124) involving both the critic function and its gradient, while Peyre (2018) considers the weighted homogeneous Sobolev norm which constraints a critic function in a semi-norm involving only gradient of the critic function (see Equ. (3) and (4) in Peyre (2018)). Peyre's approach shares the same spirit as the $2$-order Sobolev transport (Le et al., 2022). We will clarify it.

The proposed regularized Sobolev IPM may share some spirit with the weighted homogeneous Sobolev norm and the Sobolev transport (i.e., constraint on gradient of a critic function). However, we clarify that the weight function $\hat{w}$ (Equ. (5)) plays the key role to establish the equivalence between Sobolev norm and weighted $L_p$ norm (Theorem 3.2) for our novel regularization for Sobolev IPM.

(4) [...] (example) quantity (Equ. 1)[...]

→ We clarify that Equ. (1) is reviewed from Le et al., 2022. Please see Fig. 1 in Le et al. (2022) for such illustration.

We will follow your suggestion to quote more texts and figures from Le et al. (2022) for the review within the limited space in the main manuscript (or placed in the supplementary).

(5) [...] (define) quantities such as $\lambda(\Gamma(x)), \lambda(\gamma_e)$ (how to compute them)[...]

→ $\lambda$ is a nonnegative Borel measure on graph $\mathbb{G}$ (line 70); $\Gamma(x)$, $\gamma_e$ are subgraphs defined in Equ. (1) (line 57-59); $\lambda(\Gamma(x))$, $\lambda(\gamma_e)$ are standard notions of measures on sets.

For a specific instance, as in Theorem 3.5, we consider $\lambda$ to be the length measure on graph $\mathbb{G}$ (see a review in Def. B.2 and Lemma B.3 in line 1117-1133 (Appendix B.2)), and hence $\lambda(\gamma_e)$ is the total length of $\gamma_e$.

(6) [...]regularized IPM (not make sense)[...]Weighted Sobolev IPM[...]

→ Following Theorem 3.2, we propose to relax the set of feasible critic functions $\mathcal{B}(p’)$ (line 128) by $\mathcal{B}(p’, \hat{w})$ (Equ. (7), line 128). Therefore, we call it regularized Sobolev IPM.

For “weighted Sobolev IPM”, it may confuse with IPM where a critic function is constrained within the unit ball w.r.t. weighted Sobolev norm (e.g., some weighted versions of the Sobolev norm in Equ. (3)), which are essentially different to our proposed regularized Sobolev IPM.

We will consider your suggestion. Thank you.

(7) [...] (not) introducing these concepts in a clear way[... ]address the clarity issues[...]

→ We respectfully clarify that all definitions, theoretical findings, and corresponding proofs are elaborated rigorously in mathematics. We will follow your suggestions to add more explanation within the limited space.

Concluding remarks. We would be grateful if you could let us know whether our clarifications and answers address the raised concerns. If so, we kindly ask that you consider increasing your rating. We are also pleased to discuss any other questions you may have.