# DOTIN: Dropping Task-Irrelevant Nodes for GNNs

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 43 references that are in the map.
- First posted on arXiv 28 Apr 2022.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale](https://mlsanity.com/paper/2010.11929/) (2020)
- [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)
- [Fast and Accurate Deep Network Learning by Exponential Linear Units (ELUs)](https://mlsanity.com/paper/1511.07289/) (2015)
- [Hierarchical Graph Representation Learning with Differentiable Pooling](https://mlsanity.com/paper/1806.08804/) (2018)
- [DropEdge: Towards Deep Graph Convolutional Networks on Node Classification](https://mlsanity.com/paper/1907.10903/) (2019)
- [Graph U-Nets](https://mlsanity.com/paper/1905.05178/) (2019)
- [Self-Attention Graph Pooling](https://mlsanity.com/paper/1904.08082/) (2019)
- [Not All Patches are What You Need: Expediting Vision Transformers via Token Reorganizations](https://mlsanity.com/paper/2202.07800/) (2022)
- [DeeperGCN: All You Need to Train Deeper GCNs](https://mlsanity.com/paper/2006.07739/) (2020)
- [Order Matters: Sequence to sequence for sets](https://mlsanity.com/paper/1511.06391/) (2015)
- [Graph Matching Networks for Learning the Similarity of Graph Structured Objects](https://mlsanity.com/paper/1904.12787/) (2019)
- [Discriminative Embeddings of Latent Variable Models for Structured Data](https://mlsanity.com/paper/1603.05629/) (2016)
- [DropGNN: Random Dropouts Increase the Expressiveness of Graph Neural Networks](https://mlsanity.com/paper/2111.06283/) (2021)
- [Towards Sparse Hierarchical Graph Classifiers](https://mlsanity.com/paper/1811.01287/) (2018)
- [Rethinking pooling in graph neural networks](https://mlsanity.com/paper/2010.11418/) (2020)
- [Understanding Pooling in Graph Neural Networks](https://mlsanity.com/paper/2110.05292/) (2021)
- [Dynamic Graph Message Passing Networks](https://mlsanity.com/paper/1908.06955/) (2019)
- [Revisiting Over-smoothing in Deep GCNs](https://mlsanity.com/paper/2003.13663/) (2020)
- [Octree guided CNN with Spherical Kernels for 3D Point Clouds](https://mlsanity.com/paper/1903.00343/) (2019)
- [Graph Classification via Deep Learning with Virtual Nodes](https://mlsanity.com/paper/1708.04357/) (2017)
- [Combinatorial Learning of Graph Edit Distance via Dynamic Embedding](https://mlsanity.com/paper/2011.15039/) (2020)
- [Towards Interpretable Sparse Graph Representation Learning with Laplacian Pooling](https://mlsanity.com/paper/1905.11577/) (2019)

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

- [Interpreting Unfairness in Graph Neural Networks via Training Node Attribution](https://mlsanity.com/paper/2211.14383/) (2022)
- [ES-GNN: Generalizing Graph Neural Networks Beyond Homophily with Edge Splitting](https://mlsanity.com/paper/2205.13700/) (2022)

## Abstract (arXiv)

Scalability is an important consideration for deep graph neural networks. Inspired by the conventional pooling layers in CNNs, many recent graph learning approaches have introduced the pooling strategy to reduce the size of graphs for learning, such that the scalability and efficiency can be improved. However, these pooling-based methods are mainly tailored to a single graph-level task and pay more attention to local information, limiting their performance in multi-task settings which often require task-specific global information. In this paper, departure from these pooling-based efforts, we design a new approach called DOTIN (underlineDrunderlineopping underlineTask-underlineIrrelevant underlineNodes) to reduce the size of graphs. Specifically, by introducing K learnable virtual nodes to represent the graph embeddings targeted to K different graph-level tasks, respectively, up to 90% raw nodes with low attentiveness with an attention model -- a transformer in this paper, can be adaptively dropped without notable performance decreasing. Achieving almost the same accuracy, our method speeds up GAT by about 50% on graph-level tasks including graph classification and graph edit distance (GED) with about 60% less memory, on D&D dataset. Code will be made publicly available in https://github.com/Sherrylone/DOTIN.