Node embedding learns a low-dimensional representation for each node in the
graph. Recent progress on node embedding shows that proximity matrix
factorization methods gain superb performance and scale to large graphs with
millions of nodes. Existing approaches first define a proximity matrix and then
learn the embeddings that fit the proximity by matrix factorization. Most
existing matrix factorization methods adopt the same proximity for different
tasks, while it is observed that different tasks and datasets may require
different proximity, limiting their representation power.
Motivated by this, we propose {\em Lemane}, a framework with trainable
proximity measures, which can be learned to best suit the datasets and tasks at
hand automatically. Our method is end-to-end, which incorporates differentiable
SVD in the pipeline so that the parameters can be trained via backpropagation.
However, this learning process is still expensive on large graphs. To improve
the scalability, we train proximity measures only on carefully subsampled
graphs, and then apply standard proximity matrix factorization on the original
graph using the learned proximity. Note that, computing the learned proximities
for each pair is still expensive for large graphs, and existing techniques for
computing proximities are not applicable to the learned proximities. Thus, we
present generalized push techniques to make our solution scalable to large
graphs with millions of nodes. Extensive experiments show that our proposed
solution outperforms existing solutions on both link prediction and node
classification tasks on almost all datasets.

该论文提出了一种可训练相似度度量的节点嵌入方法 ——Lemane，该方法在大规模图上有着较高的可扩展性和更好的表现。

基于学习的邻近矩阵分解用于节点嵌入

Learning Based Proximity Matrix Factorization for Node Embedding

We provide a deterministic data summarization algorithm that approximates the
mean $\bar{p}=\frac{1}{n}\sum_{p\in P} p$ of a set $P$ of $n$ vectors in
$\REAL^d$, by a weighted mean $\tilde{p}$ of a \emph{subset} of $O(1/\eps)$
vectors, i.e., independent of both $n$ and $d$. We prove that the squared
Euclidean distance between $\bar{p}$ and $\tilde{p}$ is at most $\eps$
multiplied by the variance of $P$. We use this algorithm to maintain an
approximated sum of vectors from an unbounded stream, using memory that is
independent of $d$, and logarithmic in the $n$ vectors seen so far. Our main
application is to extract and represent in a compact way friend groups and
activity summaries of users from underlying data exchanges. For example, in the
case of mobile networks, we can use GPS traces to identify meetings, in the
case of social networks, we can use information exchange to identify friend
groups. Our algorithm provably identifies the {\it Heavy Hitter} entries in a
proximity (adjacency) matrix. The Heavy Hitters can be used to extract and
represent in a compact way friend groups and activity summaries of users from
underlying data exchanges. We evaluate the algorithm on several large data
sets.

提供一种确定性数据汇总的算法来表示用户的好友群体和活动摘要，这可以被用于从 GPS 轨迹或信息交换来识别会议或好友组，并可以标识邻接矩阵中的重要节点。