Source-linked AI summary
Optimal Transport for structured data with application on graphs
Titouan Vayer, Laetitia Chapel, Rémi Flamary, Romain Tavenard, Nicolas Courty
TL;DR
Computing distances between structured objects is difficult because standard optimal transport compares features but does not leverage structural information. The paper introduces Fused Gromov-Wasserstein distance, which jointly compares features and structure, and reports strong graph-classification performance, including the best results on 4 of 6 vector-attributed datasets.
Problem
Computing distances between structured objects is nontrivial because standard optimal transport compares feature representations without leveraging structural information.
Method
Fused Gromov-Wasserstein distance jointly transports feature and structural information, balancing their contributions while supporting graphs with different numbers of nodes.
Results
FGW performs best on 4 of 6 vector-attributed graph datasets, outperforms competitive methods on discrete labeled graphs, and GW outperforms graph kernels on non-attributed social graphs.
Takeaways & Limitations
FGW provides a metric framework for graph analysis that supports classification and barycentric graph clustering.
Takeaways & Limitations
The approach uses shortest-path structural distances and feature distances, while reducing optimization complexity remains necessary for scalability to very large graphs.
Abstract
from arXiv · showhide
This work considers the problem of computing distances between structured objects such as undirected graphs, seen as probability distributions in a specific metric space. We consider a new transportation distance (i.e. that minimizes a total cost of transporting probability masses) that unveils the geometric nature of the structured objects space. Unlike Wasserstein or Gromov-Wasserstein metrics that focus solely and respectively on features (by considering a metric in the feature space) or structure (by seeing structure as a metric space), our new distance exploits jointly both information, and is consequently called Fused Gromov-Wasserstein (FGW). After discussing its properties and computational aspects, we show results on a graph classification task, where our method outperforms both graph kernels and deep graph convolutional networks. Exploiting further on the metric properties of FGW, interesting geometric objects such as Fréchet means or barycenters of graphs are illustrated and discussed in a clustering context.
1. Introduction
The paper introduces a transportation distance for structured data that jointly captures feature and structural information by representing graphs as probability distributions. Its framework supports comparisons across different feature and structure spaces through a tunable trade-off between them.
- Motivation: Structured data combine feature and structural information, encompassing graphs, time series, trees, and images.Graphs are described as attributed nodes linked by relations.
- Related work: Existing kernels, including the Weisfeiler-Lehman kernel, address the challenge of combining features with structural similarity.
- Contributions: The proposed framework represents structured data as probability measures and incorporates both feature and structural information into an optimal transport problem.It is intended for usual structured machine-learning data, including undirected labeled graphs.
- Limitations of existing transport distances: Standard optimal transport compares feature representations but cannot directly leverage structural information, while Gromov-Wasserstein compares structures across different ground spaces.Comparing graph structures is difficult because nodes are unordered and structural similarity requires an isometry-based notion.
- Contributions: A trade-off parameter balances the importance of features and structure, even when they inhabit spaces of different dimensions.
2. Structured data as probability measures
Structured data are modeled as weighted undirected labeled graphs that combine vertex features with graph-specific structural similarities. Their complete representation is a fully supported probability measure over the product of feature and structure spaces, with vertex weights encoding relative importance.
- Graph representation: An undirected labeled graph combines vertex features a_i in a feature metric space with structural representations x_i measured by a graph-specific similarity function C.The structure space is implicit; knowing C, or its matrix of pairwise node similarities, is sufficient.
- Weighted structured data: Assigning vertex weights h_i produces structured data S = (G, h_G), where weights signal the vertices’ relative importance.The weights belong to the probability simplex and can encode a priori information about the data.
- Probability-measure representation: The structured object is represented by the fully supported probability measure µ = Σ_i h_iδ_(x_i,a_i) over the product of structure and feature spaces.Its marginals µ_X and µ_A describe the structure and feature components, respectively.
- Weight interpretation: When all vertex weights are equal, the structured data contain exactly the same information as the underlying graph.Unequal weights instead preserve additional importance information, such as segmented-image area ratios.
3. Fused Gromov-Wasserstein approach for structured data
This section introduces Fused Gromov-Wasserstein (FGW), an optimal-transport distance that jointly matches node features and intra-graph structure. It establishes FGW’s interpolation and metric properties, then extends it to structured-data barycenters and scalable optimization.
- Interpolation properties: As α approaches 0, FGW recovers Wasserstein distance on features, while α approaching 1 recovers Gromov-Wasserstein distance on structures.Thus, FGW generalizes both Wasserstein and Gromov-Wasserstein distances through a single interpolation parameter.
- Metric properties: For q = 1, FGW is a metric under distance-matrix assumptions, whereas for q > 1 it is a semi-metric with the triangle inequality relaxed by 2^(q−1).For q = 1, zero distance corresponds to a weight-, feature-, and structure-preserving bijection between the graphs.
- Applications: FGW is unsupervised and supports nearest-neighbor, kernel, embedding, and representative-set methods while exposing similarity through its optimal node mapping.This mapping-based interpretation contrasts with end-to-end neural-network approaches.
- FGW barycenters: FGW defines structured-data barycenters as Fréchet means by jointly optimizing their feature representation and structure matrix.The barycenter objective is jointly convex in its structure and features, though not in the couplings; variants can fix either component.
- Optimization: For q = 2, FGW computation avoids explicit O(m^2n^2) tensor construction, achieving O(mn^2 + m^2n) complexity and using conditional-gradient updates with classical OT subproblems.Barycenters are computed with block coordinate descent, alternating over couplings, structure, and features.
4. Experimental results
Across vector-attributed, discrete-labeled, and non-attributed graph benchmarks, FGW achieves strong classification performance, while validation selects intermediate α values that combine feature and structural information. FGW also supports clustering graphs and recovering meaningful cluster barycenters.
- Vector attributed graphs: FGW performs best on 4 of 6 vector-attributed graph datasets and falls within the best methods’ error bars on the remaining two.The comparison uses average accuracies from Table 1.
- Discrete labeled graphs: FGW with WL attributes outperforms all competing methods and FGW with raw features on discrete-labeled graphs.WL attributes encode neighborhood labels more finely than raw features, which use only shortest-path structure.
- Non-attributed graphs: GW greatly outperforms SPK and GK on non-attributed social graphs, providing the first reported GW application to social graph classification.The accuracies are reported in Table 3.
- Comparison between FGW, W and GW: Validation consistently selects α strictly between 0 and 1, indicating that both feature and structural information are necessary.The selected trade-off excludes the pure Wasserstein and pure Gromov-Wasserstein endpoints.
- Clustering and barycenters: FGW k-means clusters 40 community graphs into four groups and evolves graph barycenters from random initializations to final centroids.Each group contains 10 graphs, and each centroid is fixed to 30 nodes.
5. Discussion and conclusion
The paper introduces FGW as a distance for labeled structured data, proves it is a valid distance on graphs of arbitrary sizes, and demonstrates its utility for classification and graph-based k-means. Future work includes alternative or learned structure and feature distances, deep-learning applications, and reduced computational complexity.
- 5. Discussion and conclusion: FGW defines a distance on structured data and consequently on graphs of arbitrary sizes.It generalizes transportation distances to probability measures combining graph features and structures.
- 5. Discussion and conclusion: FGW reaches or surpasses state-of-the-art performance most of the time on graph classification and provides a framework for graph-based k-means.
- 5. Discussion and conclusion: Future work may use alternative or end-to-end learned distances for graph structure and features, apply FGW in graph deep-learning settings, and reduce its computational complexity.Potential applications include graph autoencoders, where a distance between graphs is needed.
6. Supplementary Material
The supplementary material formalizes FGW’s transport notation and establishes its interpolation, metric, and triangle-inequality properties. Cross-validation further shows that FGW generally matches or exceeds W and GW, with differences otherwise not statistically significant.
- Notation and formulation: The supplementary formulation defines admissible couplings, feature-distance matrices, structure matrices, and the tensor measuring pairwise structural similarity used by FGW.The FGW minimum is well defined because it minimizes a continuous function over a compact coupling set.
- Interpolation properties: FGW interpolates between Wasserstein and Gromov-Wasserstein distances: as α approaches 0 it recovers W, while as α approaches 1 it recovers GW.It is also lower-bounded by the corresponding straight-forward interpolation of the Wasserstein and Gromov-Wasserstein losses.
- Metric properties: FGW is a metric for q = 1 and a semi-metric for q > 1, with the triangle inequality relaxed by a factor 2^q−1 when q > 1.For q = 1, the distance satisfies the triangle inequality; for q > 1, it satisfies the relaxed version with coefficient 2^q−1.
- Cross validation results: Cross-validation found FGW scores usually greater than or equal to both W and GW across datasets, with exceptions not statistically significant.Nested 10-fold cross-validation selected α within [0, 1]; experiments were repeated 10 times per dataset, or 50 times for MUTAG and PTC.