{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,7]],"date-time":"2026-04-07T17:02:40Z","timestamp":1775581360768,"version":"3.50.1"},"reference-count":71,"publisher":"Frontiers Media SA","license":[{"start":{"date-parts":[[2023,8,22]],"date-time":"2023-08-22T00:00:00Z","timestamp":1692662400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["frontiersin.org"],"crossmark-restriction":true},"short-container-title":["Front. Artif. Intell."],"abstract":"<jats:p>Reasoning about graphs, and learning from graph data is a field of artificial intelligence that has recently received much attention in the machine learning areas of graph representation learning and graph neural networks. Graphs are also the underlying structures of interest in a wide range of more traditional fields ranging from logic-oriented knowledge representation and reasoning to graph kernels and statistical relational learning. In this review we outline a broad map and inventory of the field of learning and reasoning with graphs that spans the spectrum from reasoning in the form of logical deduction to learning node embeddings. To obtain a unified perspective on such a diverse landscape we introduce a simple and general semantic concept of a model that covers logic knowledge bases, graph neural networks, kernel support vector machines, and many other types of frameworks. Still at a high semantic level, we survey common strategies for model specification using probabilistic factorization and standard feature construction techniques. Based on this semantic foundation we introduce a taxonomy of reasoning tasks that casts problems ranging from transductive link prediction to asymptotic analysis of random graph models as queries of different complexities for a given model. Similarly, we express learning in different frameworks and settings in terms of a common statistical maximum likelihood principle. Overall, this review aims to provide a coherent conceptual framework that provides a basis for further theoretical analyses of respective strengths and limitations of different approaches to handling graph data, and that facilitates combination and integration of different modeling paradigms.<\/jats:p>","DOI":"10.3389\/frai.2023.1124718","type":"journal-article","created":{"date-parts":[[2023,8,22]],"date-time":"2023-08-22T09:07:45Z","timestamp":1692695265000},"update-policy":"https:\/\/doi.org\/10.3389\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Learning and reasoning with graph data"],"prefix":"10.3389","volume":"6","author":[{"given":"Manfred","family":"Jaeger","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1965","published-online":{"date-parts":[[2023,8,22]]},"reference":[{"key":"B1","doi-asserted-by":"publisher","DOI":"10.24963\/ijcai.2021\/291","article-title":"\u201cThe surprising power of graph neural networks with random node initialization,\u201d","author":"Abboud","year":"2021","journal-title":"Proceedings of IJCAI 2021"},{"key":"B2","article-title":"\u201cThe logical expressiveness of graph neural networks,\u201d","author":"Barcel\u00f3","year":"2020","journal-title":"8th International Conference on Learning Representations (ICLR 2020)"},{"key":"B3","doi-asserted-by":"publisher","first-page":"179","DOI":"10.2307\/2987782","article-title":"Statistical analysis of non-lattice data","volume":"24","author":"Besag","year":"1975","journal-title":"J. R. Stat. Soc. Ser. D"},{"key":"B4","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1016\/S0004-3702(98)00034-4","article-title":"Top-down induction of first-order logical decision trees","volume":"101","author":"Blockeel","year":"1998","journal-title":"Artif. Intell."},{"key":"B5","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3379445","article-title":"Graph generators: state of the art and open challenges","volume":"53","author":"Bonifati","year":"2020","journal-title":"ACM Comput. Surveys"},{"key":"B6","doi-asserted-by":"publisher","first-page":"1580","DOI":"10.1109\/21.328909","article-title":"Introduction to the special section on knowledge-based construction of probabilistic decision models","volume":"24","author":"Breese","year":"1994","journal-title":"IEEE Trans. Syst. Man Cybern"},{"key":"B7","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1016\/j.ijar.2019.04.003","article-title":"The finite model theory of Bayesian network specifications: Descriptive complexity and zero\/one laws","volume":"110","author":"Cozman","year":"2019","journal-title":"Int. J. Approx. Reason"},{"key":"B8","unstructured":"\u201cLearning steady-states of iterative algorithms over graphs,\u201d DaiH. KozarevaZ. DaiB. SmolaA. SongL. International Conference on Machine Learning (PMLR)2018"},{"key":"B9","first-page":"2302","article-title":"\u201cScalable deep generative modeling for sparse graphs,\u201d","author":"Dai","year":"2020","journal-title":"International Conference on Machine Learning"},{"key":"B10","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1016\/S0004-3702(97)00041-6","article-title":"Logical settings for concept-learning","volume":"95","author":"De Raedt","year":"1997","journal-title":"Artif. Intell"},{"key":"B11","first-page":"2462","article-title":"\u201cProblog: a probabilistic prolog and its application in link discovery,\u201d","author":"De Raedt","year":"2007","journal-title":"IJCAI, Vol. 7"},{"key":"B12","doi-asserted-by":"publisher","first-page":"1997","DOI":"10.1007\/978-3-030-05318-5_3","article-title":"Neural architecture search: a survey","volume":"20","author":"Elsken","year":"2019","journal-title":"J. Mach. Learn. Res"},{"key":"B13","first-page":"17","article-title":"On the evolution of random graphs","volume":"5","author":"Erd\u0151s","year":"1960","journal-title":"Publ. Math. Inst. Hung. Acad. Sci"},{"key":"B14","doi-asserted-by":"publisher","first-page":"50","DOI":"10.2307\/2272945","article-title":"Probabilities on finite models","volume":"41","author":"Fagin","year":"1976","journal-title":"J. Symb. Logic"},{"key":"B15","article-title":"\u201cInference in probabilistic logic programs using weighted CNF's,\u201d","author":"Fierens","year":"2011","journal-title":"Proceedings of UAI 2011"},{"key":"B16","article-title":"\u201cLearning probabilistic relational models,\u201d","author":"Friedman","year":"1999","journal-title":"Proceedings of the 16th International Joint Conference on Artificial Intelligence (IJCAI-99)"},{"key":"B17","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1007\/978-3-540-45167-9_11","article-title":"\u201cOn graph kernels: hardness results and efficient alternatives,\u201d","volume-title":"Learning Theory and Kernel Machines: 16th Annual Conference on Learning Theory and 7th Kernel Workshop, COLT\/Kernel 2003","author":"G\u00e4rtner","year":"2003"},{"key":"B18","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1016\/S0019-9958(83)80043-6","article-title":"Complexity of the first-order theory of almost all finite strucutures","volume":"57","author":"Grandjean","year":"1983","journal-title":"Inform. Control"},{"key":"B19","doi-asserted-by":"publisher","DOI":"10.1145\/2939672.2939754","article-title":"\u201cnode2vec: scalable feature learning for networks,\u201d","author":"Grover","year":"2016","journal-title":"Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining"},{"key":"B20","doi-asserted-by":"publisher","DOI":"10.1016\/B978-0-12-450010-5.50015-3","article-title":"\u201cModel checking vs. theorem proving: a manifesto,\u201d","author":"Halpern","year":"1991","journal-title":"Artificial Intelligence and Mathematical Theory of Computation: Papers in Honor of John McCarthy"},{"key":"B21","volume-title":"Graph Representation Learning, Vol. 46 of Synthesis Lectures on Artifical Intelligence and Machine Learning","author":"Hamilton","year":"2020"},{"key":"B22","first-page":"1024","article-title":"\u201cInductive representation learning on large graphs,\u201d","author":"Hamilton","year":"2017","journal-title":"Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017"},{"key":"B23","first-page":"265","article-title":"\u201cHOL light: A tutorial introduction,\u201d","volume-title":"International Conference on Formal Methods in Computer-Aided Design","author":"Harrison","year":"1996"},{"key":"B24","doi-asserted-by":"crossref","DOI":"10.7551\/mitpress\/7432.003.0009","article-title":"\u201cProbabilistic entity-relationship models, PRMs, and plate models,\u201d","volume-title":"Introduction to Statistical Relational Learning","author":"Heckerman","year":"2007"},{"key":"B25","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1016\/0378-8733(83)90021-7","article-title":"Stochastic blockmodels: first steps","volume":"5","author":"Holland","year":"1983","journal-title":"Soc. Netw"},{"key":"B26","first-page":"266","article-title":"\u201cRelational Bayesian networks,\u201d","volume-title":"Proceedings of the 13th Conference of Uncertainty in Artificial Intelligence (UAI-13)","author":"Jaeger","year":"1997"},{"key":"B27","doi-asserted-by":"publisher","first-page":"44","DOI":"10.1109\/LICS.1998.705642","article-title":"\u201cConvergence results for relational Bayesian networks,\u201d","author":"Jaeger","year":"1998","journal-title":"Proceedings of the 13th Annual IEEE Symposium on Logic in Computer Science (LICS-98)"},{"key":"B28","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1016\/S0004-3702(99)00109-5","article-title":"On the complexity of inference about probabilistic relational models","volume":"117","author":"Jaeger","year":"2000","journal-title":"Artif. Intell"},{"key":"B29","unstructured":"\u201cLearning and reasoning with graph data: neural and statistical-relational approaches,\u201d15 JaegerM. International Research School in Artificial Intelligence in Bergen (AIB 2022), Vol. 99 of Open Access Series in Informatics (OASIcs)52022"},{"key":"B30","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44797-0_10","article-title":"\u201cTowards combining inductive logic programming and Bayesian networks,\u201d","author":"Kersting","year":"2001","journal-title":"Proceedings of the Eleventh International Conference on Inductive Logic Programming (ILP-2001)"},{"key":"B31","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.1611.07308","article-title":"Variational graph auto-encoders","author":"Kipf","year":"2016","journal-title":"arXiv [Preprint]."},{"key":"B32","unstructured":"\u201cSemi-supervised classification with graph convolutional networks,\u201d KipfT. N. WellingM. International Conference on Learning Representations2017"},{"key":"B33","doi-asserted-by":"publisher","first-page":"105061","DOI":"10.1016\/j.ic.2023.105061","article-title":"Asymptotic elimination of partially continuous aggregation functions in directed graphical models","volume":"293","author":"Koponen","year":"2023","journal-title":"Infm. Comput."},{"key":"B34","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1007\/978-1-4899-7637-6_3","article-title":"\u201cAdvances in collaborative filtering,\u201d","author":"Koren","year":"2015","journal-title":"Recommender Systems Handbook"},{"key":"B35","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s41109-019-0195-3","article-title":"A survey on graph kernels","volume":"5","author":"Kriege","year":"2020","journal-title":"Appl. Netw. Sci"},{"key":"B36","doi-asserted-by":"publisher","first-page":"124289","DOI":"10.1016\/j.physa.2020.124289","article-title":"Link prediction techniques, applications, and performance: a survey","volume":"553","author":"Kumar","year":"2020","journal-title":"Phys. A Stat. Mech. Appl"},{"key":"B37","doi-asserted-by":"publisher","first-page":"140","DOI":"10.1016\/j.artint.2007.09.006","article-title":"MEBN: a language for first-order Bayesian knowledge bases","volume":"172","author":"Laskey","year":"2008","journal-title":"Artif. Intell"},{"key":"B38","first-page":"334","article-title":"\u201cNetwork fragments: representing knowledge for constructing probabilistic models,\u201d","volume-title":"Proceedings of the 13th Annual Conference on Uncertainty in Artificial Intelligence (UAI-97)","author":"Laskey","year":"1997"},{"key":"B39","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1145\/1217299.1217301","article-title":"Graph evolution: densification and shrinking diameters","volume":"1","author":"Leskovec","year":"2007","journal-title":"ACM Trans. Knowl. Discov Data"},{"key":"B40","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.1803.03324","article-title":"Learning deep generative models of graphs","author":"Li","year":"2018","journal-title":"arXiv [Preprint]."},{"key":"B41","unstructured":"\u201cDeepProbLog: Neural probabilistic logic programming,\u201d ManhaeveR. DumancicS. KimmigA. DemeesterT. De RaedtL. 33693375Advances in Neural Information Processing Systems, Vol. 31.2018"},{"key":"B42","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v33i01.33014602","article-title":"\u201cWeisfeiler and leman go neural: Higher-order graph neural networks,\u201d","author":"Morris","year":"2019","journal-title":"Proceedings of the AAAI Conference on Artificial Intelligence"},{"key":"B43","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1007\/BF03037227","article-title":"Inverse entailment and progol","volume":"13","author":"Muggleton","year":"1995","journal-title":"New Generat. Comput."},{"key":"B44","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-60688-2_51","article-title":"\u201cProbabilistic logic programming and Bayesian networks,\u201d","author":"Ngo","year":"1995","journal-title":"Algorithms, Concurrency and Knowledge (Proceedings ACSC95), Springer Lecture Notes in Computer Science 1023"},{"key":"B45","first-page":"2014","article-title":"\u201cLearning convolutional neural networks for graphs,\u201d","author":"Niepert","year":"2016","journal-title":"International Conference on Machine Learning"},{"key":"B46","article-title":"\u201cNeural link prediction with walk pooling,\u201d","author":"Pan","year":"2021","journal-title":"International Conference on Learning Representations"},{"key":"B47","doi-asserted-by":"publisher","DOI":"10.1145\/2623330.2623732","article-title":"\u201cDeepwalk: online learning of social representations,\u201d","author":"Perozzi","year":"2014","journal-title":"Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining"},{"key":"B48","doi-asserted-by":"publisher","first-page":"7","DOI":"10.1016\/S0004-3702(97)00027-1","article-title":"The independent choice logic for modelling multiple agents under uncertainty","volume":"94","author":"Poole","year":"1997","journal-title":"Artif. Intell."},{"key":"B49","article-title":"\u201cFirst-order probabilistic inference,\u201d","author":"Poole","year":"2003","journal-title":"Proceedings of the 18th International Joint Conference on Artificial Intelligence (IJCAI-03)"},{"key":"B50","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/3-540-56602-3_124","article-title":"\u201cFOIL: A midterm report,\u201d","author":"Quinlan","year":"1993","journal-title":"Machine Learning: ECML-93: European Conference on Machine Learning Vienna, Austria, April"},{"key":"B51","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1007\/s10994-006-5833-1","article-title":"Markov logic networks","volume":"62","author":"Richardson","year":"2006","journal-title":"Mach. Learn"},{"key":"B52","doi-asserted-by":"publisher","DOI":"10.3233\/AIC-210084","article-title":"Neuro-symbolic artificial intelligence: current trends","author":"Sarker","year":"2021","journal-title":"arXiv preprint arXiv:2105.05330"},{"key":"B53","article-title":"A survey on the expressive power of graph neural networks","author":"Sato","year":"2020","journal-title":"arXiv preprint arXiv:2003.04078"},{"key":"B54","doi-asserted-by":"crossref","first-page":"333","DOI":"10.1137\/1.9781611976700.38","article-title":"\u201cRandom features strengthen graph neural networks,\u201d","volume-title":"Proceedings of the 2021 SIAM International Conference on Data Mining (SDM)","author":"Sato","year":"2021"},{"key":"B55","doi-asserted-by":"crossref","first-page":"715","DOI":"10.7551\/mitpress\/4298.003.0069","article-title":"\u201cA statistical learning method for logic programs with distribution semantics,\u201d","author":"Sato","year":"1995","journal-title":"Proceedings of the 12th International Conference on Logic Programming (ICLP'95)"},{"key":"B56","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1109\/TNN.2008.2005605","article-title":"The graph neural network model","volume":"20","author":"Scarselli","year":"2008","journal-title":"IEEE Trans. Neur. Netw."},{"key":"B57","first-page":"488","article-title":"\u201cEfficient graphlet kernels for large graph comparison,\u201d","author":"Shervashidze","year":"2009","journal-title":"Artificial Intelligence and Statistics"},{"key":"B58","doi-asserted-by":"publisher","first-page":"2539","DOI":"10.5555\/1953048.2078187","article-title":"Weisfeiler-lehman graph kernels","volume":"12","author":"Shervashidze","year":"2011","journal-title":"J. Mach. Learn. Res"},{"key":"B59","first-page":"412","article-title":"\u201cGraphvae: towards generation of small graphs using variational autoencoders,\u201d","volume-title":"International Conference on Artificial Neural Networks","author":"Simonovsky","year":"2018"},{"key":"B60","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1016\/0004-3702(95)00122-0","article-title":"Theories for mutagenicity: a study in first-order and feature-based induction","volume":"85","author":"Srinivasan","year":"1996","journal-title":"Artif. Intell"},{"key":"B61","article-title":"\u201cConditioning in first-order knowledge compilation and lifted probabilistic inference,\u201d","author":"Van den Broeck","year":"2012","journal-title":"Twenty-Sixth AAAI Conference on Artificial Intelligence"},{"key":"B62","article-title":"\u201cOn the completeness of first-order knowledge compilation for lifted probabilistic inference,\u201d","author":"Van den Broeck","year":"2011","journal-title":"Proceedings of the 25th Annual Conference on Neural Information Processing Systems (NIPS)"},{"key":"B63","article-title":"\u201cGraph attention networks,\u201d","author":"Veli\u010dkovi\u0107","year":"2018","journal-title":"International Conference on Learning Representations"},{"key":"B64","article-title":"\u201cBuilding powerful and equivariant graph neural networks with structural message-passing,\u201d","author":"Vignac","year":"2020","journal-title":"NeurIPS"},{"key":"B65","first-page":"6487","article-title":"\u201cOn the limitations of representing functions on sets,\u201d","author":"Wagstaff","year":"2019","journal-title":"International Conference on Machine Learning"},{"key":"B66","first-page":"140","article-title":"\u201cSpass version 3.5,\u201d","volume-title":"International Conference on Automated Deduction","author":"Weidenbach","year":"2009"},{"key":"B67","author":"Welling","year":"2017"},{"key":"B68","article-title":"\u201cHow powerful are graph neural networks?,\u201d","author":"Xu","year":"2019","journal-title":"International Conference on Learning Representations"},{"key":"B69","first-page":"5708","article-title":"\u201cGraphRNN: generating realistic graphs with deep auto-regressive models,\u201d","author":"You","year":"2018","journal-title":"International Conference on Machine Learning"},{"key":"B70","doi-asserted-by":"publisher","DOI":"10.1145\/3394486.3403085","article-title":"\u201cXGNN: towards model-level explanations of graph neural networks,\u201d","author":"Yuan","year":"2020","journal-title":"Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery"},{"key":"B71","article-title":"\u201cDeep sets,\u201d","volume-title":"Advances in Neural Information Processing Systems, Vol. 30","author":"Zaheer","year":"2017"}],"container-title":["Frontiers in Artificial Intelligence"],"original-title":[],"link":[{"URL":"https:\/\/www.frontiersin.org\/articles\/10.3389\/frai.2023.1124718\/full","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,12,19]],"date-time":"2023-12-19T13:51:28Z","timestamp":1702993888000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.frontiersin.org\/articles\/10.3389\/frai.2023.1124718\/full"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,8,22]]},"references-count":71,"alternative-id":["10.3389\/frai.2023.1124718"],"URL":"https:\/\/doi.org\/10.3389\/frai.2023.1124718","relation":{},"ISSN":["2624-8212"],"issn-type":[{"value":"2624-8212","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,8,22]]},"article-number":"1124718"}}