Review for NeurIPS paper: Distance Encoding: Design Provably More Powerful Neural Networks for Graph Representation Learning

Summary and Contributions: [edit: see "additional feedback" section for response to author rebuttal] This paper considers the problem of learning representations of specific subgraphs of a larger graph, in such a way that subgraphs of non-isomorphic graphs should be assigned different representations. Specifically, they note that most GNNs can only distinguish things that the 1-WL test can distinguish, and propose a new method of computing graph features (called "distance encoding") to get around this restriction. The distance encoding the authors propose appears to work as follows. Suppose we want to compute a representation of a subgraph S of a graph G. Instead of running a GNN on G and then pooling across the subgraph, the subgraph S is used to modify the features of all of the nodes in G, in particular based on the distances between those nodes in G and the nodes in S (this is DEGNN). Optionally, the subgraph is also used to modify the edge structure by, conceptually, adding additional edges and/or edge features based on pairwise distances in G (this is DEAGNN).