NeurIPS 2019
Sun Dec 8th through Sat the 14th, 2019 at Vancouver Convention Center
Paper ID:9347
Title:On the equivalence between graph isomorphism testing and function approximation with GNNs

This paper leverages the graph isomorphism problem to study the expressive power of GNNs. In addition, a measure of expressiveness is formalized using sigma-algebras and the authors propose a novel variant of GNN, RING-GNN, that is evaluated in an experimental study where it shows competitive results. The reviewers agree that this is a nice contribution, the theoretical results are interesting (though somehow expected) and that the proposed extension of G-invariant networks is relevant. However, all reviewers agree that the experimental comparison with RING-GNN-SVD is unfair and MUST BE REMOVED in a published version of the paper (that is removing the last line from table 1). One of the reviewer also note that a comparison with LanczosNet should be included (though the lack of comparison is not ground for rejection).