  The fundamental principle of Graph Neural Networks (GNNs) is to exploit the
structural information of the data by aggregating the neighboring nodes using a
`graph convolution' in conjunction with a suitable choice for the network
architecture, such as depth and activation functions. Therefore, understanding
the influence of each of the design choice on the network performance is
crucial. Convolutions based on graph Laplacian have emerged as the dominant
choice with the symmetric normalization of the adjacency matrix as the most
widely adopted one. However, some empirical studies show that row normalization
of the adjacency matrix outperforms it in node classification. Despite the
widespread use of GNNs, there is no rigorous theoretical study on the
representation power of these convolutions, that could explain this behavior.
Similarly, the empirical observation of the linear GNNs performance being on
par with non-linear ReLU GNNs lacks rigorous theory.
  In this work, we theoretically analyze the influence of different aspects of
the GNN architecture using the Graph Neural Tangent Kernel in a semi-supervised
node classification setting. Under the population Degree Corrected Stochastic
Block Model, we prove that: (i) linear networks capture the class information
as good as ReLU networks; (ii) row normalization preserves the underlying class
structure better than other convolutions; (iii) performance degrades with
network depth due to over-smoothing, but the loss in class information is the
slowest in row normalization; (iv) skip connections retain the class
information even at infinite depth, thereby eliminating over-smoothing. We
finally validate our theoretical findings numerically and on real datasets such
as Cora and Citeseer.
