Representing Graphs via Gromov-Wasserstein Factorization.

Area of Science:

• Machine Learning
• Graph Theory
• Data Science

Background:

• Graph representation is crucial for numerous real-world applications.
• Existing methods struggle with graphs of varying sizes and unknown node correspondences.
• Learning flexible and interpretable graph representations remains a significant challenge.

Purpose of the Study:

• To propose a novel paradigm, Gromov-Wasserstein Factorization (GWF), for learning graph representations.
• To develop a flexible and interpretable method for reconstructing graphs from unknown node correspondences.
• To achieve permutation-invariant graph representations.

Main Methods:

• Introduced Gromov-Wasserstein Factorization (GWF) model for graph reconstruction.
• Utilized Gromov-Wasserstein (GW) discrepancy as a pseudo-metric.
• Employed joint learning of graph factors and weights, optimizing reconstruction error.
• Incorporated envelope theorem for efficient gradient backpropagation.
• Implemented Proximal Point Algorithm (PPA) and Bregman Alternating Direction Method of Multipliers (BADMM) for GW discrepancy computation.

Main Results:

• GWF enables a nonlinear factorization of graphs into shared structural patterns (graph factors).
• Learned graph representations are permutation-invariant, reflecting factor contributions.
• Achieved comparable performance to state-of-the-art methods on various datasets.
• Demonstrated effectiveness in graph clustering and classification tasks.

Conclusions:

• Gromov-Wasserstein Factorization offers a powerful and interpretable approach to graph representation learning.
• The proposed method effectively handles graphs with unknown node correspondences and varying sizes.
• GWF shows significant potential for various graph-based machine learning applications, including clustering and classification.