Portrait of Petar Veličković is unavailable

Petar Veličković

Alumni

Publications

Asynchronous Algorithmic Alignment with Cocycles
Andrew Joseph Dudzik
Tamara von Glehn
Razvan Pascanu
Petar Veličković
State-of-the-art neural algorithmic reasoners make use of message passing in graph neural networks (GNNs). But typical GNNs blur the distinc… (see more)tion between the definition and invocation of the message function, forcing a node to send messages to its neighbours at every layer, synchronously. When applying GNNs to learn to execute dynamic programming algorithms, however, on most steps only a handful of the nodes would have meaningful updates to send. One, hence, runs the risk of inefficiencies by sending too much irrelevant data across the graph. But more importantly, many intermediate GNN steps have to learn the identity functions, which is a non-trivial learning problem. In this work, we explicitly separate the concepts of node state update and message function invocation. With this separation, we obtain a mathematical formulation that allows us to reason about asynchronous computation in both algorithms and neural networks. Our analysis yields several practical implementations of synchronous scalable GNN layers that are provably invariant under various forms of asynchrony.
2024-04-17
Proceedings of the Second Learning on Graphs Conference (published)
doi.org
arxiv.org
Latent Space Representations of Neural Algorithmic Reasoners
Vladimir V. Mirjani'c
Razvan Pascanu
Petar Velivckovi'c University of Cambridge
Petar Veličković
Google Deepmind
Neural Algorithmic Reasoning (NAR) is a research area focused on designing neural architectures that can reliably capture classical computat… (see more)ion, usually by learning to execute algorithms. A typical approach is to rely on Graph Neural Network (GNN) architectures, which encode inputs in high-dimensional latent spaces that are repeatedly transformed during the execution of the algorithm. In this work we perform a detailed analysis of the structure of the latent space induced by the GNN when executing algorithms. We identify two possible failure modes: (i) loss of resolution, making it hard to distinguish similar values; (ii) inability to deal with values outside the range observed during training. We propose to solve the first issue by relying on a softmax aggregator, and propose to decay the latent space in order to deal with out-of-range values. We show that these changes lead to improvements on the majority of algorithms in the standard CLRS-30 benchmark when using the state-of-the-art Triplet-GMPNN processor. Our code is available at https://github.com/mirjanic/nar-latent-spaces
2024-04-17
Proceedings of the Second Learning on Graphs Conference (published)
doi.org
arxiv.org
softmax is not enough (for sharp out-of-distribution)
Petar Veličković
Christos Perivolaropoulos
Federico Barbero
Razvan Pascanu
A key property of reasoning systems is the ability to make sharp decisions on their input data. For contemporary AI systems, a key carrier o… (see more)f sharp behaviour is the softmax function, with its capability to perform differentiable query-key lookups. It is a common belief that the predictive power of networks leveraging softmax arises from "circuits" which sharply perform certain kinds of computations consistently across many diverse inputs. However, for these circuits to be robust, they would need to generalise well to arbitrary valid inputs. In this paper, we dispel this myth: even for tasks as simple as finding the maximum key, any learned circuitry must disperse as the number of items grows at test time. We attribute this to a fundamental limitation of the softmax function to robustly approximate sharp functions, prove this phenomenon theoretically, and propose adaptive temperature as an ad-hoc technique for improving the sharpness of softmax at inference time.
2024-01-01
arXiv.org (preprint)
doi.org
arxiv.org
Finding Increasingly Large Extremal Graphs with AlphaZero and Tabu Search
Abbas Mehrabian
Ankit Anand
Hyunjik Kim
Nicolas Sonnerat
Matej Balog
Gheorghe Comanici
Tudor Berariu
Andrew Lee
Anian Ruoss
Anna Bulanova
Daniel Toyama
Sam Blackwell
Bernardino Romera Paredes
Petar Veličković
Laurent Orseau
Joonkyung Lee
Anurag Murty Naredla
Doina Precup
Adam Zsolt Wagner
2023-10-27
NeurIPS.cc/2023/Workshop/MATH-AI (poster)
doi.org
openreview.net
Scientific discovery in the age of artificial intelligence
Hanchen Wang
Tianfan Fu
Yuanqi Du
Wenhao Gao
Kexin Huang
Ziming Liu
Payal Chandak
Shengchao Liu
Peter Van Katwyk
Andreea Deac
Animashree Anandkumar
K. Bergen
Carla P. Gomes
Shirley Ho
Pushmeet Kohli
Joan Lasenby
Jure Leskovec
Tie-Yan Liu
A. Manrai
Debora Susan Marks … (see 10 more)
Bharath Ramsundar
Le Song
Jimeng Sun
Jian Tang
Petar Veličković
Max Welling
Linfeng Zhang
Connor Wilson. Coley
Yoshua Bengio
Marinka Žitnik
2023-08-01
Nature (published)
doi.org
Principal Neighbourhood Aggregation for Graph Nets
Gabriele Corso
Luca Cavalleri
Dominique Beaini
Pietro Lio
Petar Veličković
arxiv.org
Deep Graph Infomax
Petar Veličković
William Fedus
William L. Hamilton
Pietro Lio
Yoshua Bengio
(Rex) Devon Hjelm
We present Deep Graph Infomax (DGI), a general approach for learning node representations within graph-structured data in an unsupervised ma… (see more)nner. DGI relies on maximizing mutual information between patch representations and corresponding high-level summaries of graphs---both derived using established graph convolutional network architectures. The learnt patch representations summarize subgraphs centered around nodes of interest, and can thus be reused for downstream node-wise learning tasks. In contrast to most prior approaches to unsupervised learning with GCNs, DGI does not rely on random walk objectives, and is readily applicable to both transductive and inductive learning setups. We demonstrate competitive performance on a variety of node classification benchmarks, which at times even exceeds the performance of supervised learning.
2019-01-01
ICLR.cc/2019/Conference (poster)
openreview.net
openreview.net
Deep Graph Infomax
Petar Veličković
William Fedus
William L. Hamilton
Pietro Lio
Yoshua Bengio
(Rex) Devon Hjelm
We present Deep Graph Infomax (DGI), a general approach for learning node representations within graph-structured data in an unsupervised ma… (see more)nner. DGI relies on maximizing mutual information between patch representations and corresponding high-level summaries of graphs---both derived using established graph convolutional network architectures. The learnt patch representations summarize subgraphs centered around nodes of interest, and can thus be reused for downstream node-wise learning tasks. In contrast to most prior approaches to unsupervised learning with GCNs, DGI does not rely on random walk objectives, and is readily applicable to both transductive and inductive learning setups. We demonstrate competitive performance on a variety of node classification benchmarks, which at times even exceeds the performance of supervised learning.
2019-01-01
ICLR (Poster) (published)
arxiv.org
arxiv.org
Deep Graph Infomax
Petar Veličković
William Fedus
William L. Hamilton
Pietro Lio
Yoshua Bengio
(Rex) Devon Hjelm
2018-09-27
ArXiv (preprint)
arxiv.org
arxiv.org
Deep Graph Infomax
Petar Veličković
William Fedus
William L. Hamilton
Pietro Lio
Yoshua Bengio
(Rex) Devon Hjelm
2018-09-27
ArXiv (preprint)
arxiv.org
arxiv.org
Deep Graph Infomax
Petar Veličković
William Fedus
William L. Hamilton
Pietro Lio
Yoshua Bengio
(Rex) Devon Hjelm
We present Deep Graph Infomax (DGI), a general approach for learning node representations within graph-structured data in an unsupervised ma… (see more)nner. DGI relies on maximizing mutual information between patch representations and corresponding high-level summaries of graphs---both derived using established graph convolutional network architectures. The learnt patch representations summarize subgraphs centered around nodes of interest, and can thus be reused for downstream node-wise learning tasks. In contrast to most prior approaches to unsupervised learning with GCNs, DGI does not rely on random walk objectives, and is readily applicable to both transductive and inductive learning setups. We demonstrate competitive performance on a variety of node classification benchmarks, which at times even exceeds the performance of supervised learning.
2018-09-27
ArXiv (preprint)
arxiv.org
arxiv.org
Deep Graph Infomax
Petar Veličković
William Fedus
William L. Hamilton
Pietro Lio
Yoshua Bengio
(Rex) Devon Hjelm
We present Deep Graph Infomax (DGI), a general approach for learning node representations within graph-structured data in an unsupervised ma… (see more)nner. DGI relies on maximizing mutual information between patch representations and corresponding high-level summaries of graphs---both derived using established graph convolutional network architectures. The learnt patch representations summarize subgraphs centered around nodes of interest, and can thus be reused for downstream node-wise learning tasks. In contrast to most prior approaches to unsupervised learning with GCNs, DGI does not rely on random walk objectives, and is readily applicable to both transductive and inductive learning setups. We demonstrate competitive performance on a variety of node classification benchmarks, which at times even exceeds the performance of supervised learning.
2018-09-27
ArXiv (preprint)
arxiv.org
arxiv.org