On the Connection Between MPNN and Graph Transformer
Jul 24, 2023
Sprecher:innen
Über
Graph Transformer (GT) recently has emerged as a new paradigm of graph learning algorithms, outperforming the previously popular Message Passing Neural Network (MPNN) on multiple benchmarks. Previous work <cit.> shows that with proper position embedding, GT can approximate MPNN arbitrarily well, implying that GT is at least as powerful as MPNN. In this paper, we study the inverse connection and show that MPNN with virtual node (VN), a commonly used heuristic with little theoretical understanding, is powerful enough to arbitrarily approximate the self-attention layer of GT. In particular, we first show that if we consider one type of linear transformer, the so-called Performer/Linear Transformer <cit.>, then MPNN + VN with only 𝒪(1) depth and 𝒪(1) width can approximate a self-attention layer in Performer/Linear Transformer. Next, via a connection between MPNN + VN and DeepSets, we prove the MPNN + VN with 𝒪(n^d) width and 𝒪(1) depth can approximate the self-attention layer arbitrarily well, where d is the input feature dimension. Lastly, under some assumptions, we provide an explicit construction of MPNN + VN with 𝒪(1) width and 𝒪(n) depth approximating the self-attention layer in GT arbitrarily well. On the empirical side, we demonstrate that 1) MPNN + VN is a surprisingly strong baseline, outperforming GT on the recently proposed Long Range Graph Benchmark (LRGB) dataset, 2) our MPNN + VN improves over early implementation on a wide range of OGB datasets and 3) MPNN + VN outperforms Linear Transformer and MPNN on the climate modeling task.Graph Transformer (GT) recently has emerged as a new paradigm of graph learning algorithms, outperforming the previously popular Message Passing Neural Network (MPNN) on multiple benchmarks. Previous work <cit.> shows that with proper position embedding, GT can approximate MPNN arbitrarily well, implying that GT is at least as powerful as MPNN. In this paper, we study the inverse connection and show that MPNN with virtual node (VN), a commonly used heuristic with little theoretical unders…
Gefällt euch das Format? Vertraut auf SlidesLive, um euer nächstes Event festzuhalten!
Professionelle Aufzeichnung und Livestreaming – weltweit.
Freigeben
Empfohlene Videos
Präsentationen, deren Thema, Kategorie oder Sprecher:in ähnlich sind
Evading Black-box Classifiers Without Breaking Eggs
Später ansehen
Underspecification, inductive bias, and hybrid models
Später ansehen
A Kernel-Based View of Language Model Fine-Tuning
Später ansehen
Bi-directional Masks for Efficient N:M Sparse Training
Später ansehen
Yuxin Zhang, …
Trapdoor Normalization with Irreversible Ownership Verification
Später ansehen
Hanwen Liu, …