Top-r semantically important community search on semantic-rich heterogeneous graphs

Heterogeneous information networks (HINs) are widely used to represent complex real-world entities (nodes) and their relations (edges) in various domains^[1−5], such as social networks^[6,7], bibliographic networks^[8,9], and knowledge graphs^[10,11]. Community search (CS) on HINs is a fundamental problem in graph mining^[12−14], which identifies a cohesive subgraph from a given large-scale HIN $ G $ that contains the user-specified query node $ q $ with high structural cohesiveness and semantic quality^[13,15,16]. CS on HINs has broad applicability across multiple domains, such as marketing advertisement and event planning^[1,17], expert finding^[16,18], biological analysis^[19,20], and GraphRAG for retrieval-augmented LLM^[21−23].

Motivations. Existing methods for CS on HINs primarily rely on predefined symmetric meta-paths to identify communities adhering to specific relational semantics^{[1,3,15,16,18,24,25]}. A symmetric meta-path $ {\cal{P}} $ is a sequence of node- and edge-types satisfying that $ {\cal{P}} $ is the same as its reverse, i.e., $ {\cal{P}}^{-1}={\cal{P}} $^[1]. In Fig. 1, $ v_1 $ (${\sf{Rihanna}}$) and $ v_5 $ (${\sf{Eminem}}$) are linked via a 2-hop path instance $ p = v_1v_6v_5 $ of a symmetric $ {\cal{P}} = {\sf{Person}}{}_{}^{\underline {{{\sf{Artist}}}} }{\sf{Song}}{}_{}^{\underline {{{\sf{Artist}}}} }{\sf{Person}} $. By integrating symmetric meta-paths with classic community models, such as $ k $-core^[26,27] or $ k $-truss^[28,29], a series of meta-path-based variants like $ (k,{\cal{P}}) $-core^[1,18] and $ (k,{\cal{P}}) $-truss^[25] have emerged. A $ (k,{\cal{P}}) $-core is a subgraph where each node has at least $ k $ $ {\cal{P}} $-neighbors, and a $ (k,{\cal{P}}) $-truss is a subgraph where any two adjacent nodes share at least $ k-2 $ $ {\cal{P}} $-neighbors. Two nodes are $ {\cal{P}} $-neighbors if they are connected via a path instance of $ {\cal{P}} $, e.g., $ v_1 $ and $ v_5 $ are $ {\cal{P}} $-neighbors given the above symmetric meta-path. One can easily come up with a CS query with $ q=v_1 $, $ {\cal{P}} = {\sf{Person}}{}_{}^{\underline {{{\sf{Artist}}}} }{\sf{Song}}{}_{}^{\underline {{{\sf{Artist}}}} }{\sf{Person}} $, and $ k=2 $. The subgraph that consists of $ \{v_1,\cdots,v_6\} $ would be identified as a connected $ (2,{\cal{P}}) $-core community, where every $ {\sf{Person}} $-typed node has 2 $ {\cal{P}} $-neighbors. Although easy to implement, it suffers from two issues that undermine its usability, as shown in the following two examples in practice.

Figure 1. 

An example of the semantic-rich HIN DBpedia.

Loss of similar relational semantics. In semantic-rich HINs like DBpedia, which contain hundreds (or even more) of node- and edge-types, and forms over thousands of frequently used (both symmetric and asymmetric) meta-paths. It is common for a single relationship to be represented by multiple structurally different but semantically similar meta-paths^[30]. In such cases, existing methods that rely solely on a single symmetric meta-path would lose similar relational semantics in community results, thereby failing to cover all possible community members (see Example 1).

Example 1 Figure 1 illustrates a snapshot of DBpedia in the entertainment industry, with various semantically similar meta-paths that capture collaborative relations between musicians. Representative examples include $ {\cal{P}}_1 = {\sf{Person}}{}_{}^{\underline {{{\sf{Artist}}}} }{\sf{Song}}{}_{}^{\underline {{{\sf{Artist}}}} }{\sf{Person}} $, $ {\cal{P}}_2 = {\sf{Person}}{} _{}^{\underline {{{\sf{Artist}}}} }{\sf{Song}}{}_{}^{\underline {{{\sf{Writer}}}} }{\sf{Person}} $, $ {\cal{P}}_3 = {\sf{Person}}{}_{}^{\underline {{{\sf{Artist}}}} }{\sf{Song}}{}_{}^{\underline {{{\sf{Composer}}}} }{\sf{Person}} $, etc. Given a CS query with $ q = v_1 $, $ {\cal{P}} = {\cal{P}}_1 $, and $ k = 2 $, only a relatively small community of musicians $ \{v_1,v_3,v_5\} $ is returned. Notably excluded are several musicians with known close collaborations to ${\sf{Rihanna}}$, such as ${\sf{The}}\ {\sf{Dream}}$ and ${\sf{JAY-Z}}$. This occurs because the meta-paths connecting these nodes involve asymmetric $ {\cal{P}}_3 $, while the CS query is restricted to $ {\cal{P}}={\cal{P}}_1 $, causing these nodes to have fewer than $ k $ $ {\cal{P}} $-neighbors and thus be consequently omitted from the result.

A straightforward solution is to enumerate all semantically similar, symmetric and asymmetric meta-paths from thousands of candidate meta-paths for running CS on semantic-rich HINs, then combine the results, which is evidently time-consuming and impractical for both ordinary and expert users. A more efficient solution is to implement a lightweight semantic representation capable of flexibly matching various semantically similar meta-paths in runtime. This motivates us to employ a more generalized Semantic Meta-path Pattern (SMP), which abstracts a set of symmetric and asymmetric meta-paths using only key elements in representing their semantics without predefining precise meta-paths in advance.

Homogeneity of the community results. In practice, users often have their own specific preferences on the inherent semantics and structure characteristics of the returned community. Some may prefer a compact community with high semantic relevance to the given $ {\cal{P}} $, while others may prefer a larger community with diverse relational semantics among its members. However, existing works only return one community strictly adhering to the given $ {\cal{P}} $, which cannot provide a variety of options for selection.

Example 2 Figure 2 (middle) shows a homogeneous graph of the HIN in Fig. 1, where each colored edge between ${\sf{Person}}$-typed nodes is a path instance of a meta-path in Fig. 2 (left). Given $ q=v_1 $, some users may prefer a pure singer community of ${\sf{Rihanna}}$ involving $ \{v_1,v_3,v_5\} $ ($ H_1 $), where nodes are exclusively connected via path instances of $ {\cal{P}}_1 $. Some users may prefer a more general community, such as $ H_2 $ and $ H_3 $, which focuses on musical collaboration in a broad sense including songwriters and composers, respectively. Furthermore, some users might even be interested in the broader pan-entertainment community of ${\sf{Rihanna}}$, which includes film directors and actors. In that case, $ H_4 $ and $ H_5 $ would be their desired communities.

Figure 2. 

Diverse semantically similar communities.

Compared with returning only a single community, offering the best $ r $ ($ \geq 1 $) communities with broad semantic diversity that are most semantically relevant to user's query intention is a more effective and practical solution. This motivates us to study the top-$ r $ semantically important community search ($ r $-SICS) problem based on the proposed SMP, where the importance of a community is directly reflected by its semantic relevance to the query in real applications.

Applications. $ r $-SICS can discover high-quality communities with semantic diversity in many applications. (1) Research group detection^[5,31]. In academic peer review, $ r $-SICS can identify $ r $ research groups of varying collaborative closeness associated with an author, which helps minimize potential conflicts of interest in reviewer assignment. (2) Criminal network disruption^[32−34]. In the field of public security, $ r $-SICS can pinpoint $ r $ organizations of varying closeness with respect to specific social relationships to which a suspect belongs. This provides rich and prioritized investigative leads, enhancing the effectiveness of criminal investigation. (3) Community-based RAG^[22,23]. For LLM-driven question answering, $ r $-SICS can retrieve $ r $ knowledge communities with varying semantic relevance to the query, which helps achieve a better balance between the quality and diversity of generated answers.

Challenges and contributions. Existing community search methods on heterogeneous information networks typically rely on a predefined meta-path $ {\cal{P}} $ and aim to identify a $ (k,{\cal{P}}) $-core structure to capture a given semantic pattern, implicitly assuming that the semantic scope is explicitly specified at query time by the user-input $ {\cal{P}} $. In our setting, however, the user is only required to provide a general Semantic Meta-path Pattern (SMP) as an abstract description of their semantic expectation. Rather than conducting a deterministic search over a fixed set of meta-paths, the query process is guided by this semantic expectation to progressively explore, refine, and dynamically discover potential semantic relations. As a result, traditional community search methods, which rely on explicitly defined $ {\cal{P}} $ at query time, are no longer applicable. Motivated by this observation, we adopt a different paradigm in which community construction is tightly coupled with the exploration of potential semantic relations. Specifically, we propose a simple baseline method $\mathrm{Basic}$ (section 3), which constructs a compact, $ q $-centric semantic meta-path subgraph $ G_{\text{SMP}} $ by retaining only those meta-path instances that match the user-specified SMP. As semantic relations are continuously explored and progressively refined, $ G_{\text{SMP}} $ is dynamically expanded, and semantically important communities are repeatedly mined within this restricted and evolving subgraph. In doing so, $\mathrm{Basic}$ avoids the exponential cost of enumerating all similar semantic subgraphs, while enabling efficient discovery of candidate semantic relations and community structures. The smaller the $ G_{\text{SMP}} $, the faster the $\mathrm{Basic}$. To further improve the efficiency of $ G_{{\rm{SMP}}} $ construction, we present an optimized algorithm $\mathrm{Opt-BSS}$ with binary semantic search (section 4.1). It constructs $ G_{\text{SMP}} $ by processing edge-types in batches and applies a semantic-level binary search to iteratively extract a smaller, inherent $ G_{\text{SMP}} $ from the maximal one, avoiding repeated $ G_{{\rm{SMP}}} $ construction from scratch. We next extend $\mathrm{Opt-BSS}$ with a recording optimization that reuses intermediate information during semantic-level binary search, called $\mathrm{Opt-Record}$ (section 4.2), avoiding the SIC construction from $ G_{{\rm{SMP}}} $. Finally, to improve practical efficiency, we further incorporate a multithreaded parallel expansion strategy for $ G_{\text{SMP}} $ construction as a system-level acceleration technique. This implementation-oriented efficiency enhancement is designed to improve scalability in large-scale graphs and complements the main algorithmic framework.

Overall, we conclude our contributions as follows.

● We are the first to study the $ r $-SICS problem based on a generic and flexible semantic meta-path pattern (SMP) to return top-$ r $ communities with broad semantic diversity in a unified and efficient manner.

