# Principal Graph Encoder Embedding and Principal Community Detection

arXiv: https://arxiv.org/abs/2501.14939 · HTML: https://mlsanity.com/paper/2501.14939/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 50 references that are in the map.
- First posted on arXiv 24 Jan 2025.

## Builds on (most cited first, 22 of 22)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [node2vec: Scalable Feature Learning for Networks](https://mlsanity.com/paper/1607.00653/) (2016)
- [Graph Neural Networks: A Review of Methods and Applications](https://mlsanity.com/paper/1812.08434/) (2018)
- [Variational Graph Auto-Encoders](https://mlsanity.com/paper/1611.07308/) (2016)
- [FastGCN: Fast Learning with Graph Convolutional Networks via Importance Sampling](https://mlsanity.com/paper/1801.10247/) (2018)
- [From Louvain to Leiden: guaranteeing well-connected communities](https://mlsanity.com/paper/1810.08473/) (2018)
- [Combining Label Propagation and Simple Models Out-performs Graph Neural Networks](https://mlsanity.com/paper/2010.13993/) (2020)
- [What Can Neural Networks Reason About?](https://mlsanity.com/paper/1905.13211/) (2019)
- [Statistical inference on random dot product graphs: a survey](https://mlsanity.com/paper/1709.05454/) (2017)
- [Inference for multiple heterogeneous networks with a common invariant subspace](https://mlsanity.com/paper/1906.10026/) (2019)
- [On a 'Two Truths' Phenomenon in Spectral Graph Clustering](https://mlsanity.com/paper/1808.07801/) (2018)
- [One-Hot Graph Encoder Embedding](https://mlsanity.com/paper/2109.13098/) (2021)
- [GraSPy: Graph Statistics in Python](https://mlsanity.com/paper/1904.05329/) (2019)
- [Spectral embedding for dynamic networks with stability guarantees](https://mlsanity.com/paper/2106.01282/) (2021)
- [Graph Encoder Ensemble for Simultaneous Vertex Embedding and Community Detection](https://mlsanity.com/paper/2301.11290/) (2023)
- [Synergistic Graph Fusion via Encoder Embedding](https://mlsanity.com/paper/2303.18051/) (2023)
- [Discovering Communication Pattern Shifts in Large-Scale Labeled Networks using Encoder Embedding and Vertex Dynamics](https://mlsanity.com/paper/2305.02381/) (2023)
- [Refined Graph Encoder Embedding via Self-Training and Latent Community Recovery](https://mlsanity.com/paper/2405.12797/) (2024)
- [Community Correlations and Testing Independence Between Binary Graphs](https://mlsanity.com/paper/1906.03661/) (2019)
- [A Simple Spectral Failure Mode for Graph Convolutional Networks](https://mlsanity.com/paper/2010.13152/) (2020)
- [Encoder Embedding for General Graph and Node Classification](https://mlsanity.com/paper/2405.15473/) (2024)

## Built on by (most cited first, 2 of 2)

- [A Graph Sufficiency Perspective for Neural Networks](https://mlsanity.com/paper/2507.10215/) (2025)
- [Graph Neural Networks Powered by Encoder Embedding for Improved Node Learning](https://mlsanity.com/paper/2507.11732/) (2025)

## Abstract (arXiv)

In this paper, we introduce the concept of principal communities and propose a principal graph encoder embedding method that concurrently detects these communities and achieves vertex embedding. Given a graph adjacency matrix with vertex labels, the method computes a sample community score for each community, ranking them to measure community importance and estimate a set of principal communities. The method then produces a vertex embedding by retaining only the dimensions corresponding to these principal communities. Theoretically, we define the population version of the encoder embedding and the community score based on a random Bernoulli graph distribution. We prove that the population principal graph encoder embedding preserves the conditional density of the vertex labels and that the population community score successfully distinguishes the principal communities. We conduct a variety of simulations to demonstrate the finite-sample accuracy in detecting ground-truth principal communities, as well as the advantages in embedding visualization and subsequent vertex classification. The method is further applied to a set of real-world graphs, showcasing its numerical advantages, including robustness to label noise and computational scalability.