Universal Approximation of Invariant Functions on Graphs

15 concepts9 papers1 proposal

When designing neural networks for structured data like graphs, sets, or relational databases, standard multi-layer perceptrons (MLPs) fail to capture a fundamental property of the domain: geometric and structural symmetries. If you shuffle the rows and columns of a graph's adjacency matrix, the underlying graph remains identical. Therefore, any meaningful function we want to learn over graphs must respect this property. It must either be permutation-invariant (yielding the same global output regardless of node ordering) or permutation-equivariant (yielding node-level outputs that permute in exact correspondence with the inputs).

In traditional deep learning, the universal approximation theorem gives us confidence that an MLP can approximate any continuous function to arbitrary precision. To have the same confidence when learning on graphs, we need a universal approximation framework tailored to invariant and equivariant functions. A robust body of mathematical literature has emerged to explain exactly why and how Graph Neural Networks (GNNs) can achieve this universal expressive power.

The Equivalence Between Separation and Approximation

To understand why a GNN can approximate a function, we must first look at its ability to tell two graphs apart. This is known as the graph isomorphism problem.

Intuition suggests that a network's separating power (distinguishing non-isomorphic graphs) is intimately linked to its approximation power (learning continuous functions over those graphs). If an architecture is structurally blind to the difference between Graph A and Graph B—meaning it maps both to the exact same internal representation—it is physically impossible for that network to assign them different target values (e.g., mapping Graph A to $5$ and Graph B to $10$). Thus, graph separation forms a strict upper bound on function approximation.

Zhengdao Chen et al. and Waiss Azizian et al. independently formalized this intuition, proving a strict mathematical equivalence: the capacity of a graph neural network to distinguish between non-isomorphic graphs is identical to its capacity to approximate any permutation-invariant function on those graphs.

┌────────────────────────────────────────┐
│       Graph Separating Power           │
│  (Can the GNN tell Graph A & B apart?) │
└───────────────────▲────────────────────┘
                    │
                    │ Mathematically Equivalent
                    │
┌───────────────────▼────────────────────┐
│     Function Approximation Power       │
│ (Can the GNN learn f(A)=5 and f(B)=10?)│
└────────────────────────────────────────┘

To bridge this gap, Waiss Azizian et al. utilized a specialized variant of the classical Stone-Weierstrass theorem. The Stone-Weierstrass theorem states that if a family of functions can separate distinct points in a domain, it can be used to approximate any continuous function over that domain. By treating the space of non-isomorphic graphs as the domain, the authors showed that any GNN architecture matching the separating power of a structural test can also learn any complex continuous function over that graph space.

The Weisfeiler-Lehman Benchmark

Because separating power dictates approximation power, graph machine learning relies heavily on a classical topological algorithm: the Weisfeiler-Lehman (WL) graph isomorphism test. Standard message-passing neural networks (MPNNs), which aggregate features from immediate neighbors, are known to be bounded by the 1-WL color-refinement test.

This boundary dictates exactly what standard GNNs can and cannot learn. Giuseppe Alessio D'Inverno et al. established that GNNs serve as universal approximators for node classification and regression tasks, provided the target function respects the structural equivalences captured by the 1-WL test. If two nodes have identical 1-WL computational trees, the network must treat them identically.

To approximate functions that depend on finer structural nuances—such as counting cliques or cycles, which 1-WL cannot distinguish—we must build more expressive architectures that mimic higher-order WL tests:

  • Folklore GNNs ($k$-FGNN): Waiss Azizian et al. proved that $k$-FGNNs operate on higher-order tensors to match the separating power of the $(k+1)$-WL test, making them universal for any function bounded by that test.
  • Ring-GNN: To push past standard message-passing limits without the prohibitive cost of high-order tensors, Zhengdao Chen et al. proposed an architecture that utilizes matrix multiplication. This allows the model to achieve higher expressive power while maintaining a manageable $O(n^3)$ computational complexity.

Generalizing Universality Across Domains

The theoretical guarantee of invariant universality is not restricted to static, simple graphs; it extends across network depths, dynamic topologies, and continuous optimization problems.

Minimal Depth Requirements

