# Influence Functions for Edge Edits in Non-Convex Graph Neural Networks

arXiv: https://arxiv.org/abs/2506.04694 · HTML: https://mlsanity.com/paper/2506.04694/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 34 of its 42 references that are in the map.
- First posted on arXiv 5 Jun 2025.

## Builds on (most cited first, 30 of 34)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering](https://mlsanity.com/paper/1606.09375/) (2016)
- [Understanding Black-box Predictions via Influence Functions](https://mlsanity.com/paper/1703.04730/) (2017)
- [Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learning](https://mlsanity.com/paper/1801.07606/) (2018)
- [Revisiting Semi-Supervised Learning with Graph Embeddings](https://mlsanity.com/paper/1603.08861/) (2016)
- [Geom-GCN: Geometric Graph Convolutional Networks](https://mlsanity.com/paper/2002.05287/) (2020)
- [On the Bottleneck of Graph Neural Networks and its Practical Implications](https://mlsanity.com/paper/2006.05205/) (2020)
- [Multi-scale Attributed Node Embedding](https://mlsanity.com/paper/1909.13021/) (2019)
- [Understanding over-squashing and bottlenecks on graphs via curvature](https://mlsanity.com/paper/2111.14522/) (2021)
- [Studying Large Language Model Generalization with Influence Functions](https://mlsanity.com/paper/2308.03296/) (2023)
- [Large Language Model Unlearning](https://mlsanity.com/paper/2310.10683/) (2023)
- [Influence Functions in Deep Learning Are Fragile](https://mlsanity.com/paper/2006.14651/) (2020)
- [A Note on Over-Smoothing for Graph Neural Networks](https://mlsanity.com/paper/2006.13318/) (2020)
- [On the Accuracy of Influence Functions for Measuring Group Effects](https://mlsanity.com/paper/1905.13289/) (2019)
- [Explaining Black Box Predictions and Unveiling Data Artifacts through Influence Functions](https://mlsanity.com/paper/2005.06676/) (2020)
- [If Influence Functions are the Answer, Then What is the Question?](https://mlsanity.com/paper/2209.05364/) (2022)
- [FastIF: Scalable Influence Functions for Efficient Model Interpretation and Debugging](https://mlsanity.com/paper/2012.15781/) (2020)
- [FoSR: First-order spectral rewiring for addressing oversquashing in GNNs](https://mlsanity.com/paper/2210.11790/) (2022)
- [Robustness of Graph Neural Networks at Scale](https://mlsanity.com/paper/2110.14038/) (2021)
- [Revisiting Over-smoothing and Over-squashing Using Ollivier-Ricci Curvature](https://mlsanity.com/paper/2211.15779/) (2022)
- [What is Your Data Worth to GPT? LLM-Scale Data Valuation with Influence Functions](https://mlsanity.com/paper/2405.13954/) (2024)
- [On Second-Order Group Influence Functions for Black-Box Predictions](https://mlsanity.com/paper/1911.00418/) (2019)
- [DeepRobust: A PyTorch Library for Adversarial Attacks and Defenses](https://mlsanity.com/paper/2005.06149/) (2020)
- [Hiding Individuals and Communities in a Social Network](https://mlsanity.com/paper/1608.00375/) (2016)
- [Detecting Adversarial Samples Using Influence Functions and Nearest Neighbors](https://mlsanity.com/paper/1909.06872/) (2019)
- [GIF: A General Graph Unlearning Strategy via Influence Function](https://mlsanity.com/paper/2304.02835/) (2023)
- [Interactive Label Cleaning with Example-based Explanations](https://mlsanity.com/paper/2106.03922/) (2021)
- [Influence Functions for Scalable Data Attribution in Diffusion Models](https://mlsanity.com/paper/2410.13850/) (2024)
- [Most Influential Subset Selection: Challenges, Promises, and Beyond](https://mlsanity.com/paper/2409.18153/) (2024)

## Built on by (most cited first, 3 of 3)

- [Interaction-Aware Influence Functions for Group Attribution](https://mlsanity.com/paper/2605.15675/) (2026)
- [Transductive Generalization via Optimal Transport and Its Application to Graph Node Classification](https://mlsanity.com/paper/2603.09257/) (2026)
- [Groups Don't Move as One: A Bregman Clustering View of Linearized Group Influence](https://mlsanity.com/paper/2610.14809/) (2026)

## Abstract (arXiv)

Understanding how individual edges influence the behavior of graph neural networks (GNNs) is essential for improving their interpretability and robustness. Graph influence functions have emerged as promising tools to efficiently estimate the effects of edge deletions without retraining. However, existing influence prediction methods rely on strict convexity assumptions, exclusively consider the influence of edge deletions while disregarding edge insertions, and fail to capture changes in message propagation caused by these modifications. In this work, we propose a proximal Bregman response function specifically tailored for GNNs, relaxing the convexity requirement and enabling accurate influence prediction for standard neural network architectures. Furthermore, our method explicitly accounts for message propagation effects and extends influence prediction to both edge deletions and insertions in a principled way. Experiments with real-world datasets demonstrate accurate influence predictions for different characteristics of GNNs. We further demonstrate that the influence function is versatile in applications such as graph rewiring and adversarial attacks.