5 papers
The Expressive Power of Random-Feature MPNNs Across Graph Sizes
Robert R. Nerem, Mitchell Black, Antonis Vasileiou +2
Continuous random node features increase the expressivity of message-passing neural networks (MPNNs), but existing theoretical analyses are not fine-grained enough to capture their…
Which Algorithms Can Graph Neural Networks Learn?
Solveig Wittig, Antonis Vasileiou, Robert R. Nerem +4
In recent years, there has been growing interest in understanding neural architectures' ability to learn to execute discrete algorithms, a line of work often referred to as neural…
Understanding Generalization in Node and Link Prediction
Antonis Vasileiou, Timo Stoll, Christopher Morris
Using message-passing graph neural networks (MPNNs) for node and link prediction is crucial in various scientific and industrial domains, which has led to the development of divers…
Covered Forest: Fine-grained generalization analysis of graph neural networks
Antonis Vasileiou, Ben Finkelshtein, Floris Geerts +2
The expressive power of message-passing graph neural networks (MPNNs) is reasonably well understood, primarily through combinatorial techniques from graph isomorphism testing. Howe…
Weisfeiler-Leman at the margin: When more expressivity matters
Billy J. Franks, Christopher Morris, Ameya Velingker +1
The Weisfeiler-Leman algorithm (-WL) is a well-studied heuristic for the graph isomorphism problem. Recently, the algorithm has played a prominent role in understanding the expr…