Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The authors consider the branched optimal transport (BOT) problem with multiple sources. There is a finite number of sources with supplies and sinks (terminals) with demands located at fixed positions. We optimize the transportation between sinks and demands with respect to a directed edge-weighted graph and positions of nodes. The edges interconnect the terminals with the help of additional nodes (branching points). The edge direction indicates the direction of mass flow. The edge weight specifies the absolute flows.

First, the authors investigate the topology and geometry of BOT solutions. They prove sufficient and necessary conditions for a BOT solution to be optimal for a chosen topology (lemma 2.1). Then the authors proposed a geometric approach to optimize BOT solutions, a generalization of the previously proposed approach, developed for BOT problems with a single source.

Second, the authors consider conditions under which coupled branching points (BPs) are not optimal, which can be used to improve the transportation cost of a BOT solution. In particular, they proved that topology could be improved if its relatively optimal solution (ROS) contains coupled BPs. 

Third, they consider the case of two-dimensional Riemannian manifolds embedded into 3-dimensional Euclidean space. The authors proved a necessary condition for a ROS.

Finally, they propose heuristics and numerical optimization, which contains an effective algorithm for geometry optimization, followed by a heuristic for topology optimization. The authors claim that the paper is the first to propose heuristics for multiple sources, which do not require user supervision.
strengths_and_weaknesses: Strengths
- The authors consider a problem statement of a branched optimal transport (BOT) problem with multiple sources. Although the problem statement is purely theoretical, many real-world problems can be formulated in this way. So I consider the topic of the paper important.
- The results seem novel: the paper contains many new results about the properties of ROS for the BOT problem and new algorithms.
- The text of the paper is clearly written.

Weaknesses
- The paper is a bit theoretical. In particular, the authors did not consider solutions to any applied problems based on the proposed methods.
- I would propose to add some additional ablation studies; see comments below.
questions: - The paper (if we also consider the results in the Appendix) is very long. Still, I think it could be interesting to see some corner cases:
1) The authors mentioned methods from [26, 28] for the single source case. What is about comparing their performance to the proposed approach? Also, a comparison with the method from [21] can be made.
2) For alpha = 1, we get an OT problem. What is about comparing the proposed approach to some standard OT solvers?
3) Performance of the simulated annealing procedure significantly depends on how the probability of sampling a particular edge is defined and how the normalizing factor d_min is defined. Any empirical results on how this influences the performance?

- Description of Algorithm 2 in Appendix: step 7 is missing?

- On the one hand, the theoretical part of the paper is well written; on the other hand, I think some additional structuring of the text is needed. The paper proposes a novel algorithm. Different parts of the algorithm are scattered across the main text, while their detailed description is in the Appendix. I would propose to include some description of the main steps of the algorithm and references to the corresponding sections of the main text and the Appendix where the detailed description is provided.

- Figure 3: it seems that in Figure 3(c) a_0 is missing

- Section E.1.4 about the “numerical” proof for the remaining parameter space. Any comments on specific technical difficulties why it is impossible to provide analytical proof?

- Any fundamental qualitative explanation of the magic scaling n^{1.4} in line 1089 in the Appendix? What is the reason for such scaling?

- Any experiments for the Riemannian case?
limitations: The paper does not have any negative societal impact. It can have even positive societal impact since some resource allocation problems can be solved using the proposed approach, which is essential from ESG perspective.

I think that the limitations of the proposed approach are also adequately addressed.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: The authors perform a theoretical study of the branched optimal transport (BOT) in the plane, and also suggest a heuristic optimization strategy for the problem. On the theoretical side, they give a geometric construction algorithm for plane BOT solutions, argue for degree 3 branching of the optimal networks via a generalized argument of Bernot et al., and generalize this statement to 2D Riemannian manifolds embedded in $R^3$. 