● We propose the $\mathrm{Basic}$ algorithm, which gradually finds top-$ r $ communities from a $ q $-centric SMP-graph $ G_{{\rm{SMP}}} $, with the semantic relevance to SMP from large to small.

● We optimize $\mathrm{Basic}$ algorithm with a semantic-level binary search strategy ($\mathrm{Opt-BSS}$) to improve the efficiency of $ G_{{\rm{SMP}}} $ construction and intermediate information recording strategy $(\mathrm{Opt-Record})$ to reduce repeated SIC construction from $ G_{{\rm{SMP}}} $ in binary semantic search.

● As an implementation-level efficiency enhancement, we further introduce a parallel expansion strategy to accelerate $ G_{{\rm{SMP}}} $ construction in large-scale graphs.

● We conducted extensive experiments on four real-world, million-scale datasets and validated the effectiveness and efficiency of the proposed methods.

Definition 1 (Heterogeneous Information Network [HIN]^[3,16]). An HIN is defined as $ G = (V,E) $, where $ V $ ($ E $) is the node (edge) set. Each node $ u\in V $ has a type $ \phi(v) $ through a mapping function $ \phi : V \to {\cal{A}} $, where $ {\cal{A}} $ denotes all node types. And each edge $ e \in E $ has a type $ \psi(e) $ through a mapping function $ \psi : E \to {\cal{R}} $, where $ {\cal{R}} $ denotes all edge types. An HIN satisfies that $ |{\cal{A}}| \gt 1 $ and $ |{\cal{R}}| \gt 1 $.

Definition 2 (HIN Schema^[3,16]). Given an HIN $ G = (V,E) $ with mapping functions $ \phi : V \to {\cal{A}} $ and $ \psi : E \to {\cal{R}} $, its schema $ T_G = ({\cal{A}},{\cal{R}}) $ is defined as a graph over $ {\cal{A}} $ and $ {\cal{R}} $.

Example 3 Figure 3 (left) shows the schema of the HIN in Fig. 1. It includes four node types $ {\cal{A}} $: Person (P), Film (F), Song (S), Company (C). For example, $ v_1 $ stands for Rihanna with $ \phi (v_1) = $ P, as well as seven edge types $ {\cal{R}} $ : Artist (Art.), Writer (Writ.), Composer (Comp.), Director (Dir.), Starring (Star.), Production Company (Prod.Co) and Founded_by (Found.By), e.g., $ \psi (e_{v_1v_2}) = $ Art., indicating that Rihanna ($ v_1 $) is the artist of What's My Name ($ v_2 $).

Figure 3. 

The schema of the HIN illustrated in Fig. 1 with five example meta-paths between nodes with a type $\mathrm{Person}$.

In HINs, communities are widely prevalent cohesive subgraphs, whose cohesiveness is evaluated by semantic cohesiveness and structural cohesiveness, as discussed.

2.1.   Semantic cohesiveness

We start with the meta-path, which is commonly used to represent the semantic relationships between two node types.

Definition 3 (Meta-path^[1,18]). A meta-path $ {\cal{P}} $ is a path defined on an HIN schema $ T_G = ({\cal{A}},{\cal{R}}) $, and is denoted in the form $A_1 \underline {R_1}{} A_2 \underline {R_2}{}\cdots \underline {R_l}{} A_{l+1}$, where l is the length of $ {\cal{P}} $, $ A_i \in {\cal{A}} $ ($ 1 \leq i \leq l+1 $) and $ R_j \in {\cal{R}} $ ($ 1 \leq j \leq l $).

We denote a path between $ v_1 $ and $ v_l $ as $ p_{v_{1}v_{l}} = v_1\cdots v_l $. If $ p_{v_{1}v_{l}} $ conforms to a $ {\cal{P}} $, it is called a path instance of $ {\cal{P}} $.

In semantic-rich HINs, various meta-paths can describe the same type of relationship. For instance, the four meta-paths in Fig. 3 (right) all represent collaboration in the entertainment industry, yet reflect distinct semantics due to: (1) Domain differences: $ {\cal{P}}_1 $$ \sim $$ {\cal{P}}_3 $ primarily focus on the music domain, while $ {\cal{P}}_4 $ pertains to the film. (2) Even within the same domain, differences in roles can lead to variations in collaborative semantics. e.g., $ {\cal{P}}_1 $ indicates co-artist collaboration, $ {\cal{P}}_2 $ and $ {\cal{P}}_3 $ involve artist-songwriter/composer collaborations. Nevertheless, all of them consistently express the collaborative semantics in music creation. To precisely capture the user's desired relational semantics for a community of interest, it is necessary to enumerate as many semantically similar meta-paths as possible. However, this is extremely challenging in semantic-rich HINs. For instance, in DBpedia (with 359 node types and 676 edge types), it has over 1,000 frequently used meta-paths, with the total number of meta-paths within 4 hops exceeding 50,000. Accurately predefining meta-paths is impractical in semantic-rich HINs.

Therefore, we employ a more generalized Semantic Meta-path Pattern (SMP) instead of relying on specific meta-paths, to extract key elements that characterize the semantics of meta-paths and better capture the intended semantics of user interests.

Definition 4 (Semantic Meta-path Pattern [SMP]). An SMP is defined as a quadruple $ \langle A_t, A_a, S, \hat{l} \rangle $ is the end node type of a semantic meta-path, which represents the target members of a community of interest. (1) $ A_t \in {\cal{A}} $ is the end node type of a meta-path, representing the target members of a community. (2) $ A_a \in {\cal{A}} $ is defined as the anchor node type located in the middle of the semantic meta-path, serving to specify its domain. (3) $ S \in {\cal{R}} $ is an edge type indicating the semantics in which the user is interested. (4) $ \hat{l} $ is the upper bound of the length of a meta-path. It is designed to prevent excessive meta-path length.

A meta-path structurally matches an SMP if it starts and ends with $ A_t $, passes through $ A_a $, and has a length within $ \hat{l} $ hops, denoted as $ {\cal{P}}\models $ SMP; otherwise, $ {\cal{P}}\not\models $ SMP. The SMP imposes only a coarse-grained semantic constraint on candidate meta-paths; its role is to capture an abstract representation of the user’s semantic expectation, rather than to provide a complete or precise characterization of the user’s intended semantics.

Example 4 To find a collaboration community in the music industry from DBpedia, a user may come up with a simple SMP = $ \langle $Person, Song, Artist, 3$ \rangle $, where $ A_t $ = Person, $ A_a $ = Song, $ S $ = Artist, $ \hat{l} $ = 3. This SMP indicates that the community consists of individuals (${\sf{Person}}$) engaged in the music domain (${\sf{Song}}$) and connected via relations similar to ${\sf{Artist}}$ within a collaboration range of 3 hops. Figure 3 (right) shows three meta-paths $ {\cal{P}}_1\sim{\cal{P}}_3 $ matching this SMP.

Although multiple meta-paths may structurally conform to a given SMP, they can exhibit substantially different degrees of semantic relevance to the user intent. Therefore, rather than treating SMP matching as the final criterion, we introduce Meta-path Semantic Similarity to explicitly quantify how well a meta-path aligns with the target semantics, denoted as $ W_{{\cal{P}}\rightarrow {\rm{SMP}}} $.

Definition 5 (Meta-path Semantic Similarity). Given an $ l $-hop meta-path $ {\cal{P}} $ that matches an SMP = $ \langle A_t,A_a,S,\hat{l} \rangle $, its semantic similarity to the SMP, denoted by $ W_{{\cal{P}} \rightarrow {\rm{SMP}}} $, characterizes the actual semantic relevance of $ {\cal{P}} $ to the user intent. We define it to be dominated by the minimum edge-type similarity to $ S $ (Eq. 1), where $ S_i $ ($ i \in [1,l] $) denotes the $ i $-th edge type in $ {\cal{P}} $, and $ W_{S_i \rightarrow S} $ represents the semantic similarity between $ S_i $ and $ S $.

This design is based on the intuition that a meta-path instance can serve as a reliable semantic connection only when all of its constituent relations remain compatible with the target semantics. Once one edge type becomes semantically weak or mismatched, the semantic interpretation of the whole path is correspondingly constrained. Thus, the minimum value is used not to oversimplify the semantics of a meta-path instance, but to provide a conservative estimate of its overall semantic validity. In addition, this minimum-based formulation is widely adopted in graph mining due to its effectiveness^[4], and is computationally simpler than alternative aggregation measures such as the geometric mean^[30,35], making it particularly suitable for large-scale graphs. To compute $ W_{{\cal{P}} \rightarrow {\rm{SMP}}} $, we first need to compute $ W_{S_i\rightarrow S} $: (1) we employ an offline heterogeneous graph embedding model, e.g., TransE^[36] and RotatE^[37], to represent each $ S_i $ in an HIN $ G $ as a $ d $-dimensional vector $ \vec{S}_i $, which effectively preserves the intrinsic semantics of original relations in vectors^[38]; (2) $ W_{S_i\rightarrow S}\in[0, 1] $ is then computed as Eq. 2.

Example 5 We provide the semantic similarity of the meta-paths shown in Fig. 3 to the SMP = $ \langle $Person,Song,Artist,3$ \rangle $. Given that $ W_{{\text{Art.} \rightarrow \text{Art.}}} = 1.0 $ and $ W_{\text{Wr.} \rightarrow \text{Art.}} = 0.95 $ (obtained via TransE embedding model), we have $ W_{{\cal{P}}_1 \rightarrow {\rm{SMP}}} = \min\{1.0, 1.0\} = 1.0 $ and $ W_{{\cal{P}}_2 \rightarrow {\rm{SMP}}} = \min\{1.0, 0.95\} = 0.95 $. This indicates that $ {\cal{P}}_1 $ is more semantically similar to SMP than $ {\cal{P}}_2 $. Besides, $ W_{{\cal{P}}_4 \rightarrow {\rm{SMP}}} = 0 $ as $ {\cal{P}}_4\not\models{{\rm{SMP}}} $.

Semantic cohesiveness of two nodes. Given two nodes $ u, v \in V $ connected by a path instance $ p_{uv} $ conforming to a meta-path $ {\cal{P}}_{uv}\models{{\rm{SMP}}} $, the semantic cohesiveness between $ u $ and $ v $ with respect to the SMP is determined by its corresponding meta-path's semantic similarity to SMP, i.e., $ W_{{\cal{P}}_{uv}\rightarrow {\rm{SMP}}} $. The greater the similarity of $ {\cal{P}}_{uv} $ to SMP, the cohesiveness between $ u $ and $ v $.

