A comparison of statistical relational learning and graph neural networks for aggregate graph queries
Open Access
- 17 June 2021
- journal article
- research article
- Published by Springer Nature in Machine Learning
- Vol. 110 (7) , 1847-1866
Abstract
Statistical relational learning (SRL) and graph neural networks (GNNs) are two powerful approaches for learning and inference over graphs. Typically, they are evaluated in terms of simple metrics such as accuracy over individual node labels. Complexaggregate graph queries(AGQ) involving multiple nodes, edges, and labels are common in the graph mining community and are used to estimate important network properties such as social cohesion and influence. While graph mining algorithms support AGQs, they typically do not take into account uncertainty, or when they do, make simplifying assumptions and do not build full probabilistic models. In this paper, we examine the performance of SRL and GNNs on AGQs over graphs with partially observed node labels. We show that, not surprisingly, inferring the unobserved node labels as a first step and then evaluating the queries on the fully observed graph can lead to sub-optimal estimates, and that a better approach is to compute these queries as an expectation under the joint distribution. We propose a sampling framework to tractably compute the expected values of AGQs. Motivated by the analysis of subgroup cohesion in social networks, we propose a suite of AGQs that estimate the community structure in graphs. In our empirical evaluation, we show that by estimating these queries as an expectation, SRL-based approaches yield up to a 50-fold reduction in average error when compared to existing GNN-based approaches.Keywords
Funding Information
- National Science Foundation (CCF-1740850, IIS-1703331)
This publication has 26 references indexed in Scilit:
- VEGAS: Visual influEnce GrAph Summarization on Citation NetworksIEEE Transactions on Knowledge and Data Engineering, 2015
- Probabilistic (logic) programming conceptsMachine Learning, 2015
- Graph summarization for attributed graphs2014
- Motif simplification2013
- Biased Assimilation, Homophily, and the Dynamics of PolarizationLecture Notes in Computer Science, 2012
- Markov logic networksMachine Learning, 2006
- A View of the Em Algorithm that Justifies Incremental, Sparse, and other Variants1998
- Markov Chain Monte Carlo in Practice.Journal of the American Statistical Association, 1997
- Graph bisection algorithms with good average case behaviorCombinatorica, 1987
- Stochastic blockmodels: First stepsSocial Networks, 1983