Learning distributed representations for nodes in graphs is a crucial primitive in network analysis with a wide spectrum of applications. Linear graph embedding methods learn such representations by optimizing the likelihood of both positive and negative edges while constraining the dimension of the embedding vectors. We argue that the generalization performance of these methods is not due to the dimensionality constraint as commonly believed, but rather the small norm of embedding vectors. Both theoretical and empirical evidence are provided to support this argument: (a) we prove that the generalization error of these methods can be bounded by limiting the norm of vectors, regardless of the embedding dimension; (b) we show that the generalization performance of linear graph embedding methods is correlated with the norm of embedding vectors, which is small due to the early stopping of SGD and the vanishing gradients. We performed extensive experiments to validate our analysis and showcased the importance of proper norm regularization in practice.
The manuscript proposes a theoretical bound on the generalization performance of learning graph embeddings. The authors find that the term in the generalization bound that represents the function complexity involves the norm of the learnt coordinates, based on which they argue that it is the norm of the coordinates that determines the success of the learnt representation.
I am not very familiar with the literature on graph embeddings; however, to the extent of my understanding of the paper, I have a number of concerns:
- In a generalization bound like in Theorem 1, it is very typical of the generalization error to include a term that represents the complexity of the hypothesis function class. In the presented result, this would be the second term on the rhs, which involves the spectral norm of the adjacency matrix and the bounds on the norm of the learnt coordinates. This term captures the Rademacher complexity of the hypothesis function class. In my understanding, there is nothing really surprising about this: most of the results in learning theory would include a term directly or indirectly related to some norm on the hypothesis function class. However, it would then require a lot of further justification to conclude that the key factor determining the performance is the norm of the learnt representation based on this.
- I am not sure if the results in Figure 1 provide a really meaningful justification about the importance of norm. It is observed that the norm increases during the epochs, however, shouldn’t we be also checking the evolution of the error at the same time to draw a meaningful conclusion? In particular, the norm seems to increase rather monotonically throughout the epochs, whereas we expect the error to decrease first, reach an optimal, and then start increasing due to overfitting. So can we really say that the error is proportional to the norm?
- Similarly, in the results in Figure 5, we can observe that the regularization coefficient has an optimal value that maximizes the precision. On the other hand, the norm of the learnt coordinates is expected to decrease monotonically with increasing lambda_r. Again, it seems difficult to conclude that the norm is the key factor determining the error.
- Minor comments: 
1. In page 2, in the expression of L, the node u should be in set V, I guess.
2. Please define the function sigma used in the objective functions. 
3. Typo right under Section 3 title: “grpah”
4. The definition of matrix A_sigma is not clear to me. What does the “there exists y” expression mean in the first line?
- To sum up, my feeling is that the presence of the term involving the norm in Theorem 1 is rather classical in learning theory, and its importance seems to be over-emphasized in this study. Moreover, I am not fully convinced about the experimental evidence. Therefore, I cannot recommend accepting this paper.