An Efficient Orlicz-Sobolev Approach for Transporting Unbalanced Measures on a Graph

Dear Reviewer HNe3,

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

(1) [...] (some of the settings follow prior work): (not entirely clear) optimal for the current setup [...] more intuition behind the selection of the Orlicz functions $\Phi_0, \Phi_1, \Phi_2$? [...] (explanation) specific form of the weight functions $w_1$ and $w_2$ [...] (ablation or sensitivity analysis) parameter choices on performance or efficiency? [...]

→ $N$-functions $\Phi_1, \Phi_2$ and the limit case $\Phi_0$ have been popularly utilized for Orlicz geometric structure in the literature [36, 17, 3, 49, 26, 4, 54, 13, 2, R8].

The performance of Orlicz-EPT/OST typically depends on the choice of the $N$-function $\Phi$ (Equation (7) and Definition 4.1 respectively), similar to how kernel functions impact performance in kernel-dependent machine learning frameworks. In our experiments with $N$-functions $\Phi_1$ and $\Phi_2$ (Section 7), we observed slightly different performances. Similar findings have been reported for GST [36].

We agree that determining the optimal $N$-function $\Phi$ for Orlicz-EPT/OST in a given task is an open problem that warrants further investigation. Given that the primary focus of our paper is on Orlicz-EPT/OST, we leave this topic for future work for a careful study. As an interim solution, cross-validation can be used to select $\Phi$ from a set of candidate functions.

Following the theoretical result in Proposition 5.7, and theoretical properties on the EPT on a graph [35] (Corollary 3.2, Corollary 4.6, Proposition 5.4), weight functions $w_1, w_2$ are $b$-Lipschitz, e.g., we simply choose $w_1(x) = w_2(x) = a_1 d_{\mathbb{G}}(x, z_0) + a_0$ where $a_1 = b, a_0 =1$, see line 288-289.

We consider different graphs $\mathbb{G}$_Sqrt, and $\mathbb{G}$_Log. For all datasets, except MPEG7 dataset, graph $\mathbb{G}$_Sqrt consists of 10K nodes and 1 million edges, while graph $\mathbb{G}$_Log comprises 10K nodes and 100K edges. Due to the smaller size of the MPEG7 dataset, we constructed graph $\mathbb{G}$_Sqrt with 1K nodes and 32K edges, and graph $\mathbb{G}$_Log with 1K nodes and 7K edges. We also consider different $N$-functions ($\Phi_1, \Phi_2, \Phi_0$). Some other parameters, e.g., $b, \alpha, w_1, w_2$, are set by following our derived theoretical results (Section 5) and theoretical properties of EPT [33, 35] used in their experiments.

Furthermore, we carry out more additional experiments for different $b, \alpha$. The average accuracy results are as follows:

$\star$ For document classification on TWITTER

• For graph $\mathbb{G}$_Sqrt:

• For graph $\mathbb{G}$_Log

$\star$ For TDA on MPEG7

• For graph $\mathbb{G}$_Sqrt

• For graph $\mathbb{G}$_Log

These empirical results suggest that turning these hyperparameters (e.g., by cross-validation) may help to improve the performances further. We will clarify it.

(2) [...] (Section 3) would benefit from additional intuition or illustrative examples. [...]

→ Thank you for your suggestion. We will add more text and examples to further clarify technical concepts (Section 3) within the constraints of the main manuscript or supplement.

Concluding remarks. We would be grateful if you could let us know whether our clarifications and answers are satisfied to 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.

Reference

[R8] Vershynin, High-dimensional probability: An introduction with applications in data science. Cambridge university press, 2018

Dear Reviewer uDto,

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

(1) [...] The method presents an incremental development of several well-established ideas [...] the first work to explore Orlicz-Wasserstein distance for unbalanced measures specifically on graph structures, which is a meaningful contribution. [...]

→ We respectfully disagree that our proposed methods are incremental. Below are the reasons:

• GST is recognized as a scalable variant of OW (see a review in Appendix B.1.5) [36]. However, unlike OT, extending GST to accommodate unbalanced measures on a graph with a mass constraint is nontrivial, as discussed in lines 57-60.

• We believe that it is non-trivial to establish a connection between EPT on a graph [35] and a potential extension of GST [36] for unbalanced measures.

• As noted in Remark 3.1 (lines 138-140), simply applying Caffarelli and McCann's (2010) observations without calibration would result in a new ground cost for standard OT that is not guaranteed to be nonnegative, similar to [12, 33, 35]. We stress that our calibration is crucial for the development involving Orlicz geometric structure, given that the $N$-function is defined on $\mathbb{R}_{+}$ (see lines 98-100).

• We leverage insights from [35, 36] to develop a novel regularization for OST (Definition 4.1), which involves new tools to control integral of gradient on shortest paths and its duality with Orlicz geometry, as shown in Equation (12) and Appendix A.2.4.

We emphasize that we do not claim any new techniques for the theoretical proofs. We appreciate your evaluation that the proposed methods are meaningful contributions: our work is the first approach to efficiently extend OW/GST for unbalanced measures on a graph.

