T-GROW: Robust and Scalable Tree-based Gromov-Wasserstein

Comparing structured and multi-modal data across different representation spaces remains a core challenge in machine learning, as metric distances between individual samples are not directly defined across domains. The Gromov-Wasserstein (GW) distance addresses this by seeking a geometry-preserving alignment between probability measures supported on different metric spaces. However, its underlying non-convex quadratic formulation becomes computationally prohibitive at scale. To alleviate this burden, scalable tree-based methods replace full pairwise geometry with simpler summaries of hierarchical structure. While relying solely on root-to-node path lengths enables fast alignment, this structural reduction discards rich pairwise relational geometry within the tree hierarchy. In this work, we introduce T-GROW, a robust and scalable tree-based GW discrepancy built on co-depth, defined as the length of the root path shared by two samples before their paths diverge. For any fixed hierarchy, we prove that solving GW over its leaf clusters under co-depth is exactly equivalent to solving GW over the original samples under the induced tree metric. This theoretical equivalence guarantees that T-GROW retains the complete pairwise geometry of the hierarchy without approximation loss, while shifting the quadratic optimization to a significantly compressed leaf resolution. Experimental evaluations show that T-GROW consistently improves structural matching over scalable GW baselines, exhibits strong robustness to structural noise, and scales efficiently to tens of millions of samples.