Document Open Access Logo

Learning and Reasoning with Graph Data: Neural and Statistical-Relational Approaches (Invited Paper)

Author Manfred Jaeger

PDF
Thumbnail PDF

File

OASIcs.AIB.2022.5.pdf
  • Filesize: 1.44 MB
  • 42 pages

Document Identifiers

Author Details

Manfred Jaeger
  • Aalborg University, Denmark

Cite As Get BibTex

Manfred Jaeger. Learning and Reasoning with Graph Data: Neural and Statistical-Relational Approaches (Invited Paper). In International Research School in Artificial Intelligence in Bergen (AIB 2022). Open Access Series in Informatics (OASIcs), Volume 99, pp. 5:1-5:42, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/OASIcs.AIB.2022.5

Abstract

Graph neural networks (GNNs) have emerged in recent years as a very powerful and popular modeling tool for graph and network data. Though much of the work on GNNs has focused on graphs with a single edge relation, they have also been adapted to multi-relational graphs, including knowledge graphs. In such multi-relational domains, the objectives and possible applications of GNNs become quite similar to what for many years has been investigated and developed in the field of statistical relational learning (SRL). This article first gives a brief overview of the main features of GNN and SRL approaches to learning and reasoning with graph data. It analyzes then in more detail their commonalities and differences with respect to semantics, representation, parameterization, interpretability, and flexibility. A particular focus will be on relational Bayesian networks (RBNs) as the SRL framework that is most closely related to GNNs. We show how common GNN architectures can be directly encoded as RBNs, thus enabling the direct integration of "low level" neural model components with the "high level" symbolic representation and flexible inference capabilities of SRL.

Subject Classification

ACM Subject Classification
  • Computing methodologies → Logical and relational learning
  • Computing methodologies → Neural networks
