Technical Summary: Convex Distance Operator Transport (CDOT)

Problem Statement

Optimal Transport (OT) provides a fundamental framework for comparing probability measures by quantifying the minimal cost to transport mass. However, classical OT based on the Wasserstein distance requires data distributions to reside in the same space, a restriction that limits its application to heterogeneous domains. The Gromov–Wasserstein (GW) and Fused Gromov–Wasserstein (FGW) frameworks address this by comparing distributions through their intrinsic metric-measure (mm) spaces, aligning structural information without requiring a cross-domain cost.

Despite their versatility, (F)GW formulations suffer from a fundamental limitation: non-convexity. This arises because the GW cost involves a tensor product of the coupling ($\pi \otimes \pi$), leading to pairwise distance comparisons that create a non-convex optimization landscape. Consequently, standard optimization algorithms typically converge only to local stationary points, and the resulting solutions may lack global optimality guarantees. Furthermore, existing convex relaxations often fail to preserve the pseudometric property on the space of attributed mm spaces or require additional smoothing parameters (e.g., entropic regularization) that alter the problem's geometry.

Methodology: Convex Distance Operator Transport (CDOT)

The authors propose Convex Distance Operator Transport (CDOT), the first convex optimal transport framework designed to align heterogeneous mm spaces while preserving both feature correspondence and intrinsic geometric structure.

Core Formulation

CDOT lifts the geometric structure of each space and the transport plan into linear operators acting on $L^2$ spaces. Instead of comparing pairwise distances directly, CDOT aligns aggregated distance structures via operator composition.

Given two attributed compact mm spaces $\mathcal{X} = (X, d_X, P_X, f_X)$ and $\mathcal{Y} = (Y, d_Y, P_Y, f_Y)$, and a transport plan $\pi \in \Pi(P_X, P_Y)$, the CDOT objective $L_\alpha(\pi)$ balances two components:

1. Feature Alignment: $F(\pi) = \mathbb{E}_\pi[\|f_X(X) - f_Y(Y)\|_2^2]$, which encourages element-wise similarity between features.
2. Structural Regularization: $R(\pi) = \|D_{P_X} T_\pi - T_\pi D_{P_Y}\|_{HS}^2$, which penalizes structural discrepancy.

Here:

• $D_{P_X}$ and $D_{P_Y}$ are distance operators defined as integral operators on $L^2(X, P_X)$ and $L^2(Y, P_Y)$, representing the continuous analogue of pairwise distance matrices.
• $T_\pi$ is the conditional expectation operator associated with the coupling $\pi$, mapping functions from $L^2(Y, P_Y)$ to $L^2(X, P_X)$.
• $\|\cdot\|_{HS}$ denotes the Hilbert–Schmidt norm.

The CDOT problem is formulated as:
$$\inf_{\pi \in \Pi(P_X, P_Y)} \left[ (1-\alpha)F(\pi) + \frac{\alpha}{2}R(\pi) \right]$$

Theoretical Foundations

• Convexity: The authors prove that the CDOT objective is convex. This is achieved because the structural term $R(\pi)$ depends linearly on the conditional expectation operator $T_\pi$ (which is affine in $\pi$) and the squared Hilbert–Schmidt norm is convex. This contrasts with GW, where the quadratic dependence on $\pi$ creates non-convexity.
• Pseudometricity: The resulting CDOT discrepancy, defined as the square root of the minimum objective value, is proven to be a valid pseudometric on the space of attributed compact mm spaces.
• Dispersion Gap: The paper introduces a "dispersion gap" analysis to formally elucidate the relationship between CDOT and GW. It is shown that the GW objective can be decomposed into the CDOT objective plus a dispersion penalty $V(\pi)$, which quantifies the spatial uncertainty of the coupling. The non-convexity of GW stems from this dispersion term, which favors deterministic (concentrated) couplings. CDOT achieves convexity by isolating the structural component and discarding this penalty.

