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

Understand

Learning representations of sets of nodes in a graph is crucial for applications ranging from node-role discovery to link prediction and molecule classification.

• Graph Neural Networks (GNNs) have achieved great success in graph representation learning.
• However, expressive power of GNNs is limited by the 1-Weisfeiler-Lehman (WL) test and thus GNNs generate identical representations for graph substructures that may in fact be very different.
• More powerful GNNs, proposed recently by mimicking higher-order-WL tests, only focus on representing entire graphs and they are computationally inefficient as they cannot utilize sparsity of the underlying graph.