The Identifiability of Vertex Signals on Graphs under Quadratic Readouts

A readout layer $R$ of a graph neural network is a permutation invariant map from vertex signals $X\in {\mathbb{R}}^{n\times d}$ to some fixed vector space agnostic to the size $n$ of the graph. We measure how a readout $R$ can fail to locally distinguish a signal $X$ in ${\mathbb{R}}^{n\times d}$ using the dimension $\delta$ of the fibre $R^{-1}(R(X))\subset {\mathbb{R}}^{n\times d}$. In this study, we consider a quadratic readout of the form $R(X)=(1^{T}X,X^{T}X,X^{T}MX)$, where $M$ is the adjacency or Laplacian matrix of the graph. We show that if the signal channel dimension $d$ is sufficiently large relative to the size of the graph ($d\ge n$), and the spectrum of $M$ is simple, we can achieve perfect local identifiability $\delta =0$ for generic (full rank) vertex signals. In contrast, the commonly used sum readout $1^{T}X$ or a graph agnostic $(1^{T}X,X^{T}X)$ quadratic readout has fibre dimension $\delta$ that is non-decreasing with $d$. These observations inform the design of graph neural network architectures, as they demonstrate how information loss in the readout layers can be potentially mitigated with careful consideration of the nonlinearity of the readout, the number of vertex signal channels $d$, and how it relates to the size of the graph $n$.