Research map / Graph learning / GNN architectures
Influence Functions for Edge Edits in Non-Convex Graph Neural Networks
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes a proximal Bregman response function-based influence function for edge insertions and deletions in non-convex GNNs, explicitly modeling message-propagation effects, and applies it to edge editing, adversarial attacks and rewiring analysis.
Problem
Influence functions for GNNs assume strict convexity and only model parameter shifts from edge deletions, ignoring edge insertions and changes in message propagation, so they predict edge-edit effects poorly for non-convex GNNs.
Approach
Derives an edge-edit proximal Bregman response function (PBRF) whose influence decomposes into a parameter-shift term (via a Gauss-Newton Hessian with damping, relaxing convexity) and an explicit message-propagation term from the derivative of the evaluation function with respect to the adjacency matrix, handling both edge deletions and insertions.
Key results
- On Cora with a four-layer GCN, the proposed influence achieves correlations up to 0.95 with actual influence, versus 0.09 and 0.14 for GIF on over-squashing and Dirichlet energy.
- Edits guided by validation-loss influence raise test accuracy on Cora from 81.0 to 82.1 and PubMed from 75.6 to 76.4, while GIF-guided edits do not improve it.
- Validation-loss-guided adversarial edge edits reduce Cora accuracy to 78.4 at 5% attack ratio, outperforming DICE (80.0) and PRBCD (78.7).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the proposed influence function instead of GIF | GCN edge-influence prediction · Cora, over-squashing influence | correlation: 0.09 -> 0.95 | Helped |
| Use the proposed influence function instead of GIF | GCN edge-influence prediction · Cora, Dirichlet energy influence | correlation: 0.14 -> 0.95 | Helped |
| Select edge edits using validation-loss influence | GCN · Cora | test accuracy: 81.0 -> 82.1 | Helped |
| Select edge edits using validation-loss influence | GCN · CiteSeer | test accuracy: 69.3 -> 69.6 | Helped |
| Select edge edits using validation-loss influence | GCN · PubMed | test accuracy: 75.6 -> 76.4 | Helped |
| Select edge edits using Dirichlet-energy or over-squashing influence rather than validation-loss influence | GCN edge editing · Cora, CiteSeer, and PubMed | test accuracy | Mixed |
| Use the proposed influence function to select edits instead of GIF | GCN validation-loss edge editing · Cora, CiteSeer, and PubMed | test accuracy | Helped |
| Increase the number of simultaneous edge insertions | Ours influence estimation · Cora, validation loss | correlation: 0.84 under 100 simultaneous edge edits | Hurt |
| Include message-propagation effects in addition to parameter shifts | Ours edge-influence prediction · Cora | influence-estimate completeness | Helped |
| Insert homophilic rather than heterophilic edges | GCN · Six datasets, validation loss | validation loss | Helped |
| Delete homophilic rather than heterophilic edges | GCN · Six datasets, validation loss | validation loss | Hurt |
| Use validation-loss influence for adversarial edge edits instead of GIF | GCN · Cora, CiteSeer, and PubMed at attack ratios 1%, 3%, and 5% | test accuracy | Hurt |
Surprising findings
- Editing edges to improve Dirichlet energy or over-squashing measures does not consistently improve test accuracy.
- The validation-loss-based attack is more effective than tailored over-squashing or over-smoothing attacks and the PRBCD and DICE baselines.
Limitations
- Prediction accuracy declines as the number of simultaneous edge edits increases, due to first-order approximation error.
- Scalability to deep GNNs remains challenging.
Experimental setup
Datasets: Cora CiteSeer PubMed Chameleon Squirrel Actor Texas
Benchmarks: Cora CiteSeer PubMed Chameleon Squirrel Actor Texas
Metrics: Pearson correlation between predicted and actual influence test accuracy validation loss Dirichlet energy over-squashing measure
Baselines: GIF DICE PRBCD BORF FoSR random edge deletion
Builds on: influence functions proximal Bregman response function GIF LiSSA
Closest papers by meaning
- Characterizing the Influence of Graph Elements (ICLR 2023 · similarity 0.92)
- If Influence Functions are the Answer, Then What is the Question? (NeurIPS 2022 · similarity 0.89)
- DiffIM: Differentiable Influence Minimization with Surrogate Modeling and Continuous Relaxation (AAAI 2025 · similarity 0.86)
- Edge Prompt Tuning for Graph Neural Networks (ICLR 2025 · similarity 0.86)
- DeepSN: A Sheaf Neural Framework for Influence Maximization (AAAI 2025 · similarity 0.85)
- Feature Distribution on Graph Topology Mediates the Effect of Graph Convolution: Homophily Perspective (ICML 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.