On the numerics and optimization side, their algorithm has two subalgorithms: one aimed at optimization of branching points given a tree topology, and another aimed at optimizing the tree topology. The first is inspired and drawn from a method of Smith for finding Steiner trees, while the second follows an informed heuristic based on node-edge distance to delete random edges and replace them with improved topologies. The method is tested on small numbers of terminals and is shown to achieve optimality quickly in many instances compared to the brute-force approach.
strengths_and_weaknesses: Strengths:

- The theoretical arguments are rather extensive and seem valid, as far as I have checked them.
- The problem tackled is an interesting one, from a theoretical perspective, and does not seem to be extensively studied. 
- The result on limited degree of branching points is a nice, easy to understand, and impactful result.

Weaknesses: 
- The paper does not cover or recommend any concrete ML applications of the plane BOT problem.
- Nearly all of the theoretical arguments and constructions, as well as the optimization procedure for fixed topology are generalizations of ideas presented in other approaches.
- The result on generalization to 2D embedded surfaces seems relatively straightforward and not all that significant perhaps. Especially without algorithms adapted to that scenario, or example uses.
- The exposition is challenging to follow, as it generally provides brief glimpses into various theoretical constructions, and then directs the reader to extensive appendices.
- The numerical section is rather brief, given the applied nature of NeurIPS. Only one simple experiment is referenced (though more are in the appendix.

This paper leaves me wandering if it would be better split into a theoretical and numerical investigation. The theoretical portion could be submitted to a different venue, while the numerical portion could be more extensively explored and detailed. As it stands, the paper is sort of an odd omnibus.
questions: 1. Do you have any specific machine learning applications in mind for this problem? Many examples are given or suggested for OT with convex costs, but not for OT with concave costs. In particular, I imagine the plane restriction might be rather limiting, since most data in ML is high-dimensional.
2. Do you have more detailed information on runtime that could be placed in the main text and/or summarized there? I think many researchers looking to apply your method would be interested to have them there.
3. Do you have any insights on whether the techniques or heuristics would be valid for the problem in higher dimensions?
4. Why didn't you compare to the algorithm of Oudet and Santambrogio (A Modica-Mortola approximation for
branched transport and applications)?
limitations: The authors have acknowledged the limitations of their method, which mainly center around limited scope, but have not motivated why this limited scope is still interesting.
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: The paper studies Branched Optimal Transport (BOT). The problem consists of finding the optimal topology, and achieving the optimal geometry of the BOT network of multiple sources and sinks, given the optimal topology. While it is known that the optimal topologies for such embeddings are trees, the authors make a further step by show that, in the optimal topology, every branching point has at most 3 neighbors. Given the optimal topology, this work also proposes a new geometric optimization strategy for the case of multiple sources, which is generalized from an approach in the literature.  The results also generalize to BOT on Riemannian manifolds. Finally, based on the developed results, they propose heuristic algorithms to solve the BOT problem.

strengths_and_weaknesses: My main concern is that the paper's scope might not be much relevant to the ML community, while certain technical contribution can be interesting. The theoretical results can fit the mathematics community more for its combinatorial and geometrical nature, or fit the OR community for its relevance to routing and/or transportation systems. Yet, I cannot see how this paper can much benefit the ML community. Note that though OT is a simpler formulation than that considered in this work, it has applications in GAN vastly, domain adaptation, and color transfer, etc. so research aiming to solve OT competitively or study OT has been helpful. 
The authors may consider well motivating the paper by some concrete applications in ML, whereby BOT is part of the problem formulation or at least conveys some idea/intuition. 
questions: N.A.
limitations: As above.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper under review studied the problem of branched optimal transport with multiple sources.
As a generalization of OT, BOT optimizes the transportation by allowing extra branching points. 
A hyperparameter $\alpha$ is used to control the efficiency of transporting mass together.
The transportation flow is captured as a graph, whose vertex set contains the sources, sinks and BP.
In order to obtain an optimal solution, 
one needs to find both how vertices are connected (topology) and where the BPs are located (geometry).

