Representing Graphs via Gromov-Wasserstein Factorization

Journal Article (Journal Article)

We propose a new nonlinear factorization model for graphs that have topological structures, and optionally, node attributes. This model is based on a pseudo-metric called Gromov-Wasserstein (GW) discrepancy, which compares graphs in a relational way. It estimates observed graphs as the GW barycenters constructed by a set of graph bases with different weights. By minimizing the difference between each observed graph and its GW barycenter-based estimation, we learn the graph bases and their weights associated with the observed graphs. The model achieves a novel and flexible factorization mechanism for graphs, in which both the observed graphs and the learnable graph bases can be unaligned and with different sizes. We design an effective approximate algorithm for learning this Gromov-Wasserstein factorization (GWF) model, unrolling loopy computations as stacked modules and computing gradients with backpropagation. For each observed graph, the weights lead to its permutation-invariant representation. These weights can be parametrized by a graph neural network so that we can extend the proposed transductive GWF model to an inductive version. Compared with state-of-the-art methods, our GWF method can represent graphs with better interpretability and using lower dimensionality, while simultaneously achieving encouraging results in graph clustering and classification task

Full Text

Duke Authors

Cited Authors

  • Xu, H; Liu, J; Luo, D; Carin, L

Published Date

  • January 1, 2022

Published In

Electronic International Standard Serial Number (EISSN)

  • 1939-3539

International Standard Serial Number (ISSN)

  • 0162-8828

Digital Object Identifier (DOI)

  • 10.1109/TPAMI.2022.3153126

Citation Source

  • Scopus