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.

arXiv comment7 pages main + 7 pages appendix

References in corpus (11)

• Community structure in social and biological networks
• DeepWalk: Online Learning of Social Representations
• 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
• Spectral clustering and the high-dimensional stochastic blockmodel
• Consistency of community detection in networks under degree-corrected stochastic block models
• On a 'Two Truths' Phenomenon in Spectral Graph Clustering
• Subsampling bootstrap of count features of networks
• Universally consistent vertex classification for latent positions graphs
• Robust Vertex Classification

Cited by in corpus (9)

• 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
• Universally Consistent K-Sample Tests via Dependence Measures
• 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