Explainable, Stable, and Scalable Network Embedding Algorithms for Unsupervised Learning of Graph Representations

Network embedding that maps nodes in a graph to vectors in a Euclidean space is a very powerful method to address various tasks on a graph. However, most network embedding algorithms, in particular, graph neural networks (GNNs), are difficult to interpret and do not scale well to handle millions of nodes. In this article, we tackle the problem from a new perspective based on the equivalence of three constrained optimization problems: the network embedding problem, the trace maximization problem of the modularity matrix in a sampled graph, and the matrix factorization problem of the modularity matrix in a sampled graph. The optimal solutions to these three problems are the dominant eigenvectors of the modularity matrix. We propose two unsupervised learning algorithms that belong to a special class of graph convolutional networks (GCNs) for solving these problems: 1) Clustering As Feature Embedding (CAFE) and 2) Sphere. Both algorithms are stable trace maximization algorithms and yield good approximations of dominant eigenvectors. Moreover, there are linear-time implementations for sparse graphs. Various experiments are conducted to evaluate our algorithms and show that our proposed algorithms outperform several baseline methods.