Detection of Model-based Planted Pseudo-cliques in Random Dot Product Graphs by the Adjacency Spectral Embedding and the Graph Encoder Embedding
Not on the map. Why?
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.
Key facts. Cited by 1 paper 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
52 of 132 references.
References · 52
- 2016Variational Graph Auto-Encoderscited by 1,382
- 2018From Louvain to Leiden: guaranteeing well-connected communitiescited by 385
- 2017Statistical inference on random dot product graphs: a surveycited by 70
- 2017A statistical interpretation of spectral embedding: the generalised random dot product graphcited by 55
- 2014Graph Matching: Relax at Your Own Riskcited by 27
- 2018On a 'Two Truths' Phenomenon in Spectral Graph Clusteringcited by 24
- 2013Perfect Clustering for Stochastic Blockmodel Graphs via Adjacency Spectral Embeddingcited by 23
- 2015Community Detection and Classification in Hierarchical Stochastic Blockmodelscited by 23
- 2014Computational Lower Bounds for Community Detection on Random Graphscited by 22
- 2013Seeded graph matching for correlated ErdHos-R'enyi graphscited by 20
- 2016Limit theorems for eigenvectors of the normalized Laplacian for random graphscited by 17
- 2021One-Hot Graph Encoder Embeddingcited by 16
38 more
- 2013Vertex nomination schemes for membership predictioncited by 8
- 2016Information Recovery in Shuffled Graphs via Graph Matchingcited by 8
- 2023Graph Encoder Ensemble for Simultaneous Vertex Embedding and Community Detectioncited by 8
- 2019Vertex Nomination, Consistent Estimation, and Adversarial Modificationcited by 7
- 2018Vertex nomination: The canonical sampling and the extended spectral nomination schemescited by 6
- 2018Matched Filters for Noisy Induced Subgraph Detectioncited by 6
- 2018Maximum Likelihood Estimation and Graph Matching in Errorfully Observed Networkscited by 6
- 2020Multiple Network Embedding for Anomaly Detection in Time Series of Graphscited by 6
- 2013Spectral Clustering for Divide-and-Conquer Graph Matchingcited by 5
- 2014Seeded Graph Matching Via Joint Optimization of Fidelity and Commensurabilitycited by 5
- 2015Scalable Out-of-Sample Extension of Graph Embeddings Using Deep Neural Networkscited by 5
- 2017Vertex Nomination Via Seeded Graph Matchingcited by 5
- 2017Semiparametric spectral modeling of the Drosophila connectomecited by 5
- 2020The Importance of Being Correlated: Implications of Dependence in Joint Spectral Inference across Multiple Networkscited by 5
- 2020The Strongish Planted Clique Hypothesis and Its Consequencescited by 5
- 2021Hypothesis Testing for Equality of Latent Positions in Random Graphscited by 5
- 2013The blessing of transitivity in sparse and stochastic networkscited by 4
- 2016Connectome Smoothing via Low-rank Approximationscited by 4
- 2017On consistent vertex nomination schemescited by 4
- 2020A Simple Spectral Failure Mode for Graph Convolutional Networkscited by 4
- 2021The Phantom Alignment Strength Conjecture: Practical use of graph matching alignment strength to indicate a meaningful graph matchcited by 4
- 2013Community Detection in Random Networkscited by 3
- 2014A Spectral Framework for Anomalous Subgraph Detectioncited by 3
- 2016Laplacian Eigenmaps from Sparse, Noisy Similarity Measurementscited by 3
- 2016On the Consistency of the Likelihood Maximization Vertex Nomination Scheme: Bridging the Gap Between Maximum Likelihood Estimation and Graph Matchingcited by 3
- 2019Flowless: Extracting Densest Subgraphs Without Flow Computationscited by 3
- 2020Graph matching between bipartite and unipartite networks: to collapse, or not to collapse, that is the questioncited by 3
- 2020Vertex nomination between graphs via spectral embedding and quadratic programmingcited by 3
- 2022Lost in the Shuffle: Testing Power in the Presence of Errorful Network Vertex Labelscited by 3
- 2015Fast Embedding for JOFC Using the Raw Stress Criterioncited by 2
- 2018Unseeded low-rank graph matching by transform-based unsupervised point registrationcited by 2
- 2019Multiplex graph matching matched filterscited by 2
- 2021Leveraging semantically similar queries for ranking via combining representationscited by 2
- 2022Clustered Graph Matching for Label Recovery and Graph Classificationcited by 2
- 2020On a complete and sufficient statistic for the correlated Bernoulli random graph modelcited by 1
- 2021Subgraph nomination: Query by Example Subgraph Retrieval in Networkscited by 1
- 2022Concentration inequalities for correlated network-valued processes with applications to community estimation and changepoint analysiscited by 1
- 2023On seeded subgraph-to-subgraph matching: The ssSGM Algorithm and matchability information theorycited by 1
50 most cited of 52 All 52 (JSON)
Built on by
Citing papers per year: 2026: 1.
1 paper.