2022/08/06 by Pradeep Banerjee, Kedar Karhadkar, Banerjee, Pradeep Kr. +7 · 7 citations
Computer Science · Engineering · #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)
paper · pdf · doi:10.48550/arxiv.2208.03471
openalex publication_date 2022/08/06 · 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.