Logical Expressivity and Explanations for Monotonic GNNs with Scoring Functions

• URL: http://arxiv.org/abs/2508.14091v1
• Date: Thu, 14 Aug 2025 15:56:48 GMT
• Title: Logical Expressivity and Explanations for Monotonic GNNs with Scoring Functions
• Authors: Matthew Morris, David J. Tena Cucala, Bernardo Cuenca Grau,
• Abstract summary: Graph neural networks (GNNs) are often used for the task of link prediction.<n>We show how GNNs and scoring functions can be adapted to be monotonic.
• Score: 10.533348468499826
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Graph neural networks (GNNs) are often used for the task of link prediction: predicting missing binary facts in knowledge graphs (KGs). To address the lack of explainability of GNNs on KGs, recent works extract Datalog rules from GNNs with provable correspondence guarantees. The extracted rules can be used to explain the GNN's predictions; furthermore, they can help characterise the expressive power of various GNN models. However, these works address only a form of link prediction based on a restricted, low-expressivity graph encoding/decoding method. In this paper, we consider a more general and popular approach for link prediction where a scoring function is used to decode the GNN output into fact predictions. We show how GNNs and scoring functions can be adapted to be monotonic, use the monotonicity to extract sound rules for explaining predictions, and leverage existing results about the kind of rules that scoring functions can capture. We also define procedures for obtaining equivalent Datalog programs for certain classes of monotonic GNNs with scoring functions. Our experiments show that, on link prediction benchmarks, monotonic GNNs and scoring functions perform well in practice and yield many sound rules.

Related papers

• Sound Logical Explanations for Mean Aggregation Graph Neural Networks [7.08300385454159]
  Graph neural networks (GNNs) are frequently used for knowledge graph completion.<n>We consider GNNs with mean aggregation and non-negative weights (MAGNNs)<n>Our experiments show that restricting mean-aggregation GNNs to have non-negative weights yields comparable or improved performance on standard inductive benchmarks.
  arXiv  Detail & Related papers  (2025-10-27T13:23:21Z)
• Global Graph Counterfactual Explanation: A Subgraph Mapping Approach [54.42907350881448]
  Graph Neural Networks (GNNs) have been widely deployed in various real-world applications. Counterfactual explanation aims to find minimum perturbations on input graphs that change the GNN predictions. We propose GlobalGCE, a novel global-level graph counterfactual explanation method.
  arXiv  Detail & Related papers  (2024-10-25T21:39:05Z)
• Relational Graph Convolutional Networks Do Not Learn Sound Rules [13.66949379381985]
  Graph neural networks (GNNs) are frequently used to predict missing facts in knowledge graphs (KGs) Recent work has aimed to explain their predictions using Datalog, a widely used logic-based formalism. We consider one of the most popular GNN architectures for KGs, R-GCN, and we provide two methods to extract rules that explain its predictions and are sound.
  arXiv  Detail & Related papers  (2024-08-14T15:46:42Z)
• Explainable Graph Neural Networks Under Fire [69.15708723429307]
  Graph neural networks (GNNs) usually lack interpretability due to their complex computational behavior and the abstract nature of graphs. Most GNN explanation methods work in a post-hoc manner and provide explanations in the form of a small subset of important edges and/or nodes. In this paper we demonstrate that these explanations can unfortunately not be trusted, as common GNN explanation methods turn out to be highly susceptible to adversarial perturbations.
  arXiv  Detail & Related papers  (2024-06-10T16:09:16Z)
• GNNEvaluator: Evaluating GNN Performance On Unseen Graphs Without Labels [81.93520935479984]
  We study a new problem, GNN model evaluation, that aims to assess the performance of a specific GNN model trained on labeled and observed graphs. We propose a two-stage GNN model evaluation framework, including (1) DiscGraph set construction and (2) GNNEvaluator training and inference. Under the effective training supervision from the DiscGraph set, GNNEvaluator learns to precisely estimate node classification accuracy of the to-be-evaluated GNN model.
  arXiv  Detail & Related papers  (2023-10-23T05:51:59Z)
• GNNInterpreter: A Probabilistic Generative Model-Level Explanation for Graph Neural Networks [25.94529851210956]
  We propose a model-agnostic model-level explanation method for different Graph Neural Networks (GNNs) that follow the message passing scheme, GNNInterpreter. GNNInterpreter learns a probabilistic generative graph distribution that produces the most discriminative graph pattern the GNN tries to detect. Compared to existing works, GNNInterpreter is more flexible and computationally efficient in generating explanation graphs with different types of node and edge features.
  arXiv  Detail & Related papers  (2022-09-15T07:45:35Z)
• ProtGNN: Towards Self-Explaining Graph Neural Networks [12.789013658551454]
  We propose Prototype Graph Neural Network (ProtGNN), which combines prototype learning with GNNs. ProtGNN and ProtGNN+ can provide inherent interpretability while achieving accuracy on par with the non-interpretable counterparts.
  arXiv  Detail & Related papers  (2021-12-02T01:16:29Z)
• The Surprising Power of Graph Neural Networks with Random Node Initialization [54.4101931234922]
  Graph neural networks (GNNs) are effective models for representation learning on relational data. Standard GNNs are limited in their expressive power, as they cannot distinguish beyond the capability of the Weisfeiler-Leman graph isomorphism. In this work, we analyze the expressive power of GNNs with random node (RNI) We prove that these models are universal, a first such result for GNNs not relying on computationally demanding higher-order properties.
  arXiv  Detail & Related papers  (2020-10-02T19:53:05Z)
• Distance Encoding: Design Provably More Powerful Neural Networks for Graph Representation Learning [63.97983530843762]
  Graph Neural Networks (GNNs) have achieved great success in graph representation learning. GNNs generate identical representations for graph substructures that may in fact be very different. More powerful GNNs, proposed recently by mimicking higher-order tests, are inefficient as they cannot sparsity of underlying graph structure. We propose Distance Depiction (DE) as a new class of graph representation learning.
  arXiv  Detail & Related papers  (2020-08-31T23:15:40Z)
• XGNN: Towards Model-Level Explanations of Graph Neural Networks [113.51160387804484]
  Graphs neural networks (GNNs) learn node features by aggregating and combining neighbor information. GNNs are mostly treated as black-boxes and lack human intelligible explanations. We propose a novel approach, known as XGNN, to interpret GNNs at the model-level.
  arXiv  Detail & Related papers  (2020-06-03T23:52:43Z)
• Graph Sequential Network for Reasoning over Sequences [38.766982479196926]
  We consider a novel case where reasoning is needed over graphs built from sequences. Existing GNN models fulfill this goal by first summarizing the node sequences into fixed-dimensional vectors, then applying GNN on these vectors. We propose a new type of GNN called Graph Sequential Network (GSN), which features a new message passing algorithm based on co-attention between a node and each of its neighbors.
  arXiv  Detail & Related papers  (2020-04-04T19:18:54Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.