Under the above framework, the authors proved that for a graph to be optimal, 
the degree of a branch point has to be 3. 
Moreover, the authors provided an analytic approach and a numerical algorithm to find the optimal locations of BP.
Furthermore, the authors presented an algorithm to approximate the optimal topology of BOT.
In addition, the authors considered generalization to 2-D Riemannian manifolds.

strengths_and_weaknesses: Strengths:
The paper is well-written and easy to follow.
The idea of allowing multiple sources for BOT is natural, 
the interpolation between OT and euclidean Steiner tree problem is interesting. 
The results are novel and sound.


Weaknesses:

A little concern regarding the motivation and practicality.

Motivation: it would be nice if the authors could provide some further explanation why would BOT be useful.
For example, describe a practical example where combined transportation is feasible,
then in that example, how do one pick $\alpha$ to model the case (illustrate that OT is not optimal).
And further how to use algorithms (or theoretical results) developed in this paper to obtain an optimal plan.

Practicality: the running time is not shown in the paper, how fast is the algorithm comparing to Sinkhorn for OT,
i.e. for a given problem, pick $\alpha = 1$, $\alpha = 0.5$, run Sinkhorn for $\alpha = 1$, 
run Alg 1 and Alg3 (from the supp) for $\alpha = 0.5$, comparing the running time. 

questions: Q1: Regarding the topology of $T$: it is unclear what information are enclosed in the topology of $T$.
From the description in the paper, it seems only the graph structure is consider as the topology of a tree.
However from the set up (eq 1), number of branch points ($|B|$), weights on edges ($m_{ij}$) are all variables.
How does one optimize these. In particular, for instance if two edges going out of a source, how does one 
determine how much flow each edge shall carry? 



Q2: (continuation of Q1) In line 106, the authors stated "first, we determine all edge flows (see Sect. 2)".
How are the edge flows are chosen? Could not find in section 2. Are the edge flows randomly initialized, 
then optimized somehow?


Q3: Line 289: "Then, one calculates the distance $d(e, c)$
between $c$ and every edge $e = (i, j)$ in the larger component". How does the distance $d(e, c)$ is defined here?

Q4: Some interpretation on "no degree greater than 3 branch points 
are possible for optimal solution" would be nice.
If it is just graph, one can easily switch between
a degree 4 branch point and two degree 3 branch points.
It is not feasible when cost are related,why?

Q5: Is the optimal solution for BOT unique? 



Minor points: 
- change of disk sizes in Fig 1 is not that visible, could scale a bit more.

- it is probably better to move algorithms to the main text if space allows.

- line 293, "node c" --> "component c".

limitations: The authors mentioned that it is difficulty 
to verify the efficiency of the proposed algorithm for large BOT problem. 
My guess is that the running time will be long for the proposed BOT problem comparing to OT.
Considering BOT is a NP-problem, it is expected. It would be nice if the authors could say a bit 
more along this line.
review_title: null

Meta-review: metareview: The paper presents novel structural and algorithmic results for solving the branched optimal transport problem. In the problem, flow is to be routed from sources to sinks (terminals) in the plane with the possibility of adding non-terminal intermediate nodes. The flow cost on each edge is proportional to the distance between endpoints and subadditive in flow amount; this encourages solutions   with “branching”, where flow is routed along common paths. The problem is to select the topology of the graph, location of branching points, and flow amounts. The paper presents structural results about the optimal solution: it is always a tree, which also determines the optimal flow amounts. Results are also given about the branching factor and angles in an optimal solution, which are used in a heuristic algorithm for placing the branching points.

Reviewers unanimously found the results to be novel and interesting, and the paper of high quality. They appreciated the theoretical and algorithmic work. Reviewers questioned what applications this work might have (especially to ML) — no concrete applications were given in the paper, but the authors speculated on some in the rebuttal. Given this, two reviewers questioned whether the scope of the paper was a good match for NeurIPS. The meta-reviewer finds the match appropriate, given the interest in optimization and OT within the NeurIPS community, but these reviewer comments indicate that the audience is likely narrow, and the paper could be strengthened by connecting it to concrete applications. 

confidence: Certain
Decision: Accept