Graph Convolutional Neural Networks as Parametric CoKleisli morphisms
This work provides a theoretical foundation for GCNNs using category theory, which could aid in understanding and generalizing graph neural networks, though it is incremental in applying existing categorical frameworks to a specific domain.
The paper tackles the problem of providing a categorical characterization of Graph Convolutional Neural Networks (GCNNs) by defining them as parametric CoKleisli morphisms, showing they can be factored through existing categorical constructions like Para and Lens, and proving an injective-on-objects, faithful 2-functor exists. This allows treating the adjacency matrix as a global parameter, offering a high-level characterization of GCNNs' inductive bias.
We define the bicategory of Graph Convolutional Neural Networks $\mathbf{GCNN}_n$ for an arbitrary graph with $n$ nodes. We show it can be factored through the already existing categorical constructions for deep learning called $\mathbf{Para}$ and $\mathbf{Lens}$ with the base category set to the CoKleisli category of the product comonad. We prove that there exists an injective-on-objects, faithful 2-functor $\mathbf{GCNN}_n \to \mathbf{Para}(\mathsf{CoKl}(\mathbb{R}^{n \times n} \times -))$. We show that this construction allows us to treat the adjacency matrix of a GCNN as a global parameter instead of a a local, layer-wise one. This gives us a high-level categorical characterisation of a particular kind of inductive bias GCNNs possess. Lastly, we hypothesize about possible generalisations of GCNNs to general message-passing graph neural networks, connections to equivariant learning, and the (lack of) functoriality of activation functions.