Scalable Network Embedding With Approximate Equitable Partitions

Squillace, Giuseppe

doi:10.1109/tkde.2026.3682970

Scalable Network Embedding With Approximate Equitable Partitions

2026-07-01

0

PRE

AI

S

Squillace, Giuseppe *

DOI：10.1109/tkde.2026.3682970

Original

Original request for help

Save

Abstract

En 中文

Network embedding is a fundamental technique to project a network into a lower-dimensional space while preserving similarities among nodes. Traditional network embeddings primarily capture node proximity, making them effective for community detection but insufficient for identifying roles, i.e., patterns of interaction beyond local neighborhoods. To address this limitation, we introduce a simple and efficient embedding technique based on approximate variants of equitable partitions. Our approach, called $\varepsilon$epsilon-BE, introduces 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 extend this framework to weighted and directed networks, ensuring applicability to a more general class of graphs and filling a gap in the literature where few approaches are present. We compare our method against state-of-the-art embedding techniques on synthetic and real-world networks. We report comparable-when not superior-performance for visualization, classification, clustering, and regression tasks with smaller running times, enabling the embedding of large-scale networks that could not be efficiently handled by most of the competing techniques. These results and the capability to handle weighted and directed networks make our approach a compelling alternative for structural network embedding.

Keywords:

Motion pictures

Broadcasting

Recommender systems

Information filtering

Central Processing Unit

Integrated circuits

Radio access networks

Regional area networks

Electronic mail

Communication systems

Network embedding

graph embedding

equitable partitions

structural equivalence

role discovery

graph partitioning

directed networks

weighted networks

graph algorithms

network analysis

Scalable Network Embedding With Approximate Equitable Partitions

Abstract

Journal

Organization

Cited Papers