Research map / Graph learning / GNN architectures

Graph Neural Networks and Arithmetic Circuits

NeurIPS 2024 · Graph learning › GNN architectures · approach: Simple and scalable GNNs · 1 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Shows an exact correspondence between constant-depth real arithmetic circuits and circuit graph neural networks (C-GNNs) whose node computations are circuits, with activation functions as gate types.

Problem

Characterizing the computational power of graph neural networks over real numbers, beyond Boolean inputs and beyond the aggregate-combine (AC-GNN) architecture.

Approach

Treat GNN message passing as a fixed-layer framework whose node computations are arbitrary constant-depth real arithmetic circuits (C-GNNs), and prove that C-GNNs and constant-depth arithmetic circuits over the reals (with activation functions as gate types) simulate each other.

Key results

• Establishes that constant-depth, polynomial-size real arithmetic circuit families (FAC^0_R) and C-GNNs with tail-symmetric circuits simulate each other exactly, with the number of GNN layers equal to circuit depth.
• Shows that AC-GNNs with aggregation computable in the circuit class can be simulated by C-GNNs with a constant number of layers.
• Result holds for countably injective activation functions (ReLU, sigmoid, tanh) in the function-layer form restriction.

Limitations

• Simulations require tail-symmetric circuits in the C-GNN and function-layer form on the circuit side, leaving a gap between the two sides.
• Uniformity notion for GNNs is not made precise; only non-uniform and informal uniform statements are given.
• No experiments; the circuit classes' practical power is not well understood.

Experimental setup

Builds on: AC-GNN Weisfeiler-Leman TC^0 characterization of threshold circuits

Closest papers by meaning

• A Theoretical Comparison of Graph Neural Network Extensions (ICML 2022 · similarity 0.87)
• Fast and Deep Graph Neural Networks (AAAI 2020 · similarity 0.87)
• What do Graph Neural Networks learn? Insights from Tropical Geometry (NeurIPS 2024 · similarity 0.87)
• Logical characterizations of recurrent graph neural networks with reals and floats (NeurIPS 2024 · similarity 0.86)
• $\mathscr{N}$-WL: A New Hierarchy of Expressivity for Graph Neural Networks (ICLR 2023 · similarity 0.86)
• Zero-One Laws of Graph Neural Networks (NeurIPS 2023 · similarity 0.86)