Graph Neural Networks (GNNs) have been successfully used in many problemsinvolving graph-structured data, achieving state-of-the-art performance. GNNstypically employ a message-passing scheme, in which every node aggregatesinformation from its neighbors using a permutation-invariant aggregationfunction. Standard well-examined choices such as the mean or sum aggregationfunctions have limited capabilities, as they are not able to captureinteractions among neighbors. In this work, we formalize these interactionsusing an information-theoretic framework that notably includes synergisticinformation. Driven by this definition, we introduce the Graph OrderingAttention (GOAT) layer, a novel GNN component that captures interactionsbetween nodes in a neighborhood. This is achieved by learning local nodeorderings via an attention mechanism and processing the ordered representationsusing a recurrent neural network aggregator. This design allows us to make useof a permutation-sensitive aggregator while maintaining thepermutation-equivariance of the proposed GOAT layer. The GOAT modeldemonstrates its increased performance in modeling graph metrics that capturecomplex information, such as the betweenness centrality and the effective sizeof a node. In practical use-cases, its superior modeling capability isconfirmed through its success in several real-world node classificationbenchmarks.