2022/11/19 by Chang Liu, Yuwen Yang, Liu, Chang +5 · 1 citation
Computer Science · Mathematics · #Advanced Graph Neural Networks #Computer science #Discrete mathematics #Equivariant map #FOS: Computer and information sciences #Graph #Graph factorization #Graph isomorphism #Line graph #Machine Learning (cs.LG) #Mathematics #Message passing #Null graph #Parallel computing #Permutation (music) #Theoretical computer science #Topic Modeling #Voltage graph #cs.LG
paper · pdf · doi:10.48550/arxiv.2211.10739
published in arXiv (Cornell University) (Cornell University)
arxiv created 2022/11/19 · openalex publication_date 2022/11/19 · arxiv updated 2022/11/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/06
The message-passing scheme is the core of graph representation learning. While most existing message-passing graph neural networks (MPNNs) are permutation-invariant in graph-level representation learning and permutation-equivariant in node- and edge-level representation learning, their expressive power is commonly limited by the 1-Weisfeiler-Lehman (1-WL) graph isomorphism test. Recently proposed expressive graph neural networks (GNNs) with specially designed complex message-passing mechanisms are not practical. To bridge the gap, we propose a plug-in Equivariant Distance ENcoding (EDEN) for MPNNs. EDEN is derived from a series of interpretable transformations on the graph's distance matrix. We theoretically prove that EDEN is permutation-equivariant for all level graph representation learning, and we empirically illustrate that EDEN's expressive power can reach up to the 3-WL test. Extensive experiments on real-world datasets show that combining EDEN with conventional GNNs surpasses recent advanced GNNs.