Advancing clustering and embedding for attributed network structures

Abstract

Attributed network structures, encompassing graphs, hypergraphs, and multi-view graphs, are fundamental in modeling complex systems across domains like social networks, bioinformatics, and e-commerce. However, existing clustering and embedding methods often struggle to capture complex network structures and scale for big data, limiting their effectiveness. This thesis advances the analysis of attributed network structures by proposing novel approaches that integrate structural and attribute information to achieve high-quality, efficient, and scalable solutions for clustering and embedding. The first contribution introduces ANCKA, a versatile clustering framework that leverages K-nearest neighbor augmentation to partition nodes across attributed graphs, hypergraphs, and multiplex graphs. By efficiently optimizing a novel objective based on random walk, ANCKA delivers superior clustering performance. Building on this, the second contribution presents SAHE, an efficient embedding method for attributed hypergraphs, which unifies the computation of node and hyperedge embeddings to preserve multi-hop relationships. SAHE enhances quality and scalability through innovative similarity measures and approximation techniques. Finally, the third contribution develops SGLA and SGLA+, spectrum-guided algorithms for clustering and embedding multi-view attributed graphs. These algorithms cohesively integrate multiple graph and attribute views, achieving exceptional performance and efficiency. Through extensive experiments on diverse real-world datasets, these frameworks demonstrate significant improvements over numerous baselines, often outperforming competitors by orders of magnitude in efficiency while producing high-quality results. Collectively, this thesis bridges critical gaps in effectiveness, efficiency, and scalability, enabling potential applications in community detection, bioinformatics modeling, and recommendation systems. By providing open-source implementations, including GPU-accelerated variants, this work lays a foundation for future advancements in attributed network analysis, fostering impactful solutions for complex network systems.