One-Hot Graph Encoder Embedding

Abstract

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.

7 pages main + 7 pages appendix

References in corpus (3)

• Finding community structure in networks using the eigenvectors of matrices
• Measuring and testing dependence by correlation of distances
• Stochastic blockmodels and community structure in networks

Cited by in corpus (8)

• Discovering Communication Pattern Shifts in Large-Scale Labeled Networks using Encoder Embedding and Vertex Dynamics
• Graph Encoder Ensemble for Simultaneous Vertex Embedding and Community Detection
• Synergistic Graph Fusion via Encoder Embedding
• Encoder Embedding for General Graph and Node Classification
• Refined Graph Encoder Embedding via Self-Training and Latent Community Recovery
• Fast and Scalable Multi-Kernel Encoder Classifier
• Graph Transformer with Disease Subgraph Positional Encoding for Improved Comorbidity Prediction
• Efficient Graph Encoder Embedding for Large Sparse Graphs in Python