On dimensionality of feature vectors in MPNNs

2024/02/06 by César Bravo, Alexander Kozachinskiy, Bravo, César +3 · 3 citations
Computer Science · #FOS: Computer and information sciences #Fuzzy Logic and Control Systems #Machine Learning (cs.LG)

paper · pdf · doi:10.48550/arxiv.2402.03966

openalex publication_date 2024/02/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We revisit the classical result of Morris et al.~(AAAI'19) that message-passing graphs neural networks (MPNNs) are equal in their distinguishing power to the Weisfeiler--Leman (WL) isomorphism test. Morris et al.~show their simulation result with ReLU activation function and O(n)-dimensional feature vectors, where n is the number of nodes of the graph. By introducing randomness into the architecture, Aamand et al.~(NeurIPS'22) were able to improve this bound to O(log n)-dimensional feature vectors, again for ReLU activation, although at the expense of guaranteeing perfect simulation only with high probability. Recently, Amir et al.~(NeurIPS'23) have shown that for any non-polynomial analytic activation function, it is enough to use just 1-dimensional feature vectors. In this paper, we give a simple proof of the result of Amit et al.~and provide an independent experimental validation of it.

Cited by

• Message Passing on the Edge: Towards Scalable and Expressive GNNs
• On the (Non) Injectivity of Piecewise Linear Janossy Pooling
• Repetition Makes Perfect: Recurrent Graph Neural Networks Match Message-Passing Limit

Related

• 1-WL Expressiveness Is (Almost) All You Need
• Walk Message Passing Neural Networks and Second-Order Graph Neural Networks
• Fine-grained Expressivity of Graph Neural Networks
• A note on the VC dimension of 1-dimensional GNNs
• VC dimension of Graph Neural Networks with Pfaffian activation functions