# Detection of Model-based Planted Pseudo-cliques in Random Dot Product Graphs by the Adjacency Spectral Embedding and the Graph Encoder Embedding

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 52 of its 132 references that are in the map.
- First posted on arXiv 18 Dec 2023.

## Builds on (most cited first, 30 of 52)

- [Variational Graph Auto-Encoders](https://mlsanity.com/paper/1611.07308/) (2016)
- [From Louvain to Leiden: guaranteeing well-connected communities](https://mlsanity.com/paper/1810.08473/) (2018)
- [Statistical inference on random dot product graphs: a survey](https://mlsanity.com/paper/1709.05454/) (2017)
- [A statistical interpretation of spectral embedding: the generalised random dot product graph](https://mlsanity.com/paper/1709.05506/) (2017)
- [Graph Matching: Relax at Your Own Risk](https://mlsanity.com/paper/1405.3133/) (2014)
- [On a 'Two Truths' Phenomenon in Spectral Graph Clustering](https://mlsanity.com/paper/1808.07801/) (2018)
- [Perfect Clustering for Stochastic Blockmodel Graphs via Adjacency Spectral Embedding](https://mlsanity.com/paper/1310.0532/) (2013)
- [Community Detection and Classification in Hierarchical Stochastic Blockmodels](https://mlsanity.com/paper/1503.02115/) (2015)
- [Computational Lower Bounds for Community Detection on Random Graphs](https://mlsanity.com/paper/1406.6625/) (2014)
- [Seeded graph matching for correlated ErdHos-R'enyi graphs](https://mlsanity.com/paper/1304.7844/) (2013)
- [Limit theorems for eigenvectors of the normalized Laplacian for random graphs](https://mlsanity.com/paper/1607.08601/) (2016)
- [One-Hot Graph Encoder Embedding](https://mlsanity.com/paper/2109.13098/) (2021)
- [Vertex nomination schemes for membership prediction](https://mlsanity.com/paper/1312.2638/) (2013)
- [Information Recovery in Shuffled Graphs via Graph Matching](https://mlsanity.com/paper/1605.02315/) (2016)
- [Graph Encoder Ensemble for Simultaneous Vertex Embedding and Community Detection](https://mlsanity.com/paper/2301.11290/) (2023)
- [Vertex Nomination, Consistent Estimation, and Adversarial Modification](https://mlsanity.com/paper/1905.01776/) (2019)
- [Vertex nomination: The canonical sampling and the extended spectral nomination schemes](https://mlsanity.com/paper/1802.04960/) (2018)
- [Matched Filters for Noisy Induced Subgraph Detection](https://mlsanity.com/paper/1803.02423/) (2018)
- [Maximum Likelihood Estimation and Graph Matching in Errorfully Observed Networks](https://mlsanity.com/paper/1812.10519/) (2018)
- [Multiple Network Embedding for Anomaly Detection in Time Series of Graphs](https://mlsanity.com/paper/2008.10055/) (2020)
- [Spectral Clustering for Divide-and-Conquer Graph Matching](https://mlsanity.com/paper/1310.1297/) (2013)
- [Seeded Graph Matching Via Joint Optimization of Fidelity and Commensurability](https://mlsanity.com/paper/1401.3813/) (2014)
- [Scalable Out-of-Sample Extension of Graph Embeddings Using Deep Neural Networks](https://mlsanity.com/paper/1508.04422/) (2015)
- [Vertex Nomination Via Seeded Graph Matching](https://mlsanity.com/paper/1705.00674/) (2017)
- [Semiparametric spectral modeling of the Drosophila connectome](https://mlsanity.com/paper/1705.03297/) (2017)
- [The Importance of Being Correlated: Implications of Dependence in Joint Spectral Inference across Multiple Networks](https://mlsanity.com/paper/2008.00163/) (2020)
- [The Strongish Planted Clique Hypothesis and Its Consequences](https://mlsanity.com/paper/2011.05555/) (2020)
- [Hypothesis Testing for Equality of Latent Positions in Random Graphs](https://mlsanity.com/paper/2105.10838/) (2021)
- [The blessing of transitivity in sparse and stochastic networks](https://mlsanity.com/paper/1307.2302/) (2013)
- [Connectome Smoothing via Low-rank Approximations](https://mlsanity.com/paper/1609.01672/) (2016)

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

- [A Subsampled Davis-Kahan Bound for Large-Scale Eigenspace Estimation](https://mlsanity.com/paper/2609.09211/) (2026)

## Abstract (arXiv)

In this paper, we explore the capability of both the Adjacency Spectral Embedding (ASE) and the Graph Encoder Embedding (GEE) for capturing an embedded pseudo-clique structure in the random dot product graph setting. In both theory and experiments, we demonstrate that, in the absence of additional clean (i.e., without the implanted pseudo-clique) network data, this pairing of model and methods can yield worse results than the best existing spectral clique detection methods. However, these methods can be used to asymptotically localize the pseudo-cliques if additional clean, independent network data is provided. This demonstrates at once the methods' potential ability/inability to capture modestly sized pseudo-cliques and the methods' robustness to the model contamination giving rise to the pseudo-clique structure. To further enrich our analysis, we also consider the Variational Graph Auto-Encoder (VGAE) model in our simulation and real data experiments.