Résumé Technique : Transport de Distance d'Opérateur Convexe (CDOT)

Énoncé du Problème

Le transport optimal (OT) fournit un cadre fondamental pour comparer des mesures de probabilité en quantifiant le coût minimal pour transporter la masse. Cependant, l'OT classique basé sur la distance de Wasserstein exige que les distributions de données résident dans le même espace, une restriction qui limite son application aux domaines hétérogènes. Les cadres de Gromov–Wasserstein (GW) et de Gromov–Wasserstein Fusionné (FGW) remédient à cela en comparant les distributions à travers leurs espaces métriques-mesures (mm) intrinsèques, alignant l'information structurelle sans nécessiter de coût inter-domaine.

Malgré leur polyvalence, les formulations (F)GW souffrent d'une limitation fondamentale : la non-convexité. Cela découle du fait que le coût GW implique un produit tensoriel du couplage ($\pi \otimes \pi$), ce qui conduit à des comparaisons de distances par paires qui créent un paysage d'optimisation non convexe. Par conséquent, les algorithmes d'optimisation standards convergent généralement uniquement vers des points stationnaires locaux, et les solutions résultantes peuvent manquer de garanties d'optimalité globale. De plus, les relaxations convexes existantes échouent souvent à préserver la propriété de pseudométrique sur l'espace des espaces mm attribués ou nécessitent des paramètres de lissage supplémentaires (par exemple, la régularisation entropique) qui altèrent la géométrie du problème.

Méthodologie : Transport de Distance d'Opérateur Convexe (CDOT)

Les auteurs proposent le Transport de Distance d'Opérateur Convexe (CDOT), le premier cadre de transport optimal convexe conçu pour aligner des espaces mm hétérogènes tout en préservant à la fois la correspondance des caractéristiques et la structure géométrique intrinsèque.

Formulation Centrale

Le CDOT lève la structure géométrique de chaque espace et le plan de transport en opérateurs linéaires agissant sur des espaces $L^2$. Au lieu de comparer directement les distances par paires, le CDOT aligne des structures de distance agrégées via la composition d'opérateurs.

Étant donné deux espaces mm compacts attribués $\mathcal{X} = (X, d_X, P_X, f_X)$ et $\mathcal{Y} = (Y, d_Y, P_Y, f_Y)$, et un plan de transport $\pi \in \Pi(P_X, P_Y)$, l'objectif CDOT équilibre deux composantes :

1. Alignement des Caractéristiques : $F(\pi) = \mathbb{E}_\pi[\|f_X(X) - f_Y(Y)\|_2^2]$, qui encourage la similitude élément par élément entre les caractéristiques.
2. Régularisation Structurelle : $R(\pi) = \|D_{P_X} T_\pi - T_\pi D_{P_Y}\|_{HS}^2$, qui pénalise la divergence structurelle.

Ici :

• $D_{P_X}$ et $D_{P_Y}$ sont des opérateurs de distance définis comme des opérateurs intégraux sur $L^2(X, P_X)$ et $L^2(Y, P_Y)$, représentant l'analogue continu des matrices de distance par paires.
• $T_\pi$ est l'opérateur d'espérance conditionnelle associé au couplage $\pi$, mappant les fonctions de $L^2(Y, P_Y)$ vers $L^2(X, P_X)$.
• $\|\cdot\|_{HS}$ désigne la norme de Hilbert–Schmidt.

Le problème CDOT est formulé comme :
$$\inf_{\pi \in \Pi(P_X, P_Y)} \left[ (1-\alpha)F(\pi) + \frac{\alpha}{2}R(\pi) \right]$$

Fondements Théoriques

• Convexité : Les auteurs prouvent que l'objectif CDOT est convexe. Cela est rendu possible car le terme structurel $R(\pi)$ dépend linéairement de l'opérateur d'espérance conditionnelle $T_\pi$ (qui est affine en $\pi$) et que la norme de Hilbert–Schmidt au carré est convexe. Cela contraste avec GW, où la dépendance quadratique de $\pi$ crée une non-convexité.
• Pseudométricité : La divergence CDOT résultante, définie comme la racine carrée de la valeur minimale de l'objectif, est prouvée être une pseudométrique valide sur l'espace des espaces mm compacts attribués.
• Écart de Dispersion : L'article introduit une analyse de l'« écart de dispersion » pour élucider formellement la relation entre CDOT et GW. Il est démontré que l'objectif GW peut être décomposé en l'objectif CDOT plus une pénalité de dispersion $V(\pi)$, qui quantifie l'incertitude spatiale du couplage. La non-convexité de GW provient de ce terme de dispersion, qui favorise les couplages déterministes (concentrés). Le CDOT atteint la convexité en isolant la composante structurelle et en écartant cette pénalité.

Optimisation

