{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,18]],"date-time":"2026-08-18T03:55:55Z","timestamp":1787025355201,"version":"build-2736575974"},"publisher-location":"California","reference-count":0,"publisher":"International Joint Conferences on Artificial Intelligence Organization","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2023,9]]},"abstract":"<jats:p>Although there has been significant interest in applying machine learning techniques to structured data, the expressivity (i.e., a description of what can be learned) of such techniques is still poorly understood. In this paper, we study data transformations based on graph neural networks (GNNs). First, we note that the choice of how a dataset is encoded into a numeric form processable by a GNN can obscure the characterisation of a model's expressivity, and we argue that a canonical encoding provides an appropriate basis. Second, we study the expressivity of monotonic max-sum GNNs, which cover a subclass of GNNs with max and sum aggregation functions. We show that, for each such GNN, one can compute a Datalog program such that applying the GNN to any dataset produces the same facts as a single round of application of the program's rules to the dataset. Monotonic max-sum GNNs can sum an unbounded number of feature vectors which can result in arbitrarily large feature values, whereas rule application requires only a bounded number of constants. Hence, our result shows that the unbounded summation of monotonic max-sum GNNs does not increase their expressive power. Third, we sharpen our result to the subclass of monotonic max GNNs, which use only the max aggregation function, and identify a corresponding class of Datalog programs.<\/jats:p>","DOI":"10.24963\/kr.2023\/64","type":"proceedings-article","created":{"date-parts":[[2023,7,31]],"date-time":"2023-07-31T18:27:47Z","timestamp":1690828067000},"page":"658-667","source":"Crossref","is-referenced-by-count":1,"title":["On the Correspondence Between Monotonic Max-Sum GNNs and Datalog"],"prefix":"10.24963","author":[{"given":"David","family":"Tena Cucala","sequence":"first","affiliation":[{"name":"University of Oxford"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Bernardo","family":"Cuenca Grau","sequence":"additional","affiliation":[{"name":"University of Oxford"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Boris","family":"Motik","sequence":"additional","affiliation":[{"name":"University of Oxford"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Egor V.","family":"Kostylev","sequence":"additional","affiliation":[{"name":"University of Oslo"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"10584","event":{"name":"20th International Conference on Principles of Knowledge Representation and Reasoning {KR-2023}","theme":"Artificial Intelligence","location":"Rhodes, Greece","acronym":"KR-2023","number":"20","sponsor":["Artificial Intelligence Journal","Principles of Knowledge Representation and Reasoning Inc.","Academic College of Tel-Aviv","European Association for Artificial Intelligence","National Science Foundation"],"start":{"date-parts":[[2023,9,2]]},"end":{"date-parts":[[2023,9,8]]}},"container-title":["Proceedings of the Twentieth International Conference on Principles of Knowledge Representation and Reasoning"],"original-title":[],"deposited":{"date-parts":[[2023,7,31]],"date-time":"2023-07-31T18:28:51Z","timestamp":1690828131000},"score":1,"resource":{"primary":{"URL":"https:\/\/proceedings.kr.org\/2023\/64"}},"subtitle":[],"proceedings-subject":"Artificial Intelligence Research Articles","short-title":[],"issued":{"date-parts":[[2023,9]]},"references-count":0,"URL":"https:\/\/doi.org\/10.24963\/kr.2023\/64","relation":{},"subject":[],"published":{"date-parts":[[2023,9]]}}}