Graph Machine Learning @ ICML 2023

We <a href="https://towardsdatascience.com/graphgps-navigating-graph-transformers-c2cc223a051c" rel="noopener" target="_blank">presented</a> 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 <a href="https://openreview.net/forum?id=3Ge74dgjjU" rel="noopener ugc nofollow" target="_blank">Shirzad, Velingker, Venkatachalam et al</a> 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 <a href="https://en.wikipedia.org/wiki/Expander_graph" rel="noopener ugc nofollow" target="_blank">expander edges</a>. 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 <a href="https://arxiv.org/abs/2210.02997" rel="noopener ugc nofollow" target="_blank">Expander Graph Propagation</a> by Deac, Lackenby, and Veličković. In a similar vein, <a href="https://openreview.net/forum?id=1EuHYKFPgA" rel="noopener ugc nofollow" target="_blank">Cai et al</a> 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 <a href="https://towardsdatascience.com/lrgb-long-range-graph-benchmark-909a6818f02c" rel="noopener" target="_blank">released</a> the <a href="https://github.com/vijaydwivedi75/lrgb" rel="noopener ugc nofollow" target="_blank">LGRB benchmark</a> last year exactly for measuring long-range capabilities of GNNs and GTs). <a href="https://towardsdatascience.com/graph-machine-learning-icml-2023-9b5e4306a1cc">Website</a>