Post #717

Graph Papers of the Week Expander Graph Propagation by Andreea Deac, Marc Lackenby, Petar Veličković. A clever approach to bypass bottlenecks without fully-connected graph transformers. Turns out that sparse but well-connected 4-regular Cayley graphs (expander graphs) can be a helpful template for message propagation. Cayley graphs of a desired size can be pre-computed w/o looking at the original graph. Practically, you can add a GNN layer propagating along a Cayley graph after each normal GNN layer over the original graph. The anonymous ICLR 2023 submission Exphormer: Scaling Graph Transformers with Expander Graphs applies the same idea of expander graphs as a sparse attention in Graph Transformers allowing them to scale to ogb-arxiv (170k nodes) Rethinking Knowledge Graph Evaluation Under the Open-World Assumption by Haotong Yang, Zhouchen Lin, Muhan Zhang. When evaluating KG link prediction tasks, there is no guarantee that the test set contains really all missing triples. The authors show that if there is an additional set of true triples (not labeled as true in the test), as small as 10% of the test set, MRR on the original test set only log-correlates with the MRR on the true test set. It means that if your model shows 40% MRR on the test set and you think it’s incomplete, chances are the true MRR can be much higher, you should inspect the top predictions as possibly new unlabeled true triples. Pre-training via Denoising for Molecular Property Prediction by Sheheryar Zaidi, Michael Schaarschmidt, and DeepMind team. The paper takes the NoisyNodes SSL objective to the next level (aka NoisyNodes on steroids). NoisyNodes takes a molecular graph with 3D coordinates, adds Gaussian noise to those 3D features, and asks to predict this noise as a loss term. NoisyNodes, as an auxiliary objective, was used in many OGB Large-Scale Challenge winning approaches, but now the authors study NoisyNodes as the sole pre-training SSL objective. Theory-wise, the authors find a link between denoising and score-matching (commonly used in generative diffusion models) and find that denoising helps to learn force fields. MPNN pre-trained on PCQM4Mv2 with this objective transfers well to QM9 and OC20 datasets and often outperforms fancier models like DimeNet++ and E(n)-GNN.