Sam Adam-Day

Graph neural networks (GNNs) are de facto standard deep learning architectures for machine learning on graphs. This has led to a large body of work analyzing the capabilities and limitations of these models, particularly pertaining to their representation and extrapolation capacity. We offer a novel theoretical perspective on the representation and extrapolation capacity of GNNs, by answering the question: how do GNNs behave as the number of graph nodes become very large? Under mild assumptions, we show that when we draw graphs of increasing size from the Erdős-Rényi model, the probability that such graphs are mapped to a particular output by a class of GNN classifiers tends to either zero or to one. This class includes the popular graph convolutional network architecture. The result establishes ’zero-one laws’ for these GNNs, and analogously to other convergence laws, entails theoretical limitations on their capacity. We empirically verify our results, observing that the theoretical asymptotic limits are evident already on relatively small graphs.

An \(\mathbb R\)-tree is a certain kind of metric space tree in which every point can be branching. Favre and Jonsson posed the following problem in 2004: can the class of orders underlying \(\mathbb R\)-trees be characterised by the fact that every branch is order-isomorphic to a real interval? In the first part, I answer this question in the negative: there is a ’branchwise-real tree order’ which is not ‘continuously gradable’. In the second part, I show that a branchwise-real tree order is continuously gradable if and only if every well-stratified subtree is \(\mathbb R\)-gradable. This link with set theory is put to work in the third part answering refinements of the main question, yielding several independence results. For example, when \(κ≥\mathfrak c\), there is a branchwise-real tree order which is not continuously gradable, and which satisfies a property corresponding to \(κ\)-separability. Conversely, under Martin’s Axiom at \(κ\)such a tree does not exist.

We investigate a recently-devised polyhedral semantics for intermediate logics, in which formulas are interpreted in n-dimensional polyhedra. An intermediate logic is polyhedrally complete if it is complete with respect to some class of polyhedra. The first main result of this paper is a necessary and sufficient condition for the polyhedral-completeness of a logic. This condition, which we call the Nerve Criterion, is expressed in terms of Alexandrov’s notion of the nerve of a poset. It affords a purely combinatorial characterisation of polyhedrally-complete logics. Using the Nerve Criterion we show, easily, that there are continuum many intermediate logics that are not polyhedrally-complete but which have the finite model property. We also provide, at considerable combinatorial labour, a countably infinite class of logics axiomatised by the Jankov-Fine formulas of ’starlike trees’ all of which are polyhedrally-complete. The polyhedral completeness theorem for these ’starlike logics’ is the second main result of this paper.