GNN as Functor

Read a graph as a functor and its dynamics as a natural transformation, and a graph-neural-network layer becomes a morphism between such functors.

Fix a small category whose objects and arrows encode a graph’s incidence, meaning the nodes, the edges, and the maps attaching an edge to its endpoints. A feature-decorated graph is then a functor , assigning a feature to every node and edge; a time step or diffusion of those features is a natural transformation , natural precisely because it must commute with incidence. A graph neural network (GNN) layer is a map of such functors, one rule sending a decoration to the next, applied uniformly across the graph’s local shape.

The atom of a layer is an aggregator, a vector-multiset → vector map that collapses the unordered, repetition-carrying collection of neighbour features into one vector, followed by a node update. To separate non-isomorphic neighbourhoods the aggregator must be injective on multisets; GIN achieves this by relabelling each neighbour tuple and taking a plain vector sum , since a sum over sufficiently generic embeddings is injective. A different route defines convolution by counting graph homomorphisms from small pattern graphs. How many triangles or paths land at a node becomes a feature, tying expressivity to the chosen pattern family. Higher-order structure widens the domain. A hyperedge is an ordered subset of nodes, so a message is a map out of tuples rather than pairs, one aggregator per arity. Pushed to genuine 3-D structure, the -body terms want a higher operad rather than a graph.

Two demands pull against each other. Discriminability wants distinct neighbourhoods sent to distinct vectors, that is injective aggregation up to the Weisfeiler–Leman ceiling. Proximity wants adjacent or similar nodes sent to nearby vectors, the smoothing that aids generalisation. Pushing proximity too far is oversmoothing. Stacking layers repeatedly averages features until every node collapses toward the graph mean, the fixed point of over-averaging, so depth trades identity for reach.

Remark. Naturality is weight sharing

That a layer is a map of functors rather than an arbitrary function is exactly the inductive bias of a GNN. The same update acts at every node and commutes with the incidence maps, so a permutation of the graph acts on inputs and outputs alike. Equivariance is naturality; the learnable content lives only in the multiset aggregator and the node update, shared across the whole graph.

References

• K. Xu, W. Hu, J. Leskovec, S. Jegelka, How Powerful are Graph Neural Networks? (ICLR 2019)