Relational graphs encapsulate nontrivial inherent interactions among entities in heterogeneous data sources. Iden-tifying hubs in relational graphs is vital in various applications such as fraud detection, influence analysis, and protein complex discovery. However, building relational graphs induced by meta-paths on heterogeneous data entails substantial costs, thus hin-dering efficient hub discovery. In this paper, we propose a novel sketch propagation framework for approximate hub queries in induced relational graphs that avoids explicitly materializing those graphs. Our framework specifically supports hub queries that ask for all nodes whose centrality scores, based on degree or h-index, are in the top quantile with provable guarantees under the notion of ∊-separable sets. In addition, we devise pruning techniques that efficiently process personalized hub queries asking whether a given node is a hub. Extensive experiments on real-world and synthetic data confirm the efficacy and efficiency of our proposals, which achieve orders of magnitude speed-ups over exact methods while consistently attaining accuracy beyond 90%.

How can we efficiently identify the densest subgraph over relational graphs? Existing dense subgraph discovery (DSD) approaches assume that a relational graph H is already derived from a heterogeneous data source and they focus on efficient discovery of the densest subgraph on the materialized H. Unfortunately, materializing relational graphs can be resource-intensive, which thus limits the practical usefulness of existing algorithms over large datasets. To mitigate this, we propose a novel Summary-bAsed deNsest Subgraph discovery (SANS) system. Our unique summary-based peeling algorithm forms the core of SANS. Following the peeling paradigm, it utilizes summaries of each node's neighborhood to efficiently estimate peeling coefficients and subgraph densities at each peeling iteration and thus avoids materializing the relational graph completely. Through extensive experiments, we demonstrate the efficacy and efficiency of SANS, reaching orders of magnitude speedups compared to the conventional baselines with materialization, while consistently achieving at least 95% accuracy compared to peeling algorithms based on materialization.

Community detection in heterogeneous information networks (HINs) poses significant challenges due to the diversity of entity types and the complexity of their interrelations. While traditional algorithms may perform adequately in some scenarios, many struggle with the high memory usage and computational demands of large-scale HINs. To address these challenges, we introduce a novel framework, SCAR, which efficiently uncovers community structures in HINs without requiring network materialization. SCAR leverages insights from meta-paths to interpret multi-relational data through compact vertex-based sketches, significantly reducing computational overhead and materialization overhead. We propose a sketch-based technique for estimating changes in modularity, improving both the precision and speed in community detection. Our extensive evaluations on diverse real-world datasets provide detailed comparative metrics, demonstrating that SCAR outperforms several state-of-the-art methods, including Gdy, Louvain, Leiden, Infomap, Walktrap, and Networkit, in execution time and memory consumption while maintaining competitive accuracy. Overall, SCAR offers a robust and scalable solution for revealing community structures in large HINs, with applications across various domains, including social networks, academic collaboration networks, and e-commerce platforms.

What is the widest community in which a person exercises a strong impact? Although extensive attention has been devoted to searching communities containing given individuals, the problem of finding their unique communities of influence has barely been examined. In this paper, we study the novel problem of Characteristic cOmmunity Discovery (COD) in attributed graphs. Our goal is to identify the largest community, taking into account the query attribute, in which the query node has a significant impact. The key challenge of the COD problem is that it requires evaluating the influence of the query node over a large number of hierarchically structured communities. We first propose a novel compressed COD evaluation approach to accelerate the influence estimation by eliminating redundant computations for overlapping communities. Then, we further devise a local hierarchical reclustering method to alleviate the skewness of hierarchical communities generated by global clustering for a specific query attribute. Extensive experiments confirm the effectiveness and efficiency of our solutions to COD: they find characteristic communities better than existing community search methods by several quality measures and achieve up to 25 x speedups against well-crafted baselines.

In this paper, we study local clustering over labeled graphs, which extracts a subgraph with nodes having high label density matched to the query labels as well as high structure density around a seed node. Despite the progress made in the last few years, we observe two major limitations of existing methods: (I) The candidate subgraphs have to comply with strict topology-driven models and better candidates can be pruned by these topological constraints; (II) The topological constraints give rise to substantial computational overheads and existing works have to construct prohibitively large indexes for online processing. To mitigate these limitations, we explore the idea of using conductance in local clustering that ensures structure density through minimizing conductance. Conductance is a well-understood metric primarily for detecting unlabeled clusters but for labeled graphs, applying conductance directly is insufficient because the label information is not taken into consideration. To this end, we propose a novel Label-Aware Motif weighted framework (LAM) to transform the labeled graph to a weighted graph so that both the label and the structure proximity of nodes are captured. We define label-aware motifs as small high-order structures of nodes with query labels. Nodes within a label-aware motif are both closely connected and relevant to query labels, which ease the process of identifying labeled clusters. Our theoretical study shows that LAM is able to better distinguish the desired candidates under the personalized pagerank distribution from the seed node on random graphs generated by the stochastic block model. Based on such nice properties of LAM, we propose an index-free peeling algorithm to efficiently search local clusters on labeled graphs. Extensive experiments on both real-world and synthetic networks show that our proposed algorithm can achieve up to 90% relative effectiveness improvements (F1 scores), while using 10 times less memory than the SOTA algorithm.