7 papers
Random Probing for Structural Self-Interactions in Graph Neural Networks
Saku Peltonen, H. Çağrı Bilgi, Kubilay Atasu
Graph Neural Networks (GNNs) fundamentally lack the ability to capture structural properties defined by node self-interactions, such as cycle counts, subgraph centrality, and heat…
Autoregressive Frontier Expansion: Growing Trees with Graph Machine Learning
Umer Gupta, Saku Peltonen, Martin Ritzert
Tree-like branching structures are common in nature, from botanical trees to neurons, blood vessels and respiratory trees. Their branching shape often reflects function, making str…
GraphARC: A Comprehensive Benchmark for Graph-Based Abstract Reasoning
Saku Peltonen, August Bøgh Rønberg, Andreas Plesner +1
Relational reasoning lies at the heart of intelligence, but existing benchmarks are typically confined to formats such as grids or text. We introduce GraphARC, a benchmark for abst…
From Message-Passing to Linearized Graph Sequence Models
Joël Mathys, Basil Rohner, Saku Peltonen +1
Message-passing based approaches form the default backbone of most learning architectures on graph-structured data. However, the rapid progress of modern deep learning architecture…
On the Expressive Power of GNNs for Boolean Satisfiability
Saku Peltonen, Roger Wattenhofer
Machine learning approaches to solving Boolean Satisfiability (SAT) aim to replace handcrafted heuristics with learning-based models. Graph Neural Networks have emerged as the main…
Distributed Lovász Local Lemma under Bandwidth Limitations
Magnús M. Halldórsson, Yannic Maus, Saku Peltonen
The constructive Lovász Local Lemma has become a central tool for designing efficient distributed algorithms. While it has been extensively studied in the classic LOCAL model that…
Distributed Symmetry Breaking on Power Graphs via Sparsification
Yannic Maus, Saku Peltonen, Jara Uitto
In this paper, we present efficient distributed algorithms for classical symmetry breaking problems, maximal independent sets (MIS) and ruling sets, in power graphs. We work in the…