Reproduce “Universality and Approximation Rates of Graph Neural Networks with Random Features” on OpenResearch

About this paper

Lukas Gonon, Thilo Meyer-Brandis, Niklas Weber

This research provides a universality theorem for Permutation-Equivariant Neural Networks (PENNs) augmented with random node features, demonstrating their ability to approximate any measurable permutation-equivariant or invariant function on directed graphs. It also establishes approximation rates for sufficiently regular functions, quantifying the architectural complexity required to achieve specific accuracy levels.

Key insights

• PENNs, a general and practical GNN architecture, can approximate any measurable permutation-equivariant or invariant function if augmented with random node features that reliably provide unique node identifiers.
• For sufficiently regular (k-times continuously differentiable) functions, the depth of the approximating PENN's internal feedforward networks grows logarithmically with approximation error, while the number of non-zero weights grows polynomially.
• By averaging PENN outputs over multiple random feature samplings, the model can maintain permutation equivariance in expectation without sacrificing its universal approximation capabilities.

Summary by alphaXiv.