There is recently a surge in approaches that learn low-dimensional embeddings of nodes in networks. As there are many large-scale real-world networks, it's inefficient for existing approaches to store amounts of parameters in memory and update them edge after edge. With the knowledge that nodes having similar neighborhood will be close to each other in embedding space, we propose COSINE (COmpresSIve NE) algorithm which reduces the memory footprint and accelerates the training process by parameters sharing among similar nodes. COSINE applies graph partitioning algorithms to networks and builds parameter sharing dependency of nodes based on the result of partitioning. With parameters sharing among similar nodes, COSINE injects prior knowledge about higher structural information into training process which makes network embedding more efficient and effective. COSINE can be applied to any embedding lookup method and learn high-quality embeddings with limited memory and shorter training time. We conduct experiments of multi-label classification and link prediction, where baselines and our model have the same memory usage. Experimental results show that COSINE gives baselines up to 23% increase on classification and up to 25% increase on link prediction. Moreover, time of all representation learning methods using COSINE decreases from 30% to 70%.

本研究提出了一种名为COSINE的算法，它利用网络中节点相似的邻居特性，在训练过程中通过参数共享来降低内存开销并加速训练，并通过图分区算法构建节点间的参数共享依赖关系，使得网络嵌入更为高效和有效。COSINE可应用于任何嵌入式查找方法，具有较高的嵌入质量，更少的内存开销和更短的训练时间。实验证明，与基线相比，COSINE可以提高多标签分类和链接预测的准确率，且降低嵌入学习方法的训练时间。

COSINE: 大规模信息网络上的压缩网络嵌入