Are there neural networks that accept graphs or trees as inputs?

Question

As far I know, the RNN accepts a sequence as input and can produce as a sequence as output.

Are there neural networks that accept graphs or trees as inputs, so that to represent the relationships between the nodes of the graph or tree?

Answer 1

Yes, there are numerous, coming under the umbrella term Graph Neural Networks (GNN).

The most common input structures accepted by these techniques are the adjacency matrix of the graph (optionally accompanied by its node feature matrix and/or edge feature matrix, if the graph has such information).

A Comprehensive Survey on Graph Neural Networks, Wu et al (2019) divides GNN's into four subgroups:

• Recurrent graph neural networks (RecGNN)
• Convolutional graph neural networks (ConvGNN)
• Graph autoencoders (GAE)
• Spatial-temporal graph neural networks (STGNN)

ConvGNN's can themselves be classified by whether they use Spectral methods or Spatial methods, and GAE's by whether they are designed for Network embedding or Graph generation.

Answer 2

There are types of neural networks designed exactly for that purpose. For example, graph convolutional networks (GCN) by Thomas N. Kipf. The input to the network will be a matrix of size $N \times F$, where $N$ is the number of nodes and $F$ the number of features (for each node). You then can multiply the feature matrix with the adjacency matrix (each node is going to be a weighted sum of its first-degree neighbors). There are a lot of other variations, such as diffusion convolutional networks, gated graph neural networks, etc. There is a nice survey that describes most of the recent related work in the field Graph Neural Networks: A review of methods and applications by Jie Zhou et al.