notesum.ai

Published at November 26

Rewiring Techniques to Mitigate Oversquashing and Oversmoothing in GNNs: A Survey

cs.LG

cs.AI

Released Date: November 26, 2024

Authors: Hugo Attali¹, Davide Buscaldi¹, Nathalie Pernelle¹

Aff.: ¹LIPN, CNRS UMR 7030, Université Paris Sorbonne Nord, France

Arxiv: http://arxiv.org/abs/2411.17429v1

Refer to caption

Models	Venues	OSQ	OSM	Measure
KNN		NO	NO	Distance
Master Node	[ICML 2017]	YES	NO	Connectivity
Drop Edge ¹¹1https://github.com/DropEdge/DropEdge	[ICLR 2020] [46]	NO	Yes	Random
DIGL ²²2https://github.com/gasteigerjo/gdc	[NEURIPS 2019] [33]	NO	NO	Page Rank
PPRGo ³³3https://github.com/gasteigerjo/gdc	[KDD 2020] [13]	NO	NO	Page Rank
FA	[ICLR 2021] [3]	YES	NO	Connectivity
SDRF ⁴⁴4https://github.com/jctops/understanding-oversquashing/tree/main	[ICLR 2022] [54]	YES	NO	Balanced Forman Curvature
RLEF ⁵⁵5https://github.com/kedar2/Oversquashing	[IEEE AACCCC 2022] [8]	Yes	NO	Spectral GAP
DiffWire ⁶⁶6https://github.com/AdrianArnaiz/DiffWire	[LOG 2022] [4]	Yes	NO	Learning Rewiring
EGP ⁷⁷7https://github.com/josephjwilson/ $cayley_{g}raph_{p}ropagation$	[LOG 2022] [20]	NO	YES	Cayley graph
FOSR ⁸⁸8https://github.com/kedar2/FoSR/tree/main	[ICLR 2023] [32]	NO	YES	Spectral GAP
BORF ⁹⁹9https://github.com/hieubkvn123/revisiting-gnn-curvature	[ICML 2023] [39]	YES	YES	Ollivier Curvature
GTR ¹⁰¹⁰10https://github.com/blackmit/gtr_rewiring	[ICML 2023] [11]	NO	YES	Effective Resistance
SLJR ¹¹¹¹11https://github.com/jhonygiraldo/SJLR	[CIKM 2023] [26]	YES	YES	Jost and Liu Curvature
AFR-3 ¹²¹²12https://github.com/Weber-GeoML/ $AFRC_{R}ewiring$	[LOG 2023] [24]	YES	YES	Augmented Forman Curvature
PR-MPNNs ¹³¹³13https://github.com/chendiqian/PR-MPNN/	[ICLR 2024] [45]	Yes	NO	Probilistic learning rewiring
LASER ¹⁴¹⁴14https://github.com/Fedzbar/laser-release	[ICLR 2024] [9]	NO	YES	Random Walk
DR ¹⁵¹⁵15https://github.com/Hugo-Attali/Delaunay-Rewiring	[ICML 2024] [6]	YES	YES	Delaunay Triangulation