On the Computational Capability of Graph Neural Networks: A Circuit Complexity Bound Perspective

Xiaoyu Li, Yingyu Liang, Zhenmei Shi +3

Graph Neural Networks (GNNs) have become the standard approach for learning and reasoning over relational data, leveraging the message-passing mechanism that iteratively propagates…