# Are All Edges Necessary? A Unified Framework for Graph Purification

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 14 of its 30 references that are in the map.
- First posted on arXiv 9 Nov 2022.

## Builds on (most cited first, 14 of 14)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Explaining and Harnessing Adversarial Examples](https://mlsanity.com/paper/1412.6572/) (2014)
- [DropEdge: Towards Deep Graph Convolutional Networks on Node Classification](https://mlsanity.com/paper/1907.10903/) (2019)
- [Adversarial Attacks on Neural Networks for Graph Data](https://mlsanity.com/paper/1805.07984/) (2018)
- [Adversarial Attacks on Graph Neural Networks via Meta Learning](https://mlsanity.com/paper/1902.08412/) (2019)
- [Topology Attack and Defense for Graph Neural Networks: An Optimization Perspective](https://mlsanity.com/paper/1906.04214/) (2019)
- [Residual Connections Encourage Iterative Inference](https://mlsanity.com/paper/1710.04773/) (2017)
- [Highway and Residual Networks learn Unrolled Iterative Estimation](https://mlsanity.com/paper/1612.07771/) (2016)
- [Bridging the Gaps Between Residual Learning, Recurrent Neural Networks and Visual Cortex](https://mlsanity.com/paper/1604.03640/) (2016)
- [Adversarial Attacks and Defenses on Graphs: A Review, A Tool and Empirical Studies](https://mlsanity.com/paper/2003.00653/) (2020)
- [A Survey of Adversarial Learning on Graphs](https://mlsanity.com/paper/2003.05730/) (2020)
- [Should Graph Convolution Trust Neighbors? A Simple Causal Inference Method](https://mlsanity.com/paper/2010.11797/) (2020)

## Abstract (arXiv)

Graph Neural Networks (GNNs) as deep learning models working on graph-structure data have achieved advanced performance in many works. However, it has been proved repeatedly that, not all edges in a graph are necessary for the training of machine learning models. In other words, some of the connections between nodes may bring redundant or even misleading information to downstream tasks. In this paper, we try to provide a method to drop edges in order to purify the graph data from a new perspective. Specifically, it is a framework to purify graphs with the least loss of information, under which the core problems are how to better evaluate the edges and how to delete the relatively redundant edges with the least loss of information. To address the above two problems, we propose several measurements for the evaluation and different judges and filters for the edge deletion. We also introduce a residual-iteration strategy and a surrogate model for measurements requiring unknown information. The experimental results show that our proposed measurements for KL divergence with constraints to maintain the connectivity of the graph and delete edges in an iterative way can find out the most edges while keeping the performance of GNNs. What's more, further experiments show that this method also achieves the best defense performance against adversarial attacks.