1. Efficient Network Embedding by Approximate Equitable Partitions
- Author
-
Squillace, Giuseppe, Tribastone, Mirco, Tschaikowski, Max, and Vandin, Andrea
- Subjects
Computer Science - Social and Information Networks ,Computer Science - Machine Learning ,Electrical Engineering and Systems Science - Systems and Control - Abstract
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., Comment: Accepted at ICDM 2024
- Published
- 2024