Optimality of Message-Passing Architectures for Sparse Graphs

Aseem Baranwal, Kimon Fountoulakis, Aukosh Jagannath

We study the node classification problem on feature-decorated graphs in the sparse setting, i.e., when the expected degree of a node is $O(1)$ in the number of nodes, in the fixed-…