Global Minima, Recoverability Thresholds, and Higher-Order Structure in
  GNNS
Drake Brown Trevor Garrity Kaden Parker Jason Oliphant Stone Carson Cole Hanson Zachary Boyd
We analyze the performance of graph neural network (GNN) architectures from
the perspective of random graph theory. Our approach promises to complement
existing lenses on GNN analysis, such as combinatorial expressive power and
worst-case adversarial analysis, by connecting the performance of GNNs to
typical-case properties of the training data. First, we theoretically
characterize the nodewise accuracy of one- and two-layer GCNs relative to the
contextual stochastic block model (cSBM) and related models. We additionally
prove that GCNs cannot beat linear models under certain circumstances. Second,
we numerically map the recoverability thresholds, in terms of accuracy, of four
diverse GNN architectures (GCN, GAT, SAGE, and Graph Transformer) under a
variety of assumptions about the data. Sample results of this second analysis
include: heavy-tailed degree distributions enhance GNN performance, GNNs can
work well on strongly heterophilous graphs, and SAGE and Graph Transformer can
perform well on arbitrarily noisy edge data, but no architecture handled
sufficiently noisy feature data well. Finally, we show how both specific
higher-order structures in synthetic data and the mix of empirical structures
in real data have dramatic effects (usually negative) on GNN performance.