Universal Function Approximation on Graphs

Rickard Brüel Gabrielsson

Graph learning typically involves mapping graph structures to vector representations. However, most popular frameworks, such as standard Graph Neural Networks (GNNs), are fundamentally limited in their "discriminative power." They often cannot distinguish between certain non-isomorphic graphs, a limitation mathematically equivalent to the 1-Weisfeiler-Lehman (1-WL) test.

To achieve true Universal Function Approximation, a model must be able to represent any function on graph isomorphism classes. This requires an injective mapping—where different graphs always result in different vectors. Unfortunately, finding a single canonical injective function is computationally prohibitive because the graph isomorphism problem itself is notoriously hard.

In this work, the authors introduce a theoretical framework and a novel algorithm, the Node Parsing Algorithm (NPA), to tackle this challenge. By leveraging "iso-injective" multivalued functions and hierarchical message passing, NPA achieves state-of-the-art performance on standard benchmarks and solves complex graph classification tasks that traditional GNNs cannot.

The Node Parsing Algorithm (NPA)

The authors propose NPA as a departure from the standard neighborhood aggregation used in traditional GNNs. The approach is built on four core pillars:

  1. Iso-Injectivity: Instead of searching for a single, difficult-to-construct injective function, the authors prove that "iso-injective" functions—functions on graphs that are injective with respect to isomorphism classes—are sufficient for universal approximation.
Diagram showing the relationship between injective functions on isomorphism classes and iso-injective functions on graphs.
  1. Hierarchical Parsing: NPA operates as a local-to-global recursive algorithm. It processes a graph by adding one edge at a time, merging disjoint subgraphs into progressively larger ones. This process is heavily inspired by 0-dimensional persistent homology and dependency parsing in Natural Language Processing (NLP).
  2. Neural Implementation: To make this hierarchical process learnable, the algorithm utilizes Tree-LSTMs to encode the merging of subgraphs and standard LSTMs to update node features.
  3. Subgraph Dropout: Because the order in which edges are "parsed" affects the final representation, the authors introduce a technique called subgraph dropout. During training, the model randomly samples edge orderings. This prevents the network from over-relying on a specific sequence and significantly improves generalization.

Key Insights: Moving Beyond 1-WL

The most significant breakthrough of this framework is its ability to distinguish graphs that neighborhood-based GNNs find identical. By treating the graph representation as a set of possible encodings (based on different edge orderings), the authors bypass the need for a single, perfect canonical form.

Structurally, this represents a major shift. While standard GNNs pass messages across a fixed, grid-like neighborhood, NPA builds a dynamic, tree-like structure of dependencies.

Comparison of message passing: Node Parsing (hierarchical/tree-like) vs. GNN (neighborhood-based).

Empirical Performance

The framework was evaluated on both real-world benchmarks (NCI1, MUTAG, PROTEINS, and PTC) and synthetic "hard" datasets designed specifically to test the limits of discriminative power (such as distinguishing two small cycles from one large cycle).

  • Breaking GNN Limits: On the synthetic GNN-Hard dataset, standard GNNs (like GIN) achieved only 50% accuracy—no better than random guessing. In contrast, NPA achieved a perfect 100% accuracy.
  • State-of-the-Art (SOTA): NPA achieved SOTA or near-SOTA results on all four real-world datasets. Notably, it reached 84.0% accuracy on NCI1 and 93.3% on MUTAG, outperforming established models like PatchySan and DGCNN.
  • Computational Efficiency: Despite its theoretical power, the algorithm maintains a practical runtime complexity of $O(\#edges \times \#nodes)$, making it applicable to real-world problems.

Limitations and Future Work

While the complexity is polynomial, the $O(E \times V)$ requirement may still be slower than simple GNNs for extremely large, dense graphs. Additionally, the authors acknowledge that their framework shares some weaknesses with GNNs when dealing with certain highly regular graphs (e.g., Random-Regular graphs where all nodes have the same degree), suggesting that further refinements in handling "class-redundancy" are needed.

A promising future direction is the development of hybrid models: combining the powerful "iso-injective" properties of NPA with the highly efficient invariant encodings of standard GNNs to achieve the best of both worlds.

Summary updated

Abstract

In this work we produce a framework for constructing universal function approximators on graph isomorphism classes. We prove how this framework comes with a collection of theoretically desirable properties and enables novel analysis. We show how this allows us to achieve state-of-the-art performance on four different well-known datasets in graph classification and separate classes of graphs that other graph-learning methods cannot. Our approach is inspired by persistent homology, dependency parsing for NLP, and multivalued functions. The complexity of the underlying algorithm is O(#edges x #nodes) and code is publicly available (https://github.com/bruel-gabrielsson/universal-function-approximation-on-graphs).
BibTeX
@inproceedings{gabrielsson2020universal,
  author = {Rickard Brüel Gabrielsson},
  title = {{Universal Function Approximation on Graphs}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=vUxzUtsrna},
}
Figure