![[2602.18409] Unifying approach to uniform expressivity of graph neural networks](https://arxiv.org/static/browse/0.3.4/images/arxiv-logo-fb.png){kind=logo}
[2602.18409] Unifying approach to uniform expressivity of graph neural networks
Summary
This paper presents a unified framework for enhancing the expressivity of Graph Neural Networks (GNNs) through Template GNNs (T-GNNs), establishing a connection with Graded template modal logic (GML(T)).
Why It Matters
Understanding the expressivity of GNNs is crucial for advancing machine learning applications in graph-based data. This research provides a comprehensive framework that can lead to improved GNN architectures, enhancing their performance in various domains such as social network analysis and biological data processing.
Key Takeaways
- Introduces Template GNNs (T-GNNs) to enhance GNN expressivity.
- Establishes a formal equivalence between T-GNNs and Graded template modal logic (GML(T)).
- Provides a unifying approach to analyze GNN expressivity.
- Demonstrates how standard AC-GNNs relate to T-GNNs.
- Advances the understanding of GNNs in relation to first-order logic.
Computer Science > Machine Learning arXiv:2602.18409 (cs) [Submitted on 20 Feb 2026] Title:Unifying approach to uniform expressivity of graph neural networks Authors:Huan Luo, Jonni Virtema View a PDF of the paper titled Unifying approach to uniform expressivity of graph neural networks, by Huan Luo and 1 other authors View PDF HTML (experimental) Abstract:The expressive power of Graph Neural Networks (GNNs) is often analysed via correspondence to the Weisfeiler-Leman (WL) algorithm and fragments of first-order logic. Standard GNNs are limited to performing aggregation over immediate neighbourhoods or over global read-outs. To increase their expressivity, recent attempts have been made to incorporate substructural information (e.g. cycle counts and subgraph properties). In this paper, we formalize this architectural trend by introducing Template GNNs (T-GNNs), a generalized framework where node features are updated by aggregating over valid template embeddings from a specified set of graph templates. We propose a corresponding logic, Graded template modal logic (GML(T)), and generalized notions of template-based bisimulation and WL algorithm. We establish an equivalence between the expressive power of T-GNNs and GML(T), and provide a unifying approach for analysing GNN expressivity: we show how standard AC-GNNs and its recent variants can be interpreted as instantiations of T-GNNs. Subjects: Machine Learning (cs.LG); Artificial Intelligence (cs.AI); Logic in Computer Scien...
