k-hop Graph Neural Networks
  Graph neural networks (GNNs) have emerged recently as a powerful architecture
for learning node and graph representations. Standard GNNs have the same
expressive power as the Weisfeiler-Leman test of graph isomorphism in terms of
distinguishing non-isomorphic graphs. However, it was recently shown that this
test cannot identify fundamental graph properties such as connectivity and
triangle freeness. We show that GNNs also suffer from the same limitation. To
address this limitation, we propose a more expressive architecture, k-hop GNNs,
which updates a node's representation by aggregating information not only from
its direct neighbors, but from its k-hop neighborhood. We show that the
proposed architecture can identify fundamental graph properties. We evaluate
the proposed architecture on standard node classification and graph
classification datasets. Our experimental evaluation confirms our theoretical
findings since the proposed model achieves performance better or comparable to
standard GNNs and to state-of-the-art algorithms.