Optimization

In the finite-sample regime, the CDOT problem reduces to a convex quadratic program over a transport polytope. The authors solve this using the Frank–Wolfe (FW) algorithm, chosen for its projection-free nature. They propose a "lazy gradient" variant that exploits the quadratic structure to update gradients efficiently, reducing the per-iteration computational overhead from cubic to quadratic time relative to the matrix operations, though the overall complexity remains dominated by the linear minimization oracle ($O(n^3)$).

Key Contributions

1. First Convex Geometry-Aware OT Framework: CDOT is the first framework to provide a convex formulation for aligning heterogeneous mm spaces that explicitly recovers an optimal transport plan, unlike slicing-based methods that only estimate discrepancy.
2. Theoretical Guarantees:
   • Existence and Convexity: Proven existence of an optimal coupling and the convexity of the objective without requiring entropic regularization.
   • Pseudometric Property: Established that the CDOT discrepancy is a valid pseudometric.
   • Risk Consistency: Derived non-asymptotic risk bounds decomposed into optimization and statistical errors, proving that the estimator is risk-consistent under a globally convergent Frank–Wolfe algorithm.
3. Geometric Insight: The "dispersion gap" analysis formally explains the source of non-convexity in GW and demonstrates how CDOT filters out the dispersion term to achieve a convex landscape.
4. Empirical Performance: Demonstrated superior performance over existing methods (FGW, Entropic FGW, IsoRank, Spectral Matching, COPT) on synthetic point clouds, brain connectomes (OASIS-3), and graph classification benchmarks (TUDataset).

Experimental Results

• Synthetic Data: On 2D clustered point clouds, CDOT consistently achieved the lowest Mean Squared Error (MSE) across varying sample sizes, showing stable convergence. In contrast, Entropic FGW (EFGW) exhibited high sensitivity to the regularization parameter $\epsilon$, often failing to match CDOT's precision or getting trapped in local optima when $\epsilon$ was small.
• Brain Connectomes (OASIS-3): On structural brain networks, CDOT significantly outperformed FGW when using diffusion distance (a robust, global metric), achieving 61.36% matching accuracy versus 18.53% for FGW. The authors attribute this to CDOT's ability to align aggregated geometric profiles even when pairwise contrasts are smoothed out by diffusion, whereas the non-convex GW objective loses discriminative power in such flat landscapes. Under geodesic distance, FGW performed slightly better, highlighting the trade-off between rigid pairwise alignment and robust global alignment.
• Graph Classification: On TUDataset benchmarks, CDOT consistently outperformed baseline methods (FGW, GW, COPT) in classification accuracy, particularly in datasets rich in feature information (e.g., MUTAG, ENZYMES). Notably, CDOT maintained the best performance even on the IMDB-BINARY dataset (no node features), suggesting its operator-based geometry captures topological distinctions more effectively than standard GW approaches.

Significance and Claims

The paper claims that CDOT offers a robust and reliable alternative to existing non-convex OT methods for structured data. By ensuring a convex optimization landscape, CDOT guarantees convergence to a global optimum without the need for hyperparameter tuning (like entropic regularization) that can destabilize solutions. The framework is particularly significant for applications involving heterogeneous domains where intrinsic geometric structures must be preserved, such as brain network analysis and graph classification.

The authors modestly note two limitations:

1. CDOT is designed for operator-level alignment rather than strict one-to-one matching; zero discrepancy does not necessarily imply exact measure-preserving isometry.
2. While convex, the current implementation relies on Frank–Wolfe iterations dominated by OT subproblems, making it better suited for moderate problem sizes rather than very large-scale settings.

Future directions suggested by the authors include developing statistical inference frameworks (e.g., hypothesis testing for isomorphism) based on the CDOT discrepancy and integrating the CDOT objective as a differentiable layer in deep neural networks to jointly learn optimal ground metrics.