Keywords
  • Graph neural networks
  • Statistical relational learning

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Ralph Abboud, Ismail Ilkan Ceylan, Martin Grohe, and Thomas Lukasiewicz. The surprising power of graph neural networks with random node initialization. In Proceedings of IJCAI 2021, 2021. Google Scholar
  2. Francis Bach. Breaking the curse of dimensionality with convex neural networks. The Journal of Machine Learning Research, 18(1):629-681, 2017. Google Scholar
  3. Albert-László Barabási and Réka Albert. Emergence of scaling in random networks. science, 286(5439):509-512, 1999. Google Scholar
  4. Pablo Barceló, Egor Kostylev, Mikael Monet, Jorge Pérez, Juan Reutter, and Juan-Pablo Silva. The logical expressiveness of graph neural networks. In 8th International Conference on Learning Representations (ICLR 2020), 2020. Google Scholar
  5. Elena Bellodi and Fabrizio Riguzzi. Structure learning of probabilistic logic programs by searching the clause space. Theory and Practice of Logic Programming, 15(2):169-212, 2015. Google Scholar
  6. Yoshua Bengio, Nicolas Le Roux, Pascal Vincent, Olivier Delalleau, and Patrice Marcotte. Convex neural networks. Advances in neural information processing systems, 18:123, 2006. Google Scholar
  7. J. S. Breese, R. P. Goldman, and M. P. Wellman. Introduction to the special section on knowledge-based construction of probabilistic decision models. IEEE Transactions on Systems, Man, and Cybernetics, 24(11), 1994. Google Scholar
  8. Luitzen EJ Brouwer. Beweis der Invarianz des n-dimensionalen Gebiets. Mathematische Annalen, 71(3):305-313, 1911. Google Scholar
  9. Alon Brutzkus and Amir Globerson. Why do larger models generalize better? a theoretical perspective via the xor problem. In International Conference on Machine Learning, pages 822-830. PMLR, 2019. Google Scholar
  10. Gabriele Corso, Luca Cavalleri, Dominique Beaini, Pietro Liò, and Petar Veličković. Principal neighbourhood aggregation for graph nets. Advances in Neural Information Processing Systems, 33, 2020. Google Scholar
  11. Hanjun Dai, Azade Nazi, Yujia Li, Bo Dai, and Dale Schuurmans. Scalable deep generative modeling for sparse graphs. In International Conference on Machine Learning, pages 2302-2312. PMLR, 2020. Google Scholar
  12. L. De Raedt. Logical and Relational Learning. Springer, 2008. Google Scholar
  13. R. de Salvo Braz, E. Amir, and D. Roth. Lifted first-order probabilistic inference. In Proceedings of the 19th International Joint Conference on Artificial Intelligence (IJCAI-05), pages 1319-1325, 2005. Google Scholar
  14. Thomas Elsken, Jan Hendrik Metzen, and Frank Hutter. Neural architecture search: A survey. The Journal of Machine Learning Research, 20(1):1997-2017, 2019. Google Scholar
  15. Varun Embar, Sriram Srinivasan, and Lise Getoor. A comparison of statistical relational learning and graph neural networks for aggregate graph queries. Machine Learning, pages 1-20, 2021. Google Scholar
  16. Herbert B Enderton. A mathematical introduction to logic. Elsevier, 2001. Google Scholar
  17. Paul Erdos, Alfréd Rényi, et al. On the evolution of random graphs. Publ. Math. Inst. Hung. Acad. Sci, 5(1):17-60, 1960. Google Scholar
  18. N. Friedman, Lise Getoor, D. Koller, and A. Pfeffer. Learning probabilistic relational models. In Proceedings of the 16th International Joint Conference on Artificial Intelligence (IJCAI-99), 1999. Google Scholar
  19. Vikas Garg, Stefanie Jegelka, and Tommi Jaakkola. Generalization and representational limits of graph neural networks. In International Conference on Machine Learning, pages 3419-3430. PMLR, 2020. Google Scholar
  20. L. Getoor and B. Taskar, editors. Introduction to Statistical Relational Learning. MIT Press, 2007. Google Scholar
  21. Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In International conference on machine learning, pages 1263-1272. PMLR, 2017. Google Scholar
  22. Ian Goodfellow, Yoshua Bengio, and Aaron Courville. Deep Learning. MIT Press, 2016. URL: http://www.deeplearningbook.org.
  23. William L Hamilton. Graph representation learning. Synthesis Lectures on Artifical Intelligence and Machine Learning, 14(3):1-159, 2020. Google Scholar
  24. William L. Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, 4-9 December 2017, Long Beach, CA, USA, pages 1024-1034, 2017. URL: http://papers.nips.cc/paper/6703-inductive-representation-learning-on-large-graphs.
  25. D. Heckerman, C. Meek, and D. Koller. Probabilistic entity-relationship models, PRMs, and plate models. In L. Getoor and B. Taskar, editors, Introduction to Statistical Relational Learning. MIT Press, 2007. Google Scholar
  26. Peter D Hoff, Adrian E Raftery, and Mark S Handcock. Latent space approaches to social network analysis. Journal of the American Statistical Association, 97(460):1090-1098, 2002. Google Scholar
  27. Paul W Holland, Kathryn Blackmond Laskey, and Samuel Leinhardt. Stochastic blockmodels: First steps. Social networks, 5(2):109-137, 1983. Google Scholar
  28. Kurt Hornik. Approximation capabilities of multilayer feedforward networks. Neural networks, 4(2):251-257, 1991. Google Scholar
  29. Manfred Jaeger. Relational Bayesian networks. In Dan Geiger and Prakash Pundalik Shenoy, editors, Proceedings of the 13th Conference of Uncertainty in Artificial Intelligence (UAI-13), pages 266-273, Providence, USA, 1997. Morgan Kaufmann. Google Scholar
  30. Manfred Jaeger. On the complexity of inference about probabilistic relational models. Artificial Intelligence, 117:297-308, 2000. Google Scholar
  31. Manfred Jaeger. Model-theoretic expressivity analysis. In L. De Raedt, K. Frasconi, P.and Kersting, and S.H. Muggleton, editors, Probabilistic Inductive Logic Programming, volume 4911 of LNCS, pages 325-339. Springer, 2008. Google Scholar
  32. Manfred Jaeger. Probabilistic logic and relational models. In Reda Alhajj and Jon Rokne, editors, Encyclopedia of Social Network Analysis and Mining, pages 1-15. Springer New York, New York, NY, 2017. URL: https://doi.org/10.1007/978-1-4614-7163-9_157-1.
  33. Manfred Jaeger, Marco Lippi, Andrea Passerini, and Paolo Frasconi. Type extension trees for feature construction and learning in relational domains. Artificial Intelligence, 204:30-55, 2013. URL: https://doi.org/10.1016/j.artint.2013.08.002.
  34. Manfred * Jaeger. Complex probabilistic modeling with recursive relational Bayesian networks. Annals of Mathematics and Artificial Intelligence, 32:179-220, 2001. Google Scholar
  35. Manfred Jaeger*. Parameter learning for relational Bayesian networks. In Proceedings of the 24th International Conference on Machine Learning (ICML), 2007. Google Scholar
  36. Jiuchuan Jiang and Manfred Jaeger. Numeric input relations for relational learning with applications to community structure analysis. CoRR, abs/1506.05055, 2015. URL: http://arxiv.org/abs/1506.05055.
  37. K. Kersting and L. De Raedt. Towards combining inductive logic programming and Bayesian networks. In Proceedings of the Eleventh International Conference on Inductive Logic Programming (ILP-2001), Springer Lecture Notes in AI 2157, 2001. Google Scholar
  38. Tushar Khot, Sriraam Natarajan, Kristian Kersting, and Jude Shavlik. Learning Markov logic networks via functional gradient boosting. In 2011 IEEE 11th international conference on data mining, pages 320-329. IEEE, 2011. Google Scholar
  39. Angelika Kimmig, Bart Demoen, L De Raedt, V. Santos Costa, and Ricardo Rocha. On the implementation of the probabilistic logic programming language ProbLog. Theory and Practice of Logic Programming, 11(2-3):235-262, 2011. URL: https://doi.org/10.1017/S1471068410000566.
  40. Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint, 2014. URL: http://arxiv.org/abs/1412.6980.
  41. Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. arXiv preprint, 2016. URL: http://arxiv.org/abs/1609.02907.
  42. Thomas N Kipf and Max Welling. Variational graph auto-encoders. arXiv preprint, 2016. URL: http://arxiv.org/abs/1611.07308.
  43. Stanley Kok and Pedro Domingos. Learning the structure of markov logic networks. In Proceedings of the 22nd international conference on Machine learning, pages 441-448, 2005. Google Scholar
  44. Daphne Koller and Nir Friedman. Probabilistic graphical models: principles and techniques. MIT press, 2009. Google Scholar
  45. Kathryn Blackmond Laskey. MEBN: A language for first-order Bayesian knowledge bases. Artificial Intelligence, 172(2-3):140-178, 2008. URL: https://doi.org/10.1016/j.artint.2007.09.006.
  46. Kathryn Blackmond Laskey and Suzanne M. Mahoney. Network fragments: Representing knowledge for constructing probabilistic models. In Proceedings of the 13th Annual Conference on Uncertainty in Artificial Intelligence (UAI-97), pages 334-341, San Francisco, CA, 1997. Morgan Kaufmann Publishers. Google Scholar
  47. Yujia Li, Oriol Vinyals, Chris Dyer, Razvan Pascanu, and Peter Battaglia. Learning deep generative models of graphs. arXiv preprint, 2018. URL: http://arxiv.org/abs/1803.03324.
  48. Yao Ma, Suhang Wang, Chara C Aggarwal, Dawei Yin, and Jiliang Tang. Multi-dimensional graph convolutional networks. In Proceedings of the 2019 SIAM International Conference on Data Mining, pages 657-665. SIAM, 2019. Google Scholar
  49. Robin Manhaeve, Sebastijan Dumancic, Angelika Kimmig, Thomas Demeester, and Luc De Raedt. Deepproblog: Neural probabilistic logic programming. Advances in Neural Information Processing Systems, 31:3749-3759, 2018. Google Scholar
  50. Lilyana Mihalkova and Raymond J Mooney. Bottom-up learning of Markov logic network structure. In Proceedings of the 24th international conference on Machine learning, pages 625-632, 2007. Google Scholar
  51. Christopher Morris, Martin Ritzert, Matthias Fey, William L Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. Weisfeiler and leman go neural: Higher-order graph neural networks. In Proceedings of the AAAI Conference on Artificial Intelligence, pages 4602-4609, 2019. Google Scholar
  52. Behnam Neyshabur, Zhiyuan Li, Srinadh Bhojanapalli, Yann LeCun, and Nathan Srebro. The role of over-parametrization in generalization of neural networks. In International Conference on Learning Representations, 2018. Google Scholar
  53. L. Ngo and P. Haddawy. Probabilistic logic programming and Bayesian networks. In Algorithms, Concurrency and Knowledge (Proceedings ACSC95), Springer Lecture Notes in Computer Science 1023, pages 286-300, 1995. Google Scholar
  54. Jorge Nocedal. Updating quasi-newton matrices with limited storage. Mathematics of computation, 35(151):773-782, 1980. Google Scholar
  55. Giovanni Pellegrini, Alessandro Tibo, Paolo Frasconi, Andrea Passerini, and Manfred Jaeger. Learning aggregation functions. In Proceedings of the Thirty International Joint Conference on Artificial Intelligence (IJCAI-21). International Joint Conferences on Artificial Intelligence, 2021. Google Scholar
  56. Trang Pham, Truyen Tran, Dinh Phung, and Svetha Venkatesh. Column networks for collective classification. In Thirty-first AAAI conference on artificial intelligence, 2017. Google Scholar
  57. D. Poole. First-order probabilistic inference. In Proceedings of the 18th International Joint Conference on Artificial Intelligence (IJCAI-03), 2003. Google Scholar
  58. David Poole. The independent choice logic for modelling multiple agents under uncertainty. Artificial Intelligence, 94(1-2):7-56, 1997. Google Scholar
  59. Meng Qu, Yoshua Bengio, and Jian Tang. Gmnn: Graph Markov neural networks. In International conference on machine learning, pages 5241-5250. PMLR, 2019. Google Scholar
  60. Luc De Raedt, Kristian Kersting, Sriraam Natarajan, and David Poole. Statistical relational artificial intelligence: Logic, probability, and computation. Synthesis lectures on artificial intelligence and machine learning, 10(2):1-189, 2016. Google Scholar
  61. Marco Tulio Ribeiro, Sameer Singh, and Carlos Guestrin. "Why should I trust you?" explaining the predictions of any classifier. In Proceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and data mining, pages 1135-1144, 2016. Google Scholar
  62. M. Richardson and P. Domingos. Markov logic networks. Machine Learning, 62(1-2):107-136, 2006. Google Scholar
  63. S. Russell and P. Norvig. Artificial Intelligence: A Modern Approach. Pearson, third edition edition, 2010. Google Scholar
  64. Ryoma Sato. A survey on the expressive power of graph neural networks. arXiv preprint, 2020. URL: http://arxiv.org/abs/2003.04078.
  65. Ryoma Sato, Makoto Yamada, and Hisashi Kashima. Random features strengthen graph neural networks. In Proceedings of the 2021 SIAM International Conference on Data Mining (SDM), pages 333-341. SIAM, 2021. Google Scholar
  66. T. Sato. A statistical learning method for logic programs with distribution semantics. In Proceedings of the 12th International Conference on Logic Programming (ICLP'95), pages 715-729, 1995. Google Scholar
  67. Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE transactions on neural networks, 20(1):61-80, 2008. Google Scholar
  68. Michael Schlichtkrull, Thomas N Kipf, Peter Bloem, Rianne Van Den Berg, Ivan Titov, and Max Welling. Modeling relational data with graph convolutional networks. In European semantic web conference, pages 593-607. Springer, 2018. Google Scholar
  69. Gustav Šourek, Filip Železnỳ, and Ondřej Kuželka. Beyond graph neural networks with lifted relational neural networks. Machine Learning, pages 1-44, 2021. Google Scholar
  70. J. van Mill. Domain invariance. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Domain_invariance&oldid=16623.
  71. Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations, 2018. Google Scholar
  72. Clément Vignac, Andreas Loukas, and Pascal Frossard. Building powerful and equivariant graph neural networks with structural message-passing. In NeurIPS, 2020. Google Scholar
  73. Edward Wagstaff, Fabian Fuchs, Martin Engelcke, Ingmar Posner, and Michael A Osborne. On the limitations of representing functions on sets. In International Conference on Machine Learning, pages 6487-6494. PMLR, 2019. Google Scholar
  74. Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and S Yu Philip. A comprehensive survey on graph neural networks. IEEE transactions on neural networks and learning systems, 32(1):4-24, 2021. Google Scholar
  75. Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference on Learning Representations, 2019. Google Scholar
  76. Jiaxuan You, Rex Ying, Xiang Ren, William Hamilton, and Jure Leskovec. Graphrnn: Generating realistic graphs with deep auto-regressive models. In International conference on machine learning, pages 5708-5717. PMLR, 2018. Google Scholar
  77. Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Russ R Salakhutdinov, and Alexander J Smola. Deep sets. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017. URL: https://proceedings.neurips.cc/paper/2017/file/f22e4747da1aa27e363d86d40ff442fe-Paper.pdf.
  78. Muhan Zhang and Yixin Chen. Link prediction based on graph neural networks. Advances in Neural Information Processing Systems, 31:5165-5175, 2018. Google Scholar
  79. Jie Zhou, Ganqu Cui, Shengding Hu, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, Lifeng Wang, Changcheng Li, and Maosong Sun. Graph neural networks: A review of methods and applications. AI Open, 1:57-81, 2020. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact