  This paper focuses on the discrimination capacity of aggregation functions:
these are the permutation invariant functions used by graph neural networks to
combine the features of nodes. Realizing that the most powerful aggregation
functions suffer from a dimensionality curse, we consider a restricted setting.
In particular, we show that the standard sum and a novel histogram-based
function have the capacity to discriminate between any fixed number of inputs
chosen by an adversary. Based on our insights, we design a graph neural network
aiming, not to maximize discrimination capacity, but to learn discriminative
graph representations that generalize well. Our empirical evaluation provides
evidence that our choices can yield benefits to the problem of structural graph
classification.
