TY - GEN
T1 - Efficient Integration of Multi-View Attributed Graphs for Clustering and Embedding
AU - Li, Yiran
AU - Guo, Gongyao
AU - Shi, Jieming
AU - Wang, Sibo
AU - Li, Qing
N1 - Publisher Copyright:
© 2025 IEEE.
PY - 2025/5/1
Y1 - 2025/5/1
N2 - A multi-view attributed graph (MVAG) G captures the diverse relationships and properties of real-world entities through multiple graph views and attribute views. Effectively utilizing all views in G is essential for MVAG clustering and embedding, which are important for applications like recommendation systems, anomaly detection, social network analysis, etc. Existing methods either achieve inferior result quality or incur significant computational costs to handle large-scale MVAGs. In this paper, we present a spectrum-guided Laplacian aggregation scheme with an effective objective formulation and two efficient algorithms SGLA and SGLA+, to cohesively integrate all views of G into an MVAG Laplacian matrix, which readily enables classic graph algorithms to handle G with superior performance in clustering and embedding tasks. We begin by conducting a theoretical analysis to design an integrated objective that consists of two components, the eigengap and connectivity objectives, aiming to link the spectral properties of the aggregated MVAG Laplacian with the underlying community and connectivity properties of G. A constrained optimization problem is then formulated for the integration, which is computationally expensive to solve. Thus, we first develop the SGLA algorithm, which already achieves excellent performance compared with existing methods. To further enhance efficiency, we design SGLA+ to reduce the number of costly objective evaluations via sampling and approximation to quickly find an approximate optimum. Extensive experiments compare our methods against 12 baselines for clustering and 8 baselines for embedding on 8 multi-view attributed graphs, validating the superior performance of SGLA and SGLA+ in terms of result quality and efficiency. Compared with the most effective baselines, our methods are significantly faster, often by up to orders of magnitude. Our implementation is available at https://github.com/CyanideCentral/SGLA/.
AB - A multi-view attributed graph (MVAG) G captures the diverse relationships and properties of real-world entities through multiple graph views and attribute views. Effectively utilizing all views in G is essential for MVAG clustering and embedding, which are important for applications like recommendation systems, anomaly detection, social network analysis, etc. Existing methods either achieve inferior result quality or incur significant computational costs to handle large-scale MVAGs. In this paper, we present a spectrum-guided Laplacian aggregation scheme with an effective objective formulation and two efficient algorithms SGLA and SGLA+, to cohesively integrate all views of G into an MVAG Laplacian matrix, which readily enables classic graph algorithms to handle G with superior performance in clustering and embedding tasks. We begin by conducting a theoretical analysis to design an integrated objective that consists of two components, the eigengap and connectivity objectives, aiming to link the spectral properties of the aggregated MVAG Laplacian with the underlying community and connectivity properties of G. A constrained optimization problem is then formulated for the integration, which is computationally expensive to solve. Thus, we first develop the SGLA algorithm, which already achieves excellent performance compared with existing methods. To further enhance efficiency, we design SGLA+ to reduce the number of costly objective evaluations via sampling and approximation to quickly find an approximate optimum. Extensive experiments compare our methods against 12 baselines for clustering and 8 baselines for embedding on 8 multi-view attributed graphs, validating the superior performance of SGLA and SGLA+ in terms of result quality and efficiency. Compared with the most effective baselines, our methods are significantly faster, often by up to orders of magnitude. Our implementation is available at https://github.com/CyanideCentral/SGLA/.
KW - Multi-view attributed graph
KW - clustering
KW - embedding
UR - https://www.scopus.com/pages/publications/105015535111
M3 - Conference article published in proceeding or book
T3 - Proceedings - International Conference on Data Engineering
SP - 3863
EP - 3875
BT - Proceedings - 2025 IEEE 41st International Conference on Data Engineering, ICDE 2025
PB - IEEE Computer Society
ER -