PARROT: Position-Aware Regularized Optimal Transport for Network Alignment

Zhichen Zeng, Si Zhang, Yinglong Xia, Hanghang Tong

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Network alignment is a critical steppingstone behind a variety of multi-network mining tasks. Most of the existing methods essentially optimize a Frobenius-like distance or ranking-based loss, ignoring the underlying geometry of graph data. Optimal transport (OT), together with Wasserstein distance, has emerged to be a powerful approach accounting for the underlying geometry explicitly. Promising as it might be, the state-of-the-art OT-based alignment methods suffer from two fundamental limitations, including (1) effectiveness due to the insufficient use of topology and consistency information and (2) scalability due to the non-convex formulation and repeated computationally costly loss calculation. In this paper, we propose a position-aware regularized optimal transport framework for network alignment named PARROT. To tackle the effectiveness issue, the proposed PARROT captures topology information by random walk with restart, with three carefully designed consistency regularization terms. To tackle the scalability issue, the regularized OT problem is decomposed into a series of convex subproblems and can be efficiently solved by the proposed constrained proximal point method with guaranteed convergence. Extensive experiments show that our algorithm achieves significant improvements in both effectiveness and scalability, outperforming the state-of-the-art network alignment methods and speeding up existing OT-based methods by up to 100 times.

Original languageEnglish (US)
Title of host publicationACM Web Conference 2023 - Proceedings of the World Wide Web Conference, WWW 2023
PublisherAssociation for Computing Machinery
Pages372-382
Number of pages11
ISBN (Electronic)9781450394161
DOIs
StatePublished - Apr 30 2023
Event2023 World Wide Web Conference, WWW 2023 - Austin, United States
Duration: Apr 30 2023May 4 2023

Publication series

NameACM Web Conference 2023 - Proceedings of the World Wide Web Conference, WWW 2023

Conference

Conference2023 World Wide Web Conference, WWW 2023
Country/TerritoryUnited States
CityAustin
Period4/30/235/4/23

Keywords

  • Network alignment
  • alignment consistency
  • optimal transport

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Software

Fingerprint

Dive into the research topics of 'PARROT: Position-Aware Regularized Optimal Transport for Network Alignment'. Together they form a unique fingerprint.

Cite this