Enhancing Logical Expressiveness in Graph Neural Networks via Path-Neighbor Aggregation

• URL: http://arxiv.org/abs/2511.07994v2
• Date: Fri, 14 Nov 2025 01:34:06 GMT
• Title: Enhancing Logical Expressiveness in Graph Neural Networks via Path-Neighbor Aggregation
• Authors: Han Yu, Xiaojuan Zhao, Aiping Li, Kai Chen, Ziniu Liu, Zhichao Peng,
• Abstract summary: We propose Path-Neighbor enhanced GNN (PN-GNN) to enhance the logical expressive power of GNN.<n>First, we analyze the logical expressive power of existing GNN-based methods and point out the shortcomings of these methods.<n>Then, we theoretically investigate the logical expressive power of PN-GNN, showing that it not only has strictly stronger expressive power than C-GNN but also that its $(k+1)$-hop logical expressiveness is strictly superior to that of $k$-hop.
• Score: 22.086161213961244
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Graph neural networks (GNNs) can effectively model structural information of graphs, making them widely used in knowledge graph (KG) reasoning. However, existing studies on the expressive power of GNNs mainly focuses on simple single-relation graphs, and there is still insufficient discussion on the power of GNN to express logical rules in KGs. How to enhance the logical expressive power of GNNs is still a key issue. Motivated by this, we propose Path-Neighbor enhanced GNN (PN-GNN), a method to enhance the logical expressive power of GNN by aggregating node-neighbor embeddings on the reasoning path. First, we analyze the logical expressive power of existing GNN-based methods and point out the shortcomings of the expressive power of these methods. Then, we theoretically investigate the logical expressive power of PN-GNN, showing that it not only has strictly stronger expressive power than C-GNN but also that its $(k+1)$-hop logical expressiveness is strictly superior to that of $k$-hop. Finally, we evaluate the logical expressive power of PN-GNN on six synthetic datasets and two real-world datasets. Both theoretical analysis and extensive experiments confirm that PN-GNN enhances the expressive power of logical rules without compromising generalization, as evidenced by its competitive performance in KG reasoning tasks.

Related papers

• How Expressive Are Graph Neural Networks in the Presence of Node Identifiers? [8.242194776558897]
  Graph neural networks (GNNs) are a widely used class of machine learning models for graph-structured data.<n>We study the key-invariant expressive power of GNNs, inspired by the notion of order-invariant definability in finite model theory.<n>We provide answers for various classes of GNNs with local max- or sum-aggregation.
  arXiv  Detail & Related papers  (2026-01-29T15:46:35Z)
• On The Expressive Power of GNN Derivatives [36.813086027407714]
  High-Order Derivative GNN (HOD-GNN) is a novel method that enhances the expressivity of Message Passing Neural Networks (MPNNs)<n>We show that the resulting architecture family's expressive power aligns with the WL hierarchy.<n>For computational efficiency, we develop a message-passing algorithm for computing high-order derivatives of MPNNs.
  arXiv  Detail & Related papers  (2025-10-02T21:00:20Z)
• The Correspondence Between Bounded Graph Neural Networks and Fragments of First-Order Logic [8.430502131775723]
  We propose GNN architectures that correspond precisely to prominent fragments of first-order logic (FO)<n>Our results provide a unifying framework for understanding the logical expressiveness of GNNs within FO.
  arXiv  Detail & Related papers  (2025-05-12T19:45:45Z)
• Rethinking GNN Expressive Power from a Distributed Computational Model Perspective [29.47675861430167]
  We argue that using well-defined computational models, such as a modified CONGEST model with clearly specified preprocessing and postprocessing, offers a more sound framework for analyzing GNN expressiveness.<n>We show that allowing unrestricted preprocessing or incorporating externally computed features, while claiming that these precomputations enhance the expressiveness, can sometimes lead to problems.<n>Despite these negative results, we also present positive results that characterize the effects of virtual nodes and edges from a computational model perspective.
  arXiv  Detail & Related papers  (2024-10-02T08:01:50Z)
• Logical Distillation of Graph Neural Networks [47.859911892875346]
  We present a logic based interpretable model for learning on graphs and an algorithm to distill this model from a Graph Neural Network (GNN) Recent results have shown connections between the expressivity of GNNs and the two-variable fragment of first-order logic with counting quantifiers (C2)
  arXiv  Detail & Related papers  (2024-06-11T10:18:58Z)
• A Manifold Perspective on the Statistical Generalization of Graph Neural Networks [84.01980526069075]
  We take a manifold perspective to establish the statistical generalization theory of GNNs on graphs sampled from a manifold in the spectral domain.<n>We prove that the generalization bounds of GNNs decrease linearly with the size of the graphs in the logarithmic scale, and increase linearly with the spectral continuity constants of the filter functions.
  arXiv  Detail & Related papers  (2024-06-07T19:25:02Z)
• Understanding Expressivity of GNN in Rule Learning [36.04983130825589]
  Rule learning is critical to improving knowledge graph (KG) reasoning. GNNs with tail entity scoring are unified into a common framework. We propose a novel labeling strategy to learn more rules in KG reasoning.
  arXiv  Detail & Related papers  (2023-03-22T04:49:00Z)
• Equivariant Polynomials for Graph Neural Networks [38.15983687193912]
  Graph Networks (GNN) are inherently limited in their expressive power. This paper introduces an alternative power hierarchy based on the ability of GNNs to calculate equivariants of certain degree. These enhanced GNNs demonstrate state-of-the-art results in experiments across multiple graph learning benchmarks.
  arXiv  Detail & Related papers  (2023-02-22T18:53:38Z)
• Representation Power of Graph Neural Networks: Improved Expressivity via Algebraic Analysis [124.97061497512804]
  We show that standard Graph Neural Networks (GNNs) produce more discriminative representations than the Weisfeiler-Lehman (WL) algorithm. We also show that simple convolutional architectures with white inputs, produce equivariant features that count the closed paths in the graph.
  arXiv  Detail & Related papers  (2022-05-19T18:40:25Z)
• Expressiveness and Approximation Properties of Graph Neural Networks [6.1323142294300625]
  We provide an elegant way to obtain bounds on the separation power of GNNs in terms of the Weisfeiler-Leman (WL) tests. We use tensor language to define Higher-Order Message-Passing Neural Networks (or k-MPNNs), a natural extension of MPNNs. Our approach provides a toolbox with which GNN architecture designers can analyze the separation power of their GNNs.
  arXiv  Detail & Related papers  (2022-04-10T11:33:04Z)
• 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)
• Eigen-GNN: A Graph Structure Preserving Plug-in for GNNs [95.63153473559865]
  Graph Neural Networks (GNNs) are emerging machine learning models on graphs. Most existing GNN models in practice are shallow and essentially feature-centric. We show empirically and analytically that the existing shallow GNNs cannot preserve graph structures well. We propose Eigen-GNN, a plug-in module to boost GNNs ability in preserving graph structures.
  arXiv  Detail & Related papers  (2020-06-08T02:47:38Z)
• Efficient Probabilistic Logic Reasoning with Graph Neural Networks [63.099999467118245]
  Markov Logic Networks (MLNs) can be used to address many knowledge graph problems. Inference in MLN is computationally intensive, making the industrial-scale application of MLN very difficult. We propose a graph neural network (GNN) variant, named ExpressGNN, which strikes a nice balance between the representation power and the simplicity of the model.
  arXiv  Detail & Related papers  (2020-01-29T23:34:36Z)

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.