  Graph neural networks (GNNs) are widely used for modeling complex
interactions between entities represented as vertices of a graph. Despite
recent efforts to theoretically analyze the expressive power of GNNs, a formal
characterization of their ability to model interactions is lacking. The current
paper aims to address this gap. Formalizing strength of interactions through an
established measure known as separation rank, we quantify the ability of
certain GNNs to model interaction between a given subset of vertices and its
complement, i.e. between the sides of a given partition of input vertices. Our
results reveal that the ability to model interaction is primarily determined by
the partition's walk index -- a graph-theoretical characteristic defined by the
number of walks originating from the boundary of the partition. Experiments
with common GNN architectures corroborate this finding. As a practical
application of our theory, we design an edge sparsification algorithm named
Walk Index Sparsification (WIS), which preserves the ability of a GNN to model
interactions when input edges are removed. WIS is simple, computationally
efficient, and in our experiments has markedly outperformed alternative methods
in terms of induced prediction accuracy. More broadly, it showcases the
potential of improving GNNs by theoretically analyzing the interactions they
can model.
