2022/08/06 by Pradeep Banerjee, Pradeep Kr. Banerjee, Kedar Karhadkar +8 · 11 citations
Computer Science · Engineering · Mathematics · #Advanced Graph Neural Networks #Advanced Memory and Neural Computing #FOS: Computer and information sciences #Ferroelectric and Negative Capacitance Devices #Information Theory (cs.IT) #Machine Learning (cs.LG) #cs.IT #cs.LG #math.IT
paper · pdf · doi:10.48550/arxiv.2208.03471
8 pages, 5 figures; Accepted at the 58th Annual Allerton Conference on Communication, Control, and Computing
arxiv created 2022/08/06 · openalex publication_date 2022/08/06 · arxiv updated 2022/08/09 · openalex created_date 2022/10/02 · openalex updated_date 2026/07/28
The quality of signal propagation in message-passing graph neural networks (GNNs) strongly influences their expressivity as has been observed in recent works. In particular, for prediction tasks relying on long-range interactions, recursive aggregation of node features can lead to an undesired phenomenon called "oversquashing". We present a framework for analyzing oversquashing based on information contraction. Our analysis is guided by a model of reliable computation due to von Neumann that lends a new insight into oversquashing as signal quenching in noisy computation graphs. Building on this, we propose a graph rewiring algorithm aimed at alleviating oversquashing. Our algorithm employs a random local edge flip primitive motivated by an expander graph construction. We compare the spectral expansion properties of our algorithm with that of an existing curvature-based non-local rewiring strategy. Synthetic experiments show that while our algorithm in general has a slower rate of expansion, it is overall computationally cheaper, preserves the node degrees exactly and never disconnects the graph.