Given an input graph G and a node v in G, homogeneous network embedding (HNE)
maps the graph structure in the vicinity of v to a compact, fixed-dimensional
feature vector. This paper focuses on HNE for massive graphs, e.g., with
billions of edges. On this scale, most existing approaches fail, as they incur
either prohibitively high costs, or severely compromised result utility. Our
proposed solution, called Node-Reweighted PageRank (NRP), is based on a classic
idea of deriving embedding vectors from pairwise personalized PageRank (PPR)
values. Our contributions are twofold: first, we design a simple and efficient
baseline HNE method based on PPR that is capable of handling billion-edge
graphs on commodity hardware; second and more importantly, we identify an
inherent drawback of vanilla PPR, and address it in our main proposal NRP.
Specifically, PPR was designed for a very different purpose, i.e., ranking
nodes in G based on their relative importance from a source node's perspective.
In contrast, HNE aims to build node embeddings considering the whole graph.
Consequently, node embeddings derived directly from PPR are of suboptimal
utility. The proposed NRP approach overcomes the above deficiency through an
effective and efficient node reweighting algorithm, which augments PPR values
with node degree information, and iteratively adjusts embedding vectors
accordingly. Overall, NRP takes O(mlogn) time and O(m) space to compute all
node embeddings for a graph with m edges and n nodes. Our extensive experiments
that compare NRP against 18 existing solutions over 7 real graphs demonstrate
that NRP achieves higher result utility than all the solutions for link
prediction, graph reconstruction and node classification, while being up to
orders of magnitude faster. In particular, on a billion-edge Twitter graph, NRP
terminates within 4 hours, using a single CPU core.

本文介绍了一种针对海量图形的基于节点重加权 PageRank（NRP）的同质网络嵌入方法。经实验证明，与现有的 18 种解决方案相比，NRP 在链接预测、图形重建和节点分类方面的效果更好，且速度更快。