Technische Samenvatting: Convex Distance Operator Transport (CDOT)

Probleemstelling

Optimal Transport (OT) biedt een fundamenteel kader voor het vergelijken van waarschijnlijkheidsmaten door de minimale kosten te kwantificeren om massa te transporteren. Echter, klassieke OT gebaseerd op de Wasserstein-afstand vereist dat datadistributies zich in dezelfde ruimte bevinden, een beperking die de toepassing op heterogene domeinen limiteert. De Gromov–Wasserstein (GW) en Fused Gromov–Wasserstein (FGW) kaders pakken dit aan door distributies te vergelijken via hun intrinsieke metriek-maat (mm) ruimtes, waarbij structurele informatie wordt uitgelijnd zonder dat een cross-domein kostenfunctie nodig is.

Ondanks hun veelzijdigheid lijden (F)GW-formuleringen aan een fundamentele beperking: niet-convexiteit. Dit komt doordat de GW-kosten een tensorproduct van de koppeling ($\pi \otimes \pi$) bevatten, wat leidt tot paarwijze afstandvergelijkingen die een niet-convexe optimalisatielandschap creëren. Bijgevolg convergeren standaard optimalisatiealgoritmen doorgaans slechts naar lokale stationaire punten, en de resulterende oplossingen missen vaak garanties op globale optimaliteit. Bovendien falen bestaande convexe relaxaties vaak in het behouden van de pseudometrische eigenschap op de ruimte van geattribueerde mm-ruimtes, of vereisen ze extra smoothing-parameters (bijv. entropische regularisatie) die de geometrie van het probleem veranderen.

Methodologie: Convex Distance Operator Transport (CDOT)

De auteurs stellen Convex Distance Operator Transport (CDFOT) voor, het eerste convexe optimale transport-kader ontworpen om heterogene mm-ruimtes uit te lijnen terwijl zowel de feature-correspondentie als de intrinsieke geometrische structuur behouden blijven.

Kernformulering

CDOT tilt de geometrische structuur van elke ruimte en het transportplan naar lineaire operatoren werkend op $L^2$-ruimtes. In plaats van paarwijze afstanden direct te vergelijken, lijnt CDOT geaggregeerde afstandstructuren uit via operatorcompositie.

Gegeven twee geattribueerde compacte mm-ruimtes $\mathcal{X} = (X, d_X, P_X, f_X)$ en $\mathcal{Y} = (Y, d_Y, P_Y, f_Y)$, en een transportplan $\pi \in \Pi(P_X, P_Y)$, balanceert de CDOT-doelfunctie $L_\alpha(\pi)$ twee componenten:

1. Feature Alignment: $F(\pi) = \mathbb{E}_\pi[\|f_X(X) - f_Y(Y)\|_2^2]$, wat elementaire gelijkenis tussen features stimuleert.
2. Structural Regularization: $R(\pi) = \|D_{P_X} T_\pi - T_\pi D_{P_Y}\|_{HS}^2$, wat de structurele discrepantie bestraft.

Hierbij:

• $D_{P_X}$ en $D_{P_Y}$ zijn afstandoperatoren gedefinieerd als integraaloperatoren op $L^2(X, P_X)$ en $L^2(Y, P_Y)$, die de continue analogon zijn van paarwijze afstandmatrices.
• $T_\pi$ is de conditionele verwachtingsoperator geassocieerd met de koppeling $\pi$, die functies van $L^2(Y, P_Y)$ naar $L^2(X, P_X)$ brengt.
• $\|\cdot\|_{HS}$ staat voor de Hilbert–Schmidt-norm.

Het CDOT-probleem wordt geformuleerd als:
$$\inf_{\pi \in \Pi(P_X, P_Y)} \left[ (1-\alpha)F(\pi) + \frac{\alpha}{2}R(\pi) \right]$$

Theoretische Fundamenten

• Convexiteit: De auteurs bewijzen dat de CDOT-doelfunctie convex is. Dit wordt bereikt omdat de structurele term $R(\pi)$ lineair afhankelijk is van de conditionele verwachtingsoperator $T_\pi$ (die affien is in $\pi$) en de gekwadrateerde Hilbert–Schmidt-norm convex is. Dit contrasteert met GW, waar de kwadratische afhankelijkheid van $\pi$ niet-convexiteit creëert.
• Pseudometriciteit: De resulterende CDOT-discrepantie, gedefinieerd als de wortel van de minimale doelfunctiewaarde, wordt bewezen een geldige pseudometriek te zijn op de ruimte van geattribueerde compacte mm-ruimtes.
• Dispersion Gap: Het artikel introduceert een "dispersion gap"-analyse om de relatie tussen CDOT en GW formeel toe te lichten. Er wordt aangetoond dat de GW-doelfunctie kan worden ontleed in de CDOT-doelfunctie plus een dispersie-straf $V(\pi)$, die de ruimtelijke onzekerheid van de koppeling kwantificeert. De niet-convexiteit van GW komt voort uit deze dispersieterm, die deterministische (geconcentreerde) koppelingen bevoordeelt. CDOT bereikt convexiteit door de structurele component te isoleren en deze straf weg te laten.

Optimalisatie

