The field of graph neural networks (GNNs) and graph algorithms is rapidly advancing, with a focus on improving the expressivity and efficiency of these models. Recent developments have explored the use of directional information in GNNs, leading to improved performance and more accurate explanations. Additionally, new algorithms have been proposed for solving classic graph problems, such as finding minimum separators and approximating graph parameters. Noteworthy papers in this area include those that propose novel GNN architectures, such as the Directed Sheaf Neural Network, and those that develop more efficient algorithms for graph problems, such as the iterative planar pruning technique for finding approximate light spanners. Furthermore, researchers have also made significant progress in understanding the limitations and potential biases of GNNs, highlighting the need for more nuanced and direction-aware explanations.
Advances in Graph Neural Networks and Graph Algorithms
Sources
Improved Approximations for Hard Graph Problems using Predictions
Weisfeiler and Leman Follow the Arrow of Time: Expressive Power of Message Passing in Temporal Event Graphs
WILTing Trees: Interpreting the Distance Between MPNN Embeddings
Approximate Light Spanners in Planar Graphs
Towards Unsupervised Training of Matching-based Graph Edit Distance Solver via Preference-aware GAN
Machine Learning for Consistency Violation Faults Analysis
ReconXF: Graph Reconstruction Attack via Public Feature Explanations on Privatized Node Features and Labels
Sheaves Reloaded: A Directional Awakening
Upper bounds on the theta function of random graphs
How Explanations Leak the Decision Logic: Stealing Graph Neural Networks via Explanation Alignment
Connectivity-Preserving Minimum Separator in AT-free Graphs
Stability Notions for Hospital Residents with Sizes
Weisfeiler and Leman Go Gambling: Why Expressive Lottery Tickets Win
A Few Moments Please: Scalable Graphon Learning via Moment Matching
Improving the average dilation of a metric graph by adding edges
ExDiff: A Framework for Simulating Diffusion Processes on Complex Networks with Explainable AI Integration
Faster MPC Algorithms for Approximate Allocation in Uniformly Sparse Graphs
Ignoring Directionality Leads to Compromised Graph Neural Network Explanations
The Oversmoothing Fallacy: A Misguided Narrative in GNN Research
Influence Functions for Edge Edits in Non-Convex Graph Neural Networks
Online matching on stochastic block model