Universal Function Approximation on Graphs using Multivalued Functions

Rickard Brüel Gabrielsson

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.

Introduction: The Expressivity Gap in GNNs

Graph Neural Networks (GNNs) have become the standard tool for modeling structured data, from drug discovery to social network analysis. However, they face a fundamental "glass ceiling": their expressivity is limited by the 1-Weisfeiler-Lehman (WL) isomorphism test. This limitation means that standard GNNs cannot distinguish between many pairs of non-isomorphic graphs, mapping them to identical internal representations. Consequently, they can never learn to assign different labels to these distinct structures.

To achieve universal function approximation—the ability to learn any possible function on a graph—a model must first be able to distinguish between any two non-isomorphic graphs. While creating a perfectly injective representation (a unique code for every unique graph) would solve this, it is computationally equivalent to the graph isomorphism problem, which lacks an efficient general-purpose algorithm. This research introduces the Node Parsing Algorithm (NPA), a framework that breaks through this ceiling by utilizing the theory of multivalued functions.

Theoretical Foundation: Iso-Injective Multivalued Functions

The core innovation of this framework is the shift from searching for a single, perfect injective function to using "iso-injective" multivalued functions. Instead of mapping a graph to a single point, the model maps it to a set of values.

The theoretical relationship between injective functions on isomorphism classes and iso-injective functions on graphs.

As shown in the commutative diagram above, the framework establishes that if a representation is iso-injective, a neural network can approximate any continuous function on graph isomorphism classes. This theoretical shift allows the model to maintain high expressivity while remaining computationally tractable.

The Node Parsing Algorithm (NPA)

The NPA adopts a local-to-global approach, building graph representations by adding one edge at a time. This process is inspired by 0-dimensional persistent homology, capturing how graph components merge and evolve.

Key Innovations:

  • Disjoint Subgraph Processing: Unlike standard GNNs that aggregate overlapping neighborhoods, NPA keeps its processed subgraphs disjoint. This ensures that node identities remain unique within each subgraph, a prerequisite for high expressivity.
  • Neural Implementation: The algorithm is implemented using standard neural components like LSTMs and tree-LSTMs. The paper proves that these architectures can approximate the necessary injective functions for both bounded and unbounded graph domains.
  • Subgraph Dropout: Because a graph's edges can be processed in $m!$ possible orderings, the authors employ a "dropout" technique during training—using a single random ordering per run—and average over multiple orderings at test time to ensure stability.
Comparison of graph processing: The original graph (left) is processed by NPA into a disjoint tree structure (middle), whereas standard GNNs use overlapping message-passing trellises (right).

Empirical Performance and Benchmarking

The framework was evaluated on both real-world and synthetic benchmarks, demonstrating superior expressivity and accuracy.

  • Real-World Datasets: NPA achieved state-of-the-art results on datasets like NCI1, reaching 84.0% accuracy, compared to 82.7% for standard GNNs. It also showed strong performance on MUTAG, PROTEINS, and PTC.
  • Synthetic "Hard" Cases: On the GNN-Hard dataset—which requires distinguishing between two disconnected cycles and one large cycle—NPA achieved 100% accuracy. Traditional message-passing models typically fail this test, performing no better than a coin flip (50%).
  • Efficiency: Despite its high theoretical expressivity, the algorithm maintains a complexity of $O(\#edges \times \#nodes)$, making it practical for large-scale applications.

Conclusion and Future Directions

By ensuring unique node identification within subgraphs, NPA distinguishes structures that are "invisible" to the neighborhood-aggregation schemes of traditional GNNs. While the method still faces challenges with highly regular graphs (like honeycomb lattices) and the computational redundancy of edge ordering, it represents a significant step toward universal graph learning. Future work may involve hybrid models that combine the iso-injective properties of NPA with the invariant properties of traditional GNNs to maximize both efficiency and expressivity.

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 using Multivalued Functions}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=vUxzUtsrna},
}
Figure