Boosting Graph Structure Learning with Dummy Nodes

2022-06-17 · Xin Liu, Jiayang Cheng, Yangqiu Song, Xin Jiang

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.

📄 PDF Abstract BibTeX arXiv:2206.08561

Code (1)

hkust-knowcomp/dummynode4graphlearning 공식 구현 pytorch

Tasks

Graph Classification Graph Representation Learning Graph structure learning Representation Learning

Stochastic Iterative Graph Matching

2021-06-04 · Linfeng Liu, Michael C. Hughes, Soha Hassoun, Li-Ping Liu

Recent works leveraging Graph Neural Networks to approach graph matching tasks have shown promising results. Recent progress in learning discrete distributions poses new opportunities for learning graph matching models. …

Graph Matching Stochastic Optimization

Learning Graph-Level Representation for Drug Discovery

2017-09-12 · Junying Li, Deng Cai, Xiaofei He

Predicating macroscopic influences of drugs on human body, like efficacy and toxicity, is a central problem of small-molecule based drug discovery. Molecules can be represented as an undirected graph, and we can utilize …

All Drug Discovery General Classification regression

Maximum Cohesive Grid of Superpixels for Fast Object Localization

2013-06-01 · CVPR 2013 6 · Liang Li, Wei Feng, Liang Wan, Jiawan Zhang

This paper addresses a challenging problem of regularizing arbitrary superpixels into an optimal grid structure, which may significantly extend current low-level vision algorithms by allowing them to use superpixels (SPs…

Object Object Localization Superpixels

path_boost: A Python Package for Interpretable Graph-Level Prediction using Path-Based Gradient Boosting

2026-07-08 · Claudio Meggio, Johan Pensar, Riccardo De Bin arxiv

We present path_boost, a Python package for interpretable supervised learning on graph-structured input data. The package implements PathBoost, a gradient boosting algorithm that automatically discovers predictive labele…

Molecular Property Prediction Binary Classification Graph Neural Network

ifMixup: Interpolating Graph Pair to Regularize Graph Classification

2021-10-18 · Hongyu Guo, Yongyi Mao

We present a simple and yet effective interpolation-based regularization technique, aiming to improve the generalization of Graph Neural Networks (GNNs) on supervised graph classification. We leverage Mixup, an effective…

Classification Graph Classification