Rong Zhu
Abstract
An increasing number of machine learning tasks require dealing with large graph datasets, which capture rich and complex relationship among potentially billions of elements. Graph Neural Network (GNN) becomes an effective way to address the graph learning problem by converting the graph data into a low dimensional space while keeping both the structural and property information to the maximum extent and constructing a neural network for training and referencing. However, it is challenging to provide an efficient graph storage and computation capabilities to facilitate GNN training and enable development of new GNN algorithms. In this paper, we present a comprehensive graph neural network system, namely AliGraph, which consists of distributed graph storage, optimized sampling operators and runtime to efficiently support not only existing popular GNNs but also a series of in-house developed ones for different scenarios. The system is currently deployed at Alibaba to support a variety of business scenarios, including product recommendation and personalized search at Alibaba's E-Commerce platform. By conducting extensive experiments on a real-world dataset with 492.90 million vertices, 6.82 billion edges and rich attributes, AliGraph performs an order of magnitude faster in terms of graph building (5 minutes vs hours reported from the state-of-the-art PowerGraph platform). At training, AliGraph runs 40%-50% faster with the novel caching strategy and demonstrates around 12 times speed up with the improved runtime. In addition, our in-house developed GNN models all showcase their statistically significant superiorities in terms of both effectiveness and efficiency (e.g., 4.12%--17.19% lift by F1 scores).
- P. Battaglia, R. Pascanu, M. Lai, and D. J. Rezende. Interaction networks for learning about objects, relations and physics. In NIPS, pages 4502--4510, 2016. Google Scholar
Digital Library
- S. Bhagat, G. Cormode, and S. Muthukrishnan. Node classification in social networks. Computer Science, 16(3):115--148, 2011.Google Scholar
- E. G. Boman, K. D. Devine, and S. Rajamanickam. Scalable matrix computations on large scale-free graphs using 2d graph partitioning. 2013.Google Scholar
- U. Brandes, M. Gaertler, and D. Wagner. Experiments on graph clustering algorithms. LNCS, 2832:568--579, 2003.Google Scholar
- H. Cai, V. W. Zheng, C. C. Chang, H. Cai, V. W. Zheng, and C. C. Chang. A comprehensive survey of graph embedding: Problems, techniques and applications. TKDE, 30(9):1616--1637, 2017.Google Scholar
- S. Chang, W. Han, J. Tang, G.-J. Qi, C. C. Aggarwal, and T. S. Huang. Heterogeneous network embedding via deep architectures. In KDD, pages 119--128, 2015. Google ScholarDigital Library
- Cen, Y., Zou, X., Zhang, J., Yang, H., Zhou, J., Tang, J. Representation Learning for Attributed Multiplex Heterogeneous Network. In KDD, 2019. Google ScholarDigital Library
- Liu, N., Tan, Q., Li, Y., Yang, H., Zhou, J., Hu, X. Is a Single Vector Enough? Exploring Node Polysemy for Network Embedding. In KDD, 2019. Google ScholarDigital Library
- Li, C., Shen, D., Jia, K., Yang, H. Hierarchical Representation Learning for Bipartite Graphs. In IJCAI, 2019.Google Scholar
- Zhao, Y., Wang, X., Yang, H., Song, L. and Tang, J. Large Scale Evolving Graphs with Burst Detection. In IJCAI, 2019.Google Scholar
- J. Chen, T. Ma, and C. Xiao. Fastgcn: fast learning with graph convolutional networks via importance sampling. arXiv.1801.10247, 2018.Google Scholar
- M. Chrobak and J. Noga. Lru is better than fifo. In Acm-siam Symposium on Discrete Algorithms, 1998. Google ScholarDigital Library
- P. Cui, X. Wang, J. Pei, and W. Zhu. A survey on network embedding. TKDE, 2018.Google Scholar
- Y. Dong, N. V. Chawla, and A. Swami. metapath2vec: Scalable representation learning for heterogeneous networks. In KDD, pages 135--144, 2017. Google ScholarDigital Library
- L. Du, Y. Wang, G. Song, Z. Lu, and J. Wang. Dynamic network embedding: An extended approach for skip-gram based network embedding. In IJCAI, pages 2086--2092, 2018. Google ScholarDigital Library
- A. G. Duran and M. Niepert. Learning graph representations with embedding propagation. In Advances in Neural Information Processing Systems, pages 5119--5130, 2017.Google Scholar
- W. Fan, J. Xu, Y. Wu, W. Yu, J. Jiang, Z. Zheng, B. Zhang, Y. Cao, and C. Tian. Parallelizing sequential graph computations. In SIGMOD, pages 495--510, 2017. Google ScholarDigital Library
- A. Fout, J. Byrd, B. Shariat, and A. Ben-Hur. Protein interface prediction using graph convolutional networks. In NIPS, pages 6530--6539, 2017. Google ScholarDigital Library
- H. Gao and H. Huang. Deep attributed network embedding. In IJCAI, pages 3364--3370, 2018. Google ScholarDigital Library
- J. E. Gonzalez, Y. Low, H. Gu, D. Bickson, and C. Guestrin. Powergraph: Distributed graph-parallel computation on natural graphs. In OSDI, 2012. Google ScholarDigital Library
- P. Goyal and E. Ferrara. Graph embedding techniques, applications, and performance: A survey. Knowledge-Based Systems, 2018.Google Scholar
- A. Grover and J. Leskovec. node2vec: Scalable feature learning for networks. In KDD, pages 855--864, 2016. Google ScholarDigital Library
- T. Hamaguchi, H. Oiwa, M. Shimbo, and Y. Matsumoto. Knowledge transfer for out-of-knowledge-base entities : A graph neural network approach. In IJCAI, 2017. Google ScholarDigital Library
- W. L. Hamilton, R. Ying, and J. Leskovec. Representation learning on graphs: Methods and applications. 2017.Google Scholar
- W. L. Hamilton, Z. Ying, and J. Leskovec. Inductive representation learning on large graphs. In NIPS, pages 1025--1035, 2017. Google ScholarDigital Library
- R. He and J. McAuley. Ups and downs: Modeling the visual evolution of fashion trends with one-class collaborative filtering. In WWW, pages 507--517. Google ScholarDigital Library
- X. Huang, J. Li, and X. Hu. Accelerated attributed network embedding. In SDM, pages 633--641. SIAM, 2017.Google Scholar
- X. Huang, J. Li, and X. Hu. Label informed attributed network embedding. In WSDM, pages 731--739, 2017. Google ScholarDigital Library
- D. R. Hush and J. M. Salas. Improving the learning rate of back-propagation with the gradient reuse algorithm. In IEEE International Conference on Neural Networks, 1988.Google ScholarCross Ref
- G. Karypis and V. Kumar. Metis-unstructured graph partitioning and sparse matrix ordering system. Technical Report.Google Scholar
- D. P. Kingma and M. Welling. Auto-encoding variational bayes. arXiv.1312.6114, 2013.Google Scholar
- T. N. Kipf and M. Welling. Semi-supervised classification with graph convolutional networks. In ICLR, 2017.Google Scholar
- Y. LeCun, Y. Bengio, and G. Hinton. Deep learning. In Nature, pages 521--436. 2015.Google Scholar
- J. Li, H. Dani, X. Hu, J. Tang, Y. Chang, and H. Liu. Attributed network embedding for learning in a dynamic environment. In CIKM, pages 387--396. ACM, 2017. Google ScholarDigital Library
- Li, C., Shen, D., Jia, K., Yang, H. Hierarchical Representation Learning for Bipartite Graphs. In IJCAI, 2019.Google Scholar
- D. Liang, R. G. Krishnan, M. D. Hoffman, and T. Jebara. Variational autoencoders for collaborative filtering. 2018.Google Scholar
- L. Liao, X. He, H. Zhang, and T.-S. Chua. Attributed social network embedding. TKDE, 30(12):2257--2270, 2018.Google ScholarDigital Library
- D. Liben-Nowell and J. Kleinberg. The link prediction problem for social networks. 2003.Google Scholar
- Z. Lin, M. Feng, C. N. d. Santos, M. Yu, B. Xiang, B. Zhou, and Y. Bengio. A structured self-attentive sentence embedding. arXiv:1703.03130, 2017.Google Scholar
- W. Liu, P.-Y. Chen, S. Yeung, T. Suzumura, and L. Chen. Principled multilayer network embedding. In ICDM, pages 134--141. IEEE, 2017.Google ScholarCross Ref
- Liu, N., Tan, Q., Li, Y., Yang, H., Zhou, J., Hu, X. Is a Single Vector Enough? Exploring Node Polysemy for Network Embedding. In KDD, 2019. Google ScholarDigital Library
- J. McAuley, C. Targett, Q. Shi, and A. Van Den Hengel. Image-based recommendations on styles and substitutes. In SIGIR, pages 43--52. ACM, 2015. Google ScholarDigital Library
- B. Perozzi, R. Al-Rfou, and S. Skiena. Deepwalk: Online learning of social representations. In KDD, pages 701--710. ACM, 2014. Google ScholarDigital Library
- J. Qiu, Y. Dong, H. Ma, J. Li, K. Wang, and J. Tang. Network embedding as matrix factorization: Unifying deepwalk, line, pte, and node2vec. In WSDM, pages 459--467, 2018. Google ScholarDigital Library
- M. Qu, J. Tang, J. Shang, X. Ren, M. Zhang, and J. Han. An attention-based collaboration framework for multi-view network representation learning. In CIKM, pages 1767--1776. ACM, 2017. Google ScholarDigital Library
- L. F. R. Ribeiro, P. H. P. Saverese, and D. R. Figueiredo. struc2vec : Learning node representations from structural identity. 2017.Google Scholar
- C. Shi, B. Hu, X. Zhao, and P. Yu. Heterogeneous information network embedding for recommendation. TKDE, 2018. Google ScholarDigital Library
- I. Stanton and G. Kliot. Streaming graph partitioning for large distributed graphs. In KDD, 2013. Google ScholarDigital Library
- J. Tang, M. Qu, and Q. Mei. Pte: Predictive text embedding through large-scale heterogeneous text networks. In KDD, pages 1165--1174. ACM, 2015. Google ScholarDigital Library
- J. Tang, M. Qu, M. Wang, M. Zhang, J. Yan, and Q. Mei. Line: Large-scale information network embedding. In WWW, pages 1067--1077, 2015. Google ScholarDigital Library
- S. Tanimoto. Power laws of the in-degree and out-degree distributions of complex networks. Physics, 2009.Google Scholar
- P. Vincent, H. Larochelle, Y. Bengio, and P. A. Manzagol. Extracting and composing robust features with denoising autoencoders. In ICML, 2008. Google ScholarDigital Library
- D. Wang, P. Cui, and W. Zhu. Structural deep network embedding. In KDD, pages 1225--1234, 2016. Google ScholarDigital Library
- Z. Wang, Y. Tan, and Z. Ming. Graph-based recommendation on social networks. In APWeb, 2010. Google ScholarDigital Library
- W. Xiong, M. Yu, S. Chang, X. Guo, and W. Y. Wang. One-shot relational learning for knowledge graphs. In EMNLP, pages 1980--1990, 2018.Google ScholarCross Ref
- C. Yang, Z. Liu, D. Zhao, M. Sun, and E. Y. Chang. Network representation learning with rich text information. In IJCAI, 2015. Google ScholarDigital Library
- H. Zhang, L. Qiu, L. Yi, and Y. Song. Scalable multiplex network embedding. In IJCAI, pages 3082--3088, 2018. Google ScholarDigital Library
- Z. Zhang, H. Yang, J. Bu, S. Zhou, P. Yu, J. Zhang, M. Ester, and C. Wang. Anrl: Attributed network representation learning via deep neural networks. In IJCAI, pages 3155--3161, 2018. Google ScholarDigital Library
- V. W. Zheng, M. Sha, Y. Li, H. Yang, Z. Zhang, and K.-L. Tan. Heterogeneous embedding propagation for large-scale e-commerce user alignment. In ICDM, 2018.Google ScholarCross Ref
- L. Zhou, Y. Yang, X. Ren, F. Wu, and Y. Zhuang. Dynamic network embedding by modeling triadic closure process. In AAAI, 2018.Google ScholarCross Ref
- Zhao, Y., Wang, X., Yang, H., Song, L. and Tang, J. Large Scale Evolving Graphs with Burst Detection. In IJCAI, 2019.Google Scholar
Recommendations
AliGraph: A Comprehensive Graph Neural Network Platform
KDD '19: Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data MiningAn increasing number of machine learning tasks require dealing with large graph datasets, which capture rich and complex relation- ship among potentially billions of elements. Graph Neural Network (GNN) becomes an effective way to address the graph ...
On the Multichromatic Number of s-Stable Kneser Graphs
For positive integers n and s, a subset Sï [n] is s-stable if sï |i-j|ï n-s for distinct i,j∈S . The s-stable r-uniform Kneser hypergraph KGrn,ks-stable is the r-uniform hypergraph that has the collection of all s-stable k-element subsets of [n] as ...
Adjacent vertex-distinguishing edge and total chromatic numbers of hypercubes
An adjacent vertex-distinguishing edge coloring of a simple graph G is a proper edge coloring of G such that incident edge sets of any two adjacent vertices are assigned different sets of colors. A total coloring of a graph G is a coloring of both the ...
Comments