NeurIPS 2020

Can Graph Neural Networks Count Substructures?

Meta Review

There was consensus from the referees that this paper provides interesting theory while also shedding light on what graph neural networks might be learning. For that reason, the recommendation is to accept. That being said, there is one important point that remains unclear. There are a number of fast and easy algorithms that one could use to count substructures / graphlets / motifs, so why not just use these algorithms to produce node features? (For example, see “Efficiently Counting Vertex Orbits of All 5-vertex Subgraphs, by EVOKE” by Pashanasangi and Seshadhri and references therein for a large body of literature on the topic of counting subgraph patterns.) The author response addresses this concern in part by arguing that the GNNs could learn the right attributed subgraph patterns. That seems like much better motivation, and I would encourage emphasizing that point in the camera version. To augment this, the experiments on the “Real tasks” could include a pre-processing step, where subgraph participation counts are computed and then introduced as node features. If this substantially changes the performance, then there would be additional substantiation for the story in the paper.