Celia Rubio Madrigal - Rewiring Graph Neural Networks: When Less is More and Structure Matters

How can removing connections actually improve Graph Neural Networks (GNNs)? While GNNs excel at processing graph-structured data, they face two key challenges. First, information can get stuck in bottlenecks when traveling between distant parts of the network (over-squashing). Second, node representations can become indistinct through successive layers of the network (over-smoothing). While adding edges to maximize the spectral gap addresses the first issue, it often worsens the second. This has long been considered an inherent trade-off in GNNs. Drawing inspiration from the Braess paradox—where removing specific roads can improve traffic flow—we argue that removing edges to maximize the spectral gap can solve both challenges at once. Our research also shows that minimizing the spectral gap, instead of maximizing it, can sometimes improve generalization. Since the spectral gap primarily influences community strength—how nodes naturally cluster together—improvement occurs when the graph's community structure aligns with node labels. Based on these findings, we propose three rewiring strategies that focus on community structure, feature similarity maximization, and the alignment between them Bio: "I am Celia, a second-year PhD candidate at the CISPA Helmholtz Center for Information Security in Saarland, Germany, working under Dr. Rebekka Burkholz. My research focuses on generalization challenges in graph learning, particularly how input graphs serve as both data and computational models, and the implications of rewiring them under different criteria. I hold degrees in Mathematics and Computer Science from Universidad Complutense de Madrid, and have held a postgraduate fellowship from la Caixa Foundation." This session is brought to you by the Cohere For AI Open Science Community - a space where ML researchers, engineers, linguists, social scientists, and lifelong learners connect and collaborate with each other. We'd like to extend a special thank you to Anier Vela