In het regime van eindige steekproeven reduceert het CDOT-probleem tot een convex kwadratisch programma over een transportpolytoop. De auteurs lossen dit op met het Frank–Wolfe (FW) algoritme, gekozen vanwege de projectievrije aard. Ze stellen een "lazy gradient"-variant voor die de kwadratische structuur exploiteert om gradiënten efficiënt bij te werken, waardoor de computationele overhead per iteratie wordt verminderd van cubisch naar kwadratisch ten opzichte van de matrixoperaties, hoewel de algehele complexiteit dominant blijft door de lineaire minimalisatie-oracle ($O(n^3)$).

Belangrijkste Bijdragen

1. Eerste Convexe Geometrie-bewuste OT-framework: CDOT is het eerste framework dat een convexe formulering biedt voor het uitlijnen van heterogene mm-ruimtes die expliciet een optimaal transportplan herstelt, in tegen tegenstelling tot slicing-gebaseerde methoden die alleen de discrepantie schatten.
2. Theoretische Garanties:
   • Bestaan en Convexiteit: Bewijs van het bestaan van een optimale koppeling en de convexiteit van de doelfunctie zonder dat entropische regularisatie vereist is.
   • Pseudometrische Eigenschap: Vastgesteld dat de CDOT-discrepantie een geldige pseudometriek is.
   • Risico-consistentie: Afgeleide niet-asymptotische risicobanden gedecomposed in optimalisatie- en statistische fouten, waarmee bewezen wordt dat de estimator risico-consistent is onder een globaal convergerend Frank–Wolfe-algoritme.
3. Geometrisch Inzicht: De "dispersion gap"-analyse legt formeel uit wat de bron van niet-convexiteit in GW is en demonstreert hoe CDOT de dispersieterm filtert om een convex landschap te bereiken.
4. Empirische Prestaties: Toont superieure prestaties aan ten opzichte van bestaande methoden (FGW, Entropic FGW, IsoRank, Spectral Matching, COPT) op synthetische puntenwolken, hersenconnectomen (OASIS-3) en grafiekclassificatie-benchmarks (TUDataset).

Experimentele Resultaten

• Synthetische Data: Op 2D geclusterde puntenwolken behaalde CDOT consistent de laagste Mean Squared Error (MSE) over variërende steekproefgroottes, waarbij stabiele convergentie werd getoond. In contrast vertoonde Entropic FGW (EFGW) een hoge gevoeligheid voor de regularisatieparameter $\epsilon$, waarbij het vaak faalde om de precisie van CDOT te evenaren of vastliep in lokale optima wanneer $\epsilon$ klein was.
• Hersenconnectomen (OASIS-3): Op structurele hersennetwerken presteerde CDOT aanzienlijk beter dan FGW bij het gebruik van diffusieafstand (een robuuste, globale metriek), met een matching nauwkeurigheid van 61,36% versus 18,53% voor FGW. De auteurs schrijven dit toe aan het vermogen van CDOT om geaggregeerde geometrische profielen uit te lijnen, zelfs wanneer paarwijze contrasten zijn afgevlakt door diffusie, terwijl de niet-convexe GW-doelfunctie aan onderscheidend vermogen verliest in dergelijke vlakke landschappen. Onder geodesische afstand presteerde FGW iets beter, wat de afweging benadrukt tussen rigide paarwijze uitlijning en robuuste globale uitlijning.
• Grafiekclassificatie: Op TUDataset-benchmarks presteerde CDOT consequent beter dan baseline-methoden (FGW, GW, COPT) in classificatienauwkeurigheid, met name op datasets die rijk zijn aan feature-informatie (bijv. MUTAG, ENZYMES). Opvallend genoeg behield CDOT de beste prestaties, zelfs op de IMDB-BINARY dataset (geen node-features), wat suggereert dat de operator-gebaseerde geometrie van CDOT topologische verschillen effectiever vastlegt dan standaard GW-benaderingen.

Betekenis en Claims

Het artikel claimt dat CDOT een robuust en betrouwbaar alternatief biedt voor bestaande niet-convexe OT-methoden voor gestructureerde data. Door een convex optimalisatielandschap te garanderen, verzekert CDOT convergentie naar een globaal optimum zonder de noodzaak voor hyperparameter-tuning (zoals entropische regularisatie) die oplossingen kan destabiliseren. Het kader is bijzonder significant voor toepassingen waarbij heterogene domeinen betrokken zijn waarbij intrinsieke geometrische structuren behouden moeten blijven, zoals hersennetwerkanalyse en grafiekclassificatie.

De auteurs merken bescheiden twee beperkingen op:

1. CDOT is ontworpen voor uitlijning op operatorniveau in plaats van strikte één-op-één matching; een nul-discrepantie impliceert niet noodzakelijkerwijs een exacte maat-behoudende isometrie.
2. Hoewel convex, is de huidige implementatie afhankelijk van Frank–Wolfe-iteraties die gedomineerd worden door OT-subproblemen, waardoor het beter geschikt is voor matige probleemgroottes dan voor zeer grootschalige settings.

Toekomstige richtingen die door de auteurs worden gesuggereerd, omvatten het ontwikkelen van statistische inferentiekaders (bijv. hypothesetesten voor isomorfisme) gebaseerd op de CDOT-discrepantie en het integreren van de CDOT-doelfunctie als een differentieerbare laag in diepe neurale netwerken om optimale grondmetrieken gezamenlijk te leren.