In practical scenarios, multiple meta-path instances conforming to the SMP often exist between the same pair of nodes. Generally, if a path contains any semantically mismatched or weak edge type, the path can hardly be regarded as semantically valid, and its overall semantic connection can be considered 'broken'. Meanwhile, when multiple relational explanations exist between two nodes, weaker relations should not negate the existence of a stronger and more semantically consistent one; the presence of at least one highly coherent and tightly coupled semantic path is sufficient to indicate a strong semantic association between the two nodes. Based on these intuitions, we adopt the following design: when multiple meta-paths connect nodes $ u $ and $ v $, the semantic similarity of each meta-path is determined by its weakest edge type, and the overall semantic cohesiveness between $ u $ and $ v $ is defined as the maximum semantic similarity among all matching meta-paths.

Semantic cohesiveness of a subgraph. We next formally define the semantic cohesiveness of a subgraph as follows.

Definition 6 (Semantic Cohesiveness of a Graph). Given a subgraph $ H $ $ \subseteq $ $ G $ and an SMP, the semantic cohesiveness of $ H $ is defined as the minimum semantic cohesiveness of any two nodes in $ H $, i.e., $ W_{H\rightarrow {\rm{SMP}}} = \min_{u,v \in V}W_{{\cal{P}}_{uv}\rightarrow {\rm{SMP}}} $.

Example 6 Recall the graph in Fig. 2 (middle). For SMP = $ \langle $Person,Song,Artist,3$ \rangle $, if we consider the subgraph $ H_1 $ that consists of $ \{v_1,v_3,v_5\} $, then $ W_{H_1\rightarrow {{\rm{SMP}}}} = 1.0 $ as each pair of nodes exhibits the same high semantic cohesiveness with respect to SMP dominating by the meta-path $ {\cal{P}} = {\sf{Person}}{}_{}^{\underline {{{\sf{Artist}}}} }{\sf{Song}}{}_{}^{\underline {{{\sf{Artist}}}} }{\sf{Person}} $. Similarly, when we consider the subgraph $ H_2 $, then $ W_{H_2\rightarrow {{\rm{SMP}}}} = 0.95 $ as the semantic cohesiveness between $ v_1 $ and $ v_8 $ (or $ v_8 $ and $ v_9 $) is the worst due to they are connected via the path instance of $ {\sf{Person}}{}_{}^{\underline {{{\sf{Artist}}}} }{\sf{Song}}{}_{}^{\underline {{{\sf{Write}}}} }{\sf{Person}} $ with $ W_{\text{Wr.} \rightarrow \text{Art.}} = 0.95 $.

2.2.   Structural cohesiveness

We next integrate the SMP with the widely used $ k $-core model to measure community structure cohesiveness from a structural perspective.

Definition 7 ($ {\cal{P}}^* $-neighbor). Given an SMP and two nodes $ u $ and $ v $ in an HIN, if $ u $ is connected to $ v $ via a path instance $ p_{uv} $ of $ {\cal{P}}^*\models {{\rm{SMP}}} $, then $ v $ is a $ {\cal{P}}^* $-neighbor of $ u $, where $ {\cal{P}}^* $ is a wildcard representing any meta-path that matches the SMP.

Definition 8 ($ {\cal{P}}^* $-edge). Given an SMP and two nodes $ u $ and $ v $ in an HIN that are mutual $ {\cal{P}}^* $-neighbors, the path instance $ p_{uv} $ of $ {\cal{P}}^*\models {{\rm{SMP}}} $ between them is called a $ {\cal{P}}^* $-edge.

Definition 9 (Connected ($ k $, SMP)-core). Given an HIN $ G $, an SMP, and an integer $ k\geq $ 0, a connected ($ k $,$ {\rm{SMP}} $)-core $ H \subseteq G $ is a connected subgraph of nodes linked by $ {\cal{P}}^* $-edges, of which every node $ u $ has at least $ k $ distinct $ {\cal{P}}^* $-neighbors.

Notably, $ k $ serves only as a minimum degree constraint, and the core is not required to achieve the maximum possible $ k $.

Example 7 Given an SMP = $ \langle \text{Person}, \text{Song}, \text{Artist}, 3 \rangle $ and $ k $ = 2, Fig. 2 (middle) shows a connected $ (2,{{\rm{SMP}}}) $-core extracted from the HIN in Fig. 1. Each Person-typed node has at least two $ {\cal{P}}^* $-neighbors ($ {\cal{P}}^* $ refers to any of the five meta-paths in Fig. 2 (left) that match the given SMP), e.g., node $ v_1 $ (Rihanna) has eight distinct $ {\cal{P}}^* $-neighbors (i.e., $ v_3 $, $ v_5 $, $ v_8 $, $ v_9 $, $ v_{11} $, $ v_{14} $, $ v_{16} $, $ v_{17} $), the $ {\cal{P}}^* $-edge between $ v_1 $ and $ v_5 $ (Eminem) is $ {\sf{Person}}{}_{}^{\underline {{{\sf{Artist}}}} }{\sf{Song}}{}_{}^{\underline {{{\sf{Artist}}}} }{\sf{Person}} $.

The connected ($ k $, SMP)-core generalizes the traditional ($ k $, $ {\cal{P}} $)-core by allowing any meta-path $ {\cal{P}}^*\models {{\rm{SMP}}} $, rather than being restricted to a single $ {\cal{P}} $. This, in a more flexible and expressive manner, enhances the semantic diversity of a community.

2.3.   Problem definition

We first introduce the concept of Semantically Important Community (SIC), which is defined based on the semantic cohesiveness and the connected ($ k $,$ {\rm{SMP}} $)-core.

Definition 10 (Semantically Important Community [SIC]). Given an HIN $ G $ = ($ V $, $ E $), an SMP = $ \langle A_t, A_a, S, \hat{l} \rangle $, a query node $ q $ with type $ A_t $, and an integer $ k $ $ \geq $ 0, a subgraph $ H $ $ \subseteq $ $ G $ is called an SIC if it satisfies the following conditions:

● Query Participation: The subgraph $ H $ contains $ q $;

● Structure cohesiveness: $ H $ is a connected (k,$ {\rm{SMP}} $)-core;

● Semantic cohesiveness: The semantic cohesiveness of $ H $ is quantified by $ W_{H \rightarrow \text{SMP}} $, where a larger $ W_{H \rightarrow \text{SMP}} $ implys a stronger semantic importance of $ H $ to SMP;

● Maximality: There does not exist another subgraph $ H' $ $ \supseteq $ $ H $ satisfying the first two conditions and having the same semantic cohesiveness as $ W_{H\rightarrow {{\rm{SMP}}}} $.

More precisely, an SIC is defined as the largest one among all connected $ (k,{{\rm{SMP}}}) $-cores that share an equivalent level of semantic cohesiveness (or importance) to a specific SMP. This definition enables SIC to encompass more diverse semantics without compromising semantic importance, enhancing the semantic diversity.

Example 8 The five subgraphs $ H_1 $$ \sim $$ H_5 $ in Fig. 2 (right) represent distinct SICs with varying semantic cohesiveness to a given SMP = $ \langle $Person, Song, Artist, 3$ \rangle $, as introducing additional $ {\cal{P}}^* $-neighbors or $ {\cal{P}}^* $-edges to any $ H $ would not yield a larger subgraph that maintains the same level of semantic cohesiveness. Besides, taking $ H_2=\{v_1,v_3,v_5,v_8,v_9\} $ as an example, it also contains a connected $ (2,{{\rm{SMP}}}) $-core of $ \{v_1,v_8,v_9\} $. Although both share the same semantic cohesiveness dominated by $ {\sf{Person}}{}_{}^{\underline {{{\sf{Artist}}}} }{\sf{Song}}{}_{}^{\underline {{{\sf{Write}}}} }{\sf{Person}} $, $ H_2 $ includes more nodes connected via instances of the meta-path with higher semantic similarity to SMP, exhibiting better semantic diversity. In our setting, $ H_2 $ would be the SIC rather than the smaller one.

In real-world scenarios, a node may belong to multiple SICs with varying semantic cohesiveness to a given SMP, reflecting hierarchical semantic scopes. For instance, in Fig. 2, $ v_1 $ (Rihanna) belongs to a pure singer community ($ H_1 $), a broader creative musician community encompassing songwriters and composers ($ H_2 $ and $ H_3 $), and even a more generalized entertainment community ($ H_4 $ and $ H_5 $). In practice, users are often uncertain about how broad the desired community semantics should be at query time. Some may prefer the most semantically focused community that best matches their initial intent, while others may further expect broader communities that include more semantically related members. This motivates us to study the Top-$ r $ Semantically Important Community Search ($ r $-SICS) problem, which explores the top-$ r $ SICs most relevant to the user-specific SMP and builds a multi-level answer space for user exploration. As $ r $ increases, the returned communities become progressively broader while preserving a semantic ordering from high to low importance, thereby supporting a natural exploration process from precise semantic matches to broader semantic neighborhoods.

$ r $-SICS Problem. Given an HIN $ G = (V, E) $, a semantic meta-path pattern SMP = $ \langle A_t,A_a,S,\hat{l} \rangle $, a query node $ q $ with type $ A_t $, an integer $ k \geq $ 0 and an integer $ r \geq $ 1, $ r $-SICS aims to find the best $ r $ SICs that satisfy the following requirements:

● Size monotonicity: The size of SIC satisfies $ |V_i| \lt |V_{i+1}| $ ($ |V_i| $ is the number of nodes in the $ i $-th SIC, 1$ \leq i \lt r $);

● Semantic monotonicity: The semantic cohesiveness of SIC must satisfy $ W_{H_i \rightarrow {\rm{SMP}}} \gt W_{H_{i+1} \rightarrow {\rm{SMP}}} $ ($ W_{H_i \rightarrow {\rm{SMP}}} $ is the semantic cohesiveness of the $ i $-th SIC, 1$ \leq $i $ \lt r $).

Example 9 Given an SMP = $ \langle Person, Song, Artist, 3 \rangle $, $ k = 2 $, $ r = 1 $, and a query node $ v_1 $ (Rihanna), $ r $-SICS returns $ H_1 $ as the top-1 SIC, clearly revealing the critical pure singer community of Rihanna. For $ r=3 $, $ H_2 $ and $ H_3 $ are also returned, including more songwriters and composers who have strong musical collaborations with Rihanna. For $ r=5 $, broader pan-entertainment communities $ H_4 $ and $ H_5 $ of Rihanna are identified, which involve many film directors and actors.

