Unifying approach to uniform expressivity of graph neural networks
This provides a foundational theoretical framework for analyzing and improving GNN expressivity, which is incremental as it formalizes and unifies existing architectural trends rather than introducing a completely new paradigm.
The paper tackles the limited expressive power of Graph Neural Networks (GNNs) by introducing Template GNNs (T-GNNs), a generalized framework that unifies and extends existing methods, and establishes an equivalence with a new logic, showing how standard and recent GNN variants can be interpreted as instantiations of this framework.
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.