One-Hot Graph Encoder Embedding
This provides an efficient solution for processing massive graphs, though it appears incremental as a transformation of spectral embedding.
The paper introduces one-hot graph encoder embedding, a fast graph embedding method with linear computational complexity that can process billions of edges in minutes on a standard PC, and demonstrates its computational advantages in vertex classification, clustering, and graph bootstrap applications.
In this paper we propose a lightning fast graph embedding method called one-hot graph encoder embedding. It has a linear computational complexity and the capacity to process billions of edges within minutes on standard PC -- making it an ideal candidate for huge graph processing. It is applicable to either adjacency matrix or graph Laplacian, and can be viewed as a transformation of the spectral embedding. Under random graph models, the graph encoder embedding is approximately normally distributed per vertex, and asymptotically converges to its mean. We showcase three applications: vertex classification, vertex clustering, and graph bootstrap. In every case, the graph encoder embedding exhibits unrivalled computational advantages.