- tags
- Neural networks, Graphs
Basic properties
To operate on graphs, a neural network must be invariant to isomorphism of these graphs. This translates to permutation invariance for the nodes of a graph.
\[ f(\mathbf{PX}) = f(\mathbf{X}) \]
Where \(\mathbf{P}\) is a permutation matrix. For simple sets, this amounts to performing node-wise transformations and use a permutation invariant aggregator (sum/max/avg/…). This was done in (Zaheer et al. 2018).
\[ f(\mathbf{X}) = \phi\left( \bigoplus_i \psi(\mathbf{x}_i) \right) \]
In the case of GNNs, the local neighborhood of a node can also be defined, and therefore the neural network can be written:
\[ f(\mathbf{X}, \mathbf{A}) = \begin{bmatrix} — g(\mathbf{x}_1 , \mathbf{X}_{\mathcal{N}_1} ) — \newline — g(\mathbf{x}_2 , \mathbf{X}_{\mathcal{N}_2} ) — \newline \vdots\newline — g(\mathbf{x}_n , \mathbf{X}_{\mathcal{N}_n} ) — \end{bmatrix} \]
where \(\mathbf{A}\) is the adjacency matrix of the graph. The function \(g\) also need to be permutation invariant to ensure the permutation invariance of \(f\).
The various ways of defining \(g\) give rise to three main flavours of GNNs:
Bibliography
- Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Ruslan Salakhutdinov, Alexander Smola. . "Deep Sets". Arxiv:1703.06114 [cs, Stat]. http://arxiv.org/abs/1703.06114.