A solution is to enumerate all connected $ (k, \text{SMP}) $-cores in the entire HIN $ G $ and select the top-$ r $ most semantically cohesive SICs. However, such exhaustive enumeration is computationally prohibitive. To address this, we propose a simple yet effective baseline, $\mathrm{Basic}$, which constructs a small $ q $-centric SMP-graph $ G_{\text{SMP}}\subseteq G $ that contains all potential SICs, thereby significantly reducing the search space instead of the entire $ G $. It is noteworthy that the smaller the $ G_{\text{SMP}} $ is, the faster the $\mathrm{Basic}$ runs.

Definition 11 ($ q $-centric SMP-graph). Given an HIN $ G $, an SMP, and a query node $ q $, we define the $ q $-centric SMP-graph as $ G_{\text{SMP}} \subseteq G $, a connected component containing $ q $ with all nodes connected via $ {\cal{P}}^* $-edges, for any wildcard $ {\cal{P}}^*\models $ SMP.

Figure 2 (middle) vividly illustrates the constructed $ G_{\text{SMP}} $, which is derived from the HIN in Fig. 1, with $\text{SMP} = \langle \text{Person}, \text{Song}, \text{Artist}, 3 \rangle $ and $ q = v_1 $. This $ G_{\text{SMP}} $ contains 11 nodes of type Person, which are densely connected via $ {\cal{P}}^* $-edges with $ {\cal{P}}^* $ represents any one of the five meta-paths shown in Fig. 2 (left).

Lemma 1 Given an HIN $ G $, an SMP, and a query node $ q $, any connected $ (k, SMP) $-core containing $ q $ must be a subgraph of the $ q $-centric SMP-graph $ G_{SMP}\subseteq G $.

Proof By Definition 11, $ G_{\text{SMP}} $ is the largest connected subgraph that contains $ q $ and in which all nodes are connected via $ {\cal{P}}^* $-edges. Since a connected $ (k, \text{SMP}) $-core of $ q $ requires every node to have at least $ k $ $ {\cal{P}}^* $-neighbors and be reachable via $ {\cal{P}}^* $-edges, it must be contained in the $ G_{\text{SMP}} $ of $ q $.

Overview Algorithm 1 outlines the procedure of $\mathrm{Basic}$. It operates based on the semantic monotonicity of $ r $-SICS: the semantic cohesiveness of the top-$ r $ communities decreases as $ r $ increases. More precisely, as more SICs are extracted, new edge types would be introduced, increasing semantic diversity but reducing cohesiveness. With this in mind, we use a semantic constraint set to regulate the semantic scope of the search. Specifically, it progressively expands the semantic constraint set by adding new edge types. For each expanded semantic constraint set, $\mathrm{Basic}$ constructs a $ G_{\text{SMP}} $ using all edge types in it and performs core decomposition on $ G_{\text{SMP}} $ to identify candidate SICs. The process continues until the top-$ r $ SICs with the highest semantic cohesiveness are obtained.

${\bf{\mathrm{Basic}}}$. In Algorithm 1, we first initialize several key structures: an empty set $\mathrm{HSet}$ to store discovered $ r $ SICs, an empty semantic constraint set $\mathrm{SemSet}$ to control the semantic scope, a subgraph $ H' $ to store the previous SIC, and a counter $\mathrm{count}$ to record the number of SICs found so far (lines 1-2). Then, we rank all edge types in descending order of $ W_{S_i\rightarrow S} $ and store them in a list $\mathrm{R}$ (line 3). After that, we iterate the following steps until the top-$ r $ SICs are found: (1) Semantic expansion. We progressively add new edge types (one by one) from $\mathrm{R}$ into $\mathrm{SemSet}$ to increase the semantic diversity. If $\mathrm{SemSet}$ already contains all semantics in $\mathrm{R}$, the algorithm terminates, as no further SICs with lower semantic cohesiveness can be found (lines 5−7). (2) $ G_{\text{ SMP}} $ construction. We construct $ G_{\text{SMP}} $ using the updated $\mathrm{SemSet}$ (line 8, detailed in Algorithm 2). (3) SIC extraction. We adopt the core decomposition^[39] to iteratively remove nodes with less than $ k $ $ {\cal{P}}^* $-neighbors until all target nodes have at least $ k $ $ {\cal{P}}^* $-neighbors. The remaining connected component that contains $ q $ is a feasible SIC $ H $ (line 9). (4) Quality evaluation. We check if the newly discovered $ H $ satisfies the size monotonicity mentioned in the definition of $ r $-SICS problem (lines 10–15).

We now focus on the detailed process of constructing $ G_{\text{SMP}} $ (the step (2) above), which is the key to the $\mathrm{Basic}$ algorithm.

$ \underline{G_{\text{SMP}}\ {\rm{construction}}}$. The procedure of $\mathrm{getSMPGraph}$ is outlined in Algorithm 2 We first initialize a queue $\mathrm{Expand} = \{ q \}$ to store candidate nodes for expansion, an empty set $\mathrm{Visited}$ to keep track of visited nodes, and an empty graph $G_{\mathrm{SMP}}$ (line 1). Then, $ G_{\text{SMP}} $ is constructed by two steps: (1) Neighbor retrieval. For each node in $\mathrm{Expand}$, invoke $\mathrm{FPN}$($ G $, $ u $, SMP, $\mathrm{SemSet}$) detailed in Algorithm 3 to retrieve its $ {\cal{P}}^* $-neighbors and $ {\cal{P}}^* $-edges that formed by edge types from $\mathrm{SemSet}$. (lines 3–4). (2) Graph update. We add the discovered $ {\cal{P}}^* $-neighbors and edges to $ G_{\mathrm{SMP}}$, then add unvisited neighbors into $\mathrm{Expand}$ and move the visited nodes into $\mathrm{Visited}$ (lines 5–7). These steps are repeated until the $\mathrm{Expand}$ queue becomes empty.

● $\mathrm{FPN}$($ G $, $ u $, SMP, $\mathrm{SemSet}$). In Algorithm 3, we initialize: an empty set $ N^*(u) $ to store the $ {\cal{P}}^* $-neighbors of a node $ u $, an empty set $ E^*(u) $ for $ {\cal{P}}^* $-edges of $ u $, a queue $\mathrm{NbrExpand}$ to track nodes to be expanded, and a $\mathrm{Path}$ to cache temporary path instances discovered during the search (lines 1–3). It then iterates the following to retrieve all valid $ {\cal{P}}^* $-neighbors and $ {\cal{P}}^* $-edges: (1) Neighbor exploration. We dequeue a node $ w $ from $\mathrm{NbrExpand}$ and retrieve all its neighbors from the original graph $ G $ (lines 5–7). (2) Path extension. If the edge type between $ w $ and its neighbor $ v $ is contained in $\mathrm{SemSet}$, we extend the path $ p_{uw} $ with an edge $ e_{wv} $ to form a new path instance $ p_{uv} $ (lines 9–13). (3) Neighbor update. If $ v $ is of the target type $ A_t $ and $ p_{uv} $ matches the SMP, then we add $ v $ to the $ {\cal{P}}^* $-neighbor set $ N^*(u) $ and store $ p_{uv} $ in the $ {\cal{P}}^* $-edge set $ E^*(u) $. Otherwise, the length of $ p_{uv} $ is less than upper bound $ \hat{l} $, we add $ v $ into $\mathrm{NbrExpand}$ and add $ p_{uv} $ into $\mathrm{Path}$ (lines 14–19). We repeat steps (1)–(3) until all expansion operations are completed and no nodes remain to be expanded.

Effectiveness analysis. We analyze the correctness and effectiveness of $\mathrm{Basic}$. Specifically, we rigorously demonstrate that the algorithm can (1) correctly identify the $ H $ found in each iteration satisfying all constraints specified in Definition 10 (Theorem 1): query participation, structure cohesiveness and, maximality, and (2) correctly obtain the top-$ r $ SICs with the highest semantic cohesiveness, in accordance with the size and semantic monotonicity of the $ r $-SICS problem (Theorem 2).

Theorem 1. In each iteration, the subgraph $ H $ returned by $\mathrm{Basic}$ satisfies all SIC constraints.

Proof The subgraph $ H $ returned by $\mathrm{Basic}$ is a $ (k, \text{SMP}) $-core that contains the query node $ q $, thus obviously satisfying the first two SIC constraints. For maximality, since we apply core-decomposition to find $ H $, $ H $ must be the largest connected $ (k,{{\rm{SMP}}}) $-core in $ G_{{\rm{SMP}}} $. Suppose there exists a larger connected $ (k,{{\rm{SMP}}}) $-core satisfying the other two SIC constraints, then it must be outside $ G_{{\rm{SMP}}} $; otherwise, it will be identified as $ H $ by core-decomposition. However, this contradicts Lemma 1, that is, any $ (k, \text{SMP}) $-core that contains $ q $ must be a subgraph of $ G_{\text{SMP}} $. So, $ H $ is maximal.

Theorem 2 The $\mathrm{Basic}$ algorithm can correctly discover the top-$ r $ SICs with the highest semantic cohesiveness, satisfying the size and semantic monotonicity of $ r $-SICS problem.

Proof For size monotonicity. In the $\mathrm{Basic}$ algorithm, each newly discovered $ H $ is compared with the previously found SIC $ H' $ to ensure that its size is larger, thereby fully satisfying the size monotonicity. For semantic monotonicity. In $\mathrm{Basic}$, each expansion of the semantic constraint set $\mathrm{SemSet}$ introduces an additional edge type with lower semantic similarity. This means that the semantic cohesiveness of the new subgraph $ H $ obtained based on the updated $\mathrm{SemSet}$ cannot be higher than that of the previous $ H' $, which is entirely consistent with the semantic monotonicity.

Complexity analysis. The overall time of $\mathrm{Basic}$ is $ O(r \times (|V_\text{SMP}| \times d^{\hat{l}}+|V_\text{SMP}|+|E_\text{SMP}|)) $, where $ r $ is the number of SICs to be found, $ |V_\text{SMP}| $ is the number of target nodes in $ G_\text{SMP} $, $ d $ is the average node degree in original $ G $, $ \hat{l} $ is length bound and $ |E_\text{SMP}| $ is the number of $ {\cal{P}}^* $-edges in $ G_\text{SMP} $. The main computational cost comes from $\mathrm{getSMPGraph}$ (Algorithm 2), of which each node calls $\mathrm{FPN}$ (Algorithm 3), which has a worst-case complexity of $ O(d^{\hat{l}}) $ because each node may generate up to $ d^{\hat{l}} $ path instances matching the SMP. Subsequently, the core-decomposition is applied on $ G_\text{SMP} $, with time of $ O(|V_\text{SMP}|+|E_\text{SMP}|) $ in the worst case.

