Encoder Embedding for General Graph and Node Classification
arXiv:2405.15473 · doi:10.1007/s41109-024-00678-4
Abstract
Graph encoder embedding, a recent technique for graph data, offers speed and scalability in producing vertex-level representations from binary graphs. In this paper, we extend the applicability of this method to a general graph model, which includes weighted graphs, distance matrices, and kernel matrices. We prove that the encoder embedding satisfies the law of large numbers and the central limit theorem on a per-observation basis. Under certain condition, it achieves asymptotic normality on a per-class basis, enabling optimal classification through discriminant analysis. These theoretical findings are validated through a series of experiments involving weighted graphs, as well as text and image data transformed into general graph representations using appropriate distance metrics.
16 pages
References in corpus (16)
- The structure and function of complex networks
- Community structure in social and biological networks
- A Comprehensive Survey on Graph Neural Networks
- DeepWalk: Online Learning of Social Representations
- Stochastic blockmodels and community structure in networks
- Structural Properties of the Caenorhabditis elegans Neuronal Network
- 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
- One-Hot Graph Encoder Embedding
- The Exact Equivalence of Distance and Kernel Methods for Hypothesis Testing
- Generalized Canonical Correlation Analysis for Classification
- Manifold Matching using Shortest-Path Distance and Joint Neighborhood Selection
- 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