How deep must a network be to achieve universality? Nicolas Keriven provided a foundational baseline, proving that neural networks designed for graph data can achieve universal approximation for both invariant and equivariant functions using only a single hidden layer, provided the hidden dimension (width) can grow arbitrarily large.

Dynamic and Edge-Attributed Topologies

Real-world graphs are rarely static matrices; they contain rich features on their edges and evolve over time. Silvia Beddar-Wiesing et al. extended the 1-WL framework to edge-attributed and dynamic graphs. The authors demonstrated that as long as a target function respects structural equivalence across time steps, a generalized GNN can act as a universal approximator for these evolving systems without depending on specific node indexing.

Continuous Mathematical Optimization

Can GNNs learn to output the exact solutions to complex mathematical optimization problems? Ziang Chen et al. explored this by mapping convex quadratic programs (QPs) to graph structures. They proved that if the graph representation of a problem instance is unique under the WL test, a sufficiently large GNN can universally approximate its optimal solution and feasibility boundaries. This provides a rigorous theoretical explanation for why GNNs are highly effective at accelerating classical optimization solvers.

  ┌──────────────────────────┐      ┌──────────────────────────┐
  │   Continuous Domain      │      │     Discrete Domain      │
  │  Quadratic Program (QP)  │      │ Graph Representation (G) │
  │  Minimization Function   │ ───> │ Unique under WL Test     │
  └──────────────────────────┘      └────────────┬─────────────┘
                                                 │
                                                 ▼
                                    ┌──────────────────────────┐
                                    │  Universal GNN Mapping   │
                                    │ Approximates Optimal Sol │
                                    └──────────────────────────┘

Architectural Mechanisms for Achieving Universality

While high-order tensors ($k$-FGNNs) offer theoretical universality, they are often too computationally expensive for practical use. Researchers have discovered clever architectural modifications that inject universality into simpler, more efficient models.

Global Hubs and Virtual Nodes

Graph Transformers use global self-attention to achieve high expressivity, but they scale quadratically with the number of nodes. Chen Cai et al. analyzed a much simpler heuristic: the Virtual Node (VN), a global hub connected to every node in the graph.

The authors proved that an MPNN equipped with a virtual node can exactly simulate universal set-processing architectures (like DeepSets or Set Transformers). By passing messages through this central hub, the network can compute global aggregations that allow it to approximate any permutation-equivariant map, making it functionally equivalent to full self-attention given sufficient capacity.

Handling Spectral Symmetries

When performing spectral graph learning, models ingest the eigenvalues and eigenvectors of the graph Laplacian. However, eigenvectors possess inherent symmetries: flipping the sign of an eigenvector ($\pm v$) or rotating a basis within a multi-dimensional eigenspace does not change the underlying structural operator.

Standard networks get confused by these arbitrary sign and basis choices. To solve this, Derek Lim et al. designed SignNet and BasisNet. They mathematically proved that these architectures are universal approximators for functions exhibiting sign and basis invariance, providing a principled foundation for spectral graph representation learning.

Application to Social Choice and Voting

Framing non-graph problems as graphs can unlock universal approximation in entirely different fields. For example, in voting theory, an anonymous voting rule must output a collective decision based on a set of voter preferences, treating all voters equally (permutation invariance).

Cem Anil et al. represented a set of voter ballots as nodes in a fully-connected graph. Because GNNs on fully-connected structures act as universal approximators for permutation-invariant functions, the authors demonstrated that these models can perfectly mimic any classical voting rule and even discover novel, computationally hard rules that maximize overall social welfare.

Key Foundational Work

On the equivalence between graph isomorphism testing and function approximation with GNNs (2019) — contributed 2 concept elements to this direction.
Expressive Power of Invariant and Equivariant Graph Neural Networks (2021) — contributed 2 concept elements to this direction.
Learning to Elect (2021) — contributed 2 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_invariant_function_approximation_b13e9822,
  title = {invariant function approximation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/invariant-function-approximation/rdr_b13e9822193d480c91ebfbf59eb87b96},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_invariant_function_approximation_b13e9822_v1,
  title = {invariant function approximation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/invariant-function-approximation/rdr_b13e9822193d480c91ebfbf59eb87b96/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake