- Rating
- 3
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
T-GROW propose a way to compute Gromow-Wasserstein (GW) that rely on trees. Each of the input measures is clustered with randomized hierarchies which are then used to compute an average of the discrepancy (eq. 13 in the paper). They use the Gromov product (or co-depth) to encode the geometry between the leaves (which corresponds to the distance between the root and the lowest common ancestor to those points). The paper gives theoretical insights on the method by showing for instance that GW over the leaf clusters is equal to GW over the samples under the pulled-back tree metric so that the reduction to the computation to the leaves add no optimization gap (Theorem 1). Experiments show case the method over several datasets that have up to points which corresponds to real-world scenarios.
Critical strengths
- The idea is well motivated: FlowAlign reduces the tree to a weighted list of root depth and solve a 1d problem so any two trees with the same depth distribution cannot be distinguished with GW. The paper propose to restore the co-depth term in the tree distance as they identify this as a substential loss of information.
- Cost and empirical gains: Each cloud point is clustered into a tree and this operation costs ( number of random trees, the depth, the branching factor and the feature dimension), this is linear in which allows it to be applied to large scale datasets. After building the tree, the cloud point are reduced to the leaves and GW is solved on those leaves. The numerical experiments highlight improvement in terms of accuracy on the downstream tasks over FlowAlign which relates to the claim that restoring the co-depth helps.
Critical weaknesses
- The theory is a bit weaker than what the abstract suggest:
- Theorem 1 only states that solving GW whose distances are constant on cluster of points can be solved on the clusters and not the whole points and this hold for any partition. The "zero optimization gap" applies only to the global optimum and not to the local optimum that will be reached by gradient descent on this non-convex problem. Theorem 2 bounds the gap to the true value to GW by a quantity that the paper does not control.
- In the experiments, no experiment isolates the contribution of using a tree metric. FlowAlign and DepthAlign change both the geometry of the data and the solver of the problem. A control experiment that runs the same pipeline with the original anchor distances instead of the tree distance is required to show that co-depth drives the numerical gains of the method. The unary-only variant does not answer this as it only compares co-depth with root depth.
Questions for authors
- Does the separation demonstrated in Proposition 2 extend to DepthAlign?
- Since the problem is non-convex, how sensitive is T-GROW to the initialization of the conditional-gradient solver?
- How does T-GROW perform on a large scale datasets when differ from the generating hierarchy? on a benchmark whose hierarchy is not a regular tree?
- Does T-GROW converge to GW in any regime?
6 comments
Response to Reviewer zchD Part 2
W2: "In the experiments, no experiment isolates … co-depth with root depth."
Answer
We ran the relation control on three tasks. Within each comparison, partitions, masses, slices, solver settings and readout are fixed. For nodes with member sets , masses and input distances , we compare:
- Representative distance: between node representatives, centroids on S3DIS and SNARE-seq and medoids on CIFAR-100.
- Tree path distance: , with edge lengths given by the distances between parent and child representatives. This is the tree distance of Eq. (9).
- Co-depth (ours): the mean relation estimated from the input distances on the same hierarchy,
Co-depth is the relation used in the experiments below. Its definition will be explicit in Sec. 2. On S3DIS we use the RMS over the same member pairs, , computed from cell means and covariance traces at linear cost. Each relation receives the same normalization rule: S3DIS matrices have zero diagonals and are divided by their maxima, SNARE-seq matrices retain their original scale, CIFAR-100 uses off-diagonal standardization at every level.
CIFAR-100 blind matching, 10 seeds × 5 permutations, the relation is used at every level of the solver:
| Relation at each level | Accuracy |
|---|---|
| Tree path distance | |
| Representative distance | |
| Co-depth (ours) |
S3DIS, three seeds; the relation is used at the leaves:
| Relation on the same tree partition | Lobby accuracy | Pair C accuracy |
|---|---|---|
| Tree path distance | ||
| Representative distance | ||
| Co-depth (ours) |
SNARE-seq, ten seeds, shuffled targets and independent trees, relations are used at the leaves. At each leaf budget, partitions are identical across relations.
| Leaves | Tree path distance | Representative distance | Co-depth (ours) |
|---|---|---|---|
| 4 | |||
| 8 | |||
| 16 | |||
| 32 | |||
| 64 |
Co-depth has the highest mean alignment quality in these controls. On CIFAR-100 it matches or exceeds representative distances on 45 of the 50 instances and outperforms tree path distances on 40. The relation control uses common preprocessing across variants, explaining its accuracy versus in the main configuration. On SNARE-seq, the advantage over representative distances is largest with four and eight leaves, where it wins on nine of the ten seeds in each setting. At finer resolutions the two relations perform similarly. These results support retaining within-node information that a single representative can omit.
The hierarchy itself also contributes: with the relation estimator fixed, S3DIS Pair C accuracy is with tree partitions versus with random Voronoi cells. W1 gives the SNARE-seq and CIFAR-100 partition controls. The unary ablation uses the same trees and search and gives versus for T-GROW. These controls separately assess root-depth information, partitioning and relation estimation.
Q1: "Does the separation demonstrated in Proposition 2 extend to DepthAlign?"
Answer
Proposition 2 applies to FlowAlign's root-depth summary. DepthAlign recursively aligns child-depth measures and retains more information, so the same indistinguishability argument does not establish a separation for DepthAlign. We will make this scope explicit. On identical trees, T-GROW has higher mean label-transfer accuracy than DepthAlign in every tested configuration of Q3.
Q2: "Since the problem is ... of the conditional-gradient solver?"
Answer
On SNARE-seq, for each of five hierarchy seeds we fixed the trees, relation matrices, solver settings and ensemble procedure. We compared one product-coupling start with three random feasible starts per seed, giving five and fifteen runs, respectively:
| CG initialization | FOSCTTM ↓ |
|---|---|
| Product coupling | |
| Random feasible couplings |
The two T-GROW means differ by , with a worst reported FOSCTTM of approximately . This indicates limited sensitivity to the tested initializations under the fixed ensemble procedure, which retains ten of one hundred hierarchy candidates by their leaf objective. W1 separately establishes objective and first-order stationarity identities for aggregation and lifting.
Response to Reviewer zchD Part 3
Q3: "How does T-GROW perform on a large scale datasets when differ from the generating hierarchy? on a benchmark whose hierarchy is not a regular tree?"
Answer
We built a large benchmark with an irregular generating hierarchy, fixed before any method was run. Each internal node has between two and five children at random; leaves occur at different depths, up to four, with random masses; two independent nonlinear maps produce observations in 16 and 24 dimensions; each domain has points. Encoder shapes are fixed in advance, and all tree methods use the same trees. Label-transfer accuracy over ten seeds:
| Encoder | Tree construction | T-GROW | DepthAlign | FlowAlign |
|---|---|---|---|---|
| hierarchical k-means | ||||
| hierarchical k-means | ||||
| farthest-point | ||||
| farthest-point |
T-GROW has the highest mean accuracy in all four configurations, despite the mismatch between regular encoders and the irregular hierarchy. Paired Wilcoxon tests give against both tree baselines; with k-means trees, T-GROW exceeds DepthAlign on all ten seeds. QGW with 256 cells reaches and SGW . For the encoder, total runtime is about 34 s with k-means trees and 17 s with farthest-point trees.
We also tested data generated without any tree. Latent clusters pass through two independent random nonlinear maps, to 64 and 48 dimensions, with independent additive noise. For every tree method the shape is chosen without labels, as the one with the lowest matching objective among 13 fixed shapes. Blind-matching accuracy:
| Noise | T-GROW | QGW | EGW | GW | DepthAlign | FlowAlign |
|---|---|---|---|---|---|---|
| 0.1 | ||||||
| 0.25 | ||||||
| 0.5 |
On the Fig. 1 generator, a matching encoder gives versus at most for FlowAlign and DepthAlign, a finer encoder on data gives versus at most . These tests support using an encoder at least as fine as the generating structure when that structure is known. The irregular and non-tree benchmarks above assess performance without such a match.
Q4: "Does T-GROW converge to GW in any regime?"
Answer
See W1 for convergence of optimal GW values under vanishing relation distortion, including the finite-data and vanishing-cell-diameter regimes and the numerical diagnostics.
Response to Reviewer zchD Part 1
We thank the reviewer for the constructive comments. We answer each weakness (Wi) and question (Qj) below. For the sake of clarity, we divide weaknesses into W1 and W2, corresponding to the 2 bullet points.
Answer
Theorem 1 and the role of the tree. The reduction holds for any partition. The co-depth hierarchy supplies a nested family of partitions: at depth ℓ, the represented point-level relation is dℓ=ZℓRℓZℓ⊤, where Zℓ is the membership matrix and Rℓ is a fixed node relation. Theorem 1 therefore applies at every level, supporting coarse-to-fine matching. The partition also affects the represented geometry. In a separate partition control with the relation estimator fixed, SNARE-seq FOSCTTM is 0.1498 for tree partitions, 0.1540 for random Voronoi cells and 0.1525 for flat farthest-point cells, at the same cell budget. On CIFAR-100, replacing the geometry-aware hierarchy with random balanced splits lowers accuracy from 0.653 to 0.368. The CIFAR-100 results below use the same 50 instances: 10 seeds × 5 target permutations, with shuffled targets and independent trees. Results are mean ± sample standard deviation unless a range is stated.
Local optima. The proof of Theorem 1 gives more than the statement about global optima. For every feasible point coupling π, E(π)=F(P),P=agg(π), and every feasible node coupling has a lift with the same cost. So the cost of any coupling computed at node resolution, optimal or not, equals the cost of its lift. Stationary points are preserved as well. Let gE(π)=maxγ∈Π(a,b)⟨∇E(π),π−γ⟩ be the Frank-Wolfe gap, the stopping criterion of conditional gradient. Since E=F∘agg, we have ∇E=agg∗∇F, and since aggregation maps Π(a,b) onto Π(α,β), gE(π)=maxQ∈Π(α,β)⟨∇F(P),P−Q⟩=gF(P). Thus, a first-order stationary node coupling lifts to a first-order stationary coupling of the represented point-level problem, with exactly the same objective value. The reduction does not make the problem convex; it guarantees that nothing is lost by working at node resolution, at any point of the optimization. As a numerical check on the same SNARE-seq relations, point-level and leaf-level CG agree to numerical precision in both objective values and aggregated couplings across six matched starts, including runs ending at different objective values.
Theorem 2: the distortion is controlled. For one domain with input distances dij, point masses ai, node masses αp, node-pair means Bpq, and q(i) the node containing i, the distortion of a node relation R satisfies δ2(R)=∑i,jaiaj[dij−Rq(i),q(j)]2=δ2(B)+∑p,qαpαq(Bpq−Rpq)2.
With the input distances at a fixed scale and the within-node means kept on the diagonal, the mean relation R=B therefore minimizes the distortion over all node-pair relations on a given partition. T-GROW keeps the co-depth hierarchy and estimates this mean relation between its nodes from the input distances; we call it co-depth (ours). Under nested refinement this minimum cannot increase.
The optimal represented GW values converge to the original GW value when the distortion in Theorem 2 vanishes. For the mean relation at a common fixed input scale, finite partitions refined to singletons recover the original distances exactly. More generally, on compact metric spaces, let the largest cell diameter εℓ tend to zero. For points i,i′ in one cell and j,j′ in another, ∣d(i,j)−d(i′,j′)∣≤d(i,i′)+d(j,j′)≤2εℓ. The mean member-pair relation satisfies ∥d−dℓ∥∞≤2εℓ⟶0 and Theorem 2 gives convergence of optimal GW values. The same bound permits zero diagonals because within-cell distances are at most εℓ. For the tree path distance, convergence requires its distortion to vanish, as when the weighted tree exactly represents the input metric; nested refinement alone is insufficient for arbitrary metrics. These guarantees concern optimal values, not elimination of CG optimization error.
The distortion is also measurable. On SNARE-seq, averaged over ten tree pairs, δX+δY is 0.363, 0.256, 0.210 and 0.169 for L=4,16,64,256 leaves. The separate refinement study measures values between 0.09 and 0.15 at nominal budget L=1024. The point-level CG solver returns a value of about 0.746, and computed reduced and point-level CG values differ by less than 0.013 across the tested resolutions. These numerical diagnostics are distinct from the optimal-value convergence guarantee.