Grothendieck Graph Neural Networks Framework: An Algebraic Platform for Crafting Topology-Aware GNNs

Amirreza Shiralinasab Langari [email protected], Leila Yeganeh [email protected], Kim Khoa Nguyen [email protected] · 2024

Read Grothendieck Graph Neural Networks Framework: An Algebraic Platform for Crafting Topology-Aware GNNs by Amirreza Shiralinasab Langari [email protected], Leila Yeganeh [email protected], Kim Khoa Nguyen [email protected] (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-08835.txt.

Introduction

Amirreza Shiralinasab Langari, Leila Yeganeh, and Kim Khoa Nguyen propose swapping out the neighborhood as the basic unit of graph neural networks, in a two thousand twenty-four paper. Message passing over neighborhoods caps what the network can say, at the Weisfeiler-Lehman test's power.

Their Grothendieck setup swaps in covers for neighborhoods, bringing back usual adjacency as a special case. Covers are turned, step by step, into matrices, making the idea both easy to analyze and easy to build. A flagship instance, Sieve Neural Networks, uses a cover of sieves borrowed from group theory to capture richer topology. The model records zero seen failures on hard graph isomorphism benchmarks and improves a label-spreading probe of topology awareness.

Catalog record

CREATORAmirreza Shiralinasab Langari [email protected], Leila Yeganeh [email protected], Kim Khoa Nguyen [email protected]
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE99 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-08835

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Grothendieck Graph Neural Networks Framework: An Algebraic Platform for Crafting Topology-Aware GNNs Amirreza Shiralinasab Langari [email protected], Leila Yeganeh [email protected], Kim Khoa Nguyen [email protected] Abstract Graph Neural Networks (GNNs) are almost universally built on a single primitive: the neighborhood. Regardless of architectural variations, message passing ultimately aggregates over neighborhoods, which intrinsically limits expressivity and often yields power no stronger than the Weisfeiler–Lehman (WL) test. In this work, we challenge this primitive. We introduce the Grothendieck Graph Neural Networks (GkGNN) framework, which provides a strict algebraic extension of neighborhoods to covers , and in doing so replaces neighborhoods as the fundamental objects of message passing. Neighborhoods and adjacency matrices are recovered as special cases, while covers enable a principled and flexible foundation for defining topology-aware propagation schemes. GkGNN formalizes covers and systematically translates them into matrices, analogously to how adjacency matrices encode neighborhoods, enabling both theoretical analysis and practical implementation. Within this framework, we introduce the cover of sieves , inspired by category theory, which captures rich topological structure. Based on this cover, we design Sieve Neural Networks (SNN), a canonical fixed-cover instantiation that generalizes the adjacency matrix. Experiments show that SNN achieves zero observed failures on challenging graph isomorphism benchmarks (SRG, CSL, BREC) and substantially improves topology-aware evaluation via a controlled label-propagation probe. These results establish GkGNN as a principled foundational framework for replacing neighborhoods in GNNs. Reviewed on OpenReview: https://openreview.net/forum?id=oD3qWXgB4e 1 Introduction The concept of neighborhood plays a central role in most Graph Neural Network (GNN) architectures, serving as the foundation of message passing ( Gilmer et al., 2017 ) . This reliance is not arbitrary: neighborhoods provide comprehensive coverage of the graph structure, leveraging the adjacency matrix to facilitate efficient and systematic aggregation of local information. However, this neighborhood-based perspective comes with intrinsic limitations. In particular, many GNNs have expressive power bounded by the WL test ( Sato, 2020 ) , ( Xu et al., 2019 ) , restricting their ability to capture broader topological structures. To address the limitations of neighborhoods, researchers have proposed alternatives that incorporate richer structural information. One direction uses concepts from algebraic topology, such as simplicial complexes and higher-order faces, to capture interactions beyond pairs of nodes ( Bodnar et al., 2021b ) , ( Bodnar et al., 2021a ) , ( Hajij et al., 2023 ) , ( Papillon et al., 2025 ) . Another line of work relies on specific patterns or subgraphs (e.g., motifs) to encode characteristic structures as the basis for topologically-aware message passing ( Bouritsas et al., 2023 ) , ( Ai et al., 2022 ) . While these methods enrich the local perspective, they often depend on handcrafted definitions or combinatorial choices. In contrast, neighborhoods themselves arise from a precise algebraic definition, suggesting that a systematic algebraic formalism for extending neighborhoods may provide a broader and more principled foundation for message passing itself. Viewpoint. We argue that neighborhoods should no longer be regarded as the primitive objects of message passing. Instead, we propose to replace neighborhoods by covers 1 1 1 The term cover here should not be confused with graph-theoretic vertex or edge covers; it refers to a collection of algebraically defined message-passing strategies. as the fundamental units over which message passing operates. Covers strictly generalize neighborhoods: neighborhoods are recovered as a special case, while covers enable algebraically defined alternatives to neighborhood aggregation that go beyond locality. The purpose of this paper is to establish the algebraic and invariance foundations of this replacement. In particular, we introduce the first algebraic formalism for systematically generating and implementing infinitely many message-passing strategies, ranging from standard neighborhood aggregation to covers that encode richer topological structure. Covers may be instantiated as fixed algebraic objects, as in this work, or parameterized and learned in future architectures. Throughout this paper, replacing neighborhoods refers to replacing them as the primitive abstraction of message passing, not to discarding adjacency-based information: neighborhoods appear as specific elements within a larger algebraic space of composable propagation operators. Building on this viewpoint, our work introduces an algebraic framework that extends neighborhoods to covers while preserving their structural role. This leads to the Grothendieck Graph Neural Networks (GkGNN) framework, an algebraic platform that formalizes covers, studies their invariance properties, and systematically translates them into matrix representations. In this framework, the adjacency matrix appears as a special case, while more expressive covers give rise to new message-passing operators. Because this work extends the notion of neighborhoods, any existing GNN architecture can, in principle, be reformulated to operate on covers instead of neighborhoods. Accordingly, our focus is not on proposing a new learning algorithm, but on establishing the algebraic and invariance foundations that make such a replacement possible. At the core of GkGNN is a duality between graphs and algebraic structures, showing that graphs can be characterized by monoids generated from their covers. Our main contributions are as follows. • Replacing neighborhoods by covers. We introduce the concept of covers for graphs as a strict algebraic extension of neighborhoods. This generalization provides a principled and flexible foundation for representing graph structure. • The GkGNN framework. We develop the Grothendieck Graph Neural Networks (GkGNN) framework, which creates, refines, and transforms covers into their matrix forms, recovering the adjacency matrix as a special case. GkGNN offers a systematic way to design new message-passing strategies. • Sieve Neural Networks (SNN). As a concrete instantiation of GkGNN, we introduce Sieve Neural Networks (SNN) as a canonical example showing how expressive algebraic covers can be transformed into message-passing operators. • Topology-aware evaluation. In addition to evaluating SNN on graph isomorphism tasks, we design a topology-encoding benchmark based on a special case of Label Propagation (LP) ( Zhu and Ghahramani, 2002 ; Huang et al., 2020 ) with one propagation step (\alpha=1) . Here LP is used not as a learning algorithm but as a controlled probe to directly compare covers with neighborhoods. On citation networks and ogbn-arxiv, sieve covers consistently and substantially outperform the neighborhood cover, highlighting the advantage of covers in capturing topological structure in large graphs. The proposed extension of the neighborhood concept in this paper relies on introducing four monoids (see Appendix A for formal definition of a monoid and monoidal homomorphism), (\mathsf{Mod}(G),\bullet)\subseteq(\mathsf{SMult}(G),\bullet) and (\mathsf{Mom}(G),\circ)\subseteq(\mathsf{Mat}_{n}(\mathbb{R}),\circ) . In this setting, neighborhoods are elements of \mathsf{Mod}(G) , and a monoidal homomorphism \mathsf{Tr}:\mathsf{Mod}(G)\rightarrow\mathsf{Mom}(G) translates elements of \mathsf{Mod}(G) into matrices. This organization allows us to treat graphs as algebraic spaces, in a manner analogous to familiar examples such as (\mathbb{N},\times) , where natural numbers are composed by multiplication, or (\mathsf{Mat}_{n}(\mathbb{R}),\cdot) , where matrices are composed by matrix multiplication. In the same spirit, the monoid operation \bullet enables algebraic compositions of graph-derived objects, for instance N(u)\bullet N(v) . As proved in Theorem 3.2.5 , directed edges generate \mathsf{Mod}(G) . Intuitively, directed edges act as elementary building blocks: by composing edges as e_{1}\bullet e_{2}\bullet\cdots\bullet e_{k} , one can generate both neighborhoods and elements beyond neighborhoods, in an informal sense analogous to how the monoid (\mathbb{N},\times) is generated by prime numbers under multiplication. The map \mathsf{Tr} plays an essential role in the GkGNN framework: it is not merely a function, but a monoidal homomorphism. For example, the determinant defines a monoidal homomorphism from (\mathsf{Mat}_{n}(\mathbb{R}),\cdot) to (\mathbb{R},\times) , since \det(A\cdot B)=\det(A)\times\det(B) .

Read the complete text