Boosting Graph Structure Learning with Dummy Nodes
This work addresses scalability and oversmoothing issues in graph learning for researchers and practitioners, though it is incremental as it builds on existing graph kernels and neural networks.
The paper tackles the problem of graph structure learning by introducing dummy nodes that connect to all vertices, proving they enable efficient graph transforms and preserve structures. Empirical results show this approach significantly boosts performance on graph classification and subgraph isomorphism tasks.
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.