Research map / Graph learning / GNN architectures

Function graph transformers universally approximate operators between function spaces

NeurIPS 2026 · Graph learning › GNN architectures · approach: Expressive equivariant message passing · 0 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 that graph-preserving measure-theoretic transformers (function graph transformers), built from softmax self-attention and pointwise MLPs, universally approximate nonlinear operators between function spaces, including negative-order Sobolev inputs, via lifting functions to graph measures.

Problem

Theoretical understanding of transformers for operator learning is limited; existing universal approximation results for neural operators assume fixed function-space topology and do not track the passage from continuum functions to tokens and back, and discretization invariance is needed.

Approach

Represent a function by its graph measure supported on its graph, so finite tokenizations are empirical measures. Restrict measure-theoretic transformers to graph-preserving in-context maps (x-coordinate identity, y-coordinate depending only on x and the measure), then approximate these by standard softmax self-attention and MLP compositions in W1, with a regularization (Sobolev/mollifier) step to

Key results

• Theorem: for any epsilon, a sufficiently deep softmax transformer approximates a function graph transformer uniformly in W1 over all probability measures on the compact graph-measure domain.
• Universal approximation of operators A: H^{-s} to H^{-s'} holds as an iterated limit (tau, eta, epsilon, N, m) in H^{-s'}, covering discontinuous and distributional inputs.
• Operators between different domains are represented via product graph measures with cross-attention-like structure, with output query points independent of the learned representation.

Limitations

• Results are qualitative expressivity and convergence statements; no sharp rates or sample complexity bounds.
• Does not prove training convergence or efficiency of resulting architectures.
• Does not address softmax-free, linear, or position-only attention variants without additional analysis.

Experimental setup

Builds on: measure-theoretic transformers universal in-context approximation OFormer

Closest papers by meaning

• Generalizable Insights for Graph Transformers in Theory and Practice (NeurIPS 2025 · similarity 0.85)
• GrokFormer: Graph Fourier Kolmogorov-Arnold Transformers (ICML 2025 · similarity 0.85)
• Learning Theory of Transformers: Local-to-Global Approximation via Softmax Partition of Unity (NeurIPS 2026 · similarity 0.85)
• From Theory to Practice: Rethinking Green and Martin Kernels for Unleashing Graph Transformers (ICML 2025 · similarity 0.85)
• In-context Learning on Function Classes Unveiled for Transformers (ICML 2024 · similarity 0.84)
• Towards Principled Graph Transformers (NeurIPS 2024 · similarity 0.84)