anthology-of-the-sota

LIT-580: How Powerful are Graph Neural Networks?

2 min read

Properties6
StatusActive
Tagsgraphs-and-networks, model-architecture, analysis-and-evaluation
Compared againstLIT-582 — Semi-Supervised Classification with Graph Convolutional Networks, LIT-579 — Where Did the Gap Go? Reassessing the Long-Range Graph Benchmark
Cited as “introduced by” bySOTA-351 — In a message-passing GNN for graph-level tasks, aggregate neighbours by sum with an MLP update, not by mean or max, when graph structure rather than node features carries the signal
Cited as “paper” byNOTE-319 — GIN
Cited as “source” bySOTA-351 — In a message-passing GNN for graph-level tasks, aggregate neighbours by sum with an MLP update, not by mean or max, when graph structure rather than node features carries the signal, THEORY-083 — A message-passing GNN can distinguish no more graphs than the 1-WL test, and reaches that limit only if its neighbor aggregation is injective on multisets, as a sum followed by an MLP is and a mean or max is not

Graph View

Xu, Hu, Leskovec, Jegelka, MIT and Stanford (ICLR 2019) — ARXIV-1810.00826

Key takeaways

  • Upper bound (Lemma 2): any aggregate-and-combine GNN is at most as powerful as the 1-WL test at distinguishing graphs
  • Achieving it (Theorem 3): it is achieved when the neighbor aggregation, the combine step and the graph readout are injective. Sums of an MLP over a multiset are injective (Lemma 5), and this gives h_v = MLP((1 + ε)·h_v + Σ_u h_u)
  • Mean and max are weaker (§5): mean captures the distribution of neighbor features, not their counts. Max captures only the set. Figure 3 gives simple structures both fail to distinguish
  • Training fit (Figure 4): sum–MLP fits every training set almost perfectly, and mean, max and 1-layer variants underfit many of them, in the predicted order
  • Test accuracy (Table 1, 10-fold CV): GIN-0 is best or statistically tied on all 9 datasets. The large gaps are on REDDIT-BINARY and MULTI-5K, which have no node features: sum 92.4 and 57.5, mean exactly at chance. Even with degree features, mean scores 71.2 and 41.3. Elsewhere, differences are mostly within one standard deviation. On PTC, mean–MLP (66.6) beats GIN-0 (64.6)

Standing in the anthology

Filed from #163 (“graph representation / gnn”). It is compared_against GCN (LIT-582), whose mean aggregator it analyzes. It sources THEORY-083 and SOTA-351.

What the table shows and what the abstract says. “GIN achieves state-of-the-art” rests on ties within noise on most datasets. The decisive evidence is the featureless Reddit graphs and the training-fit curves, which is where the theory predicts a difference.

Retuned against a graph transformer. Tönshoff et al. (LIT-579) use GINE, this architecture’s edge-feature variant, as one of three message-passing baselines on the Long-Range Graph Benchmark, at the same 500k-parameter budget as the GPS graph transformer. After a hyperparameter sweep, GINE goes from AP 0.550 to 0.662 on Peptides-func and from MAE 0.355 to 0.247 on Peptides-struct, ahead of GPS’s 0.653 and 0.251, with most of the gain from a multi-layer prediction head. On the PascalVOC-SP and COCO-SP superpixel tasks GPS stays ahead. What is compared is tuned performance on long-range tasks, not the expressiveness result above.

Read — NOTE-319.

Backlinks