Reproduce “An Empirical Study of Realized GNN Expressiveness” on OpenResearch

Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.

Universal app for Apple silicon and Intel. Requires macOS 11 or later.

About this paper

Yanbo Wang, Muhan Zhang

Researchers at Peking University developed BREC, a new and challenging dataset, and the Reliable Paired Comparison (RPC) method to empirically measure the realized expressive power of Graph Neural Networks (GNNs. Their study on 23 state-of-the-art GNNs revealed a quantifiable gap between theoretical and practical expressiveness, with I^2-GNN emerging as a top performer.

Key insights

  • There exists a significant and quantifiable gap between the theoretical maximum expressiveness a GNN could achieve and its realized expressiveness in practical implementations.
  • Increasing subgraph radius in subgraph-based GNNs or the number of layers in k-WL GNNs does not consistently increase realized expressiveness due to issues like information dilution or over-smoothing; optimal values often exist.
  • Profound design and encoding techniques, such as distance encoding or carefully selected components, can significantly elevate realized expressiveness and practical performance, even without direct theoretical expressiveness improvements.

Summary by alphaXiv.

Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.