On The Expressive Power of GNN Derivatives

• URL: http://arxiv.org/abs/2510.02565v1
• Date: Thu, 02 Oct 2025 21:00:20 GMT
• Title: On The Expressive Power of GNN Derivatives
• Authors: Yam Eitan, Moshe Eliasof, Yoav Gelberg, Fabrizio Frasca, Guy Bar-Shalom, Haggai Maron,
• Abstract summary: 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.
• Score: 36.813086027407714
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Despite significant advances in Graph Neural Networks (GNNs), their limited expressivity remains a fundamental challenge. Research on GNN expressivity has produced many expressive architectures, leading to architecture hierarchies with models of increasing expressive power. Separately, derivatives of GNNs with respect to node features have been widely studied in the context of the oversquashing and over-smoothing phenomena, GNN explainability, and more. To date, these derivatives remain unexplored as a means to enhance GNN expressivity. In this paper, we show that these derivatives provide a natural way to enhance the expressivity of GNNs. We introduce High-Order Derivative GNN (HOD-GNN), a novel method that enhances the expressivity of Message Passing Neural Networks (MPNNs) by leveraging high-order node derivatives of the base model. These derivatives generate expressive structure-aware node embeddings processed by a second GNN in an end-to-end trainable architecture. Theoretically, we show that the resulting architecture family's expressive power aligns with the WL hierarchy. We also draw deep connections between HOD-GNN, Subgraph GNNs, and popular structural encoding schemes. For computational efficiency, we develop a message-passing algorithm for computing high-order derivatives of MPNNs that exploits graph sparsity and parallelism. Evaluations on popular graph learning benchmarks demonstrate HOD-GNN's strong performance on popular graph learning tasks.

Related papers

• On the Computational Capability of Graph Neural Networks: A Circuit Complexity Bound Perspective [28.497567290882355]
  Graph Neural Networks (GNNs) have become the standard approach for learning and reasoning over relational data.<n>This paper explores the computational limitations of GNNs through the lens of circuit complexity.<n>Specifically, we analyze the circuit complexity of common GNN architectures and prove that under constraints of constant-depth layers, linear or sublinear embedding sizes, and precision, GNNs cannot solve key problems such as graph connectivity and graph isomorphism.
  arXiv  Detail & Related papers  (2025-01-11T05:54:10Z)
• 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)
• MAG-GNN: Reinforcement Learning Boosted Graph Neural Network [68.60884768323739]
  A particular line of work proposed subgraph GNNs that use subgraph information to improve GNNs' expressivity and achieved great success. Such effectivity sacrifices the efficiency of GNNs by enumerating all possible subgraphs. We propose Magnetic Graph Neural Network (MAG-GNN), a reinforcement learning (RL) boosted GNN, to solve the problem.
  arXiv  Detail & Related papers  (2023-10-29T20:32:21Z)
• 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)
• Graph Neural Networks are Inherently Good Generalizers: Insights by Bridging GNNs and MLPs [71.93227401463199]
  This paper pinpoints the major source of GNNs' performance gain to their intrinsic capability, by introducing an intermediate model class dubbed as P(ropagational)MLP. We observe that PMLPs consistently perform on par with (or even exceed) their GNN counterparts, while being much more efficient in training.
  arXiv  Detail & Related papers  (2022-12-18T08:17:32Z)
• 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)
• Ego-GNNs: Exploiting Ego Structures in Graph Neural Networks [12.97622530614215]
  We show that Ego-GNNs are capable of recognizing closed triangles, which is essential given the prominence of transitivity in real-world graphs. In particular, we show that Ego-GNNs are capable of recognizing closed triangles, which is essential given the prominence of transitivity in real-world graphs.
  arXiv  Detail & Related papers  (2021-07-22T23:42:23Z)
• Identity-aware Graph Neural Networks [63.6952975763946]
  We develop a class of message passing Graph Neural Networks (ID-GNNs) with greater expressive power than the 1-WL test. ID-GNN extends existing GNN architectures by inductively considering nodes' identities during message passing. We show that transforming existing GNNs to ID-GNNs yields on average 40% accuracy improvement on challenging node, edge, and graph property prediction tasks.
  arXiv  Detail & Related papers  (2021-01-25T18:59:01Z)
• 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)

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.