Discriminative structural graph classification

Younjoo Seo, Andreas Loukas, Nathanaël PerraudinarXiv 2019 · arXiv

Abstract

This paper challenges the prevailing "more is better" philosophy in Graph Neural Network (GNN) design, which often seeks perfect discrimination (injectivity) to match the Weisfeiler-Lehman (WL) isomorphism test. The authors prove that such a quest leads to a curse of dimensionality and poor generalization. Instead, they propose a novel GNN architecture using projective histograms and random node sampling to achieve "bounded discrimination," resulting in a model that generalizes significantly better for structural graph classification tasks.

The Challenge of Perfect Discrimination

In structural graph classification, models must categorize graphs based solely on topology without relying on pre-existing node or edge labels. To achieve high performance, researchers have traditionally focused on creating injective aggregation functions—functions that map different sets of node features to unique representations.

However, the authors argue that maximum discrimination is a double-edged sword. First, they prove it is mathematically expensive: achieving even approximate injectivity requires an output space that grows exponentially with the dimension of the input features. Second, a model that is too good at distinguishing every detail in the training set is prone to overfitting, failing to recognize broader patterns applicable to unseen graphs.

Methodology: Bounded Discrimination

The authors introduce three key innovations to balance discrimination power with generalization:

  1. Bounded Discrimination & (t, δ)-Injectivity: Instead of trying to distinguish everything, they propose a framework that only guarantees the ability to distinguish between a fixed number ($t$) of inputs. This avoids exponential parameter explosion.
  2. Projective Histograms (phist): They introduce a new aggregation function that projects features onto different axes and computes 1D histograms. This captures the distribution of features across the graph more efficiently than standard MLP-plus-sum aggregators.
  3. Implicit Regularization via Sampling: During training, the model samples a small, random subset of nodes (e.g., 32) to form a graph representation. This forces the network to learn robust structural features present throughout the graph rather than memorizing exact node configurations.
Generalization gap comparison between sampling and deterministic approaches.

Experimental Results

The model was evaluated on 9 benchmark datasets (Bioinformatics and Social Networks) stripped of all attributes to focus on pure structure. It was compared against 14 baselines, including 6 traditional graph kernels and 8 state-of-the-art GNNs.

Classification accuracy of the proposed model ('ours') compared to 14 baselines across 9 structural datasets.

Key Findings

  • Superior Accuracy: The proposed model achieved competitive or state-of-the-art accuracy across almost all datasets. Notably, on the ENZYMES dataset, it reached 42.0% accuracy, dwarfing the ~25% achieved by most other GNN baselines.
  • The Power of Sampling: The impact of sampling was dramatic. On the ENZYMES dataset, a "deterministic" version of the model (using all nodes) had a generalization error of 62.6%, while the sampling version dropped that error to just 22.8%.
  • Histograms vs. Sums: While a sum aggregator can theoretically be as powerful as a histogram, the phist approach achieves high discriminative power with far fewer trainable parameters.

Conclusion

This work demonstrates that the "curse of dimensionality" makes perfect GNNs unattainable in high-dimensional spaces. By adopting bounded discrimination and utilizing sampling as a powerful regularizer, the proposed model achieves superior generalization. Future work will explore how these principles apply to graphs with rich, high-dimensional node attributes.

Summary updated

Abstract

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.
BibTeX
@misc{seo2019discriminative,
  author = {Younjoo Seo and Andreas Loukas and Nathanaël Perraudin},
  title = {{Discriminative structural graph classification}},
  year = {2019},
  eprint = {1905.13422},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1905.13422},
}
Figure