Post #64

Understanding the Representation Power of Graph Neural Networks in Learning Graph Topology This is NeurIPS 2019 work by the group of Albert-László Barabási, — the one who invented a famous Barabási–Albert graph model. In this work, they study if GNN can compute the function that approximates graph moments, i.e. powers of adjacency matrix. The key result is that if GNN has number of layers more than the power of the matrix then it can learn a corresponding graph moment. For those who followed previous post, which describes a paper What graph neural networks cannot learn: depth vs width by Loukas,will see that Barabási's paper is a precursor and a partial result of Loukas' paper that states the condition on GNN for computability of any function (not just graph moments).