Aligning multiple networks

Paper Title:

Hierarchical Multi-Marginal Optimal Transport for Network Alignment

Published on:

6 October 2023

Primary Category:

Machine Learning

Paper Authors:

Zhichen Zeng,

Boxin Du,

Si Zhang,

Yinglong Xia,

Zhining Liu,

Hanghang Tong

Bullets

Key Details

•

Decomposes multi-network alignment into cluster-level and node-level subproblems

•

Uses multi-marginal fused Gromov-Wasserstein distance to jointly measure cross-network relationships

•

Develops proximal point method with guaranteed convergence to a local optimum

•

Achieves exponential reduction in time and space complexity compared to straightforward solution

•

Significantly outperforms state-of-the-art methods in both effectiveness and scalability

Explore the topics in this paper

clustering

graph alignment

graph matching

network analysis

node correspondence

AI generated summary

Aligning multiple networks

This paper proposes a new method called HOT to align nodes across multiple networks. It handles the large solution space by decomposing the problem into cluster-level and node-level alignment subproblems. To measure relationships across networks, it uses a multi-marginal generalization of the fused Gromov-Wasserstein distance. Experiments show HOT achieves much better performance and scalability than prior methods.