Universal Function Approximation on Graphs
This provides a foundational framework for graph learning with broad applicability in domains like chemistry and social networks, though it builds on existing ideas like persistent homology.
The paper tackles the problem of universal function approximation on graph isomorphism classes, achieving state-of-the-art performance on four graph classification datasets and separating graph classes that other methods cannot.
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).