Abstract
We study the node classification problem on feature-decorated graphs in thesparse setting, i.e., when the expected degree of a node is $O(1)$ in thenumber of nodes. Such graphs are typically known to be locally tree-like. Weintroduce a notion of Bayes optimality for node classification tasks, calledasymptotic local Bayes optimality, and compute the optimal classifier accordingto this criterion for a fairly general statistical data model with arbitrarydistributions of the node features and edge connectivity. The optimalclassifier is implementable using a message-passing graph neural networkarchitecture. We then compute the generalization error of this classifier andcompare its performance against existing learning methods theoretically on awell-studied statistical model with naturally identifiable signal-to-noiseratios (SNRs) in the data. We find that the optimal message-passingarchitecture interpolates between a standard MLP in the regime of low graphsignal and a typical convolution in the regime of high graph signal.Furthermore, we prove a corresponding non-asymptotic result.