(2) [...] (unclear) recover the solution to Problem (3) (for a fixed m) from the solution to Problem (4) (for a fixed $\lambda$). [...]

→ The relationship between Problem (3) and Problem (4) is established in [35], specifically through Theorem A.1 in Appendix A.1. To elaborate, Theorem A.1 in [35] demonstrates that a solution to Problem (4) directly yields a solution to Problem (3). We will provide further clarification on this connection.

Concluding remarks. We would be grateful if you could confirm whether our clarifications and responses adequately address your concerns. If they do, we kindly ask that you consider increasing your rating. We are also happy to address any additional questions or concerns you might have.

Dear Reviewer pFMB,

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

(1) [...] under what conditions the additional expressiveness of Orlicz-EPT is valuable and worthwhile and justifies its use over OST would be advantageous (further strengthen the importance and applicability of the contribution) [...]

→ Following Proposition 5.2 (line 232), we can view OST as an extension of GST [36] for handling unbalanced measures, and Orlicz-EPT as an extension of OW [55] for unbalanced measures. Notably, when the input measures have equal mass (i.e., $\mu(\mathbb{G}) = \nu(\mathbb{G})$), and $b = 1$, Orlicz-EPT reduces to OW. Furthermore, Orlicz-EPT shares the same computational complexity as OW, as shown in Equation (7). It's worth noting that GST is a scalable variant of OW for balanced measures, in the same sense, OST can be seen as a scalable variant of Orlicz-EPT.

As a result, Orlicz-EPT is applicable for all applications of OW and extends OW to handle unbalanced input measures, whereas OST may not reserve all the properties of OW.

Like OW, Orlicz-EPT involves a two-level optimization problem, limiting its applicability to small-scale domains. In contrast, OST, similar to GST, is scalable and can be applied to large-scale domains.

We appreciate the suggestion and agree that it is an interesting research direction for further exploration.

(2) [...] (experiments) limited to text files and persistence diagrams [...] (broader empirical range) biological graphs, social networks, or dynamic/temporal graphs? [...]

→ We would like to clarify that our work focuses on the OT problem with an Orlicz geometric structure for unbalanced measures supported on a graph metric space (lines 52-53). Specifically, our proposed approaches (Orlicz-EPT/OST) compute the distance between two input measures with potentially different total masses, where the measures are supported on the nodes of a graph with a metric based on shortest path lengths. Consequently, our approaches are suitable for applications that require measuring distances between measures on graph structures endowed with a graph metric. In our experiments, we demonstrate the effectiveness of our approach in document classification on four real-world datasets and topological data analysis (TDA), including orbit recognition for linked twist maps (a discrete dynamical system modeling flows in DNA microarrays [R7]) and object shape recognition in MPEG7 dataset. These evaluations on document classification and TDA are often used for tasks involving comparing measures on a graph, see [35, 36]. We believe that such experimental coverage is rich and diverse enough. We will clarify it.

Regarding the suggestion to explore broader empirical range, e.g., biological graphs, social networks, or dynamic/temporal graphs, could you please specify public datasets for the suggestion and confirm whether they involve comparing measures with potentially different total masses on a given graph? We appreciate your suggestion and would be happy to conduct additional experiments within the rebuttal period if feasible. Thank you very much.

(3) [...] (sensitivity analysis/pragmatic guidance) the Orlicz function $\Phi$, the regularization weight $b$, and the $\alpha$ range (ease of use by practitioners) [...]

→ We clarify that different Orlicz functions, such as the popular $N$-functions $\Phi_1$, $\Phi_2$, and the limit case $\Phi_0$, are illustrated in Figures 2 and 3 of the main manuscript, as well as Figures A.3 and A.4 in the supplementary materials.

The performance of Orlicz-EPT/OST typically depends on the choice of the $N$-function $\Phi$ (Equation (7) and Definition 4.1 respectively), similar to how kernel functions impact performance in kernel-dependent machine learning frameworks. In our experiments with $N$-functions $\Phi_1$ and $\Phi_2$ (Section 7), we observed slightly different performances. Similar findings have been reported for GST [36].

We agree that determining the optimal $N$-function $\Phi$ for Orlicz-EPT/OST in a given task is an open problem that warrants further investigation. Given that the primary focus of our paper is on Orlicz-EPT/OST, we leave this topic for future work for a careful study. As an interim solution, cross-validation can be used to select $\Phi$ from a set of candidate functions.

Regarding the regularization weight $b$, we used $b=1$ in the experiments based on the results in Propositions 5.2 and 5.3, as well as for simplicity. This choice of $b$ is also supported by theoretical results on EPT on a graph [35] (Lemma A.6, Remark 4.8) and has been used in previous experiments for EPT [33, 35].

For $\alpha$, from the result in Proposition 5.7 and for simplicity, we use $\alpha=0$ for the experiments. Such value for $\alpha$ is also supported by theoretical results of EPT on a graph [35] (Lemma 4.4, Proposition 5.2) and used in experiments for EPT [33, 35]. Additionally, when $\alpha=0$, $\mathcal{I}_{\alpha}$ is the largest interval (line 197).

