Reproduce “Ordered Subgraph Aggregation Networks” 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
Chendi Qian, Gaurav Rattan, Floris Geerts, Christopher Morris, Mathias Niepert
Researchers developed k-Ordered Subgraph Aggregation Networks (k-OSANs), a unified theoretical framework that rigorously characterizes the expressive power of subgraph-enhanced Graph Neural Networks. This work also introduces a data-driven method for sampling informative subgraphs via Implicit Maximum Likelihood Estimation (I-MLE), leading to improved predictive performance, such as a ~50% accuracy increase on the EXP dataset, and over 3.5x faster computation for existing models like ESAN compared to non-data-driven counterparts.
Key insights
- The k-OSAN framework unifies a broad spectrum of subgraph-enhanced GNNs and establishes that increasing subgraph size 'k' always leads to strictly increased expressive power.
- k-OSANs are proven to be strictly less expressive than (k+1)-WL but are incomparable with k-WL, offering a distinct and nuanced form of expressivity compared to traditional k-WL algorithms.
- Data-driven subgraph selection using I-MLE significantly enhances both the predictive performance and computational efficiency of subgraph-enhanced GNNs by learning to adapt sampling to the data distribution.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.