Convergent Graph Solvers

Abstract

We propose the convergent graph solver (CGS), a deep learning method that learns iterative mappings to predict the properties of a graph system at its stationary state (fixed point) with guaranteed convergence. CGS systematically computes the fixed points of a target graph system and decodes them to estimate the stationary properties of the system without the prior knowledge of existing solvers or intermediate solutions. The forward propagation of CGS proceeds in three steps: (1) constructing the input dependent linear contracting iterative maps, (2) computing the fixed-points of the linear maps, and (3) decoding the fixed-points to estimate the properties. The contractivity of the constructed linear maps guarantees the existence and uniqueness of the fixed points following the Banach fixed point theorem. To train CGS efficiently, we also derive a tractable analytical expression for its gradient by leveraging the implicit function theorem. We evaluate the performance of CGS by applying it to various network-analytic and graph benchmark problems. The results indicate that CGS has competitive capabilities for predicting the stationary properties of graph systems, irrespective of whether the target systems are linear or non-linear. CGS also shows high performance for graph classification problems where the existence or the meaning of a fixed point is hard to be clearly defined, which highlights the potential of CGS as a general graph neural network architecture.

24 pages, 8 figures

References in corpus (8)

• PyTorch: An Imperative Style, High-Performance Deep Learning Library
• Searching for Activation Functions
• Deep Equilibrium Models
• On Differentiating Parameterized Argmin and Argmax Problems with Application to Bi-level Optimization
• GraphNorm: A Principled Approach to Accelerating Graph Neural Network Training
• Physics-informed Autoencoders for Lyapunov-stable Fluid Flow Prediction
• Implicit Graph Neural Networks
• Graph neural induction of value iteration