Beyond Erdos-Renyi: Generalization in Algorithmic Reasoning on Graphs
Abstract
Neural algorithmic reasoning excels in many graph algorithms, but assessment mainly focuses on the Erdős-Rényi (ER) graph family. This study delves into graph algorithmic models' generalization across diverse distributions. Testing a leading model exposes overreliance on ER graphs for generalization assessment. We further investigate two scenarios: generalisation to every target distribution and single target distributions. Our results suggest that achieving the former is not as trivial and achieving the latter can be aided selecting source distribution via novel Tree Mover's Distance interpretation.
Cite
Text
Georgiev et al. "Beyond Erdos-Renyi: Generalization in Algorithmic Reasoning on Graphs." NeurIPS 2023 Workshops: GLFrontiers, 2023.Markdown
[Georgiev et al. "Beyond Erdos-Renyi: Generalization in Algorithmic Reasoning on Graphs." NeurIPS 2023 Workshops: GLFrontiers, 2023.](https://mlanthology.org/neuripsw/2023/georgiev2023neuripsw-beyond/)BibTeX
@inproceedings{georgiev2023neuripsw-beyond,
title = {{Beyond Erdos-Renyi: Generalization in Algorithmic Reasoning on Graphs}},
author = {Georgiev, Dobrik and Lio, Pietro and Bachurski, Jakub and Chen, Junhua and Shi, Tunan},
booktitle = {NeurIPS 2023 Workshops: GLFrontiers},
year = {2023},
url = {https://mlanthology.org/neuripsw/2023/georgiev2023neuripsw-beyond/}
}