A Representation Learning Framework for Property Graphs

ABSTRACT

Representation learning on graphs, also called graph embedding, has demonstrated its significant impact on a series of machine learning applications such as classification, prediction and recommendation. However, existing work has largely ignored the rich information contained in the properties (or attributes) of both nodes and edges of graphs in modern applications, e.g., those represented by property graphs. To date, most existing graph embedding methods either focus on plain graphs with only the graph topology, or consider properties on nodes only. We propose PGE, a graph representation learning framework that incorporates both node and edge properties into the graph embedding procedure. PGE uses node clustering to assign biases to differentiate neighbors of a node and leverages multiple data-driven matrices to aggregate the property information of neighbors sampled based on a biased strategy. PGE adopts the popular inductive model for neighborhood aggregation. We provide detailed analyses on the efficacy of our method and validate the performance of PGE by showing how PGE achieves better embedding results than the state-of-the-art graph embedding methods on benchmark applications such as node classification and link prediction over real-world datasets.

References

1. Nitin Agarwal, Huan Liu, Sudheendra Murthy, Arunabha Sen, and Xufei Wang. A social identity approach to identify familiar strangers in a social network. In ICWSM, 2009.
2. Amr Ahmed, Nino Shervashidze, Shravan M. Narayanamurthy, Vanja Josifovski, and Alexander J. Smola. Distributed large-scale natural graph factorization. In WWW, pages 37--48, 2013.
3. Eytan Bakshy, Itamar Rosenn, Cameron Marlow, and Lada A. Adamic. The role of social networks in information diffusion. In WWW, pages 519--528, 2012.
4. Mauro Barone and Michele Coscia. Birds of A feather scam together: Trustworthiness homophily in A business network. Social Networks, 54.
5. Yoshua Bengio, Aaron C. Courville, and Pascal Vincent. Representation learning: A review and new perspectives. PAMI, 35:1798--1828, 2013.
6. Smriti Bhagat, Graham Cormode, and S. Muthukrishnan. Node classification in social networks. In Social network datanalytics, pages 115--148. 2011.
7. Michael M. Bronstein, Joan Bruna, Yann LeCun, Arthur Szlam, and Pierre Vandergheynst. Geometric deep learning: Going beyond euclidean data. IEEE Signal Processing Magazine, 34.
8. Shaosheng Cao, Wei Lu, and Qiongkai Xu. Grarep: Learning graph representations with global structural information. In CIKM, pages 891--900, 2015.
9. Shaosheng Cao, Wei Lu, and Qiongkai Xu. Deep neural networks for learning graph representations. In AAAI, pages 1145--1152, 2016.
10. Haochen Chen, Bryan Perozzi, Yifan Hu, and Steven Skiena. HARP: hierarchical representation learning for networks. In AAAI, pages 2127--2134, 2018.
11. Jianfei Chen, Jun Zhu, and Le Song. Stochastic training of graph convolutional networks with variance reduction. In ICML, pages 941--949, 2018.
12. Martin Ester, Hans-Peter Kriegel, Jörg Sander, and Xiaowei Xu. A density-based algorithm for discovering clusters in large spatial databases with noise. In SIGKDD, pages 226--231, 1996.
13. Santo Fortunato. Community detection in graphs. Physics Reports, 486:75--174, 2010.
14. Thomas Gärtner, Tamás Horváth, and Stefan Wrobel. Graph kernels. In Encyclopedia of Machine Learning and Data Mining, pages 579--581. 2017.
15. Palash Goyal and Emilio Ferrara. Graph embedding techniques, applications, and performance: A survey. KBS, 151:78--94, 2018.
16. Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In SIGKDD, pages 855--864, 2016.
17. William L. Hamilton, Rex Ying, and Jure Leskovec. Representation learning on graphs: Methods and applications. IEEE Data Eng. Bull., 40:52--74, 2017.
18. William L. Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In NIPS, pages 1024--1034, 2017.
19. Keith Henderson, Brian Gallagher, Tina Eliassi-Rad, Hanghang Tong, Sugato Basu, Leman Akoglu, Danai Koutra, Christos Faloutsos, and Lei Li. Rolx: Structural role extraction & mining in large graphs. In SIGKDD, pages 1231--1239, 2012.
20. Geoffrey E. Hinton and Ruslan R. Salakhutdinov. Reducing the dimensionality of data with neural networks. Science, 313:504--507, 2006.
21. Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In ICLR, 2015.
22. Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. CoRR, 2016.
23. Thomas N. Kipf and Max Welling. Variational graph auto-encoders. CoRR, 2016.
24. David Liben-Nowell and Jon M. Kleinberg. The link-prediction problem for social networks. JASIST, 58:1019--1031, 2007.
25. James MacQueen. Some methods for classification and analysis of multivariate observations. In Berkeley Symposium on Mathematical Statistics and Probability, volume 1, pages 281--297, 1967.
26. Tomas Mikolov, Ilya Sutskever, Kai Chen, Gregory S. Corrado, and Jeffrey Dean. Distributed representations of words and phrases and their compositionality. In NIPS, pages 3111--3119, 2013.
27. Galileo Namata, Ben London, Lise Getoor, Bert Huang, and UMD EDU. Querydriven active surveying for collective classification. In MLG, 2012.
28. Maximilian Nickel, Kevin Murphy, Volker Tresp, and Evgeniy Gabrilovich. A review of relational machine learning for knowledge graphs. Proceedings of the IEEE, 104.
29. Mingdong Ou, Peng Cui, Jian Pei, Ziwei Zhang, and Wenwu Zhu. Asymmetric transitivity preserving graph embedding. In SIGKDD, pages 1105--1114, 2016.
30. Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: Online learning of social representations. In SIGKDD, pages 701--710, 2014.
31. Bryan Perozzi, Vivek Kulkarni, and Steven Skiena. Walklets: Multiscale graph embeddings for interpretable network classification. CoRR, 2016.
32. Dragomir R. Radev, Hong Qi, HarrisWu, andWeiguo Fan. Evaluating web-based question answering systems. In LREC, 2002.
33. Yutaka Sasaki. The truth of the f-measure. Teach Tutor Mater, 1:1--5, 2007.
34. Michael Sejr Schlichtkrull, Thomas N. Kipf, Peter Bloem, Rianne van den Berg, Ivan Titov, and Max Welling. Modeling relational data with graph convolutional networks. In ESWC, pages 593--607, 2018.
35. Chris Stark, Bobby-Joe Breitkreutz, Teresa Reguly, Lorrie Boucher, Ashton Breitkreutz, and Mike Tyers. Biogrid: A general repository for interaction datasets. Nucleic Acids Research, 34:535--539, 2006.
36. Daixin Wang, Peng Cui, and Wenwu Zhu. Structural deep network embedding. In SIGKDD, pages 1225--1234, 2016.
37. Jaewon Yang and Jure Leskovec. Overlapping communities explain coreperiphery organization of networks. Proceedings of the IEEE, 102.

Index Terms

• Computer systems organization

  • Architectures

    • Other architectures

      • Neural networks

• Mathematics of computing

  • Discrete mathematics

    • Graph theory

      • Graph algorithms

• Networks

  • Network algorithms

  • Network properties

    • Network structure

      • Topology analysis and generation

• Theory of computation

  • Design and analysis of algorithms

    • Graph algorithms analysis