# Boosting Graph Structure Learning with Dummy Nodes

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Builds on 30 of its 45 references that are in the map.
- First posted on arXiv 17 Jun 2022.

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

- [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)
- [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)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [Fast Graph Representation Learning with PyTorch Geometric](https://mlsanity.com/paper/1903.02428/) (2019)
- [Modeling Relational Data with Graph Convolutional Networks](https://mlsanity.com/paper/1703.06103/) (2017)
- [Relational inductive biases, deep learning, and graph networks](https://mlsanity.com/paper/1806.01261/) (2018)
- [Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learning](https://mlsanity.com/paper/1801.07606/) (2018)
- [Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks](https://mlsanity.com/paper/1810.02244/) (2018)
- [Hierarchical Graph Representation Learning with Differentiable Pooling](https://mlsanity.com/paper/1806.08804/) (2018)
- [Heterogeneous Graph Transformer](https://mlsanity.com/paper/2003.01332/) (2020)
- [Representation Learning on Graphs: Methods and Applications](https://mlsanity.com/paper/1709.05584/) (2017)
- [Composition-based Multi-Relational Graph Convolutional Networks](https://mlsanity.com/paper/1911.03082/) (2019)
- [A Fair Comparison of Graph Neural Networks for Graph Classification](https://mlsanity.com/paper/1912.09893/) (2019)
- [Inductive Relation Prediction by Subgraph Reasoning](https://mlsanity.com/paper/1911.06962/) (2019)
- [Can Graph Neural Networks Count Substructures?](https://mlsanity.com/paper/2002.04025/) (2020)
- [Equivariant Subgraph Aggregation Networks](https://mlsanity.com/paper/2110.02910/) (2021)
- [On the Universality of Invariant Networks](https://mlsanity.com/paper/1901.09342/) (2019)
- [A Survey on Graph Kernels](https://mlsanity.com/paper/1903.11835/) (2019)
- [Hierarchical Graph Pooling with Structure Learning](https://mlsanity.com/paper/1911.05954/) (2019)
- [Pointer Graph Networks](https://mlsanity.com/paper/2006.06380/) (2020)
- [On Valid Optimal Assignment Kernels and Applications to Graph Classification](https://mlsanity.com/paper/1606.01141/) (2016)
- [RetGK: Graph Kernels based on Return Probabilities of Random Walks](https://mlsanity.com/paper/1809.02670/) (2018)
- [Neural Subgraph Isomorphism Counting](https://mlsanity.com/paper/1912.11589/) (2019)
- [Graph Pointer Neural Networks](https://mlsanity.com/paper/2110.00973/) (2021)
- [Graph Convolutional Networks with Dual Message Passing for Subgraph Isomorphism Counting and Matching](https://mlsanity.com/paper/2112.08764/) (2021)
- [Node2Seq: Towards Trainable Convolutions in Graph Neural Networks](https://mlsanity.com/paper/2101.01849/) (2021)

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

- [Complex Query Answering on Eventuality Knowledge Graph with Implicit Logical Constraints](https://mlsanity.com/paper/2305.19068/) (2023)
- [Edge Prompt Tuning for Graph Neural Networks](https://mlsanity.com/paper/2503.00750/) (2025)
- [DeepRicci: Self-supervised Graph Structure-Feature Co-Refinement for Alleviating Over-squashing](https://mlsanity.com/paper/2401.12780/) (2024)
- [Enhancing User Intent Capture in Session-Based Recommendation with Attribute Patterns](https://mlsanity.com/paper/2312.16199/) (2023)
- [Towards Dynamic Message Passing on Graphs](https://mlsanity.com/paper/2410.23686/) (2024)
- [Latent Graph Inference with Limited Supervision](https://mlsanity.com/paper/2310.04314/) (2023)
- [EmoDynamiX: Emotional Support Dialogue Strategy Prediction by Modelling MiXed Emotions and Discourse Dynamics](https://mlsanity.com/paper/2408.08782/) (2024)
- [Single Node Injection Label Specificity Attack on Graph Neural Networks via Reinforcement Learning](https://mlsanity.com/paper/2305.02901/) (2023)
- [UniGAP: A Universal and Adaptive Graph Upsampling Approach to Mitigate Over-Smoothing in Node Classification Tasks](https://mlsanity.com/paper/2407.19420/) (2024)
- [What Do LLMs Need to Understand Graphs: A Survey of Parametric Representation of Graphs](https://mlsanity.com/paper/2410.12126/) (2024)
- [Harnessing Collective Structure Knowledge in Data Augmentation for Graph Neural Networks](https://mlsanity.com/paper/2405.10633/) (2024)
- [Multimodal Graph Representation Learning with Dynamic Information Pathways](https://mlsanity.com/paper/2603.09258/) (2026)
- [Predicting Protein-Ligand Binding Affinity with Equivariant Line Graph Network](https://mlsanity.com/paper/2210.16098/) (2022)

## Abstract (arXiv)

With the development of graph kernels and graph representation learning, many superior methods have been proposed to handle scalability and oversmoothing issues on graph structure learning. However, most of those strategies are designed based on practical experience rather than theoretical analysis. In this paper, we use a particular dummy node connecting to all existing vertices without affecting original vertex and edge properties. We further prove that such the dummy node can help build an efficient monomorphic edge-to-vertex transform and an epimorphic inverse to recover the original graph back. It also indicates that adding dummy nodes can preserve local and global structures for better graph representation learning. We extend graph kernels and graph neural networks with dummy nodes and conduct experiments on graph classification and subgraph isomorphism matching tasks. Empirical results demonstrate that taking graphs with dummy nodes as input significantly boosts graph structure learning, and using their edge-to-vertex graphs can also achieve similar results. We also discuss the gain of expressive power from the dummy in neural networks.