Graph Machine Learning

We presented GraphGPS about a year ago and it is pleasing to see many ICML papers building upon our framework and expanding GT capabilities even further.  Exphormer by Shirzad, Velingker, Venkatachalam et al adds a missing piece of graph-motivated sparse attention to GTs: instead of BigBird or Performer (originally designed for sequences), Exphormer’s attention builds upon 1-hop edges, virtual nodes (connected to all nodes in a graph), and a neat idea of expander edges. Expander graphs have a constant degree and are shown to approximate fully-connected graphs. All components combined, attention costs O(V+E) instead of O(V²). This allows Exphormer to outperform GraphGPS almost everywhere and scale to really large graphs of up to 160k nodes. Amazing work and all chances to make Exphormer the standard sparse attention mechanism in GTs .  Concurrently with graph transformers, expander graphs can already be used to enhance the performance of any MPNN architecture as shown in Expander Graph Propagation by Deac, Lackenby, and Veličković. In a similar vein, Cai et al show that MPNNs with virtual nodes can approximate linear Performer-like attention such that even classic GCN and GatedGCN imbued with virtual nodes show pretty much a SOTA performance in long-range graph tasks (we released the LGRB benchmark last year exactly for measuring long-range capabilities of GNNs and GTs). <a href="https://towardsdatascience.com/graph-machine-learning-icml-2023-9b5e4306a1cc">Click Here</a>