Search Efficient Binary Network Embedding
Search Efficient Binary Network Embedding
复制标题
DOI：
10.1145/3436892
复制
发表时间：
2019-01
期刊：
影响因子：
--
通讯作者：
Daokun Zhang;Jie Yin;Xingquan Zhu;Chengqi Zhang
中科院分区：
文献类型：
--
作者：
Daokun Zhang;Jie Yin;Xingquan Zhu;Chengqi Zhang
传统的网络嵌入主要侧重于学习每个节点的连续向量表示，保留网络结构和/或节点内容信息，以便现成的机器学习算法可以轻松应用于向量格式节点表示以进行网络分析。然而，学习的连续向量表示对于大规模相似性搜索来说效率低下，这通常涉及在连续向量空间中寻找通过距离或相似性测量的最近邻。在本文中，我们提出了一种名为 BinaryNE 的搜索高效二进制网络嵌入算法，通过三层神经网络同时建模节点上下文关系和节点属性关系，来学习每个节点的二进制代码。 BinaryNE 使用基于随机梯度下降的在线学习算法来学习二元节点表示。学习到的二进制编码不仅减少了表示每个节点的内存使用量，而且还允许快速按位比较，以支持比使用欧几里德或其他距离度量更快的节点相似性搜索。大量的实验和比较表明，BinaryNE 不仅可以提供比传统连续向量网络嵌入方法快 25 倍以上的搜索速度，而且可以提供与传统连续向量网络嵌入方法相当或更好的搜索质量。 BinaryNE 学习的二进制代码还在节点分类和节点聚类任务上提供了有竞争力的性能。 BinaryNE算法的源代码可在https://github.com/daokunzhang/BinaryNE获取。
Traditional network embedding primarily focuses on learning a continuous vector representation for each node, preserving network structure and/or node content information, such that off-the-shelf machine learning algorithms can be easily applied to the vector-format node representations for network analysis. However, the learned continuous vector representations are inefficient for large-scale similarity search, which often involves finding nearest neighbors measured by distance or similarity in a continuous vector space. In this article, we propose a search efficient binary network embedding algorithm called BinaryNE to learn a binary code for each node, by simultaneously modeling node context relations and node attribute relations through a three-layer neural network. BinaryNE learns binary node representations using a stochastic gradient descent-based online learning algorithm. The learned binary encoding not only reduces memory usage to represent each node, but also allows fast bit-wise comparisons to support faster node similarity search than using Euclidean or other distance measures. Extensive experiments and comparisons demonstrate that BinaryNE not only delivers more than 25 times faster search speed, but also provides comparable or better search quality than traditional continuous vector based network embedding methods. The binary codes learned by BinaryNE also render competitive performance on node classification and node clustering tasks. The source code of the BinaryNE algorithm is available at https://github.com/daokunzhang/BinaryNE.