Efficient Network Embedding by Approximate Equitable Partitions
<|reference_start|>Efficient Network Embedding by Approximate Equitable Partitions: 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.<|reference_end|>
@article{squillace2024efficient,
    title={Efficient Network Embedding by Approximate Equitable Partitions},
    author={Giuseppe Squillace, Mirco Tribastone, Max Tschaikowski, Andrea Vandin},
    journal={arXiv preprint arXiv:2409.10160},
    year={2024},
    archivePrefix={arXiv},
    eprint={2409.10160},
    primaryClass={cs.SI cs.LG cs.SY eess.SY}
}