The $\mathrm{Basic}$ algorithm requires reconstructing $ G_\text{SMP} $ from scratch each time the semantic scope is expanded with a new edge type, resulting in redundant computations. To address this, we propose the Optimized Algorithm with Binary Semantic Search ($\mathrm{Opt-BSS}$) in section 4.1. It expands the semantic scope in batches and constructs a maximal $ G_\text{SMP} $ encompassing all involved edge types. It then employs a semantic-level binary search to peel smaller, inherent $ G_\text{SMP} $ from the maximal one, avoiding costly reconstruction from scratch. Building on this, section 4.2 introduces the Optimized Algorithm with Recording ($\mathrm{Opt-Record}$), which accelerates SICs search from $ G_\text{SMP} $ by reusing intermediate information during binary search.

4.1.   Optimized with binary semantic search

Overview The basic idea of $\mathrm{Opt-BSS}$ is two-fold. First, it adds edge types to $\mathrm{SemSet}$ in batches of size $ b $ (the effect of $ b $ is studied in section 6.4), therefore constructing a comprehensive $ G_{\text{SMP}} $ that is likely to contain the top-$ r $ SICs, avoiding repeated reconstruction of $ G_{{\rm{SMP}}} $ for each edge type. Second, it adopts a semantic binary search to efficiently locate the top-$ r $ SICs from the above $ G_{{\rm{SMP}}} $. Specifically, it divides edge types into a strong and weak semantic parts based on their $ W_{S_i\rightarrow S} $. If a smaller $ G'_{\text{SMP}}\subseteq G_{{\rm{SMP}}} $ exists within the strong semantic part and SICs can be found from $ G'_{{\rm{SMP}}} $, we continue the binary search within the strong semantic part; otherwise, we search for SICs in another smaller $ G'_{\text{SMP}}\subseteq G_{{\rm{SMP}}} $ derived from the weak semantic part. There may exist multiple SICs within a single batch. Therefore, after one SIC is identified, the binary search process described above is executed again on the remaining semantics in the batch until the top-$ r $ SICs are completely found. Alternatively, if fewer than $ r $ SICs are found in the current batch, we expand $\mathrm{SemSet}$ with another batch of edge types and repeat the above.

${\bf{\mathrm{Opt-BSS}}}$. Algorithm 4 outlines $\mathrm{Opt-BSS}$. We initialize an empty $\mathrm{HSet}$ for top-$ r $ SICs, an empty semantic constraint set $\mathrm{SemSet}$, and an empty $ H' $ for the SIC with the highest semantic cohesiveness so far (line 1). All edge types are stored in a list $ R $ in descending order of their $ W_{S_i\rightarrow S} $ (line 2). We add edge types in batches of size $ b $ from $ R $ to $\mathrm{SemSet}$, following their ranking. To facilitate this process, we maintain a sliding window $ [U,D] $ to track the current batch, with $ U $ and $ D $ initialized as 1 and $ b $, indicating the first and the $ b $-th edge type in $ R $. $\mathrm{Opt-BSS}$ then iterates the following steps until the top-$ r $ SICs are searched. (1) Batch semantic expansion. We continuously slide the window (i.e., update $ U $ and $ D $) to add edge types in batches (lines 5–10). (2) $ G_{\text{SMP}} $ construction. Using the current $\mathrm{SemSet}$, we construct a $ G_\mathrm{SMP} $ by applying Algorithm 2 (line 11). (3) SIC extraction. We apply the same method as in $\mathrm{Basic}$ to extract a feasible SIC $ H $ from current $ G_\mathrm{SMP} $ (line 12). (4) Binary semantic search. If $ H $ is larger than $ H' $, this indicates that the current $ G_\mathrm{SMP} $ contains new SICs at different semantic levels from that of $ H' $ and they can be found by calling $\mathrm{BSS}$ (detailed in Algorithm 5). After the current round of binary semantic search ends, these new SICs are added to $\mathrm{HSet}$, $ U $ is updated to $ D+1 $, and $ H' $ is updated to the current $ H $. (lines 13-26).

$\underline{\mathrm{BSS}}$. Algorithm 5 outlines the process of binary semantic search in a $ G_{\text{SMP}} $. First, it initializes a left (right) boundary $\mathrm{left}$ ($\mathrm{right}$) to the highest (lowest) semantic rank $ U $ ($ D $), which are used to control the range of binary search, an empty result set $\mathrm{HSet}$, and an empty local semantic constraint set for BSS $\mathrm{SemSet}\_\mathrm{BSS}$ (lines 1 and 2). It then performs binary semantic search within the current range $ [\mathrm{left},\mathrm{right}] $ to find the top-$ r $ SICs. (1) Midpoint selection. We calculate the middle rank $\mathrm{mid}$ based on the $\mathrm{left}$ and $\mathrm{right}$. Edge types with ranks greater than or equal to $\mathrm{mid}$ are considered strong semantic part, and these edge types are added to the local $\mathrm{SemSet}\_\mathrm{BSS}$, which is reset to empty before update to ensure accurate edge type acquisition. (lines 6–11). (2) $ G'_{\text{SMP}} $ construction. Next, a smaller $ G'_{\text{SMP}} $ is constructed from the original $ G_{\text{SMP}} $ by removing edges that excluded from $\mathrm{SemSet}\_\mathrm{BSS}$ (line 12). (3) SIC extraction. Then, we apply core-decomposition to find a connected $ (k, \text{SMP}) $-core $ H $ containing $ q $ from $ G'_{\text{SMP}} $ (line 13). (4) SIC refinement. If the new SIC $ H $ is larger than the previous $ H' $, $\mathrm{BSS}$ continues binary search in the strong semantics part to check for a more cohesive and larger SIC. If $\mathrm{mid}$ equals $\mathrm{left}$, $ H $ is the best in this part, so we update $ H' $ and $\mathrm{HSet}$, increments $\mathrm{count}$, and adjusts semantic boundaries. Otherwise, we continue binary search with the right boundary as $\mathrm{mid}$–1 (lines 14–23). If no better $ H $ is found, the search next try to select more semantics from weak semantic part by setting $\mathrm{left}$ to $\mathrm{mid}$+1. When $\mathrm{left}$ exceeds $\mathrm{right}$, we check if edges ranked from $\mathrm{left}$ onward can yield a better SIC. If so, it updates for $ H' $, $\mathrm{HSet}$, $\mathrm{count}$, and boundaries (lines 24–30). Notably, when searching for the $ i{+}1^{\text{th}} $ SIC, boundary $\mathrm{left}$ is set to $\mathrm{mid}$+1, where $\mathrm{mid}$ is the midpoint when finding $ i^{th} $ SIC. Meanwhile, boundary $\mathrm{right}$ is reset to the lowest semantic rank $ D $ (line 20). We perform a semantic binary search within the updated range to obtain the $ i{+}1^{\text{th}} $ SIC. By analogy, we repeat steps (1)–(4) until the top-r SICs are found or the binary semantic search can no longer proceed.

Effectiveness analysis. $\mathrm{Opt-BSS}$ can correctly identify SICs satisfying constraints in Definition 10, as each SIC is obtained in the same manner as $\mathrm{Basic}$. Moreover, Since the semantic boundaries of binary search are adjusted to ensure that each newly found SIC satisfies the semantic monotonicity, and the size of each SIC is evaluated in line 17 to guarantee the size monotonicity. Therefore, $\mathrm{Opt-BSS}$ is capable of returning the top-$ r $ SICs for $ r $-SICS problem.

