Post #837

GraphML News (April 20th) - Near-Linear Min Cut, New blog posts, scaling GNNs LLaMa 3 dominated the ML media this week but let’s try to see through it to find some graph gems. ✂️ Google Research published a new blog post on the recently proposed near-linear min-cut algorithm for weighted graphs. Existing near-linear algorithms are either randomized or work on rather simple graphs. In contrast, the proposed algorithm is deterministic and supports weighted graphs. The key points of the devised approach: (1) the observation that cuts likely won’t change if we sparsify the graph a bit; (2) min-cuts must have low graph conductance), hence partitioning algorithms (producing well-connected clusters) might be approximately consistent with min-cuts; (3) the theory is actually applicable to weighted graphs. The work received the best paper at SODA’24 👏 🌊 Tor Fjelde, Emile Mathieu and Vincent Dutordoir released an insightful introduction to flow matching starting from the basics of conditional normalizing flows up to the most recent stochastic interpolants and mini-batch optimal transport coupling. We are a little late to the party (the post dates to January) but it’s never too late to catch up with generative modeling and flow matching. On the Scalability of GNNs for Molecular Graphs by Maciej Sypetkowski, Frederik Wenkel, and Valence / Mila folks - one of the first in-depth studies of scaling GNNs and Transformers for molecular tasks. In particular, they trained modified versions of MPNN, GPS, and vanilla Transformer models (with structural encodings of course) varying the size from 1M to 1B parameters on the LargeMix dataset of 5M molecules. Scaling does improve pretraining and downstream performance of all models but there is a clear signal that pre-training dataset size is not enough - experiments on the UltraLarge dataset with 83M molecules are likely in the works. Weekend reading: HelixFold-Multimer: Elevating Protein Complex Structure Prediction to New Heights by Xiaomin Fang and Baidu - a contender to AlphaFold 2.3 showing strong results on antibody-antigen and nanobody-antigen docking. Graph Reinforcement Learning for Combinatorial Optimization: A Survey and Unifying Perspective by Victor-Alexandru Darvariu and UCL VN-EGNN: E(3)-Equivariant Graph Neural Networks with Virtual Nodes Enhance Protein Binding Site Identification by Florian Sestak and ELLIS Linz - virtual nodes encode representations of the whole binding site