Mean-field theory of graph neural networks in graph partitioning
A theoretical performance analysis of the graph neural network (GNN) is presented. For classification tasks, the neural network approach has the advantage in terms of flexibility that it can be employed in a data-driven manner, whereas Bayesian inference requires the assumption of a specific model. A fundamental question is then whether GNN has a high accuracy in addition to this flexibility. Moreover, whether the achieved performance is predominately a result of the backpropagation or the architecture itself is a matter of considerable interest. To gain a better insight into these questions, a mean-field theory of a minimal GNN architecture is developed for the graph partitioning problem. This demonstrates a good agreement with numerical experiments.
A GNN (graph neural network) is a neural network whose input is a graph. This paper studies the problem of using a GNN to detect clusters in a graph drawn from the 2-groups SBM (stochastic block model: a popular model for random graphs with community structure).  Although it is already known how to optimally solve the SBM (i.e. find the hidden clusters), the GNN has the advantage of being a data-driven approach that does not rely on knowing the specific random model. Thus, it is of interest to analyze the performance of GNN on the SBM.  In the GNN architecture studied here, each layer has a node for each vertex in the graph. A node in the GNN is connected to its neighbors (according to the graph adjacency matrix) in the previous layer. Each node of the GNN stores a D-dimensional feature vector.  This paper analyzes the performance of an untrained GNN on the SBM. This means the GNN weights are chosen at random, the GNN runs in order to produce a D-dimensional feature vector for each vertex, and then these vectors are clustered via k-means in order to partition the vertices. The analysis is not rigorous but is a heuristic calculation based on the mean-field approximation from statistical physics. The derivation yields a conjectured threshold (depending on the SBM parameters) at which the GNN is able to detect the presence of clusters and obtain a partition that non-trivially correlates with the truth.  The authors include numerical experiments, showing that the analytically-derived threshold appears to agree reasonably well with the experimental performance of the untrained GNN. They also experimentally compare the untrained GNN with a trained one. They see that the training does not seem to significantly affect the detection threshold (at which point non-trivial recovery becomes possible) but training does significantly improve reconstruction accuracy once you're above the threshold.  I think that this paper constitutes a decent start to the rigorous study of GNN's but I'm unsure whether its contributions are enough to merit acceptance to NIPS. The results are somewhat modest because they only analyze the untrained GNN and the analysis is non-rigorous. Still, the result obtained seems to reasonably approximate the truth, and the experimental results of the paper are of value.  I suspect that the derivation in this paper may not quite give the correct result. To get a rigorously-correct (in the large-graph limit) analysis of the constant-degree SBM typically requires a self-consistency equation simliar to (7) whose state is an entire distribution (see e.g. https://arxiv.org/abs/1611.00814), whereas this paper seems to only keep track of the mean value and make a Gaussian approximation. Regardless, the computations in this paper are at least a crude approximation to the correct result.  EDIT: After reading the other reviews and the author feedback, I have changed my overall score from 5 to 6. The authors make a fair point that deriving a crude approximation to the threshold still has value. I still think it would be good to derive the exact expression for the threshold (in the large graph limit). I would suggest that the authors address whether they believe their derivation gives the exact threshold (it sounds like the answer is no?) and whether deriving the exact threshold (even non-rigorously) is within reach of established techniques from statistical physics (I suspect the answer should be yes). In any case, I have no objections to accepting the paper in its current form.