How many layers are needed in a graph network before each node (indirectly) uses information from all nodes in a graph? Let's say we have a graph G. How many layers are needed, in order for all each node to indirectly use information from all the nodes in the graph?
 A: You need to stack a number of GNN layers equal to the network diameter. [1].
[1]: https://stackoverflow.com/questions/3174569/what-is-meant-by-diameter-of-a-network
Addition after Fato39 comment:
In the Neural Message Passing framework, each node in a GNN layer makes use of the info coming from its direct neighbors.
When you stack $2$ GNN layers, it means that the $2^{nd}$ layer takes as input the info resulting from the $1^{st}$ GNN layer, thus using the info coming from the neighbors of neighbors (so called $2$-hop neighborhood, the set of nodes having shortest path from the source node equal to $2$).
This means that if you stack $N$ GNN layers, each node will make use of the info coming from the $N$-hop neighborhood (all nodes having shortest path from the source node equal to $N$).
The diameter $d$ is defined as the maximum shortest path between a pair of nodes in the network (it means that each node in the network has at most a $d$-hop neighborhood).
If you stack $d$ GNN layers then you are sure that each node is considering all nodes in a $d$-hop neighborhood that, by definition of diameter, it means all nodes in the network.
A: Spatial neural nets typically use information from the first degree neighbours of the node. That means, you need $D-1$ layers ($D$ is the diameter) to be able to get information from every node. But, spectral networks are different. It uses graph laplacian and all the information is there. So, one layer can connect all the nodes. However, typical implementations of spectral layers include approximations to the laplacian. One type of approximation is achieved by Chebyshev polynomials (Deferrard's paper), where the maximum degree, which is equivalent to the receptive field range is a hyper-parameter. For example, if you choose it as $M$, then you need $\approx D/M$ layers to reach the farthest nodes.
