​​Monday Theory: Logical Expressiveness of Hypergraph GNNs

A prominent spotlight ICLR'20 paper by Barcelo et al proved several important expressiveness boundaries for message passing GNNs on graphs with normal binary edges, ie, an edge connects two nodes. Using a well-known mapping of classifying First Order Logic formulae to the WL-test, the authors show that Aggregate-Combine GNNs are bounded by ALCQ - a common Description Logic fragment of FOL. And Aggregate-Combine-Readout (GNNs with global pooling) are bounded by FOC-2 subset for FOL, i.e., First Order Logic with counting quantifiers and at most 2 variables.

A new anonymous ICLR'22 submission extends this framework to hypergraphs, ie, the graphs where (hyper)edges are constructed from B > 2 nodes. This time, the authors resort to higher-order k-WL tests and find a natural connection between k-WL and expressiveness of hypergraph networks. Three cool contributions:

1. Hypergraphs with B-ary hyperedges are bounded by FOC-B subset of FOL. That is, a logical formula can have up to B variables now.
2. The framework includes several relational architetures such as Neural Logic Machines, Deep Sets, Transformers, and GNNs
3. The authors estimate theoretical bounds on min depth and arity of hypergraph architectures for common GRL tasks. For instance, identifying bipartiteness of n-nodes graph requires log(n) layers of 3-ary GNNs (or 2-WL kernels)

Experiments were conducted on rather toy graphs of 10-80 nodes which is explained by the need to train hypergraph nets on all possible permutations of nodes in hyperedges (and this at the moment has bad scaling properties). Still, most of the hypotheses are confirmed by the experiments, so check out the full paper if you're into logic+GNN studies!