# Alignment and Comparison of Directed Networks via Transition Couplings of Random Walks

arXiv: https://arxiv.org/abs/2106.07106 · HTML: https://mlsanity.com/paper/2106.07106/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 104 references that are in the map.
- First posted on arXiv 13 Jun 2021.

## Builds on (most cited first, 25 of 25)

- [node2vec: Scalable Feature Learning for Networks](https://mlsanity.com/paper/1607.00653/) (2016)
- [DeepWalk: Online Learning of Social Representations](https://mlsanity.com/paper/1403.6652/) (2014)
- [Computational Optimal Transport](https://mlsanity.com/paper/1803.00567/) (2018)
- [Community Detection and Stochastic Block Models](https://mlsanity.com/paper/1703.10146/) (2017)
- [Exploring Visual Relationship for Image Captioning](https://mlsanity.com/paper/1809.07041/) (2018)
- [Optimal Transport for structured data with application on graphs](https://mlsanity.com/paper/1805.09114/) (2018)
- [Gromov-Wasserstein Learning for Graph Matching and Node Embedding](https://mlsanity.com/paper/1901.06003/) (2019)
- [Gromov-Wasserstein Alignment of Word Embedding Spaces](https://mlsanity.com/paper/1809.00013/) (2018)
- [Scalable Gromov-Wasserstein Learning for Graph Partitioning and Matching](https://mlsanity.com/paper/1905.07645/) (2019)
- [Graph Optimal Transport for Cross-Domain Alignment](https://mlsanity.com/paper/2006.14744/) (2020)
- [Fused Gromov-Wasserstein distance for structured objects: theoretical foundations and mathematical properties](https://mlsanity.com/paper/1811.02834/) (2018)
- [Sliced Gromov-Wasserstein](https://mlsanity.com/paper/1905.10124/) (2019)
- [GOT: An Optimal Transport framework for Graph comparison](https://mlsanity.com/paper/1906.02085/) (2019)
- [Efficient random graph matching via degree profiles](https://mlsanity.com/paper/1811.07821/) (2018)
- [A Review of Stochastic Block Models and Extensions for Graph Clustering](https://mlsanity.com/paper/1903.00114/) (2019)
- [Exact alignment recovery for correlated ErdHos-R'enyi graphs](https://mlsanity.com/paper/1711.06783/) (2017)
- [(Nearly) Efficient Algorithms for the Graph Matching Problem on Correlated Random Graphs](https://mlsanity.com/paper/1805.02349/) (2018)
- [Partial Recovery of ErdHos-R'enyi Graph Alignment via k-Core Alignment](https://mlsanity.com/paper/1809.03553/) (2018)
- [Seeded graph matching for correlated ErdHos-R'enyi graphs](https://mlsanity.com/paper/1304.7844/) (2013)
- [COPT: Coordinated Optimal Transport for Graph Sketching](https://mlsanity.com/paper/2003.03892/) (2020)
- [Recognizing Cuneiform Signs Using Graph Based Methods](https://mlsanity.com/paper/1802.05908/) (2018)
- [An efficient reconciliation algorithm for social networks](https://mlsanity.com/paper/1307.1690/) (2013)
- [Spectral Alignment of Graphs](https://mlsanity.com/paper/1602.04181/) (2016)
- [Wasserstein-based Graph Alignment](https://mlsanity.com/paper/2003.06048/) (2020)
- [Optimal Transport for Stationary Markov Chains via Policy Iteration](https://mlsanity.com/paper/2006.07998/) (2020)

## Built on by (most cited first, 2 of 2)

- [Bisimulation Metrics are Optimal Transport Distances, and Can be Computed Efficiently](https://mlsanity.com/paper/2406.04056/) (2024)
- [Distances for Markov Chains, and Their Differentiation](https://mlsanity.com/paper/2302.08621/) (2023)

## Abstract (arXiv)

We describe and study a transport based procedure called NetOTC (network optimal transition coupling) for the comparison and alignment of two networks. The networks of interest may be directed or undirected, weighted or unweighted, and may have distinct vertex sets of different sizes. Given two networks and a cost function relating their vertices, NetOTC finds a transition coupling of their associated random walks having minimum expected cost. The minimizing cost quantifies the difference between the networks, while the optimal transport plan itself provides alignments of both the vertices and the edges of the two networks. Coupling of the full random walks, rather than their marginal distributions, ensures that NetOTC captures local and global information about the networks, and preserves edges. NetOTC has no free parameters, and does not rely on randomization. We investigate a number of theoretical properties of NetOTC and present experiments establishing its empirical performance.