Exploring the Expressiveness of Graph Neural Networks With Generic Rigidity Prediction

Abstract

Consider a graph, G = (V, E), with vertices V and edges E. A graph, G, is generically rigid if all continuous deformations on generic realizations of G preserve the distance between any two points, whether they are adjacent or not. While the case of graphs embedded in R 2 is well-established and solvable in polynomial time, no such algorithm exists for determining generic rigidity in R 3 . Graph neural networks (GNNs) are a class of deep learning designed to operate on graphs and extract structural information with message passing. Therefore, we develop a synthetic dataset of fixed-size graphs and train GNNs to predict generic rigidity for both 2D and 3D data. We find that GNNs significantly outperform non-neural baselines and are strong predictors of generic rigidity for most classes of graphs where rigidity can be determined within a node’s immediate local neighborhood; however, GNN performance begins to drop as the graph’s complexity increases (both in number of nodes and dimension). Though our models fail to predict generic rigidity perfectly, our experiments compare the expressive power of three di↵erent popular GNN architectures, highlight types of graphs that are challenging to predict, and propose areas of particular interest for future work. The ramifications of our work extend to several fields, including civil engineering, chemistry, and biology. Our code is available at https://github.com/sahiljain01/thesis.