Improving the Expressive Power of Graph Neural Network with Tinhofer Algorithm

2021/04/05 by Alan J. X. Guo, Guo, Alan J. X., Qing-Hu Hou +3
Computer Science · #Advanced Graph Neural Networks #FOS: Computer and information sciences #Graph Theory and Algorithms #Machine Learning (cs.LG) #Multimodal Machine Learning Applications

paper · pdf · doi:10.48550/arxiv.2104.01848

openalex publication_date 2021/04/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

In recent years, Graph Neural Network (GNN) has bloomly progressed for its power in processing graph-based data. Most GNNs follow a message passing scheme, and their expressive power is mathematically limited by the discriminative ability of the Weisfeiler-Lehman (WL) test. Following Tinhofer's research on compact graphs, we propose a variation of the message passing scheme, called the Weisfeiler-Lehman-Tinhofer GNN (WLT-GNN), that theoretically breaks through the limitation of the WL test. In addition, we conduct comparative experiments and ablation studies on several well-known datasets. The results show that the proposed methods have comparable performances and better expressive power on these datasets.

Citations

• Inductive Representation Learning on Large Graphs
• Invariant and Equivariant Graph Networks
• Fast Graph Representation Learning with PyTorch Geometric
• Detecting Functionality-Specific Vulnerabilities via Retrieving Individual Functionality-Equivalent APIs in Open-Source Repositories
• TUDataset: A collection of benchmark datasets for learning with graphs
• A Comprehensive Survey on Graph Neural Networks

Related

• Exponentially Improving the Complexity of Simulating the Weisfeiler-Lehman Test with Graph Neural Networks
• Empowering GNNs via Edge-Aware Weisfeiler-Leman Algorithm
• Rethinking GNN Expressive Power from a Distributed Computational Model Perspective
• Extending the Design Space of Graph Neural Networks by Rethinking Folklore Weisfeiler-Lehman
• Improving Expressivity of Graph Neural Networks