Graph Embedding for Community Preservation

• Grant number: 24/21122-1
• Support Opportunities: Scholarships in Brazil - Scientific Initiation
• Start date: February 01, 2025
• End date: December 31, 2025
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Computer Systems
• Principal Investigator: Francisco Aparecido Rodrigues
• Grantee: Pedro Augusto Ribeiro Gomes
• Host Institution: Instituto de Ciências Matemáticas e de Computação (ICMC). Universidade de São Paulo (USP). São Carlos , SP, Brazil

Abstract

Graph embeddings have emerged as powerful tools for representing complex networks in low-dimensional vector spaces while preserving essential topological properties. This project focuses on evaluating and comparing various graph embedding methods in their ability to maintain community structures-subsets of nodes with higher internal connectivity than external. While popular methods such as node2vec and DeepWalk are known for capturing local and global proximities effectively, this research also incorporates other notable approaches like LINE, GraRep, and deep learning-based techniques such as Graph Convolutional Networks (GCN) and GraphSAGE. The goal is to provide a comprehensive analysis of how these embeddings perform under different network conditions, including varying levels of sparsity and degree heterogeneity, with a specific focus on preserving community structures. By leveraging synthetic benchmarks such as the Stochastic Block Model (SBM) and real-world-inspired networks, the project aims to identify strengths and limitations of each method. This work aspires to contribute practical insights for selecting appropriate embedding techniques and lay the groundwork for developing hybrid methods that enhance community detection and representation fidelity in complex networks.