  Graph Neural Networks (GNNs) have emerged as prominent models for
representation learning on graph structured data. GNNs follow an approach of
message passing analogous to 1-dimensional Weisfeiler Lehman (1-WL) test for
graph isomorphism and consequently are limited by the distinguishing power of
1-WL. More expressive higher-order GNNs which operate on k-tuples of nodes need
increased computational resources in order to process higher-order tensors.
Instead of the WL approach, in this work, we follow the classical approach of
Individualization and Refinement (IR), a technique followed by most practical
isomorphism solvers. Individualization refers to artificially distinguishing a
node in the graph and refinement is the propagation of this information to
other nodes through message passing. We learn to adaptively select nodes to
individualize and to aggregate the resulting graphs after refinement to help
handle the complexity. Our technique lets us learn richer node embeddings while
keeping the computational complexity manageable. Theoretically, we show that
our procedure is more expressive than the 1-WL test. Experiments show that our
method outperforms prominent 1-WL GNN models as well as competitive
higher-order baselines on several benchmark synthetic and real datasets.
Furthermore, our method opens new doors for exploring the paradigm of learning
on graph structures with individualization and refinement.
