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 可以提高多标签分类和链接预测的准确率，且降低嵌入学习方法的训练时间。