Summary of Rethinking Gnn Expressive Power Research in the Machine Learning Community: Limitations, Issues, and Corrections, by Guanyu Cui et al.
Rethinking GNN Expressive Power Research in the Machine Learning Community: Limitations, Issues, and Corrections
by Guanyu Cui, Zhewei Wei, Hsin-Hao Su
First submitted to arxiv on: 2 Oct 2024
Categories
- Main: Machine Learning (cs.LG)
- Secondary: Artificial Intelligence (cs.AI)
GrooveSquid.com Paper Summaries
GrooveSquid.com’s goal is to make artificial intelligence research accessible by summarizing AI papers in simpler terms. Each summary below covers the same AI paper, written at different levels of difficulty. The medium difficulty and low difficulty versions are original summaries written by GrooveSquid.com, while the high difficulty version is the paper’s original abstract. Feel free to learn from the version that suits you best!
| Summary difficulty | Written by | Summary |
|---|---|---|
| High | Paper authors | High Difficulty Summary Read the original abstract here |
| Medium | GrooveSquid.com (original content) | Medium Difficulty Summary The paper investigates the theoretical foundations of graph neural networks (GNNs), specifically addressing the limitations of using Weisfeiler-Lehman (WL) tests as a benchmark for analyzing their expressive power. The authors identify two key issues: WL tests focus on structural equivalences rather than functional expressiveness, and they are not well-suited for handling graphs with features. By leveraging communication complexity, the study shows that the lower bound on GNN capacity to simulate one iteration of the WL test grows almost linearly with graph size, indicating the WL test is misaligned with message-passing GNNs. The authors also discuss potential issues when using precomputed features or integrating external models. To improve understanding, they propose using well-defined computational models like CONGEST from distributed computing and present results on virtual nodes and edges. Several open problems regarding GNN expressive power are highlighted for future exploration. |
| Low | GrooveSquid.com (original content) | Low Difficulty Summary The paper talks about how good graph neural networks (GNNs) are at learning patterns in graphs. Researchers often use a way to test these GNNs called the Weisfeiler-Lehman (WL) tests, but this method has some big problems. First, it only checks if two parts of a graph are alike, not what they can actually do. Second, it’s not good at handling graphs with extra information like colors or labels. The study shows that using WL tests to test GNNs doesn’t really work well because the complexity grows too fast as the graph gets bigger. This means we need to find better ways to understand how GNNs work and what they can do. |
Keywords
* Artificial intelligence * Gnn
