Monday Theory: Structural vs Positional Node Representations

In the new slide deck, Bruno Ribeiro (Purdue University) uncovers the nature of two commonly used mechanisms for building node representations. Structural representations are permutation insensitive (like GNNs) whereas positional representations are permutation sensitive (like SVD vectors). Hence, all GRL approaches can be broadly classified into those two families. Takeaway messages:

Message 1: Positional representations of k nodes are to most expressive k-node structural representations as samples of a distribution are to sufficient statistics of the distribution. This is based on the results published in the ICLR'20 paper

Message 2: As soon as you introduce some sort of node IDs you break equivariance but at the same time can predict properties of any subset of nodes (better link prediction). You’d better aggregate over multiple samples though (from the stats analogy). If you stick to equivariance, you can predict node or graph-level properties but nothing in-between.