Dans le régime d'échantillonnage fini, le problème CDOT se réduit à un programme quadratique convexe sur un polytope de transport. Les auteurs le résolvent en utilisant l'algorithme de Frank–Wolfe (FW), choisi pour sa nature sans projection. Ils proposent une variante de « gradient paresseux » qui exploite la structure quadratique pour mettre à jour les gradients efficacement, réduisant la surcharge de calcul par itération d'un temps cubique à un temps quadratique par rapport aux opérations matricielles, bien que la complexité globale reste dominée par l'oracle de minimisation linéaire ($O(n^3)$).

Contributions Clés

1. Premier Cadre de Géométrie-Aware OT Convexe : Le CDOT est le premier cadre fournissant une formulation convexe pour aligner des espaces mm hétérogènes qui récupère explicitement un plan de transport optimal, contrairement aux méthodes basées sur le tranchage (slicing) qui ne font qu'estimer la divergence.
2. Garanties Théoriques :
   • Existence et Convexité : Existence d'un couplage optimal et convexité de l'objectif prouvées sans nécessiter de régularisation entropique.
   • Propriété de Pseudométrique : Établissement que la divergence CDOT est une pseudométrique valide.
   • Consistance du Risque : Dérivation de bornes d'erreur non asymptotiques décomposées en erreurs d'optimisation et statistiques, prouvant que l'estimateur est risque-consistant sous un algorithme de Frank–Wolfe à convergence globale.
3. Insight Géométrique : L'analyse de l'« écart de dispersion » explique formellement la source de non-convexité dans GW et démontre comment le CDOT filtre le terme de dispersion pour obtenir un paysage convexe.
4. Performance Empirique : Démonstration d'une performance supérieure aux méthodes existantes (FGW, EFGW, IsoRank, Spectral Matching, COPT) sur des nuages de points synthétiques, des connectomes cérébraux (OASIS-3) et des benchmarks de classification de graphes (TUDataset).

Résultats Expérimentaux

• Données Synthétiques : Sur des nuages de points groupés en 2D, le CDOT a systématiquement obtenu l'erreur quadratique moyenne (MSE) la plus faible à travers différentes tailles d'échantillons, montrant une convergence stable. En revanche, l'EFGW (Entropic FGW) a montré une grande sensibilité au paramètre de régularisation $\epsilon$, échouant souvent à égaler la précision du CDOT ou se retrouvant piégé dans des optima locaux lorsque $\epsilon$ était faible.
• Connectomes Cérébraux (OASIS-3) : Sur des réseaux cérébraux structurels, le CDOT a nettement surpassé le FGW en utilisant la distance de diffusion (une métrique globale robuste), atteignant une précision de correspondance de 61,36 % contre 18,53 % pour le FGW. Les auteurs attribuent cela à la capacité du CDOT à aligner des profils géométriques agrégés même lorsque les contrastes par paires sont lissés par la diffusion, là où l'objectif non convexe de GW perd son pouvoir discriminatoire dans des paysages aussi plats. Sous la distance géodésique, le FGW a légèrement mieux performé, soulignant le compromis entre l'alignement rigide par paires et l'alignement global robuste.
• Classification de Graphes : Sur les benchmarks du TUDataset, le CDOT a systématiquement surpassé les méthodes de référence (FGW, GW, COPT) en précision de classification, particulièrement sur les jeux de données riches en informations de caractéristiques (ex: MUTAG, ENZYMES). Notamment, le CDOT a maintenu la meilleure performance même sur le jeu de données IMDB-BINARY (sans caractéristiques de nœuds), suggérant que la géométrie basée sur les opérateurs capture plus efficacement les distinctions topologiques que les approches GW standard.

Signification et Revendications

L'article affirme que le CDOT offre une alternative robuste et fiable aux méthodes d'OT non convexes existantes pour les données structurées. En garantissant un paysage d'optimisation convexe, le CDOT garantit la convergence vers un optimum global sans nécessiter de réglage de l'hyperparamètre (comme la régularisation entropique) qui peut déstabiliser les solutions. Le cadre est particulièrement significatif pour les applications impliquant des domaines hétérogènes où les structures géométriques intrinsèques doivent être préservées, telles que l'analyse des réseaux cérébraux et la classification de graphes.

Les auteurs notent modestement deux limitations :

1. Le CDOT est conçu pour l'alignement au niveau des opérateurs plutôt que pour une correspondance stricte un-à-un ; une divergence nulle n'implique pas nécessairement une isométrie exacte préservant la mesure.
2. Bien que convexe, l'implémentation actuelle repose sur des itérations de Frank–Wolfe dominées par des sous-problèmes d'OT, ce qui le rend plus adapté aux tailles de problèmes modérées qu'aux contextes de très grande échelle.

Les directions futures suggérées par les auteurs incluent le développement de cadres d'inférence statistique (par exemple, tests d'hypothèse pour l'isomorphisme) basés sur la divergence CDOT et l'intégration de l'objectif CDOT en tant que couche différentiable dans les réseaux de neurones profonds pour apprendre conjointement les métriques de base optimales.