Detection of Model-Based Planted Pseudo-Cliques in Random Dot Product Graphs by the Adjacency Spectral Embedding and...

Area of Science:

• Graph theory
• Network analysis
• Machine learning

Background:

• Pseudo-cliques are substructures in networks that can indicate community formation or anomalies.
• Random dot product graphs are a generative model used to study network properties.
• Spectral embedding methods are common for analyzing graph structures.

Purpose of the Study:

• To evaluate the effectiveness of Adjacency Spectral Embedding (ASE) and Graph Encoder Embedding (GEE) for detecting embedded pseudo-cliques.
• To compare these methods against existing spectral clique detection techniques.
• To assess the robustness of ASE and GEE to model contamination and the impact of additional clean data.

Main Methods:

• Theoretical analysis of ASE and GEE in the context of random dot product graphs.
• Empirical evaluation using simulations and real-world network data.
• Inclusion of the Variational Graph Auto-Encoder (VGAE) model for comparative analysis.

Main Results:

• ASE and GEE perform worse than existing spectral clique methods when no additional clean network data is provided.
• These methods can asymptotically localize pseudo-cliques when clean, independent network data is introduced.
• The study highlights the methods' variable ability to capture pseudo-cliques and their robustness to model contamination.

Conclusions:

• ASE and GEE show potential for pseudo-clique detection but are sensitive to data quality and availability.
• The effectiveness of these graph embedding methods is contingent on the presence of clean, supplementary network data.
• Further research can explore hybrid approaches or model refinements to improve pseudo-clique detection capabilities.