Following your suggestion, we evaluate more additional experiments with different $b, \alpha$. The average accuracy results are as follows:

$\star$ For document classification on TWITTER

• For graph $\mathbb{G}$_Sqrt:

• For graph $\mathbb{G}$_Log

$\star$ For TDA on MPEG7

• For graph $\mathbb{G}$_Sqrt

• For graph $\mathbb{G}$_Log

These empirical results suggest that turning these hyperparameters (e.g., by cross-validation) may help to improve the performances further. We will clarify it.

(4) [...] (performance) alters the size of the graph (nodes/edges) or density (graphs of thousands of nodes) [...]

→ We clarify that our experiments (Section 7) utilize two graphs: $\mathbb{G}$_Sqrt and $\mathbb{G}$_Log. For all datasets, except MPEG7 dataset, graph $\mathbb{G}$_Sqrt consists of 10K nodes and 1 million edges, while graph $\mathbb{G}$_Log comprises 10K nodes and 100K edges. Due to the smaller size of the MPEG7 dataset, we constructed graph $\mathbb{G}$_Sqrt with 1K nodes and 32K edges, and graph $\mathbb{G}$_Log with 1K nodes and 7K edges. Additionally, the graph is assumed to be given in our experiments, see line 267-268. We will clarify it.

(5) [...] (dual forms and cost calibration) may benefit from a little more intuition or figures [...] (Orlicz-EPT) may arguably be seen as a modest extension of available forms like EPT [...]

→ We will follow your suggestions to add more text to further clarify dual forms and cost calibration within the constraints of the main manuscript or supplement.

We respectfully disagree that Orlicz-EPT is a modest extension of EPT. Below are the reasons:

• GST is recognized as a scalable variant of OW (see a review in Appendix B.1.5) [36]. However, unlike OT, extending GST to accommodate unbalanced measures on a graph with a mass constraint is nontrivial, as discussed in lines 57-60.

• We believe that it is non-trivial to establish a connection between EPT on a graph [35] and a potential extension of GST [36] for unbalanced measures.

• As noted in Remark 3.1 (lines 138-140), simply applying Caffarelli and McCann's (2010) observations without calibration would result in a new ground cost for standard OT that is not guaranteed to be nonnegative, similar to [12, 33, 35] (including EPT). We stress that our calibration is crucial for the development involving Orlicz geometric structure, given that the $N$-function is defined on $\mathbb{R}_{+}$ (see lines 98-100).

Concluding remarks. We would be grateful if you could confirm whether our clarifications and responses adequately address your concerns. If they do, we kindly ask that you consider increasing your rating. We are also happy to address any additional questions or concerns you might have.

Reference

[R7] Hertzsch et al., DNA microarrays: design principles for maximizing ergodic, chaotic mixing. Small, 2007.

Dear Reviewer VFH4,

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

(1) [...] (OT on a graph) is not appropriately motivated [...] some more context would be appreciated [...]

→ OT problems for measures supported on a graph metric space have been explored in previous studies [34, 35, 36]. Notably, graph metrics extend tree metrics, which are utilized in scalable optimal transport methods like tree-sliced Wasserstein [R1, R2, R3, R4]. Tree-sliced Wasserstein, in turn, generalizes the popular sliced-Wasserstein approach [R5, R6]. The graph structure offers greater flexibility and degrees of freedom compared to the tree structure in tree-sliced Wasserstein and the line structure in sliced-Wasserstein. For a more in-depth discussion on the motivation behind optimal transport on graphs, please refer to [34]. We will elaborate on this further.

(2) [...] (computations) leading up to Equation (6) is relevant enough to be a Theorem or Proposition [...]

→ Thank you for your suggestion. We will summarize Equation (6) as a Proposition.

(3) [...] (weakness) writing and lack of clarity [...] (abstract) repetitive concepts and sentence structures that make reading this paper incredibly difficult [...] (in-display equations) crammed into the text [...] tables and figures (small) [...] giving more high-level insights [...]

→ We outline the key ideas of our proposed approaches in lines 52-81 and in the abstract (lines 1-25). We try to keep all important equations separated with explanatory text and define technical notions within both the equations and surrounding text.

We will follow your suggestions to incorporate additional text to clarify technical concepts, as well as expand figures and tables within the constraints of the main manuscript or supplement.

Concluding remarks. We would be grateful if you could confirm whether our clarifications and responses adequately address your concerns. If they do, we kindly ask that you consider increasing your rating. We are also happy to address any additional questions or concerns you might have.

References

[R1] Indyk & Thaper, Fast Image Retrieval via Embeddings. IWSCTV, 2003

[R2] Le et al., Tree-Sliced Variants of Wasserstein Distances. NeurIPS, 2019

[R3] Tran et al., Distance-based Tree-Sliced Wasserstein Distance. ICLR, 2025

[R4] Tran et al., Tree-Sliced Wasserstein Distance: A Geometric Perspective. ICML, 2025

[R5] Rabin et al., Wasserstein Barycenter and its Application to Texture Mixing. SSVMCV, 2011

[R6] Bonneel et al., Sliced and Radon Wasserstein Barycenters of Measures. JMIV, 2015