# Efficient Network Embedding by Approximate Equitable Partitions

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 49 references that are in the map.
- First posted on arXiv 16 Sep 2024.

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

- [Distributed Representations of Words and Phrases and their Compositionality](https://mlsanity.com/paper/1310.4546/) (2013)
- [GCC: Graph Contrastive Coding for Graph Neural Network Pre-Training](https://mlsanity.com/paper/2006.09963/) (2020)
- [struc2vec: Learning Node Representations from Structural Identity](https://mlsanity.com/paper/1704.03165/) (2017)
- [A Survey on Network Embedding](https://mlsanity.com/paper/1711.08752/) (2017)
- [Learning Structural Node Embeddings Via Diffusion Wavelets](https://mlsanity.com/paper/1710.10321/) (2017)
- [REGAL: Representation Learning-based Graph Alignment](https://mlsanity.com/paper/1802.06257/) (2018)
- [GraLSP: Graph Neural Networks with Local Structural Patterns](https://mlsanity.com/paper/1911.07675/) (2019)
- [Principled approach to the selection of the embedding dimension of networks](https://mlsanity.com/paper/2004.09928/) (2020)
- [node2bits: Compact Time- and Attribute-aware Node Representations for User Stitching](https://mlsanity.com/paper/1904.08572/) (2019)
- [A Survey on Role-Oriented Network Embedding](https://mlsanity.com/paper/2107.08379/) (2021)

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

- [RAwR: Role-Aware Rewiring via Approximate Equitable Partition](https://mlsanity.com/paper/2605.09457/) (2026)
- [Scaling Weisfeiler-Leman Expressiveness Analysis to Massive Graphs with GPUs](https://mlsanity.com/paper/2607.02603/) (2026)

## Abstract (arXiv)

Structural network embedding is a crucial step in enabling effective downstream tasks for complex systems that aims to project a network into a lower-dimensional space while preserving similarities among nodes. We introduce a simple and efficient embedding technique based on approximate variants of equitable partitions. The approximation consists in introducing a user-tunable tolerance parameter relaxing the otherwise strict condition for exact equitable partitions that can be hardly found in real-world networks. We exploit a relationship between equitable partitions and equivalence relations for Markov chains and ordinary differential equations to develop a partition refinement algorithm for computing an approximate equitable partition in polynomial time. We compare our method against state-of-the-art embedding techniques on benchmark networks. We report comparable -- when not superior -- performance for visualization, classification, and regression tasks at a cost between one and three orders of magnitude smaller using a prototype implementation, enabling the embedding of large-scale networks which could not be efficiently handled by most of the competing techniques.