On the Ability of Graph Neural Networks to Model Interactions Between Vertices

Understand

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.