Discriminative structural graph classification
This work addresses a domain-specific problem in graph neural networks, focusing on improving discriminative representations for graph classification, with incremental contributions.
The paper tackles the discrimination capacity of aggregation functions in graph neural networks, showing that sum and a novel histogram-based function can discriminate between any fixed number of adversarial inputs, and designs a network that yields benefits for structural graph classification.
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.