A multi-view attributed graph (MVAG)$\mathcal{G}$captures the diverse relationships and properties of real-world entities through multiple graph views and attribute views. Effectively utilizing all views in$\mathcal{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$\mathcal{G}$into an MVAG Laplacian matrix, which readily enables classic graph algorithms to handle$\mathcal{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$\mathcal{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/.

An attributed hypergraph comprises nodes with attributes and hyperedges that connect varying numbers of nodes. Attributed hypergraph node and hyperedge embedding (AHNEE) maps nodes and hyperedges to compact vectors for use in important tasks such as node classification, hyperedge link prediction, and hyperedge classification. Generating high-quality embeddings is challenging due to the complexity of attributed hypergraphs and the need to embed both nodes and hyperedges, especially in large-scale data. Existing solutions often fall short by focusing only on nodes or lacking native support for attributed hypergraphs, leading to inferior quality, and struggle with scalability on large attributed hypergraphs. We propose SAHE, an efficient and effective approach that unifies node and hyperedge embeddings for AHNEE computation, advancing the state of the art via comprehensive embedding formulations and algorithmic designs. First, we introduce two higher-order similarity measures, HMS-N and HMS-E, to capture similarities between node pairs and hyperedge pairs, respectively. These measures consider multi-hop connections and global topology within an extended hypergraph that incorporates attribute-based hyperedges. SAHE formulates the AHNEE objective to jointly preserve all-pair HMS-N and HMS-E similarities. Direct optimization is computationally expensive, so we analyze and unify core approximations of all-pair HMS-N and HMS-E to solve them simultaneously. To enhance efficiency, we design several non-trivial optimizations that avoid iteratively materializing large dense matrices while maintaining high-quality results. Extensive experiments on diverse attributed hypergraphs and 3 downstream tasks, compared against 11 baselines, show that SAHE consistently outperforms existing methods in embedding quality and is up to orders of magnitude faster.

Abstract Attributed networks containing entity-specific information in node attributes are ubiquitous in modeling social networks, e-commerce, bioinformatics, etc. Their inherent network topology ranges from simple graphs to hypergraphs with high-order interactions and multiplex graphs with separate layers. An important graph mining task is node clustering, aiming to partition the nodes of an attributed network into k disjoint clusters such that intra-cluster nodes are closely connected and share similar attributes, while inter-cluster nodes are far apart and dissimilar. It is highly challenging to capture multi-hop connections via nodes or attributes for effective clustering on multiple types of attributed networks. In this paper, we first present as an efficient approach to attributed hypergraph clustering (AHC). includes a carefully-crafted K -nearest neighbor augmentation strategy for the optimized exploitation of attribute information on hypergraphs, a joint hypergraph random walk model to devise an effective AHC objective, and an efficient solver with speedup techniques for the objective optimization. The proposed techniques are extensible to various types of attributed networks, and thus, we develop as a versatile attributed network clustering framework, capable of attributed graph clustering , attributed multiplex graph clustering , and AHC. Moreover, we devise with algorithmic designs tailored for GPU acceleration to boost efficiency. We have conducted extensive experiments to compare our methods with 19 competitors on 8 attributed hypergraphs, 16 competitors on 6 attributed graphs, and 16 competitors on 3 attributed multiplex graphs, all demonstrating the superb clustering quality and efficiency of our methods.

Hypergraphs are an omnipresent data structure used to represent high-order interactions among entities. Given a hypergraph H wherein nodes are associated with attributes, attributed hypergraph clustering (AHC) aims to partition the nodes in H into k disjoint clusters, such that intra-cluster nodes are closely connected and share similar attributes, while inter-cluster nodes are far apart and dissimilar. It is highly challenging to capture multi-hop connections via nodes or attributes on large attributed hypergraphs for accurate clustering. Existing AHC solutions suffer from issues of prohibitive computational costs, sub-par clustering quality, or both. In this paper, we present AHCKA, an efficient approach to AHC, which achieves state-of-the-art result quality via several algorithmic designs. Under the hood, AHCKA includes three key components: (i) a carefully-crafted K-nearest neighbor augmentation strategy for the optimized exploitation of attribute information on hypergraphs, (ii) a joint hypergraph random walk model to devise an effective optimization objective towards AHC, and (iii) a highly efficient solver with speedup techniques for the problem optimization. Extensive experiments, comparing AHCKA against 15 baselines over 8 real attributed hypergraphs, reveal that AHCKA is superior to existing competitors in terms of clustering quality, while often being up to orders of magnitude faster.