# Characterizing the Influence of Graph Elements

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

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- Builds on 35 of its 50 references that are in the map.
- First posted on arXiv 14 Oct 2022.

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

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Understanding Black-box Predictions via Influence Functions](https://mlsanity.com/paper/1703.04730/) (2017)
- [Simplifying Graph Convolutional Networks](https://mlsanity.com/paper/1902.07153/) (2019)
- [LightGCN: Simplifying and Powering Graph Convolution Network for Recommendation](https://mlsanity.com/paper/2002.02126/) (2020)
- [Deep Graph Infomax](https://mlsanity.com/paper/1809.10341/) (2018)
- [Pitfalls of Graph Neural Network Evaluation](https://mlsanity.com/paper/1811.05868/) (2018)
- [Link Prediction Based on Graph Neural Networks](https://mlsanity.com/paper/1802.09691/) (2018)
- [Gated Graph Sequence Neural Networks](https://mlsanity.com/paper/1511.05493/) (2015)
- [GNNExplainer: Generating Explanations for Graph Neural Networks](https://mlsanity.com/paper/1903.03894/) (2019)
- [Graph Neural Networks for Social Recommendation](https://mlsanity.com/paper/1902.07243/) (2019)
- [FastGCN: Fast Learning with Graph Convolutional Networks via Importance Sampling](https://mlsanity.com/paper/1801.10247/) (2018)
- [Adversarial Attacks on Neural Networks for Graph Data](https://mlsanity.com/paper/1805.07984/) (2018)
- [On Explainability of Graph Neural Networks via Subgraph Explorations](https://mlsanity.com/paper/2102.05152/) (2021)
- [Adversarial Attacks on Graph Neural Networks via Meta Learning](https://mlsanity.com/paper/1902.08412/) (2019)
- [Wiki-CS: A Wikipedia-Based Benchmark for Graph Neural Networks](https://mlsanity.com/paper/2007.02901/) (2020)
- [GraphLIME: Local Interpretable Model Explanations for Graph Neural Networks](https://mlsanity.com/paper/2001.06216/) (2020)
- [Topology Attack and Defense for Graph Neural Networks: An Optimization Perspective](https://mlsanity.com/paper/1906.04214/) (2019)
- [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)
- [Adversarial Attacks on Node Embeddings via Graph Poisoning](https://mlsanity.com/paper/1809.01093/) (2018)
- [Influence Function based Data Poisoning Attacks to Top-N Recommender Systems](https://mlsanity.com/paper/2002.08025/) (2020)
- [A Swiss Army Infinitesimal Jackknife](https://mlsanity.com/paper/1806.00550/) (2018)
- [Graph Robustness Benchmark: Benchmarking the Adversarial Robustness of Graph Machine Learning](https://mlsanity.com/paper/2111.04314/) (2021)
- [Learning Graph-Level Representation for Drug Discovery](https://mlsanity.com/paper/1709.03741/) (2017)
- [Achieving Fairness at No Utility Cost via Data Reweighing with Influence](https://mlsanity.com/paper/2202.00787/) (2022)
- [Less Is Better: Unweighted Data Subsampling via Influence Function](https://mlsanity.com/paper/1912.01321/) (2019)

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

- [GIF: A General Graph Unlearning Strategy via Influence Function](https://mlsanity.com/paper/2304.02835/) (2023)
- [Dynamic Graph Unlearning: A General and Efficient Post-Processing Method via Gradient Transformation](https://mlsanity.com/paper/2405.14407/) (2024)
- [Erase then Rectify: A Training-Free Parameter Editing Approach for Cost-Effective Graph Unlearning](https://mlsanity.com/paper/2409.16684/) (2024)
- [Precedence-Constrained Winter Value for Effective Graph Data Valuation](https://mlsanity.com/paper/2402.01943/) (2024)
- [Can Graph Neural Networks Expose Training Data Properties? An Efficient Risk Assessment Approach](https://mlsanity.com/paper/2411.03663/) (2024)
- [Influence Functions for Edge Edits in Non-Convex Graph Neural Networks](https://mlsanity.com/paper/2506.04694/) (2025)
- [Unraveling the Impact of Heterophilic Structures on Graph Positive-Unlabeled Learning](https://mlsanity.com/paper/2405.19919/) (2024)
- [A Cognac Shot To Forget Bad Memories: Corrective Unlearning for Graph Neural Networks](https://mlsanity.com/paper/2412.00789/) (2024)
- [Adaptive Graph Unlearning](https://mlsanity.com/paper/2505.12614/) (2025)
- [DeGLIF for Label Noise Robust Node Classification using GNNs](https://mlsanity.com/paper/2506.00244/) (2025)
- [On the Cause of Unfairness: A Training Sample Perspective](https://mlsanity.com/paper/2306.17828/) (2023)
- [Promoting Fairness in GNNs: A Characterization of Stability](https://mlsanity.com/paper/2309.03648/) (2023)
- [On the Equivalence of Graph Convolution and Mixup](https://mlsanity.com/paper/2310.00183/) (2023)
- [Salutary Labeling with Zero Human Annotation](https://mlsanity.com/paper/2405.17627/) (2024)
- [Explaining Graph Neural Networks for Node Similarity on Graphs](https://mlsanity.com/paper/2407.07639/) (2024)
- [GraphToxin: Reconstructing Full Unlearned Graphs from Graph Unlearning](https://mlsanity.com/paper/2511.10936/) (2025)

## Abstract (arXiv)

Influence function, a method from robust statistics, measures the changes of model parameters or some functions about model parameters concerning the removal or modification of training instances. It is an efficient and useful post-hoc method for studying the interpretability of machine learning models without the need for expensive model re-training. Recently, graph convolution networks (GCNs), which operate on graph data, have attracted a great deal of attention. However, there is no preceding research on the influence functions of GCNs to shed light on the effects of removing training nodes/edges from an input graph. Since the nodes/edges in a graph are interdependent in GCNs, it is challenging to derive influence functions for GCNs. To fill this gap, we started with the simple graph convolution (SGC) model that operates on an attributed graph and formulated an influence function to approximate the changes in model parameters when a node or an edge is removed from an attributed graph. Moreover, we theoretically analyzed the error bound of the estimated influence of removing an edge. We experimentally validated the accuracy and effectiveness of our influence estimation function. In addition, we showed that the influence function of an SGC model could be used to estimate the impact of removing training nodes/edges on the test performance of the SGC without re-training the model. Finally, we demonstrated how to use influence functions to guide the adversarial attacks on GCNs effectively.