Scalable Graph Embedding for Asymmetric Proximity

By Chang Zhou, Yuqiong Liu, Xiaofei Liu, Zhongyi Liu, Jun Gao. 2017

210 citations recorded by the source corpus.

Graph Embedding methods are aimed at mapping each vertex into a low dimensional vector space, which preserves certain structural relationships among the vertices in the original graph. Recently, several works have been proposed to learn embeddings based on sampled paths from the graph, e.g., DeepWalk, Line, Node2Vec. However, their methods only preserve symmetric proximities, which could be insufficient in many applications, even the underlying graph is undirected. Besides, they lack of theoretical analysis of what exactly the relationships they preserve in their embedding space. In this paper, we propose an asymmetric proximity preserving (APP) graph embedding method via random walk with restart, which captures both asymmetric and high-order similarities between node pairs. We give theoretical analysis that our method implicitly preserves the Rooted PageRank score for any two vertices. We conduct extensive experiments on tasks of link prediction and node recommendation on open source datasets, as well as online recommendation services in Alibaba Group, in which the training graph has over 290 million vertices and 18 billion edges, showing our method to be highly scalable and effective.

Subfields: Artificial Intelligence, Information Systems, Statistical and Nonlinear Physics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Xing Xie
2. Hongwei Wang
3. Fuzheng Zhang
4. Minyi Guo
5. Miao Zhao
6. Chengqi Zhang
7. Xia Hu
8. Ninghao Liu

In Information Systems

1. Xing Xie
2. Miao Zhao
3. Hongwei Wang
4. Fuzheng Zhang
5. Minyi Guo
6. Dik Lun Lee
7. Chengqi Zhang
8. Xingquan Zhu

In Statistical and Nonlinear Physics

1. Chengqi Zhang
2. Xingquan Zhu
3. Jie Yin
4. Daokun Zhang
5. Xing Xie
6. Binqiang Zhao
7. Dik Lun Lee
8. Minyi Guo

Citations in the corpus

• SHINE: Signed Heterogeneous Information Network Embedding for Sentiment Link Prediction (2017, background): “A few recent studies have focused on this asymmetry issue [16, 36].”
• GraphGAN: Graph Representation Learning with Generative Adversarial Nets (2017, methodology): “examined applying representation learning methods to various types of graphs, such as weighted graphs (Grover and Leskovec 2016), directed graphs (Zhou et al. 2017), signed graphs (Wang et al.”
• Billion-scale Commodity Embedding for E-commerce Recommendation in Alibaba (2018, methodology): “ation machine to the embeddings for recommendation. In [28], Zhang et al. proposed a joint embedding framework to learn the embeddings of graph, text and images, which are used for recommendation. In [30], Zhou et al. proposed graph embedding to capture asymmetric similarities for node recommendatio”
• Deep Representation Learning for Social Network Analysis (2019, background): “In general, the majority of previous work focuses on predicting missing links between users under homogeneous network settings (Grover and Leskovec, 2016; Ou et al., 2016; Zhou et al., 2017), and some efforts also attempt to predict missing links in heterogeneous networks (Liu Z.”
• Network Representation Learning: A Survey (2017, methodology): “APP [36] is another NRL algorithm designed to capture”