A Novel Higher-order Weisfeiler-Lehman Graph Convolution

2020/07/01 by Clemens Damke, Damke, Clemens, Vitalik Melnikov +3
Computer Science · Physics and Astronomy · #Advanced Graph Neural Networks #Caching and Content Delivery #Complex Network Analysis Techniques #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML)

paper · doi:10.48550/arxiv.2007.00346

openalex publication_date 2020/07/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29

Abstract

Current GNN architectures use a vertex neighborhood aggregation scheme, which limits their discriminative power to that of the 1-dimensional Weisfeiler-Lehman (WL) graph isomorphism test. Here, we propose a novel graph convolution operator that is based on the 2-dimensional WL test. We formally show that the resulting 2-WL-GNN architecture is more discriminative than existing GNN approaches. This theoretical result is complemented by experimental studies using synthetic and real data. On multiple common graph classification benchmarks, we demonstrate that the proposed model is competitive with state-of-the-art graph kernels and GNNs.

Citations

• The Multiscale Laplacian Graph Kernel
• Inductive Representation Learning on Large Graphs
• Detecting Functionality-Specific Vulnerabilities via Retrieving Individual Functionality-Equivalent APIs in Open-Source Repositories

Related

• Twin Weisfeiler-Lehman: High Expressive GNNs for Graph Classification
• Breaking the Expressive Bottlenecks of Graph Neural Networks
• Exponentially Improving the Complexity of Simulating the Weisfeiler-Lehman Test with Graph Neural Networks
• Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks
• Graph Neural Networks with Local Graph Parameters