Complexity analysis. The overall time of $\mathrm{BSS-Opt}$ is $ O(\frac{|{\cal{R}}|}{b} \cdot (|V_{\text{SMP}}| \cdot d^{\hat{l}} + |V_{\text{SMP}}| + |E_{\text{SMP}}| + r \cdot (\log b \cdot |V_{\text{SMP}}| + |V'_{\text{SMP}}| + |E'_{\text{SMP}}|)))$, where $ |{\cal{R}}| $ is the number of edge types, $ b $ is the batch size, $ |V_{\text{SMP}}| $ ($ |V'_{\text{SMP}}| $) and $ |E_{\text{SMP}}| $ ($ |E'_{\text{SMP}}| $) are the number of target nodes and $ {\cal{P}}^* $-edges in $ G_{\text{SMP}} $ ($ G'_{{\rm{SMP}}} $). In the worst case, it performs $ \frac{|{\cal{R}}|}{b} $ batches of semantic expansions. In each batch, it constructs a new $ G_{\text{SMP}} $ by Algorithm 2 and performs a core-decomposition on it, which costs $ O(|V_{\text{SMP}}| \cdot d^{\hat{l}} + |V_{\text{SMP}}| + |E_{\text{SMP}}|) $ time. In practice, when $ b $ is appropriately set, only 1–2 batches are needed to obtain the top-$ r $ SICs. Within each batch, it invokes Algorithm 5 to find an SIC with at most $ \log b $ iterations, which costs $ O(\log b \cdot |V_{\text{SMP}}| + |V'_{\text{SMP}}| + |E'_{\text{SMP}}|) $ time. Since at most $ r $ SICs are identified from a single $ G_{\text{SMP}} $, the time for one batch is $ O(r \cdot (\log b \cdot |V_{\text{SMP}}| + |V'_{\text{SMP}}| + |E'_{\text{SMP}}|)) $. Thus, the total time of $\mathrm{BSS-Opt}$ is $ O(\frac{|{\cal{R}}|}{b} \cdot (|V_{\text{SMP}}| \cdot d^l + |V_{\text{SMP}}| + |E_{\text{SMP}}| + r \cdot (\log b \cdot |V_{\text{SMP}}| + |V'_{\text{SMP}}| + |E'_{\text{SMP}}|))) $.

4.2.   Optimized algorithm with recording

In Section 4.1, the $\mathrm{Opt-BSS}$ algorithm sets the search boundary for the $ (i+1)^{th} $ SIC as [$\mathrm{mid}_i+1 $, D]. This is a crude boundary selection, which causes a large number of semantics to be repeatedly added to $ \mathrm{SemSet}\_\mathrm{BSS}$ for SIC discovery, thereby significantly reducing search efficiency. To address this issue, the $\mathrm{Opt-Record}$ algorithm proposed in this section records intermediate information during each binary semantic search and reuses it in subsequent searches, thereby effectively avoiding repeated calculations.

Overview The key to implementing $\mathrm{Opt-Record}$ lies in identifying the information that should be recorded. To this end, we start from Theorem 3, first rigorously proving an SIC constructed from a $ \mathrm{SemSet}\_\mathrm{BSS}$ containing highly similar semantics is necessarily contained within an SIC formed by lower semantic similarity. Based on this, it is no longer necessary to use a large range with the right boundary is D for searching SICs; instead, the search can be confined by the already discovered SICs formed from $ \mathrm{SemSet}\_\mathrm{BSS}$ containing lowly similar semantics. We thus design a global map $ \mathrm{findedH}$ to record the discovered SICs and their corresponding semantics to implement the recorded binary semantic search.

Theorem 3 Let $ \{H_1,\dots,H_r\} $ be $ r $ SICs of the same query node $ q $ with semantic cohesiveness from high to low. Then, for any $ 1 \le i \lt r $, we have $ H_i \subsetneq H_{i+1} $.

Proof Let node $ v \in V_{H_i} $ but $ v \notin V_{H_{i+1}} $ for $ i\in(0,r-1] $. By Definitions 10 and 6, the semantic cohesiveness between any two nodes in $ V_{H_i} $ satisfies $ W_{{\cal{P}}_{uv}\rightarrow {{\rm{SMP}}}}\geq W_{H_i\rightarrow {{\rm{SMP}}}} $. Since we assume $ W_{H_i\rightarrow {{\rm{SMP}}}}\geq W_{H_{i+1}\rightarrow {{\rm{SMP}}}} $, $ W_{{\cal{P}}_{uv}\rightarrow {{\rm{SMP}}}}\geq W_{H_{i+1}\rightarrow {{\rm{SMP}}}} $ holds. According to the maximality constraint in Definition 10, $ H_{i+1} $ should be the largest connected $ (k,{{\rm{SMP}}}) $-core at the semantic level $ W_{H_{i+1}\rightarrow {{\rm{SMP}}}} $. However, by including $ v $ via $ {\cal{P}}_{uv} $ would enlarge $ H_{i+1} $'s size while keep $ W_{H_{i+1}\rightarrow {{\rm{SMP}}}} $ unchanged, contradicting the maximality of $ H_{i+1} $. So, $ v $ must also belong to $ H_{i+1} $, implying $ H_i\subsetneq H_{i+1} $.

${\bf{\mathrm{Opt-Record}}}$. $\mathrm{Opt-Record}$ is detailed in Algorithm 6. Compared with the $\mathrm{Opt-BSS}$ algorithm, $\mathrm{Opt-Record}$ introduces an additional map $\mathrm{findedH}$ to record the SICs discovered during the search process and their corresponding semantic levels, i.e., edge type count in the semantic constraint set when SIC was constructed. $\mathrm{Opt-Record}$ shares the same framework as Algorithm 4, iteratively executing four steps until the top-$ r $ communities are found: (1) Batch semantic expansion. (2) $ G_{\text{SMP}} $ construction. (3) SIC extraction. (Details of Steps 1–3 are provided in Algorithm 4). (4) Binary semantic search with recording. we perform a semantic binary search in $ H $ via BSS-Record (in Algorithm 7). After $\mathrm{BSS-Record}$ finishes, the newly discovered SICs are added to $\mathrm{HSet}$. If top-$ r $ SICs are not found, we update $ U $ to $ D+1 $, set $ H' $ to the current $ H $, and proceed to the next iteration until the top-$ r $ SICs are found(lines 7–14).

$\underline{\mathrm{BSS-Record}}$. Algorithm 7 describes binary semantic search with record. Initially, we set left (right) boundary $\mathrm{left}$ ($\mathrm{right}$) as $ U $ ($ D $), which control the semantic range during the binary search, and result set $\mathrm{HSet}$, semantic constraint set $\mathrm{SemSet}\_\mathrm{BSS}$ as empty. An empty stack $\mathrm{lastRight}$ is used to record previous right boundaries, and an empty set $\mathrm{SemSizeSet}$ to store SIC-formable semantic ranks (lines 1–3). The algorithm proceeds as follows: (1) Midpoint selection. Compute middle semantic rank to generate the corresponding semantic constraint set $\mathrm{SemSet}\_\mathrm{BSS}$ (detailed in Algorithm 5). (2) SIC extraction. By Theorem 3, SICs with smaller semantic range are necessarily contained within larger ones. Thus, we retrieve the SIC that is larger than but most similar to the current semantic range from $\mathrm{findedH}$ and denoted as $\mathrm{lastH}$. Then, edges in $\mathrm{lastH}$ that violate the current semantic constraints are removed to obtain the SIC $ H $ that conforms to $\mathrm{SemSet}\_\mathrm{BSS}$ (lines 6–10). (3) SIC refinement. Similar to Algorithm 5, if the size of $ H $ is larger than $ H' $ and $\mathrm{mid}$ exactly equals $\mathrm{left}$, the algorithm updates $ H' $, $\mathrm{HSet}$, $\mathrm{count}$, and the left and right boundaries (detailed in Algorithm 5). Notably, if the left boundary exceeds the right boundary, the right boundary is extended to the previously stored right boundary in $\mathrm{lastRight}$. If $\mathrm{mid}$ does not equal $\mathrm{left}$, the binary search continues in the strong semantic segment to find an SIC with higher semantic cohesiveness. At this point, $\mathrm{findedH}$ records the current $ H $, $\mathrm{lastRight}$ records the current right boundary, $\mathrm{SemSizeSet}$ stores the current semantic rank, and the right boundary is updated to $\mathrm{mid}$-1 (lines 19–23). If no better $ H $ is found, the search shifts to the weak semantic segment, continuing by updating the left and right boundaries. We then check whether the most semantically cohesive SIC in the weak semantic segment has already been searched (i.e., whether the semantic rank $\mathrm{mid}$+1 exists in $\mathrm{SemSizeSet}$) (lines 25–27). If so, $\mathrm{HSet}$, $ H' $, $\mathrm{count}$, and the boundaries are updated accordingly (detailed in Algorithm 5). Steps 1–3 are repeated until the top-$ r $ SICs are found or the binary semantic search can no longer proceed.

Effectiveness analysis. Next, we thoroughly analyze the correctness and effectiveness of the $\mathrm{Opt-Record}$ algorithm from two perspectives. First, $\mathrm{Opt-Record}$ can accurately identify SICs that satisfy all the constraints in Definition 10. According to Theorem 3, under the maximality and monotonicity constraints of our $ r $-SICS formulation, an SIC with stronger semantic cohesiveness is contained within a broader SIC with weaker semantic cohesiveness. Therefore, $\mathrm{Opt-Record}$ can start from a previously discovered broader SIC, remove edges that do not satisfy the current semantic requirements, and then apply core decomposition to recover the maximal connected $ (k, {\rm{SMP}}) $-core containing $ q $. First, $\mathrm{Opt-Record}$ can effectively recover the maximal connected $ (k, {\rm{SMP}}) $-core satisfying the current semantic constraints. Second, similar to $\mathrm{Opt-BSS}$, $\mathrm{Opt-Record}$ adjusts the boundaries of the semantic binary search to ensure that each newly discovered SIC satisfies the semantic monotonicity condition, while also evaluating the size of each SIC to guarantee that the top-$ r $ results satisfy the size monotonicity requirement. Therefore, $\mathrm{Opt-Record}$ can correctly obtain the top-$ r $ SICs with the highest semantic cohesiveness as required by the $ r $-SICS problem (Problem 2.3). In summary, the $\mathrm{Opt-Record}$ algorithm can correctly identify the top-$ r $ SICs that fulfill all the requirements of the $ r $-SICS problem.

Complexity analysis. The outer loop of $\mathrm{Opt-Record}$ proceeds in batches, where each batch processes $ b $ semantic levels. Therefore, the maximum number of iterations is $ \frac{|{\cal{R}}|}{b} $. For each batch, the time cost can be divided into three parts. (1) Construction of $ G_{\text{SMP}} $: the cost is $ O(|V_{\text{SMP}}|\cdot d^l) $, where $ |V_{\text{SMP}}| $ is the number of nodes in $ G_{\text{SMP}} $ and $ d^l $ denotes the semantic expansion factor. (2) SIC extraction: the cost is $ O(|V_{\text{SMP}}| + |E_{\text{SMP}}|) $. (3) Binary semantic search with recording ($\mathrm{Opt-Record}$): the number of binary steps is $ O(\log b) $. Each refinement requires processing the previously discovered community $ H $, costing $ O(|V_\text{H}| + |E_\text{H}|) $. Hence, the total cost of this step is $ O((|V_\text{H}| + |E_\text{H}|)\cdot \log b) $. Combining the above, the overall time complexity of $\mathrm{Opt-Record}$ is $ O(\frac{|{\cal{R}}|}{b}(|V_{\text{SMP}}|\cdot d^l + (|V_{\text{SMP}}|+ |E_{\text{SMP}}|) + (|V_\text{H}|+|E_\text{H}|)\log b)). $ Since $ H $ is always a subgraph of $ G_{SMP} $, we have $ |V_\text{H}|\leq |V_{\text{SMP}}| $ and $ |E_\text{H}|\leq |E_{\text{SMP}}| $. Thus, the time complexity can be further simplified to $ O(\frac{|{\cal{R}}|}{b}(|V_{\text{SMP}}|\cdot d^l + (|V_{\text{SMP}}|+|E_{\text{SMP}}|)\log b)). $

Since the $ {\cal{P}}^* $-neighbor expansion during the $ G_{{\rm{SMP}}} $ construction is completely independent with no data dependencies among them, a simple yet highly effective acceleration approach is to adopt a parallel expansion via multithreading. Specifically, once a new $ {\cal{P}}^* $-neighbors is identified, it is assigned to an independent thread to search for its subsequent $ {\cal{P}}^* $-neighbors. This speeds up $ G_{\text{SMP}} $ construction, thereby reducing the overall runtime.

Sequential expansion. As shown in Fig. 4 (left), the sequential expansion begins from the initial node $ v_1 $, recording its neighbors $ v_2, v_3, $ and $ v_4 $, and then visits them sequentially to discover their neighbors $ v_6, v_7, v_8, $ and $ v_5 $. The expansion continues iteratively with newly found nodes until all nodes are traversed. Here, completing the entire traversal requires 12 steps (the sequence of steps is associated with edges). For a large HIN with numerous $ {\cal{P}}^* $-neighbors, sequential expansion inevitably leads to linearly increasing construction time and thus results in significantly low efficiency.

Figure 4. 

Parallel $ {\cal{P}}^* $-neighbor expansion.

Parallel expansion. In contrast, the parallel $ {\cal{P}}^* $-neighbor expansion shown in Fig.4 (right) starts with the initial node as the first $ {\cal{P}}^* $-neighbor, assigned to Thread 1 for discovering its $ {\cal{P}}^* $-neighbors $ v_6, v_7, v_8, $ and $ v_5 $. While Thread 1 is expanding from $ v_6 $, idle Threads 2 and 3 can simultaneously process the expansion from $ v_7 $ and $ v_5 $, respectively. This parallel expansion completes the full traversal in just seven steps—nearly doubling the efficiency compared to the sequential expansion. Experimental results on real-world datasets (details in section 6) demonstrate that the $ G_{\text{SMP}} $ construction with parallel $ {\cal{P}}^* $-neighbor expansion can significantly improve the runtime efficiency. For the million-scale DBpedia dataset, this parallel construction improves the overall efficiency of $\mathrm{Basic}$ by 5$ \times $ and enhances that of $\mathrm{Opt-Record}$ by 3$ \times $ on average.

Remark. Although a fine-grained parallelization could be applied to the internal steps of the $ {\cal{P}}^* $-neighbor expansion, it would introduce significant synchronization overhead. Therefore, we consider the search for a $ {\cal{P}}^* $-neighbor as an atomic procedure and parallelize the $ G_{{\rm{SMP}}} $ construction at this level.

We conducted an experimental study to answer four questions. All experiments were run on a Linux Server with 3.7 GHz CPU and 128 GB memory. Our code and datasets are available at the GitHub repository^[40].

Q1: What is the effectiveness of the algorithms in practice? (section 6.2)

Q2: How do algorithms perform in terms of efficiency? (section 6.3)

Q3: How sensitive are the proposed algorithms to various parameter settings? (section 6.4)

Q4: How does our algorithms find the top-$ r $ SICs in semantic-rich HINs? (section 6.5)

6.1.   Experimental setup

Datasets. Table 1 summarizes four million-scale semantic-rich HINs. (1) Wikidata^[41] is a collaborative knowledge base that supports Wikimedia projects. (2) Freebase^[42] is a knowledge graph derived from online wiki contributions. (3) YAGO^[43] involves information from WordNet and GeoNames. (4) DBpedia^[10] is an open-domain linked data built from Wikipedia.

Methods. (1) Basic is proposed in section 3. (2) Opt−BSS is the first optimized algorithm with binary semantic search proposed in section 4.1. (3) Opt−Record is the second optimized algorithm built atop Opt−BSS in section 4.2. It enhances $ G_{{\rm{SMP}}} $ construction efficiency by caching the intermediate SICs, thereby reducing the search space for binary semantic search and avoiding redundant computations. We apply the parallel $ {\cal{P}}^* $-neighbor expansion to (1)−(3) to form three variants (4) Basic+P, (5) Opt−BSS+P, and (6) Opt−Record+P. Since the problem of $ r $-SICS on semantic-rich HINs has not been studied before, there are no existing methods that are fully aligned with our problem formulation. Therefore, we compare our methods with several representative and closely related community search baselines, and adapt them to our setting in a best-effort manner so that they are as aligned as possible under their own input forms. We compared our methods with three representative baselines considering node attributes: (7) $ r $KACS^[13], (8) VAC^[4], and (9) KC^[5]. Here, we follow the same setting as $ r $KACS to assign attributes to a node as the types of its adjacent edges, thus building the connection between relational semantics and node attributes. $ r $KACS returns top-$ r $ communities similar to the given query attributes, while VAC and KC can only return one community. In this setting, the higher attribute similarity of $ H $ to the query attributes indicates a higher relational semantic cohesiveness. In addition, we further compare our methods with a classic community search baseline on heterogeneous graphs, (10) FastOnline^[15]. FastOnline supports the use of multiple predefined symmetric meta-paths within a single query. To adapt it to our setting, we use the symmetric meta-path associated with each SIC layer in the top-$ r $ results as the predefined meta-path for the corresponding query.

Queries. We generate 200 queries per dataset. For methods (1)–(6), we randomly select a query node $ q $ and use its type as $ A_t $. Then, we randomly select a neighbor $ u $ of $ q $, use its type as $ A_a $, and take the edge type between $ q $ and $ u $ as the relational semantics $ S $. We set the meta-path length bound $ \hat{l} $ $ \leq $ 4 as longer meta-paths tend to weaken relational strength^[44−46]. Finally, a query is formed as $ q $ with SMP $ =\langle A_t,A_a,R,\hat{l}\rangle $. For methods (7)–(9), we construct query attributes by collecting the edge types appearing in the top-$ r $ SICs returned for query node $ q $, so as to provide these baselines with sufficiently informative and fair inputs under their own settings. In this way, the constructed query attributes can reflect semantic intentions similar to those in our problem formulation. As default, we set $ r=3 $ and $ \hat{l}=3 $.

Metrics. We evaluate effectiveness from three semantic perspectives: semantic diversity (NMP), semantic consistency and quality (ALSD and SC), and comparative semantic evaluation (AAS). (1) Number of Meta-Paths (NMP) is the number of distinct symmetric and asymmetric meta-paths within a community $ H $. A higher average NMP across the top-$ r $ communities indicates richer semantic diversity. (2) Adjacent-Layer Semantic Difference (ALSD) measures the semantic discrepancy between adjacent communities in the top-$ r $ results, as ALSD ($ H $,$ r $) = $ \dfrac{1}{r-1}\sum_{i \in [1,r-1]}(1-\dfrac{|{\cal{R}}_i\cap {\cal{R}}_{i+1}|}{|{\cal{R}}_i\cup {\cal{R}}_{i+1}|}) $ ($ {\cal{R}}_i $ is the edge types of the $ i $-th community). A lower ALSD reflects stronger semantic continuity across the top-$ r $ communities with respect to the given SMP. (3) Semantic Cohesiveness SC, as defined in Definition 6. A higher average SC over the top-$ r $ communities indicates better semantic quality. We also adopt a metric from the evaluation framework of $ r $KACS to assess effectiveness. (4) Average Attribute Similarity (AAS) measures how $ H $ is similar to query attributes $ Q_W $, as AAS($ H $,$ Q_W $) = $ \dfrac{1}{|V(H)|} \sum_{u \in V(H)} \dfrac{|A(u) \cap Q_W|}{|A(u) \cup Q_W|} $. Higher AAS indicates better quality. Moreover, we evaluate efficiency via response time.

6.2.   Effectiveness evaluation

Since our methods (1)–(6) yield identical results for the same query, their results are reported collectively in Tables 2 and 3.

NMP results. In Tables 2 and 3, the first column shows that ours consistently outperforms all baselines across all datasets, achieving the highest semantic diversity. This indicates that the SICs identified by us encompass more semantically similar meta-paths and capture richer multi-level relational semantics.

ALSD results. In Tables 2 and 3 (2nd column), our methods achieve an average ALSD of 20.1%, which is lower than 56.7% of $ r $KACS. This clearly indicates that our methods ensures consistently high semantic coherence across $ r $ communities with small deviation from the given SMP. In contrast, the high ALSD of $ r $KACS suggests potential semantic discontinuity among communities. ALSD is not applicable to VAC and KC, as they return only one community. Moreover, since FastOnline adopts the symmetric meta-paths corresponding to each SIC layer as the semantics in each search, its semantic modeling is consistent with ours at this level. As a result, FastOnline yields the same ALSD values as our method, making this metric not directly comparable between the two approaches.

SC results. Tables 2 and 3 (3rd column) confirm our method's superior SC across all datasets. This strongly suggests that baselines may include semantically irrelevant meta-paths in the results, which consequently leads to lower SC. This is mainly because they optimize the similarity of individual edge types (i.e., node attributes), while we optimize the similarity of the entire meta-path. Similarly to ALSD, FastOnline is also not comparable under the SC metric.

AAS results. In Tables 2 and 3 (last column), our methods outperforms all baselines on three datasets and attains competitive results on Freebase. This clearly indicates strong attribute similarity between the communities and the query attributes. As we know, node attributes are typically derived from the types of their adjacent edges, and a higher AAS reflects greater relational semantic cohesiveness.

6.3.   Efficiency evaluation

Efficiency comparison with baseline. Figure 5 further compares our methods with $ r $KACS and FastOnline, two representative community search baselines on heterogeneous graphs. Since only these methods are capable of returning the top-$ r $ communities, we focus on their runtime performance. Across all datasets, our fastest method, Opt-Record + P, consistently achieves lower runtime than both baselines. Specifically, Opt-Record + P runs 6.4$ \times $ faster than $ r $KACS on average, with notable speedups on DBpedia (11.6$ \times $) and YAGO (7.9$ \times $). Even without parallelism, Opt-Record still outperforms $ r $KACS by 3.2$ \times $. Moreover, all of our methods are consistently faster than FastOnline across all datasets. In particular, Opt-Record + P achieves an average speedup of 10.4$ \times $ over FastOnline, with the largest performance gaps observed on DBpedia (24.4$ \times $) and YAGO (19.4$ \times $), demonstrating the superior efficiency of our framework.

Figure 5. 

Efficiency comparison.

Detailed runtime analysis of our methods. Table 4 presents the runtime breakdown of our proposed methods across four datasets, where the overall cost is divided into the construction time of the $ G_{{\rm{SMP}}} $ and the remaining steps. The Basic method incurs the highest runtime on all datasets, as the construction of $ G_{{\rm{SMP}}} $ dominates the total cost due to exhaustive semantic exploration. Opt-BSS significantly reduces the runtime by adopting a binary semantic search strategy, which avoids repeated full graph construction. Building upon this, Opt-Record further improves efficiency by reusing intermediate results during the search process, consistently achieving the lowest runtime among non-parallel methods. Moreover, the parallelized variants (+P) provide substantial additional speedups, especially on large and semantic-rich datasets such as DBpedia, where the cost of $ G_{{\rm{SMP}}} $ construction is dramatically reduced. Overall, these results demonstrate that the proposed optimization strategies are complementary and jointly enable efficient and scalable $ r $-SICS on large heterogeneous information networks.

6.4.   Parameter sensitivity

Effect of $ \hat{l} $. Figure 6 shows that the runtime of all methods increases as $ \hat{l} $ grows. This is expected, since a larger $ \hat{l} $ leads to the detection of more meta-paths, which increases the cost of $ G_{{\rm{SMP}}} $ construction as well as the subsequent core decomposition process. As shown in Fig. 7, the NMP metric consistently increases with $ \hat{l} $, indicating that larger hop limits enable richer semantic diversity by incorporating more meta-path instances. Meanwhile, SC remains stable or exhibits a mild increasing trend across datasets. This suggests that although more connections are introduced when $ \hat{l} $ increases, the semantic consistency of the discovered SICs is well preserved. Overall, a larger $ \hat{l} $ provides more opportunities to construct semantically coherent communities without sacrificing structural or semantic quality.

Figure 6. 

Effect of $ \hat{l} $ on efficiency.

Figure 7. 

Effect of $ \hat{l} $ on effectiveness metrics (NMP and SC).

Effect of $ k $. Figure 8 shows that the runtime increases as $ k $ grows, which is expected since a larger $ k $ imposes a stricter $ k $-core constraint. This in turn increases the construction time of $ G_{{\rm{SMP}}} $ as well as the computational cost of the subsequent core decomposition process. As shown in Fig. 9, the NMP metric consistently increases with $ k $, indicating that stronger structural constraints encourage the incorporation of more semantically similar meta-paths, thereby enhancing semantic diversity. Meanwhile, SC remains largely stable across most datasets, with only a mild decrease observed in some cases. This suggests that although larger $ k $ may introduce additional connections to satisfy the structural constraint, the semantic consistency of the discovered SICs is generally well preserved.

Figure 8. 

Effect of $ k $ on efficiency.

Figure 9. 

Effect of $ k $ on effectiveness metrics (NMP and SC).

Effect of $ r $. Figure 10 shows the impact of $ r $ on efficiency. As $ r $ increases, the runtime naturally grows since more communities need to be enumerated and validated. Figure 11 reports the effect of $ r $ on effectiveness metrics. As $ r $ increases, the NMP metric consistently rises, indicating that returning more communities introduces richer semantic diversity. Meanwhile, SC exhibits a gradual decreasing trend. This behavior is consistent with the Semantic Monotonicity property defined in Problem 2.3, where communities with lower semantic priority are progressively included. Notably, the decrease in SC remains moderate, suggesting that we can provide multiple community results while largely preserving semantic consistency.

Figure 10. 

Effect of $ r $ on efficiency.

Figure 11. 

Effect of $ r $ on effectiveness metrics (NMP and SC).

Effect of $ b $. Since $ b $ only affects the efficiency of Opt-BSS, Opt-Record, and Opt-Record+P, we only present their corresponding results in Fig. 12. Note that a moderate value of $ b $ can improves efficiency by covering more relevant edge types to the semantics $ S $ in SMP in one batch. However, an overly large $ b $ introduces irrelevant edge types, increasing $ G_{{\rm{SMP}}} $ construction overhead. Thus, the runtime first reduces and then increases with increasing $ b $.

Figure 12. 

Effect of $ b $ on efficiency.

Effect of # threads. We provide the efficiency results of methods using parallel $ {\cal{P}}^* $-neighbor expansion in Fig. 13. As # thread increases, the runtime naturally decreases, but beyond a certain point, thread scheduling and communication overhead become dominant factors, causing performance to stabilize.

Figure 13. 

Effect of # threads on efficiency.

6.5.   Case studies

To qualitatively evaluate the effectiveness and interpretability of our methods, we conduct case studies on DBpedia, as shown in Fig. 14. In both cases, $ r $-SICS consistently discovers communities corresponding to different semantic layers rather than a single semantic view, capturing semantic diversity while yielding communities that are structurally and semantically cohesive and contextually interpretable across different levels of semantic abstraction.

Figure 14. 

Case studies on DBpedia.

Case study for Ariana Grande. We set the query node as Ariana Grande with $ k $ = 8 and and SMP = $ \langle $Person, Song, Artist, 3$ \rangle $, which captures music-related collaboration semantics. The top-3 SICs returned by $ r $-SICS clearly correspond to three distinct semantic layers. The first SIC (red) forms a singer collaboration community, consisting of artists with frequent direct collaborations, such as Nicki Minaj and Selena Gomez. This layer reflects highly specific and strongly cohesive performance-level collaboration semantics. The second SIC (green) evolves into a music production community, incorporating collaborators such as Max Martin and Iggy Azalea. This community captures songwriting- and production-level relations that are semantically close to singer collaborations but structurally different. The third SIC (yellow) further expands into a broader entertainment community, including figures such as Leonardo DiCaprio, reflecting associations between music and entertainment industry. Together, these three SICs demonstrate that $ r $-SICS can effectively uncover layered semantic structures, ranging from artist-level collaborations to entertainment community, while maintaining structural cohesiveness.

Case study for Spielberg. For Steven Spielberg, we set $ k $ = 7 and SMP = $ \langle $Person, Film, Director, 3$ \rangle $. The discovered SICs exhibit a clear profession-oriented semantic layering. The most cohesive SIC (orange) corresponds to a core director–editor layer, including long-term collaborators such as Michael Kahn and Frank Morriss, capturing coupled production-level semantics. The second SIC (purple) expands to an actor collaboration layer, incorporating actors such as Christopher Lee and Dianne Kay. The third SIC (green) further forms a film production support layer, including cinematographers and audiovisual experts such as Allen Daviau and William A. Fraker. Across these layers, $ r $-SICS provides multiple semantically coherent communities that reflect different professional roles and collaboration scopes within the film industry.

This study was motivated by two core limitations of existing community search methods on HINs, including semantic incompleteness caused by strict reliance on predefined meta-paths and the lack of diversity due to returning a single community. Our results suggest that abstracting semantic intention through SMP can effectively alleviate the inflexibility of predefined meta-path specification. By dynamically exploring semantically relevant relations rather than enumerating fixed patterns, the proposed framework better captures diverse yet semantically coherent communities. More importantly, the output of $ r $-SICS is intended to reflect the kind of answers needed for semantic exploration in semantic-rich HINs. Rather than receiving only one fixed community, users may benefit from a ranked set of communities that begins with the most semantically focused result and then gradually expands to broader but still relevant alternatives. In this sense, returning the top-$ r $ SICs is not merely a modeling choice, but also a user-oriented answer format for semantic exploration.

7.2.   Methodological advancement

Compared with traditional ($ k $, $ {\cal{P}} $)-core based methods, this work advances community search in three aspects. First, at the modeling level, it replaces fixed meta-path specification with semantic-guided exploration via SMP, improving flexibility in semantic-rich HINs. Second, at the problem-definition level, it formalizes semantically important communities (SICs) and organizes community search as a top-$ r $ ranked retrieval task. Third, at the algorithmic level, it develops Opt-BSS and Opt-Record to improve search efficiency by avoiding repeated reconstruction and redundant refinement. In addition, the multithreaded expansion introduced in section 5 serves as an implementation-level acceleration technique for large-scale deployment.

7.3.   Limitations

Despite its effectiveness, several limitations remain. First, semantic similarity estimation relies on pre-trained heterogeneous graph embeddings, whose quality may be sensitive to noise or sparsity. Second, the current framework assumes static HINs and does not explicitly address dynamic or temporal graph evolution. Third, parameters such as the length bound $ \hat{l} $, structural constraint $ k $, and batch size in semantic expansion may influence performance and require manual tuning. Fourth, because no existing baseline exactly matches the $ r $-SICS setting, the empirical comparisons in this paper are conducted under adapted best-effort settings, which may not fully reflect all aspects of advantage or disadvantage.

7.4.   Future work

Future research may proceed in several directions. (1) Developing adaptive semantic expansion strategies that incorporate user feedback or learning mechanisms. (2) Extending $ r $-SICS to dynamic heterogeneous graphs with incremental maintenance of semantic subgraphs. (3) Integrating SMP-based community discovery with large language models to support community-level retrieval-augmented generation. (4) Designing more expressive SMP variants that support multiple anchors or composite semantic constraints.

Overall, this study establishes a flexible and scalable paradigm for ranked semantic community discovery in heterogeneous information networks, providing a foundation for further exploration at the intersection of semantic modeling and graph mining.

Community search (CS) is a fundamental problem in graph mining, aiming to identify a cohesive subgraph that contains a given query node. Existing studies can be categorized based on graph homogeneity and how semantics are incorporated.

CS on homogeneous networks. Early CS studies in homogeneous graphs emphasized structural cohesiveness based on connectivity measures such as $ k $-core^[26,47], $ k $-truss^[29,48], and $ k $-clique^[49,50]. These models effectively capture dense substructures but ignore semantic information encoded in edges. Subsequent works incorporated edge weights^[51,52] or textual labels^[53] into structural metrics to improve interpretability. While these methods enhance interpretability, they fundamentally operate on simple graphs and treat semantics as auxiliary information attached to edges or nodes. As a result, they are not designed to capture complex relational semantics that arise from heterogeneous entity types and relations.

CS on heterogeneous information networks. For HINs, meta-paths $ {\cal{P}} $ have become the dominant mechanism for modeling semantic relations across different node and edge types. A series of meta-path-based community search models have been proposed, such as $ (k,{\cal{P}}) $-core and $ (k,{\cal{P}}) $-truss^[1,3,25,54], which extend classical structural cohesiveness by restricting connectivity to instances of a predefined meta-path. These approaches enable users to explicitly encode semantic intent into the community definition and have demonstrated effectiveness on structured HINs. However, relying solely on symmetric meta-paths is often insufficient to preserve semantic consistency within communities, especially in semantic-rich HINs. In such networks, similar relational semantics can be expressed by multiple structurally distinct meta-paths, including both symmetric and asymmetric ones. Restricting community search to a single symmetric meta-path lead to the loss of semantically equivalent but structurally different relational information, thereby affecting the completeness of the resulting communities. These observations highlight the need for more flexible semantic modeling in community search on semantic-rich HINs.

Semantic community search. Beyond the traditional community search paradigm, some recent studies have attempted to incorporate multiple meta-path constraints or result diversity into graph mining tasks^[13,15] to alleviate the limitations imposed by a single semantic view. However, these methods are still primarily built upon symmetric meta-paths and consequently lose the approximate semantic information captured by asymmetric meta-paths. In semantic-rich heterogeneous information networks, similar or approximate relational semantics can often be expressed through multiple structurally distinct meta-paths, including both symmetric and asymmetric ones. Expanding community search only among multiple symmetric meta-paths may therefore overlook important semantic relations captured by asymmetric meta-paths, resulting in incomplete community results from a semantic perspective. Moreover, most existing methods still focus on returning a single community and do not explicitly model the fact that a given query node may correspond to multiple semantically plausible communities. In practical applications, users often expect multiple candidate communities that reflect different semantic scopes or levels of abstraction. This practical demand further highlights the importance of jointly supporting flexible semantic modeling and multi-result community search in semantic-rich heterogeneous information networks.

We systematically study the top-$ r $ semantically important community search ($ r $-SICS) problem on semantic-rich HINs using a novel $ (k,{{\rm{SMP}}}) $-core model based on a flexible and expressive semantic meta-path pattern (SMP). We present a Basic algorithm followed by two optimizations with a semantic-level binary search and an intermediate recording strategy, and finally a parallel expansion to further improve efficiency. Extensive experiments on real-world datasets further confirm the effectiveness and efficiency of our approach in discovering diverse yet semantically coherent communities.