A Logic for Reasoning About Aggregate-Combine Graph Neural Networks

arXiv:2405.00205v1 Announce Type: cross
Abstract: We propose a modal logic in which counting modalities appear in linear inequalities. We show that each formula can be transformed into an equivalent graph neural network (GNN). We also show that a broad class of GNNs can be transformed efficiently into a formula, thus significantly improving upon the literature about the logical expressiveness of GNNs. We also show that the satisfiability problem is PSPACE-complete. These results bring together the promise of using standard logical …

abstract arxiv class cs.ai cs.lg cs.lo gnn gnns graph graph neural network graph neural networks linear logic modal network networks neural network neural networks reasoning show type