用近似等价划分实现高效网络嵌入，大幅降低计算成本。
Efficient Network Embedding by Approximate Equitable Partitions
- 基于可调容差的近似等价划分，突破真实网络难找精确划分的限制。
- 在多项式时间内完成计算，相比现有方法速度提升1至3个数量级。
- 适合处理大规模网络，尤其适用于可视化与分类任务的快速部署。
结构化网络嵌入是复杂系统下游任务的关键步骤，旨在将网络投影到低维空间以保留节点间的相似性。本文提出一种基于近似等价划分的简单高效嵌入方法，通过引入用户可调容差参数，放宽了严格等价划分在真实网络中难以满足的条件。利用等价划分与马尔可夫链及常微分方程中等价关系的联系，设计了一种多项式时间的划分细化算法。在基准网络上与当前最优嵌入技术对比，本方法在可视化、分类和回归任务中表现相当甚至更优，计算成本仅为同类方法的1至3个数量级，使以往难以高效处理的大规模网络嵌入成为可能。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。