Optimality of Message-Passing Architectures for Sparse Graphs

Understand

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-dimensional asymptotic regime, i.e., the dimension of the feature data is fixed while the number of nodes is large.

• Such graphs are typically known to be locally tree-like.
• We introduce a notion of Bayes optimality for node classification tasks, called asymptotic local Bayes optimality, and compute the optimal classifier according to this criterion for a fairly general statistical data model with arbitrary distributions of the node features and edge connectivity.
• The optimal classifier is implementable using a message-passing graph neural network architecture.