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. Graphs have long been considered as one of the most fundamental structures that can naturally represent interactions between numerous real-life objects (e.g., the Web, social networks, proteinprotein interaction networks). Graph embedding, whose goal is to learn distributed representations for nodes while preserving the structure of the given graph, is a fundamental problem in network analysis that underpins many applications. A handful of graph embedding techniques have been proposed in recent years BID10 BID15 BID2 , along with impressive results in applications like link prediction, text classification BID14 , and gene function prediction BID18 .Linear graph embedding methods preserve graph structures by converting the inner products of the node embeddings into probability distributions with a softmax function BID10 BID15 BID2 . Since the exact softmax objective is computationally expensive to optimize, the negative sampling technique BID8 is often used in these methods: instead of optimizing the softmax objective function, we try to maximize the probability of positive instances while minimizing the probability of some randomly sampled negative instances. It has been shown that by using this negative sampling technique, these graph embedding methods are essentially computing a factorization of the adjacency (or proximity) matrix of graph BID7 . Hence, it is commonly believed that the key to the generalization performance of these methods is the dimensionality constraint.However, in this paper we argue that the key factor to the good generalization of these embedding methods is not the dimensionality constraint, but rather the small norm of embedding vectors. We provide both theoretical and empirical evidence to support this argument:• Theoretically, we analyze the generalization error of two linear graph embedding hypothesis spaces (restricting embedding dimension/norm), and show that only the norm-restricted hypothesis class can theoretically guarantee good generalization in typical parameter settings.• Empirically , we show that the success of existing linear graph embedding methods BID10 BID15 BID2 are due to the early stopping of stochastic gradient descent (SGD), which implicitly restricts the norm of embedding vectors. Furthermore, with prolonged SGD execution and no proper norm regularization, the embedding vectors can severely overfit the training data. So far, we have seen many pieces of evidence supporting our argument, suggesting that the generalization of embedding vectors in linear graph embedding is determined by the vector norm. Intuitively, it means that these embedding methods are trying to embed the vertices onto a small sphere centered around the origin point. The radius of the sphere controls the model capacity, and choosing proper embedding dimension allows us to control the trade-off between the expressive power of the model and the computation efficiency.Note that the connection between norm regularization and generalization performance is actually very intuitive. To see this, let us consider the semantic meaning of embedding vectors: the probability of any particular edge (u, v) being positive is equal to DISPLAYFORM0 As we can see, this probability value is determined by three factors: DISPLAYFORM1 , the cosine similarity between x u and x v , evaluates the degree of agreement between the directions of x u and x v .• ||x u || 2 and ||x v || 2 on the other hand, reflects the degree of confidence we have regarding the embedding vectors of u and v.Therefore, by restricting the norm of embedding vectors, we are limiting the confidence level that we have regarding the embedding vectors, which is indeed intuitively helpful for preventing overfitting.It is worth noting that our results in this paper do not invalidate the analysis of BID7 , but rather clarifies on some key points: as pointed out by BID7 , linear graph embedding methods are indeed approximating the factorization of PMI matrices. However , as we have seen in this paper, the embedding vectors are primarily constrained by their norm instead of embedding dimension, which implies that the resulting factorization is not really a standard low-rank one, but rather a low-norm factorization: DISPLAYFORM2 The low-norm factorization represents an interesting alternative to the standard low-rank factorization, and our current understanding of such factorization is still very limited. Given the empirical success of linear graph embedding methods, it would be really helpful if we can have a more in-depth analysis of such factorization, to deepen our understanding and potentially inspire new algorithms. We have shown that the generalization of linear graph embedding methods are not determined by the dimensionality constraint but rather the norm of embedding vectors. We proved that limiting the norm of embedding vectors would lead to good generalization, and showed that the generalization of existing linear graph embedding methods is due to the early stopping of SGD and vanishing gradients. We experimentally investigated the impact embedding dimension choice, and demonstrated that such choice only matters when there is no norm regularization. In most cases, the best generalization performance is obtained by choosing the optimal value for the norm regularization coefficient, and in such case the impact of embedding dimension case is negligible. Our findings combined with the analysis of BID7 suggest that linear graph embedding methods are probably computing a low-norm factorization of the PMI matrix, which is an interesting alternative to the standard low-rank factorization and calls for further study.
We argue that the generalization of linear graph embedding is not due to the dimensionality constraint but rather the small norm of embedding vectors. The authors show that the generalization error of linear graph embedding methods is bounded by the norm of embedding vectors rather than dimensionality constraints The authors propose a theoretical bound on the generalization performance of learning graph embeddings and argue that the norm of the coordinates determines the success of the learnt representation.