arXiv:2604.14988v1 [cs.DB] 16 Apr 2026
Efficient Community Search on Attributed Public-Private Graphs Yuqi Chen
Weihan Zhang
Xin Huang
Hong Kong Baptist University Hong Kong, China [email protected]
Sun Yat-sen University Guangzhou, China [email protected]
Hong Kong Baptist University Hong Kong, China [email protected]
Abstract—Public-private graph, where a public network is visible to everyone and every user is also associated with its own small private graph accessed by itself only, widely exists in realworld applications of social networks and financial networks. Most existing work on community search, finding a querydependent community containing a given query, only studies on a public graph, neglecting the privacy issues in public-private networks. However, considering both the public and private attributes of users enables community search to be more accurate, comprehensive, and personalized to discover hidden patterns. In this paper, we study a novel problem of attributed community search in public-private graphs (ACS-PP), aiming to find a connected k-core community that shares the most keywords with the query node. This problem uncovers structurally cohesive communities, such as interest-based user groups or core teams in collaborative networks. To optimize search efficiency, we propose an integrated scheme of constructing a public global graph index and a private personalized graph index. For the private index, we developed a compact structure of the PP-FPtree index. The PP-FP-tree is constructed based on the public and private neighbors of the query node in the public-private graph, serving as an efficient index to mine frequent node sets that share the most common attributes with the query node. Extensive experiments on real public-private graph datasets validate both the efficiency and quality of our proposed PP-FP search algorithm against existing competitors. The case study on public-private collaboration networks provides insights into the discovery of public-private communities.
I. I NTRODUCTION Graphs are widely used to depict entities and their complex relationships, such as social networks, collaboration networks, and so on [1]–[6]. However, not all edge information may be publicly accessible in various graph data. For example, users may prefer to hide their friend relationships, e.g., in the Facebook social network, 52.6% of 1.4 million New York City users chose to hide friend lists [7]. Such a privacypreserving network is modeled as a public-private network [8], [9], in which a public network is visible to all users and each user is associated with their own small private graph. Publicprivate networks widely exist in various applications of the Weibo social network and academic collaboration networks. In collaboration networks, an edge between two researchers indicates that they have co-authored a research paper. All public edges are regarded as the collaboration of published papers in the existing literature. However, one ongoing research work that has not been published yet is treated as the private
v2
CNN, GAN MLP
v3
v1
AR VR, UI VR, MLP
VR AR, UI
v4
v5
v6
VR, AR MLP, UI AR
v9
v13
CNN GAN
GAN CNN
GAN UI, CNN
v12 SQL
v7 v8
v10
v11
GAN CNN
UI, SQL
SQL
(a) Attributed public-private graph G′v3 ∪ G′v5
v2
v1
CNN, GAN MLP
v3
VR, UI VR, MLP
AR, UI
v5
MLP, UI
v4
AR
v13
CNN GAN
GAN CNN
v6 v9
GAN UI, CNN
v7
v12 SQL
v8 H v10
v11
GAN CNN
SQL
UI, SQL
(b) Attributed public-private graph G′v5
Fig. 1: An attributed public-private graph has two private stargraphs Gv3 and Gv5 . For a query q = v5 and k = 3, the 3-core attributed community is the pink area H in Figure 1(b). collaborations for these authors. In terms of the view of each user, the whole network is the union of the public network and its private graph. The public-private graph affects not only the view of the network structure but also the task results of different algorithms. As a result, public-private graph analytics is essential for attracting various research across various tasks, including correlation [10], clustering coefficient [8], keyword search [11], truss mining [12], all-pair shortest paths [13], etc. Community search aims to find a query-dependent community containing a given set of query nodes in graphs, which has wide applications in social relations discovery and personalized recommendations. In the literature, many dense subgraph-based community models have been studied in different types of networks, including simple graphs [14], directed graphs, attributed graphs, multilayer graphs, and heterogeneous graphs [15], [16]. Unfortunately, community search over public-private networks has not been investigated, due to the technical challenges of indexing private information for efficiency. As each user has its own private network, it is an
expensive cost to build precomputed information for all users’ public-private network in a real large-scale graph with millions of users. Moreover, except for the topological structure, nodes are usually associated with attributes to represent the node properties, e.g., gender, interests, check-in information, and so on. Thus, it is important to discover query-dependent attributed communities over such public-private attributed graphs. In this paper, we study a new problem of attributed community search in public-private graphs (ACS-PP) based on k-core, where each node has at least k neighbors within it [17]–[19]. For an attributed public-private graph, the public graph is represented by the black edges in Figure 1(a), while the blue and red edges correspond to the private graphs of v3 and v5 , respectively. Given a query node q, our novel model seeks to find a connected k-core containing q that maximizes the number of common attributes in the union of the public graph and q’s private graph. For example, when the query q = v5 , the public-private community H is the 3-core containing v5 with the largest number of two common attributes {“CNN”, “GAN”} shown in Figure 1(b). To tackle ACS-PP, one straightforward method is to first enumerate the possible common attributes and then return one feasible community with the largest attributes. The enumeration can process in ascending order of attribute size or adopt a binary search strategy. However, both methods are time-consuming due to an exponential number of validations of feasible communities. To reduce the search space and accelerate k-core validation, we explore indexing-based methods for accelerating ACSPP. Due to the complex attributed network and the sensitive information of private graphs only owned by its users, designing an effective indexing structure to support queries on any node q is challenging. The reason is threefold. First, the community structure and shared keywords may be independent of each other in the community model, which brings twodimensional quality requirements to consider simultaneously. Second, for different users, it may contain quite different private structures in the graph and node attributes, in terms of size and distribution. Third, designing indexes for each publicprivate graph is impractical for a large network with millions of nodes. To tackle these, we design a new index of public-private attribute-based frequent pattern tree (PP-FP-tree). For each node v, we build the PP-FP-tree on a small neighborhood graph by integrating its neighbors’ public edges and its associated private graph. The idea of PP-FP-tree is to preserve the common attributes that frequently appear in its neighborhood for fast retrieval to quickly identify the possible number of maximum common attributes. In addition, we equip the PPFP-tree with an auxiliary structure, the graph coreness index, which keeps records of the largest k-core that the node can be involved in public graphs. Based on the PP-FP tree, we propose an efficient algorithm for ACS-PP, which first selects a small number of candidates and then performs kcore validation through local exploration. To summarize, this paper makes the following contributions: • We formulate and study a novel problem of attributed
community search over public–private graphs (Section 3). We also present two basic solutions that combine fundamental k-core decomposition along with the handling of candidate attribute sets (Section 4). • We propose an integrated scheme of constructing public global graph index and private personalized graph index. For the private index, we design a compact PP-FPtree index for each node with a private graph. These indexes allow us to efficiently search for communities in the public-private graph while protecting the privacy of each private graph user (Section 5). Based on the PPFP-tree index, we propose our efficient indexing-based search algorithm, PP-FP. In this way, we fast extract key candidates and perform community validation for searching communities (Section 6). • Experiments demonstrate the superiority of our PP-FP algorithm in addressing the ACS-PP problem, showcasing significant advantages in query efficiency and community quality for large-scale public-private graphs (Section 7). II. R ELATED W ORK Community discovery. The studies of community discovery are usually categorized into two types of community detection and community search. Community detection [1], [2], [20], [21] identifies cohesive subgroups throughout the graph, while community search [3]–[6], [22]–[25] is a query-based process that aims to find the most relevant community for a given node or set of nodes. Fang et al. [6] review community search algorithms based on structural cohesiveness metrics such as kcore [24], [26], k-truss [22], [27], [28], k-clique [25], [29] and k-edge-connected components [30], [31], and compare them on different graph types, including keyword-based, temporal [23] and spatial graphs [32], [33]. Attributed community search. Attributed community search seeks subgraphs that are both structurally cohesive and attribute similar [17], [34]–[37]. Huang et al. [34] propose attributed truss communities that maximize attribute relevance within dense subgraphs. Fang et al. [17] design the CL-tree, a hierarchical tree index that combines k-core and keyword information for efficient attributed community search. Chen [35] et al. introduce a parameter-free contextual model that retrieves communities by query keywords without preset structural parameters. Zhu et al. [36] focus on cohesive attributed communities by maintaining structural connectivity. Jiang et al. [37] develop an efficient community search framework for large star-schema heterogeneous information networks. Public-private graph analytics. Chierichetti et al. [8] develop scalable and efficient algorithms to compute key metrics such as reachability [38], centrality [39], and shortest paths [13] in public-private social networks. Archer et al. [38] focus on reachability for directed graphs with public, private, and protected nodes. Huang et al. [40] publish the PP-DBLP dataset derived from DBLP to support evaluation. Ebadian et al. [12] develop an efficient algorithm for discovering ktruss in public-private graphs. Jiang et al. [11] propose a
Notation
Meaning
q
The query vertex and also the root node of the PP-FP-tree index The private graph/The public-private graph of the query node q The vertex set of attribute α in 1-hop neighborhood/in public graph G The public attributes/The public-private attributes of the node v The nodes selected from the private graph index/the public graph index The combination of the sets publicS and privateS for candidate community validation The maximum shared attributes of the set S The public neighbors/The public-private neighbors of the query node q The tree node in the PP-FP-tree T All prefix paths ends with node u in tree T The prefix path ends with node P [v]x in tree T The coreness tree index of the public graph G
Gq /G′q Θα /θα attr(v)/attr′ (v) privateS/publicS S attr′ (S) N (q)/N ′ (q) P [v]x Prefix-Path(u) Prefix-Path(P [u]x ) coreT
TABLE I: Frequently used notations in this paper three-step public-private keyword search framework. Yu et al. [9] introduce a PP-graph model and the pp-core number for measuring user importance. To the best of our knowledge, this is the first work to formulate and study community search on attributed public-private networks. III. P RELIMINARIES In this section, we present useful preliminaries and identify the desiderata for communities. Then, we present our problem of public-private attributed community search. A. Public-Private Community Public attributed graph. We consider a simple model of attributed graph, i.e., an undirected, unweighted, public attributed graph G = (V, E, A), where V represents the set of vertices, E denotes the set of edges, and A is the universal set of attributes that can be assigned to the vertices. The public neighbors of v is denoted as N (v) = {u ∈ V : (v, u) ∈ E}. For each vertex v ∈ V , it is associated with a specific set of attributes, denoted as attr(v) ⊆ A. This means that each vertex can possess multiple attributes, with attr(v) serving to characterize the vertex’s properties and relationships within the graph, such as the users’ interests, location check-ins, and educational backgrounds in social networks. Here, the whole structure of G and the attributes attr(v) for any vertex v are publicly accessible to everyone. However, users can hide their personal contact and properties in their own graphs, leading to a private graph as follows. Definition 1 (Private Star-Graph). Given a vertex u ∈ V in a public attributed graph G, the private star-graph of u is denoted as Gu = (Vu , Eu , Au ) where u is the center node. Here, the private edge Eu ⊂ {u} × V is a star structure with Eu ∩ E = ∅. Thus, Vu is the set of u’s private neighbors, i.e., Vu = Np (u) = {v ∈ V : (v, u) ∈ Eu }. For each vertex v ∈ Vu , v is also associated with private attributes denoted by attrp (v), where attrp (v) ⊆ A and no common attributes in public and private simultaneously, i.e., attrp (v)∩attr(v) = ∅.
Combining the public graph G(V, E, A) and all private graphs Gu for u ∈ V , a real-world public-private graph can S be represented as G = G ∪ v∈V Gu . In Figure 1(a), a realworld public-private graph is the union of public graph G and all private graphs including Gv3 and Gv5 , represented as G = G ∪ G v3 ∪ G v5 . In the view of different center node, the whole graph structure and attributes are quite different as follows. Definition 2 (Public-private Graph). Given a vertex u ∈ V in a public attributed graph G, the public-private graph in the view of u is the union of public graph G and its private graph Gu , i.e., G ∪ Gu . As in Figure 1(b), the public-private graph in the view of v5 is formed by the public graph G with its private graph Gv5 , which is expressed as G′v5 = G ∪ Gv5 . Dense community structure of k-core [17]. A k-core of a graph G is a maximal subgraph H of G such that every vertex v ∈ V (H) has degree at least k within H. In other words, ∀v ∈ H, degH (v) ≥ k. This structural property makes k-cores particularly useful for capturing dense subgraphs, which has been widely used in many core-based community models [18], [19], [41]. However, the hidden relationships bring significant challenges for identifying cohesive k-core in public-private graphs. Table I lists the notations usually used in the paper. Desiderata of good public-private queried community. We analyze the criteria of a good attributed community, w.r.t., a given query vertex q in the public-private graph G ∪ Gq . Specifically, we regard a public-private connected community H should satisfy the following properties: • (I) Query node participation. Since the queried community is highly relevant to the query node, it needs query node participation, i.e., q ∈ V (H). • (II) Private relevant. The private graph is only accessed to query vertex q, which needs to be involved in the online process of community search by sharing homogeneous attributes with q in public and private graphs. • (III) High attribute correlation. The more the number of common attributes, the higher the correlation of the vertices in the community. • (IV) Structure cohesiveness. A tightly-knit structure indicates that there are more connections between the nodes within the community, reflecting a higher level of activity among its members. For the criteria of a good queried community, we can guarantee the (I), while for the subsequent (II) to (IV), we aim to find a balance that maximally satisfies these standards simultaneously. To quantify the common attributes in publicprivate graphs, we begin with a new definition as follows. Definition 3 (Common PP-Attributes). Given an attributed public-private graph H = (V, E, A). For each node v ∈ V , let attr′ (v) represent the attribute set of the node v. The attribute of the graph H is defined as the intersection of the attribute
sets of all nodes in the graph, as \ attr′ (H) = attr′ (v). v∈H
In Figure 1(b), consider the graph H consisting of nodes {v5 , v6 , v7 , v8 , v9 } with corresponding edges between them, the common pp-attributes of H is the intersection of the attributes of these nodes, that is, attr′ (H) = {CNN, GAN}. B. Problem Statement Based on the common pp-attributes, we can give a new community model to capture the homogeneous attributes in a public-private graph, which is different from the existing core-based attribute community [18], [19], [41]. Because the private information of edge connections and node attributes is only known to the query itself, the existing algorithms [34], [41] cannot precompute the information required for index construction. Hence, they are not directly applicable, which motivates our formulation. Therefore, we define the problem of k-core community search on attributed public-private graphs as follows. Problem 1 (ACS-PP). Given a public attributed graph G = (V, E, A), a query vertex q, construct a queried pp-graph G′q = G ∪ Gq = (V ∪ Vq , E ∪ Eq , A ∪ Aq ), a parameter k ∈ Z + , the problem is to find a subgraph H ⊆ G′q satisfying the following properties: • Query participation. q ⊆ V (H); • Public-private structure cohesiveness. H is a connected k-core within G′q ; • Common attribute maximality. The size of attr′ (H) is maximal. Problem hardness. The ACS-PP problem can be shown to be NP-hard problem as follows. First, one special instance of ACS-PP is equivalent to the ACQ problem [17], when the private information is empty, i.e., Gq = ∅. Thus, both ACS-PP and ACQ problems find the maximum common attributes in a k-core community containing the query vertex q. However, the problem ACQ is NP-hard by reducing from the NP-complete problem of maximum clique discovery in a graph G, which is turned out to find a complete subgraph with the largest common attributes. Example 1. Consider the attributed public-private graph G′v5 , q = {v5 } in Figure 1(b). H is a 3-core subgraph found in G′v5 , representing the community that shares the maximal common attributes {CNN, GAN} with query node v5 . Application scenarios. Our ACS-PP problem has several practical application scenarios for social recommendations and academic community search. Such public-private querying services can be supported in two setting. First, the service can be provided by the network platform, which owns the whole public network G and allows the access to private graph Gq only if the query is issued by the query user q. This follows the public-private setting proposed by Chierichetti et al. [8].
Algorithm 1 Online-basic (G′q , q, k) Input: Public graph G, query q, private graph Gq , integer k Output: An attribute-maximized k-core community H containing q 1: Construct the pp-graph G′q ← G ∪ Gq ; 2: Reduce G′q to its k-core subgraph; 3: for each attribute α ∈ attr ′ (q) do 4: Collect vertices Vα ← {v ∈ G′q | α ∈ attr(v)}; 5: for d = 1 to |attr ′ (q)| do 6: update ← False; ′ 7: for each subset T S ⊆ attr (q) with |S| = d do 8: VS ← α∈S Vα ; 9: Construct candidate graph G′q [VS ]; 10: Check if k-core community H ∗ in G′q [VS ] with q ∈ H ∗ ; 11: if such H ∗ exists then 12: H ← H ∗ ; update ← True; 13: if update = False then 14: break; 15: return the community H
In this case, the network data and public indexes could be done efficiently within the central computation by taking a small transforming cost. Second, following the fully on-device computation with strict privacy protection [42], our problem could be further extended to allowing public data G and private data Gq to be separately stored in the network platform and user q’s devices, respectively. Our developed techniques offer public and private indexing to support the extraction of a small candidate graph, which is transferred from the platform to the user devices. Finally, community candidate validation can be performed efficiently on a local device. IV. BASIC O NLINE SEARCH SOLUTIONS In the following, we introduce online search algorithms for ACS-PP in public-private graphs. Straightforward online search. Algorithm 1 of Online-basic consists of four steps. Firstly, construct the public-private graph G′q by combining the public graph G and the private graph Gq of the query node q, then reduce it to its k-core subgraph to ensure structural cohesiveness (lines 1-2). Next, for each attribute α in the query node’s attribute set attr′ (q), collect the set of vertices Vα in G′q that contain this attribute (lines 3-4). Then, start from the 1-attribute sets and iteratively increase their sizes from 1 to |attr′ (q)|. To obtain candidate node sets, we consider each attribute subset S ⊆ attr′ (q) of size d, and compute VS as the intersection of all Vα where α ∈ S. (lines 5-8). Finally, induce the subgraph G′q [VS ] from the nodes in VS , and perform k-core validation (lines 8-9). If such a community H ∗ is found, update H with H ∗ (lines 11-12). If no valid community is found for any subset of size d, the algorithm terminates and returns H (lines 13–15). Binary fast search algorithm. However, Online-basic is timeconsuming due to its sequential search strategy. To improve efficiency, we propose Online-binary, which adopts a binary search approach. It begins at the middle value |attr′ (q)/2| and adjusts the search range based on whether a valid k-
core community is found, shifting upward if successful, or downward otherwise. This continues until the community with the largest common attributes is identified. The main issue with these algorithms is the high cost of enumerating attribute combinations. To address this, we propose a novel search framework as follows. Our PP-FP framework overview. Given a query vertex q with its public-private attributed graph, our framework aims to efficiently identify a k-core community that maximizes the common attributes shared by all members. The framework is built upon two complementary index structures, a private PP-FP-tree index constructed for the query vertex q, and a public index built over the entire public graph. The query process consists of three phases. In Phase-I, the PP-FP-tree is used to identify candidate nodes in the private neighborhood that share the maximal common attributes with q. In PhaseII, the common attributes selected from the PP-FP-tree are queried over the public index to expand candidate nodes. In Phase-III, candidates from Phase-I and Phase-II are merged and validated, finding a community that meets both attribute maximality and structure constraint. V. P UBLIC - PRIVATE INDEX CONSTRUCTION In this section, we introduce our public-private index construction, which consists of two main components. • Component I: private PP-FP-tree index construction. Construct a compact PP-FP-tree index for each query node in its private graph, to quickly identify the combination of the most frequently occurring attributes. • Component II: public graph index construction. Build a coreness tree index for the entire public graph to efficiently identify nodes that can potentially contribute to forming k-core and satisfying attribute combinations. A. Preliminaries of PP-FP-Tree Index v4 b, c, d
a, c, e
b, c
v1
v2
v6
v3 b, c, d
b, c, d, e
q
v5
a, b, c, d, e
b, e
(a) Public-private attributed graph G′q
(b) Node attribute list
(c) Node attribute map
Fig. 2: Preliminaries of PP-FP-Tree Index. Now, we introduce the preliminaries for PP-FP-tree index construction. In the public-private graph, we focus on the 1-hop neighborhood, which is the subgraph of G′q induced by the union of public-private neighbors of the query node q, i.e., N ′ (q) = N (q) ∪ Np (q). The process consists of two steps. First, we collect all attributes of q, i.e., attr′ (q). For each neighbor u ∈ N ′ (q), these vertices are sorted in decreasing order of shared attributes with the query vertex q, i.e., |attr′ (u) ∩ attr′ (q)|. This results in the node attribute list. Example 2. First, we obtain the 1-hop neighborhood of the query node q from the public-private attributed graph in Figure 2(a), denoted as N ′ (q) = {v1 , v2 , v3 }. Then, these
nodes in N ′ (q) are sorted in descending order based on the number of common attributes they share with q. As a result, we obtain the node attribute list in Figure 2(b). Second, for each attribute α ∈ attr′ (q), we list the set of vertices containing the attribute α, denoted as Θα = {u ∈ N ′ (q) | α ∈ attr′ (u)}. Then, the vertices u in Θα are sorted in decreasing order of |attr′ (u) ∩ attr′ (q)|. This forms the node attribute map. Example 3. For each attribute in Figure 2(b), where attr′ (q) = {a, b, c, d, e}, we list each set of vertices containing the attribute α ∈ attr′ (q). When α = c, the corresponding vertex set is Θα = {v1 , v2 , v3 }, sorted in descending order based on the number of common attributes with q. The final result is shown in Figure 2(c). The detailed construction of the node attribute list and node attribute map can be found in Algorithm 2. B. Index Construction of PP-FP-Tree Now, we present a novel index of public-private frequent pattern tree called PP-FP-tree, which is inspired by the classic FP-tree [43] originally proposed for frequent itemset mining. Our PP-FP-tree extends the FP-tree by integrating multiple features of private edges and attributes, the structural coreness, and common attributes. For a query vertex q, its PP-FP-tree is built on the public-private graph G′q . Our PP-FP-tree consists of two data structures: one tree T and one node-link table B. First, the tree T rooted by q consists of a few nodes P [u]x , where the root is the center query node q and the neighbor u ∈ N (q) ∪ Np (q) for an integer x ∈ Z+ . For any tree node P [u]x , the prefix path of P [u]x is the path from P [u]x to root q, denoted as Prefix-Path (P [u]x ). Second, the table B consists of several structured chains, where each chain links to a public and private neighbor of q, i.e., B[u] = {PP-FP-tree node P [u]x : u ∈ N (q) ∪ Np (q)} for public-private neighbor u in G′q and the integer indicator 1 ≤ x ≤ |B[u]|. Here, the number x indicates the insertion order of u’s tree nodes into the tree T . Besides the tree structure of T rooted by node q, each tree node P [u]x is also associated with three elements, representing the additional attribute information as follows: • P [u]x .Prefix-Attr: is the set of the common attributes shared by all tree nodes along the prefix-path from P [u]x to the root q. Then, P [u]x .Prefix-Attr = T ′ P [w]y ∈Prefix-Path(P [u]x ) attr (P [w]y ). • P [u]x .Prefix-AttrNum: is the number of common attributes in P [u]x .Prefix-Attr, i.e., P [u]x .Prefix-AttrNum = |P [u]x .Prefix-Attr|. • P [u]x .Overall-AttrNum: is the number of common attributes between u and root q, i.e., P [u]x .Overall-AttrNum = |attr′ (u) ∩ attr′ (q)|. Example 4. In Figure 3(a), the prefix path of P [v3 ]1 is PrefixPath (P [v3 ]1 ) = {P [v1 ]1 , P [v2 ]1 , P [v3 ]1 }. P [v3 ]1 .Prefix-Attr represents the attributes shared by all tree nodes in PrefixPath (P [v3 ]1 ), which is {c}. Thus, P [v3 ]1 .Prefix-AttrNum
Vertex
v1
Head of node-link
v2 v3 Node-link table B
root : q v1 , 4, 4, {b, c, d, e} P[v1]1 v2 , 2, 3, {c, e} v3 , 1, 3, {c}
P[v2]1 P[v3]1
(a) PP-FP-tree index
Prefix paths ended with v3
root : q v2 , 1, 3, {a} v3 , 2, 3, {b, d}
tree T
P[v2]2 P[v3]2
{(v1 : 1, v2 : 1, v3: 1),
v1 , 4, 4, {b, c, d, e}
(v1 : 2, v3 : 2)}
v2 , 1, 3, {a}
Threshold
v2 , 2, 3, {b, c}
{(v1 :1, v3: 2),
(v1 : 1, v3 : 2)}
(b) Failed conditional PP-FP-tree
root : q
CP[v1]
v1 , 3, {b, c, d}
CP[v3]
v3 , 3, {b, c, d}
(c) Successful conditional PP-FP-tree
Fig. 3: An example of PP-FP-tree index for querying q and k = 2 to search 2-core community with at least 3 vertices. Algorithm 2 Private indexing: nodes and attributes extraction for PP-FP-tree construction Input: A query node q, and the public-private graph G′q Output: A node attribute list nalq and a node attribute map namq of the query node q 1: Get public-private neighbors N ′ (q) of the query node q in G′q ; 2: Obtain attr ′ (q) ← attr(q) ∪ attrp (q); 3: for each node v ∈ N ′ (q) do 4: attr ← attr′ (v) ∩ attr′ (q); 5: if attr ̸= ∅ then 6: Build a list node l[v] ← (v, |attr|, attr); 7: Add l[v] into nalq ; 8: Sort nalq by (−l[v].|attr|); 9: for each list node l[v] ∈ nalq do 10: for each attribute α ∈ l[v].attr do 11: Add v into the vertex set Θα in namq ; 12: return the attribute list nalq and attribute map namq ;
Algorithm 3 Private indexing: PP-FP-tree index construction Input: A node attribute map namq of the query node q Output: A PP-FP-tree T for the query node q 1: Initialize PP-FP-tree T rooted by the node q; 2: for each vertex set Θα ∈ namq do 3: Initialize r ← root; 4: for each vertex v ∈ Θα sequentially do 5: if r does not contain child node v then 6: Create a new tree node P [v]x = (1, |attr′ (v) ∩ attr′ (q)|, α); 7: else 8: Increment P [v]x .Prefix-AttrNum by 1; 9: Update r ← P [v]x ; 10: return the PP-FP-tree T
root : q v1 , 1, 1, {c}
= 1. Meanwhile, P [v3 ]1 .Overall-AttrNum represents the total number of attributes shared between node v3 and the query root q, which can be found in Figure 2(b) as 3. Therefore, in Figure 3(a), the value of P [v3 ]1 is (1, 3, {c}). We construct the PP-FP-tree using the vertex sets Θα for each attribute α ∈ attr′ (q). For each attribute α, we sequentially insert every vertex u ∈ Θα into the tree T as P [u]x and update the three key information mentioned above. Algorithm 3 outlines the details of PP-FP-tree construction in Figure 3. We firstly initialize the PP-FP-tree T rooted by the node q (line 1). For each attribute α in the node attribute map in Figure 2(c), r is initialized to the root (lines 2-3). When inserting a vertex v, we check whether v is a child node of the current node r. If not, create a new tree node P [v]x .(Prefix-AttrNum, Overall-AttrNum, Prefix-Attr) initialized to (1, |attr′ (v) ∩ attr′ (q)|, α) (lines 4-6); Otherwise, the corresponding P [v]x is updated with its prefix-AttrNum incremented by 1 (lines 7-8). r is then updated to P [v]x to continue the construction along the prefix path (line 9). Finally, return the PP-FP-tree T (line 10). Example 5. Figure 4 shows the process of PP-FP-tree construction. It illustrates two cases in Algorithm 3, creating a new tree node (lines 5-6) and updating an existing tree node (lines 7-8). Consider the node attribute map in Figure 2(c). First, we insert vertices {v1 , v2 , v3 } with attribute c, which results in Figure 4(a). Second, consider the vertices {v1 , v3 }
root : q
root : q
P[v1]1 v1 , 2, 2, {c, b} P[v1]1 v1 , 2, 2, {c, b} P[v1]1
v2 , 1, 1, {c}
P[v2]1
v2 , 1, 1, {c}
v3 , 1, 1, {c}
P[v3]1
v3 , 1, 1, {c}
(a) After processing attribute c with all vertices
P[v2]1 P[v3]1
(b) After processing attribute b with vertex v1
v2 , 1, 1, {c}
P[v2]1
v3 , 1, 2, {c}
P[v3]1
v3 , 1, 2, {b}
P[v3]2
(c) After processing attribute b with vertex v3
Fig. 4: An example on PP-FP index construction. with attribute b, and r is initialized to root. Since r has the child node v1 , thus {b} is added to P [v1 ]1 in Figure 4(b). r is then updated to P [v1 ]1 . For the next vertex v3 , since P [v1 ]1 has no child node for v3 , a new tree node P [v3 ]2 is created as the child node of P [v1 ]1 in Figure 4(c). In the following, we make two useful observations. Observation 1. If P [v]x .Prefix-AttrNum = k, all tree nodes appear in the Prefix-Path (P [v]x ) contain at least k common attributes with the query node q. Observation 2. If the length of the prefix path |Prefix-Path(P [v]x )| = n, then all n nodes in this prefix path share the attributes in P [v]x .Prefix-Attr. In Figure 3(a), since P [v3 ]1 .Prefix-AttrNum = 1, by Observation 2, the tree nodes in Prefix-Path (P [v3 ]1 ) = {P [v1 ]1 , P [v2 ]1 , P [v3 ]1 } all share one common attribute with the root node q. According to Observation 1, |Prefix-Path(P [v3 ]1 )| = 3 indicates that three tree nodes shares the attribute c.
C. Conditional PP-FP-Tree
Algorithm 4 Public indexing: global graph index construction
We note that the PP-FP-tree cannot support all queries. For instance, when searching for the 2-core community H with maximal attributes in Figure 6, the result cannot be obtained solely based on Observations 1 and 2. Since the attributes of a node may be distributed across different branches of the PP-FP-tree, it’s hard to reconstruct the complete attribute overlap for each node. To address this limitation, we construct a conditional PP-FP-tree to better identify nodes with strong attribute overlap with the query node. Observation 3 forms the basis for constructing this conditional tree.
Input: An attributed public graph G = (V, E, A) Output: The coreness tree index coreT 1: Initialize an empty coreness tree index coreT ; 2: Perform k-core decomposition to compute coreness(v) for each node v ∈ G; 3: for each connected component U ⊆ G do 4: Initialize an empty branch for connected component U ; 5: for each coreness value t in U do 6: Build a coreness tree node ut ← ut ∪ {v ∈ U | coreness (v) = t}; 7: Assign an attribute map mt to the tree node ut ; 8: for each attribute α ∈ attr(ut ) do 9: Add α to mt ; 10: for each node v ∈ ut do 11: if α ⊆ attr(v) then 12: Add v to vertex set θα for attribute α in mt ; 13: Insert (ut , mt ) into branch U in ascending order by t; 14: Insert the branch U into coreT ; 15: return coreT ;
Observation 3. Given the PP-FP-tree of the query node q represented by T , the attribute set of a node v can be represented as: [ attr′ (v) ∩ attr′ (q) = P [v]x .Prefix-Attr P [v]x ∈T
In Figure 3(a), according to Observation 3, the attribute set of v3 can be represented by the attr′ (v3 ) ∩ attr′ (q) = P [v3 ]1 .Prefix-Attr ∪ P [v3 ]2 .Prefix-Attr. To extract all possible combinations of common attributes for a subgraph containing vertex v, we motivate to construct a conditional PP-FP-tree by collecting all paths from the leaf node v to the root q. However, we do not need to enumerate all possible conditional PP-FP-trees, we can use the following requirements to reduce such constructions. Definition 4 (Requirements for Conditional PP-FP-tree Construction). Given a query node q and its PP-FP-tree T , a tree node P [v]x ∈ T is considered for conditional PP-FP-tree construction if all the following conditions hold: • P [v]x .Overall-Attr ≥ ℓ; • P [v]x .Prefix-Attr < ℓ; • |Prefix-Path(P [v]x )| ≥ k, which means at least k nodes share the prefix attributes of P [v]x with query node q. Here, ℓ denotes the required number of common attributes. Such a node v is then used to construct its conditional PPFP-tree.
Example 6. In Figure 3(c), we build a conditional PP-FP-tree Tv3 for v3 . We first obtain Prefix-Path(v3 ) from the tree T , including {v1 : 1, v2 : 1, v3 : 1} and {v1 : 2, v3 : 2}. Then, we obtain the common attribute Cv3 = attr′ (v3 ) ∩ attr′ (q). Since Cv3 ̸⊆ attr′ (v2 ), node v2 is pruned. Finally, the remaining paths are merged to form Tv3 , where node frequencies indicate co-occurrence with v3 . As shown in Figure 3(c), we obtain CP [v1 ] = (v1 , 3), CP [v3 ] = (v3 , 3), indicating that v1 , v3 and q share 3 common attributes {b, c, d}. D. Public Graph Index Construction
We first extract all prefix paths in tree T that end with node v, denoted as Prefix-Path(v). Based on these paths PrefixPath(P [v]x ) ∈ Prefix-Path(v), we construct a conditional PP-FP-tree that preserves only high-frequency nodes sharing significant attribute overlap with v. This facilitates efficient mining of frequent attribute patterns and accurate identification of nodes that share the most attributes with the query node.
The construction of the coreness tree index involves several steps. First, perform k-core decomposition to determine the coreness of each node in the public graph. Next, identify the connected component each node belongs to, grouping nodes within the same connected component each node belongs to, grouping nodes within the same connected component U into the same branch. Finally, within each branch, nodes are assigned to different tree nodes ut based on their coreness t. Besides this, we equip each tree node ut with an attribute map mt . This map records each attribute that appears in the nodes of the tree node ut , along with the corresponding nodes where each attribute occurs. This allows efficient retrieval of nodes satisfying coreness and sharing specific attributes simultaneously, facilitating attribute-based queries within the public graph. Detailed pseudocode is presented in Algorithm 4.
Definition 5 (Conditional PP-FP-tree). Given a PP-FP-tree T rooted by q and a vertex v ∈ N ′ (q), the conditional PPFP-tree of v, denoted as Tv , is defined as follows. First, extract all prefix-paths Prefix-Path(P [v]x ) from T to form a subtree rooted at q. Then, obtain the common attribute set Cv = attr′ (q) ∩ attr′ (v) and prune all tree nodes without attribute in Cv from the extracted subtree, and merge the remaining paths to obtain the conditional PP-FP-tree Tv .
Example 7. To construct the coreness tree index coreT in Figure 5(b) for the public graph G in Figure 5(a), we first perform a k-core decomposition on G to obtain the coreness of each node. Next, nodes belonging to the same connected component U are grouped into the same branch of coreT , with isolated nodes (i.e., nodes with coreness 0) serving as the root node. As a result, one branch contains tree nodes u0 : {v13 }, u1 : {v1 , v2 , v3 , v4 , v5 }, u2 : {v6 , v7 , v8 , v9 }, while
v2
VR, UI
AR, UI
v3
v1
MLP
CNN
v5
v6
MLP, UI
v4
VR, MLP
AR
v13
GAN
SQL
v7
v12
v8
v9
CNN
UI, CNN
Algorithm 5 PP-FP-tree based Attributed Community Search
v10
v11
UI, SQL
SQL
(a) Attributed public graph G α
θα
v1 v4 v2 AR UI v1 v2 v3 MLP v3 v4 v5 VR
coreness : 1
v1 v2 v3 v4 v5
m1
coreness : 2
α
v6 v7 v8 v9
u2
u1 θα
coreness : 0
α
v13
AR
u0
θα
m0
v13 coreness : 2
v10 v11 v12
u2
α UI SQL
v9 CNN v6 v8 v9 v7 GAN UI
θα
v10 v10 v11 v12
m2
m2
(b) Coreness tree index CoreT
Fig. 5: Public indexing construction for public graph G. another branch contains the tree node u2 : {v10 , v11 , v12 }, as they belong to a different connected component in the graph. Each tree node ut maintains an attribute map mt , which records, for each attribute appearing in the nodes of ut , the set of nodes in which the attribute occurs. VI. PP-FP- TREE QUERYING ALGORITHM In this section, we introduce a public-private community querying algorithm based on the public-private graph index. The key idea of our PP-FP-tree based querying algorithm consists of three phases: attribute selection, candidate subgraph expansion, and community validation. • Phase-I: Attribute selection via PP-FP-trees. We first extract the largest set of common attributes from our constructed PP-FP-trees, where a possible candidate subgraph of k nodes associated with such attributes exists. • Phase-II: Candidate subgraph expansion in public graph. Taking the attributes from Phase-I, we expand the candidate subgraph locally in public graph by involving those new nodes that have the coreness of at least k. • Phase-III: Public-private community validation. Finally, we validate the candidate subgraph peeled by the core decomposition algorithm to meet the requirements of k-core and common attributes. A. Phases-I, II: Attribute Selection and Candidate Expansion Phase-I: Attribute selection via PP-FP-trees. First, we search the PP-FP-tree index in the query node’s public-private neighborhood to find the largest attribute set attr′ (privateS) shared by at least k nodes, which forms the set privateS. Algorithm 5 outlines the details of Phase-I. We initialize privateS as an empty set. First, we set N as the maximum number of attributes shared with q among all tree nodes in T (lines 1-2). Starting from N , we iteratively search the PP-FPtree to find a node set privateS sharing N attributes (lines 3-4). If |privateS| ≥ k, we continue with the validation step in Algo. 6. If a feasible community H is found, we
Input: PP-FP-tree T , query q, integer k Output: A public-private attributed community H 1: Initialize privateS ← ∅; 2: N ← maxP [u]x ∈T P [u]x .Overall-AttrNum; 3: while N > 1 do 4: Extract a set privateS of candidate vertices with at least N common attributes, i.e., privateS = {w | w ∈ Prefix-Path(v), P [w]x .Prefix-AttrNum ≥ N }; 5: if |privateS| ≥ k then 6: Validate community H based on privateS in Algo. 6; 7: if ∃ a feasible community H then return H; 8: if P [v]x satisfies the conditions of building conditional PP-FP-tree by Def. 4 then 9: Search candidate set by constructing conditional PP-FP-Tree Tv by Def. 5 and obtain a candidate set privateS; 10: if |privateS| ≥ k then 11: Validate community H based on privateS in Algo. 6; 12: if ∃ a feasiable community H then return H; 13: Decrement N by 1; 14: return ∅;
return H (lines 5-7). If |privateS| < k, we check whether the conditions for constructing a conditional PP-FP-tree are satisfied. If so, we construct the conditional PP-FP-Tree Tv by Def. 5 to obtain a candidate set privateS; If the new |privateS| ≥ k, we continue with the validation step in Algo. 6. If a feasible community H is found, we return H (lines 8-12). If no valid community is found, we decrement N by 1 and repeat the process (line 13). Example 8. We illustrate the process of attribute selection based on PP-FP-tree in Phase-I in Figure 6. We first start from N = 4 since it is the maximal common attribute number in the tree in Figure 3(a). But, there exist no other nodes sharing the same attributes, resulting in |privateS| < k. Thus, we reduce N by one to check N = 3. We check the tree node P [v2 ]1 but cannot build its conditional PP-FP-tree shown in Figure 3(b). Then, we proceed to the tree node P [v3 ]1 and find three common attributes in Figure 3(c). This indicates a feasible community H with the node set of privateS = {v1 , v3 }, which satisfies the 2-core requirement. Phase-II: Candidate subgraph expansion in public graph. In this phase, we need to identify the nodes in the public graph G that could expand the k-core community with maximal attributes with q. First, we locate the branch in the coreness tree index coreT where the query node q is positioned, which represents the connected component U that q belongs to in the public graph. Second, using the attribute set attr′ (privateS) identified in the Phase-I, we search within the connected component U for nodes that satisfy the conditions of coreness ≥ k and sharing the attribute set attr′ (privateS). These nodes form the set publicS, representing the nodes in the public graph that could potentially expand the k-core community. Example 9. Consider the public attributed graph in Figure 6.
Phase-I : Attribute selection b, c, d
v4
public-private attributed graph G′q a, c, e b, c
v1
query
PP-FP tree index
v6
v2
b, c, d, e
v3
q
v5
b, c, d
a, b, c, d, e
b, e
shared attributes
privateS
root : q v1, 3, {b, c, d}
public attributed graph G a, e b, c
v4
v1
v3 b, d
v2
v6
b, c, d, e
q
v5
a, b, d, e
b, e
build
coreness tree index
v3, 3, {b, c, d}
index
v1
{b, c, d}
coreness ≥k
attributes
connected component
v1 v2 v3 v4
1-hop neighbors
union
v3
a b c d e
v2 v1 v3 v4 v1 v4 v1 v3 v4 v1
v4 Phase-III: Community validation
S
Phase-II : Candidate subgraph expansion b, c, d
query node
q
v3
v1
union
v1
v4
publicS
2-core community share {b, c, d}
v1
v4
v3
q
Fig. 6: PP-FP-tree query algorithm framework with k = 2. Algorithm 6 Community validation using candidate privateS
C. Complexity Analysis
Input: candidate privateS, query q, coreness tree index coreT Output: A boolean value indicating the feasibility of finding community H by privateS 1: Initialize publicS ← ∅, S ← ∅; 2: publicS ← get the union of nodes in the tree node ut with coreness t ≥ k and sharing attr(privateS) in the connected component {U | q ∈ U } from coreness tree index coreT ; 3: S ← privateS ∪ publicS; 4: if |S| ≥ k + 1 then 5: if a non-empty k-core community H exists in the induced subgraph G′q [S] containing q then return True; 6: return False;
In the following, we analyze the complexity of PP-FPtree index construction and search algorithms. We denote the size of vertices, edges, and attributes in public graph G as P n = |V |, m = |E|, and t = | v∈V attr(v)|, respectively. Assume that a connected graph G with P n ∈ O(m). The number of private edges is mp = v∈V |Np (v)|. Thus, the total number of public and private edges is denoted as m̂ = m + mp . The maximum number of public attributes and private attributes are denoted as τmax = maxv∈V |attr(v)| and ρmax = maxq∈V,v∈Np (q) |attrp (v)|, respectively. The publicprivate attribute of q is A′ (q) = attr(q) ∪ attrp (q).
To expand the k-core community with q, we first locate the connected component containing q where all nodes have coreness ≥ k. We then check whether these nodes share the attributes {b, c, d} from Phase-I. Only {v1 , v4 } satisfy this condition, forming the set publicS. B. Phase-III: Public-Private Community Validation Phase-III: Candidate community validation. Algorithm 6 presents the details of Phase-III. Two sets are initialized: publicS, representing the set of candidate nodes in the public graph; S, representing the final candidate set (line 1). publicS is determined as the union of node sets with coreness ≥ k and sharing attribute set attr′ (privateS) in the connected component where q is located from coreness tree index coreT (line 2). The final set S is then obtained as the union of privateS and publicS (line 3). If the size of S is at least k + 1, and a non-empty k-core community H containing q exists in the induced subgraph G′q [S], return True (lines 4-5). Otherwise, return False (line 6). Example 10. We obtain privateS from Phase-I and publicS from Phase-II. By combining them, we have S = privateS ∪ publicS = {v1 , v3 , v4 }. Since |S| > 2, we perform community validation and obtain a 2-core community sharing {b, c, d}.
Complexity of index construction. We analyze the index construction in terms of public indexing and private indexing. First, we consider the public indexing in Algorithm 4. The core decomposition takes O(m) time and O(m + t) space for storing the entire graph G. To construct connection components in k-cores, it makes use of union-find structure taking O(mα(n)) time and O(n) space, where α(n) is an inverse Ackermann function usually with α(n) ≤ 5 in practice. Moreover, Algorithm 4 takes O(t) time to reorganize the nodes’ attribute map. Overall, Algorithm 4 takes O(mα(n)) time and O(n + m + t) ⊆ O(m + t) space. Second, we consider the private indexing in Algorithm 2. For each vertex q ∈ V , it constructs the PP-FP-tree by the onetime scanning of all attributes P of nodes in q’s public and private neighborhood. It takes O( v∈N (q)∪Np (q) |attr(v)∪attrp (v)|) time. Thus, the total time P of constructing the PP-FP-tree P of all nodes q ∈ V is O( q∈V P v∈N (q)∪N P p (q) |attr(v) ∪ attrp (v)|) = O((ρmax + τmax ) · q∈V v∈N (q)∪Np (q) 1) = O((ρmax + τmax ) · (m + mp )) = O((ρmax + τmax )m̂) time. As Algorithm 5 can release the memory of PP-FP-tree index after the construction of each vertex, it takes O(m + t + mp + nρmax ) = O(m̂ + t + nρmax ) space. In summary, our index construction takes O(mα(n) + (ρmax + τmax )m̂)) time and O(m̂ + t + nρmax ) space, which produces the index size of O((ρmax + τmax )m̂) space.
Complexity of query processing. We analyze the complexity of public-private attributed community search in Algorithm 5. The whole framework consists of three phases. The PhaseI selects candidate attributes A∗q in the PP-FP-tree of query vertex q. Due to the problem NP-hardness, the number of A∗q is bounded by the possible combination of A′ (q), i.e., ′ |A∗q | ∈ O(2|A (q)| ), which shares the same theoretical computation with Inc-S [41] and Dec [17]. Our PP-FP-tree techniques significantly reduce the practical enumeration of A′ (q). Based on A∗q , Algorithm 6 expands A∗q to a local subgraph Ĝ in Phase-II and adopts the community validation by a linear peeling of k-core decomposition in Phase-III. These two phases take O(|E(Ĝ)| + |A(Ĝ)|) time, where |E(Ĝ)| and |A(Ĝ)| are the size of edges and attributes in Ĝ, respectively. These two phases take O(mĜ + nĜ (ρmax + τmax )) time, where mĜ and nĜ are the size of edges and nodes in Ĝ, respectively. Here, mĜ ≪ m̂ and nĜ ≪ n for a small graph Ĝ in practice. As a result, Algorithm 5 takes O(|A∗q |(mĜ + nĜ (ρmax + τmax ))) time and O(m̂ + t + nρmax ) space. VII. EXPERIMENTS Datasets. We use nine real-world datasets of public-private networks in Table II. In the five DBLP datasets [40], each vertex represents an author where the attributes are the authors’ frequent research keywords. The number of attributes per author ranges from 1 to 20. The edges represent the co-authorship relationships between authors [a] . We treat the co-authorship in published works as public graphs and the ongoing collaborations as private graphs. The Facebook dataset includes 10 egonetworks [44], each represented by its ego-user E, where E ∈ {0, 107, 348, 414, 686, 698, 1684, 1912, 3437, 3980}. Each ego-network contains multiple real communities as the social circles. The number of attributes per node ranges from 1 to 30. The last three datasets YouTube, LiveJournal, and Orkut, each contain 5000 ground-truth communities. The number of attributes per node ranges from 2 to 50. We randomly select 10% of the nodes to add noise attributes. To generate private information in these four datasets, we convert 50% of the edges of the query nodes into private edges and change 13 attributes as the private attributes of nodes. Compared methods. We compare 5 methods as follows. • Online-basic: is our proposed Algorithm 1 of a straightforward online search. • Online-binary: is our proposed algorithm of an online search with binary search. • Inc-S [41]: is an index-based static keyword community search algorithm that improves efficiency by incremental candidate expansion and pruning. • Dec [17]: is an index-based community search algorithm that verifies candidate keyword sets decrementally. • PP-FP: is our proposed PP-FP-tree based querying algorithm, which is publicly available on GitHub [b] . [a] https://github.com/samjjx/pp-data [b] https://github.com/csyqchen/PP-FP
Note that Inc-S and Dec are two community search methods originally designed for public attributed graphs. For comparison, we treat the public-private attributed graph as a dynamic graph. Specifically, we first dynamically update the keywords and edges in the indexes of Inc-S and Dec to match the publicprivate graph, and then perform community search based on the updated indexes. Parameters and evaluation metrics. We evaluate ACS-PP in terms of quality and efficiency. For quality evaluation, we use two metrics. For datasets without ground-truth communities (DBLP), we measure the number of common attributes in the discovered community |attr′ (H)|; for datasets with groundtruth communities (Facebook, LiveJournal, and YouTube, Orkut), we adopt the F1-score between the discovered comb defined as munity H and the ground-truth community H, b b 2·prec(H,H)·recall(H, H) b [34]. For efficiency, we F 1(H, H) = prec(H,H)+recall(H, b b H) evaluate the runtime of all methods across datasets. Furthermore, we evaluate scalability on efficiency across private attribute ranges and private edge ranges on real-world datasets. The default parameter is k = 3. Exp-1: Community search efficiency evaluation. We compare the efficiency of our algorithm PP-FP with other existing community search methods from two categories: non-indexed search methods (i.e., Online-basic, Online-binary) and indexed methods (i.e., Inc-S [41], Dec [17]) as shown in Figs. 7(a)–(h). The running time of Online-basic and Online-binary is generally longer due to the exhaustive enumeration of candidates. In contrast, two index-based methods Inc-S and Dec, maintain relatively high efficiency. Nevertheless, PP-FP consistently achieves the fastest time, with only a slight increase as k grows, demonstrating superior scalability and high efficiency. Exp-2: Index construction cost and memory usage. We evaluate the overhead of our method PP-FP in terms of graph size, index size, index construction time, and memory usage. The results shown in Table II demonstrate that the total index size and memory consumption grow steadily with the graph size, indicating PP-FP is practical for large attributed graphs. Exp-3: Quality evaluation. We evaluate the quality of the discovered communities in Figures 8-12. Figures 8(a)–(c) show that PP-FP achieves almost the same community attribute gains as Online-basic while running five orders of magnitude faster. Although PP-FP performs slightly worse on a few query nodes because some attributes extend beyond their publicprivate neighborhoods, its average community attribute gain remains above 0.97, demonstrating a good balance between accuracy and efficiency. We report the F1-scores between the discovered and the ground-truth communities in Figures 912. The results show that PP-FP consistently achieves higher F1-scores than Inc-S and Dec, demonstrating the superior effectiveness of our method in identifying high-quality communities. Exp-4: Scalability test. We conducted scalability tests on DBLP2017 dataset to evaluate our method against the competitor by varying private attribute size and private edge size. (I) Scalability test w.r.t. private attribute size |Aq |. We
Datasets
|V |
|E|
|Vprivate |
|Eprivate |
Graph Size
Index Size
Construction Time
Memory Usage
DBLP2013 DBLP2014 DBLP2015 DBLP2016 DBLP2017 Facebook YouTube LiveJournal Orkut
2,221,139 2,221,139 2,221,139 2,221,139 2,221,139 4,039 1,134,890 2,798,962 3,072,441
5,432,667 6,186,831 7,012,003 7,864,133 8,794,753 88,234 2,987,624 34,681,189 117,185,083
1,265,175 1,150,642 1,018,652 870,054 690,588 172 702,958 1,798,200 1,698,008
6,007,245 5,322,474 4,518,645 3,628,517 2,658,750 1,200 2,183,530 8,404,127 6,469,106
1.5GB 1.4GB 1.2GB 1.1GB 0.9GB 1.7MB 0.3GB 1.5GB 2.6GB
3.6GB 5.5GB 5.0GB 4.3GB 3.5GB 0.6MB 3.5GB 11.7GB 12.0GB
1455.5s 2026.9s 1921.1s 1440.5s 1989.8s 5.8s 1006.3s 4175.7s 4658.1s
2.0GB 2.1GB 2.3GB 2.5GB 2.7GB 4.3MB 0.6GB 3.4GB 11.3GB
TABLE II: Datasets used in our experiments.
100
Online-basic Online-binary Inc-S
102 100
10 2 2
3
4
5
6
Inc-S Dec
PP-FP
k
Online-basic Online-binary Inc-S
102
10 2 2
3
4
5
k
6
10 1
10 2 2
3
101
PP-FP
5
6
(e) Facebook
4
5
k
6
3
4
5
k
101
time (s)
time (s)
3
10 2 2
6
PP-FP Inc-S Dec
PP-FP
100
10 1
10 4 2
Dec PP-FP
(d) DBLP2016
Inc-S Dec
100
10 3
E-0 E-107 E-348 E-414 E-686 E-698 E-1684 E-1912 E-3437 E-3980
4
k
(c) DBLP2015
Inc-S Dec
10 2
10 2
Online-basic Online-binary Inc-S
102 100
(b) DBLP2014
100
Dec PP-FP
100
(a) DBLP2013 102
time (s)
Dec PP-FP
104
time (s)
time (s)
Dec PP-FP
time (s)
Online-basic Online-binary Inc-S
102
104
time (s)
104
time (s)
104
10 1
10 2 2
3
(f) LiveJournal
4
5
k
6
10 2 2
(g) YouTube
3
4
k
5
6
15
20
(h) Orkut
Fig. 7: Community search efficiency results on all datasets.
4
k
(a) DBLP2013
5
4
k
5
6
(b) DBLP2014
0
Index Size (KB)
10 1
3
4
5
k
(c) DBLP2015
9
1.0
2
100
0.9
7
0.9
7
1.0
3
1.0
2
1.0
0
0.9
0.9
6
300
1.0
3
300
101
Online-basic PP-FP
1.0
2
9
9 0.9
0
900 600
1.0
9 0.9
1.0
300
Online-basic PP-FP
600
1.0
600
900
community attribute gain
Online-basic PP-FP
community attribute gain
community attribute gain
900
6
0
5
10
The number of attributes |A 0(q)|
(d) Sensitivity test
Fig. 8: Quality score evaluation on DBLP datasets (a)-(c) and sensitivity test of index size (d). first collect query nodes with private neighbors range from 200 to 250. For each query node, we vary the size of its private attribute set from 20% to 100%, and compare the runtime of our PP-FP with the most efficient baseline Dec in Figure 13(a). Since Dec needs to update its index after acquiring private information, its runs slower than our method PP-FP with sufficient private information. (II) Scalability test w.r.t. private edge size |Eq |. We further examine how query performance is affected by the amount of private information. Specifically, we collect query nodes whose private edge counts range from 0 to 500 and compare the runtime of our PP-FP with Dec. As shown in Figure 13(b), the solid lines represent the average runtimes for both methods, while the circular markers indicate the runtime of each query node. PP-FP shown in green maintains a consistently low and stable runtime across all ranges, exhibiting little sensitivity to
the growth in private edges, whereas Dec shown in blue slows down markedly as |Eq | increases. In summary, our proposed PP-FP approach demonstrates good scalability with respect to the private attribute size |Aq | and the private graph size |Eq |, exhibiting a more stable increasing trend compared to Dec. Exp-5: Sensitivity test. We evaluate the sensitivity of the PP-FP-tree index size to the number of attributes |A′ (q)| using all query nodes in the DBLP2017 dataset. For each query node q ∈ V , we record the size of its PP-FP-tree index and the number of attributes. Figure 8(d) shows an approximately linear growth trend, indicating that the index size grows linearly with the number of attributes. Exp-6: Ablation Study. We conduct two ablation studies on DBLP2017 with 100 query nodes to evaluate the impact
1.00
0.80
0.80
0.60
0.60
0.60
0.60
F1 score
0.40
0.40
Inc-S Dec PP-FP
0.20 0
0
Facebook ego networks
Fig. 9: F1-scores on Facebook. 5
Dec PP-FP
1
0
20%
40%
60%
80%
3
4
k
5
6
100%
101 100
10 1
2
3
4
5
k
(a) Efficiency.
6
2
3
4
5
k
34289
v6 v5
200
300
400
500
800 600
4
k
5
6
Weiming Hu
v7
v4
4 common keywords q
v3 35651
v2
v1
39396
Philip Torr
Ming-Hsuan Yang
detection, image, learning, using
7 common keywords q
v3 35651
v2 39396
Ming-Hsuan Yang
visual, object, detection, tracking, image, learning, using
v1 Philip Torr
Ming-Hsuan Yang, Philip Torr, Weiming Hu et al. "The sixth visual object tracking vot2018 challenge results." ECCV workshops. 2018.
Fig. 15: The 4-core attributed communities with maximum common attributes in the public and public-private graphs.
400 200 0
3
Fig. 12: F1-scores on Orkut.
v4
Public-private graph G′q w/o PP-FP-tree index PP-FP w/o public graph expansion
2
Weiming Hu
(b) On private edge size |Eq |. 1000
0
6
Dec PP-FP
100
Inc-S Dec PP-FP
0.20
Fig. 11: F1 on YouTube.
The number of private edges |Eq|
community attribute gain
time(s)
w/o PP-FP-tree index PP-FP w/o public graph expansion
0
Public graph G
Fig. 13: Scalability test. 102
0.20
153992
The ratio of private attribute size |Aq|
(a) On private attribute size |Aq |.
2
0.40
Inc-S Dec PP-FP
34241
7 6 5 4 3 2 1 0
Time (s)
Time (s)
2
Inc-S Dec PP-FP
Fig. 10: F1 on LiveJournal.
4
3
0.40
0.20
E-0 E-107 E-348 E-414 E-686 E-698 E-1684 E-1912 E-3437 E-3980
F1 score
1.00
0.80
F1 score
1.00
0.80
F1 score
1.00
2
3
4
k
5
6
(b) Quality.
Fig. 14: Ablation study. of different components of our method in efficiency and community quality. Ablation 1: PP-FP-tree index. We remove the PP-FP-tree index and enumerate candidate nodes with attributes from the public-private neighborhood, followed by Phase-II and PhaseIII. This variant evaluates the effect of the PP-FP-tree. Ablation 2: public graph expansion. We remove the candidate subgraph expansion in public graph, using Phase-I directly followed by Phase-III. This variant evaluates the effect of subgraph expansion. Figure 14 presents the ablation results on efficiency and quality. Across all values of k, PP-FP achieves higher community attribute gain than the two ablation variants. PP-FP is consistently more efficient than the variant without PP-FP-tree index, as the tree index enables effective pruning by organizing nodes with shared attributes. When k is 2 to 5, the variant without public graph expansion is more efficient than PP-FP, since it does not expand in the public graph. Interestingly, when k is 6, PP-FP is faster than the variant without public graph expansion, since it is hard to identify a valid 6-core community within the public-private neighborhood, leading to both reduced efficiency and quality. Exp-7: Case study. We conduct a case study on the DBLP2017 dataset, focusing on a prominent researcher in computer vision, Ming-Hsuan Yang. We select him as the query node q, and search for 4-core communities with maximal common attributes. Figure 15 presents our findings. In the
public graph G, the identified 4-core community consists of eight nodes but is not highly cohesive. The query node is directly linked to only four of the remaining seven nodes, and the community shares only four attributes. In contrast, the community identified in the public-private graph is a 4core community forming a clique, representing all community members are tightly interconnected. Moreover, this community shares seven common attributes. Among these, the keywords highlighted in red {visual, object, tracking} are present only in the public-private graph. This clearly demonstrates that the public-private graph captures more comprehensive and up-todate information. Additionally, in the public graph, neither Weiming Hu nor Philip Torr has a direct collaboration with Ming-Hsuan Yang. However, these connections are successfully captured in the public-private graph, reflecting their real-world collaboration at ECCV 2018. Compared to public graphs, public-private graphs facilitate the early discovery of new connections and enable the detection of more semantically meaningful, tightly connected, and timely communities. VIII. C ONCLUSION This paper formulates and studies a novel ACS-PP problem to find cohesive communities containing query nodes over public-private graphs. We develop an index-based framework by designing new private index of public-private frequent pattern trees, which can support the fast search of common attributes. Extensive experiments are conducted on real-world public-private graphs with ground-truth communities to show the superiority of our approaches against state-of-the-art competitors. A case study on public-private collaboration graphs reveals that our model can help early identify the underlying communities working on an ongoing project.
IX. AI-G ENERATED C ONTENT ACKNOWLEDGEMENT The authors confirm that no content in this paper was generated by AI tools. R EFERENCES [1] L. Luo, Y. Fang, X. Cao, X. Zhang, and W. Zhang, “Detecting communities from heterogeneous graphs: A context path-based graph neural network model,” in Proceedings of the ACM International Conference on Information & Knowledge Management. New York, NY, USA: Association for Computing Machinery, 2021, pp. 1170–1180. [2] C. Ma, Y. Fang, R. Cheng, L. V. S. Lakshmanan, and X. Han, “A convex-programming approach for efficient directed densest subgraph discovery,” in Proceedings of the International Conference on Management of Data, 2022, pp. 845–859. [3] Y. Chen, J. Zhang, Y. Fang, X. Cao, and I. King, “Efficient community search over large directed graphs: An augmented index-based approach,” in Proceedings of the International Joint Conference on Artificial Intelligence, 2021, pp. 3544–3550. [4] Z. Dong, X. Huang, G. Yuan, H. Zhu, and H. Xiong, “Butterfly-core community search over labeled graphs,” Proceedings of the Very Large Data Bases Endowment, vol. 14, no. 11, pp. 2006–2018, 2021. [5] Y. Jiang, X. Huang, and H. Cheng, “I/O efficient K-Truss community search in massive graphs,” The International Journal on Very Large Data Bases, vol. 30, no. 5, pp. 713–738, 2021. [6] Y. Fang, X. Huang, L. Qin, Y. Zhang, W. Zhang, R. Cheng, and X. Lin, “A survey of community search over big graphs,” The International Journal on Very Large Data Bases, vol. 29, no. 1, pp. 353–392, 2020. [7] R. Dey, Z. Jelveh, and K. Ross, “Facebook users have become much more private: A large-scale study,” in Proceedings of the IEEE International Conference on Pervasive Computing and Communications Workshops. Pisa, Italy: IEEE Computer Society, 2012, pp. 346–352. [8] F. Chierichetti, A. Epasto, R. Kumar, S. Lattanzi, and V. S. Mirrokni, “Efficient algorithms for public-private social networks,” in Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2015, pp. 139–148. [9] D. Yu, X. Zhang, Q. Luo, L. Zhang, Z. Xie, and Z. Cai, “Public-private-core maintenance in public-private graphs,” Intelligent and Converged Networks, vol. 2, no. 4, pp. 306–319, 2021. [10] N. Bansal, A. Blum, and S. Chawla, “Correlation clustering,” Machine Learning, vol. 56, no. 1-3, pp. 89–113, 2004. [11] J. Jiang, X. Huang, B. Choi, J. Xu, S. S. Bhowmick, and L. Xu, “PPKWS: An efficient framework for keyword search on public-private networks,” in Proceedings of the IEEE International Conference on Data Engineering. IEEE, 2020, pp. 457–468. [12] S. Ebadian and X. Huang, “Fast algorithm for K-Truss discovery on public-private graphs,” arXiv preprint arXiv:1906.00140, 2019, preprint. [13] A. Das Sarma, S. Gollapudi, M. Najork, and R. Panigrahy, “A sketch-based distance oracle for web-scale graphs,” in Proceedings of the ACM International Conference on Web Search and Data Mining. New York, NY, USA: Association for Computing Machinery, 2010, pp. 401–410. [14] M. Sozio and A. Gionis, “The community-search problem and how to plan a successful cocktail party,” in Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York, NY, USA: Association for Computing Machinery, 2010, pp. 939–948. [15] Y. Fang, Y. Yang, W. Zhang, X. Lin, and X. Cao, “Effective and efficient community search over large heterogeneous information networks,” Proceedings of the Very Large Data Bases Endowment, vol. 13, no. 6, pp. 854–867, 2020. [16] Y. Liu, F. Guo, B. Xu, P. Bao, H. Shen, and X. Cheng, “Significant-attributed community search in heterogeneous information networks,” arXiv preprint arXiv:2308.13244, 2023, preprint. [17] Y. Fang, R. Cheng, Y. Chen, S. Luo, and J. Hu, “Effective and efficient attributed community search,” The International Journal on Very Large Data Bases, vol. 26, no. 6, pp. 803–828, 2017. [18] C. Li, F. Zhang, Y. Zhang, L. Qin, W. Zhang, and X. Lin, “Efficient progressive minimum K-Core search,” Proceedings of the Very Large Data Bases Endowment, vol. 13, no. 3, pp. 362–375, 2020. [19] Z. Lu, Y. Zhu, M. Zhong, and J. X. Yu, “On time-optimal (k, p)-core community search in dynamic graphs,” in Proceedings of the IEEE International Conference on Data Engineering. Chengdu, China: IEEE Computer Society, 2022, pp. 1396–1407.
[20] C. Bothorel, J. D. Cruz, M. Magnani, and B. Micenková, “Clustering attributed graphs: Models, measures and methods,” Network Science, vol. 3, no. 3, pp. 408–444, 2015. [21] Y. Li, C. Sha, X. Huang, and Y. Zhang, “Community detection in attributed graphs: An embedding approach,” in Proceedings of the AAAI Conference on Artificial Intelligence. AAAI Press, 2018, pp. 338–345. [22] X. Huang, H. Cheng, L. Qin, W. Tian, and J. X. Yu, “Querying K-Truss community in large and dynamic graphs,” in Proceedings of the ACM SIGMOD International Conference on Management of Data, 2014, pp. 1311–1322. [23] R. Li, J. Su, L. Qin, J. X. Yu, and Q. Dai, “Persistent community search in temporal networks,” in Proceedings of the IEEE International Conference on Data Engineering, 2018, pp. 797–808. [24] W. Cui, Y. Xiao, H. Wang, and W. Wang, “Local search of communities in large graphs,” in Proceedings of the ACM SIGMOD International Conference on Management of Data. New York, NY, USA: Association for Computing Machinery, 2014, pp. 991–1002. [25] L. Yuan, L. Qin, W. Zhang, L. Chang, and J. Yang, “Index-based densest clique percolation community search in networks,” IEEE Transactions on Knowledge and Data Engineering, vol. 30, no. 5, pp. 922–935, 2017. [26] Y. Fang, Z. Wang, R. Cheng, H. Wang, and J. Hu, “Effective and efficient community search over large directed graphs,” IEEE Transactions on Knowledge and Data Engineering, vol. 31, no. 11, pp. 2093–2107, 2019. [27] E. Akbas and P. Zhao, “Truss-based community search: A truss-equivalence based indexing approach,” Proceedings of the Very Large Data Bases Endowment, vol. 10, no. 11, pp. 1298–1309, 2017. [28] X. Huang, L. V. S. Lakshmanan, J. X. Yu, and H. Cheng, “Approximate closest community search in networks,” Proceedings of the Very Large Data Bases Endowment, vol. 9, no. 4, pp. 276–287, 2015. [29] Y. Wang, X. Jian, Z. Yang, and J. Li, “Query optimal K-Plex based community in graphs,” Data Science and Engineering, vol. 2, no. 4, pp. 257–273, 2017. [30] L. Chang, X. Lin, L. Qin, J. X. Yu, and W. Zhang, “Index-based optimal algorithms for computing steiner components with maximum connectivity,” in Proceedings of the ACM SIGMOD International Conference on Management of Data. New York, NY, USA: Association for Computing Machinery, 2015, pp. 459–474. [31] J. Hu, X. Wu, R. Cheng, S. Luo, and Y. Fang, “On minimal steiner maximum-connected subgraph queries,” IEEE Transactions on Knowledge and Data Engineering, vol. 29, no. 11, pp. 2455–2469, 2017. [32] Y. Fang, C. K. Cheng, S. Luo, J. Hu, and X. Li, “Effective community search over large spatial graphs,” Proceedings of the Very Large Data Bases Endowment, vol. 10, no. 6, pp. 709–720, 2017. [33] Q. Zhu, H. Hu, C. Xu, J. Xu, and W. Lee, “Geo-social group queries with minimum acquaintance constraints,” The International Journal on Very Large Data Bases, vol. 26, no. 5, pp. 709–727, 2017. [34] X. Huang and L. V. S. Lakshmanan, “Attribute truss community search,” arXiv preprint arXiv:1609.00090, 2016, preprint. [35] L. Chen, C. Liu, K. Liao, J. Li, and R. Zhou, “Contextual community search over large social networks,” in Proceedings of the IEEE International Conference on Data Engineering. Macau, China: IEEE Computer Society, 2019, pp. 88–99. [36] Y. Zhu, J. He, J. Ye, L. Qin, X. Huang, and J. X. Yu, “When structure meets keywords: Cohesive attributed community search,” in Proceedings of the ACM International Conference on Information & Knowledge Management. New York, NY, USA: Association for Computing Machinery, 2020, pp. 1913–1922. [37] Y. Jiang, Y. Fang, C. Ma, X. Cao, and C. Li, “Effective community search over large star-schema heterogeneous information networks,” Proceedings of the Very Large Data Bases Endowment, vol. 15, no. 11, pp. 2307–2320, 2022. [38] A. Archer, S. Lattanzi, P. Likarish, and S. Vassilvitskii, “Indexing public-private graphs,” in Proceedings of the International World Wide Web Conference. Perth, Australia: Association for Computing Machinery, 2017, pp. 1461–1470. [39] P. Boldi and S. Vigna, “In-core computation of geometric centralities with hyperball: A hundred billion nodes and beyond,” in Proceedings of the IEEE International Conference on Data Mining Workshops. Dallas, TX, USA: IEEE Computer Society, 2013, pp. 621–628. [40] X. Huang, J. Jiang, B. Choi, J. Xu, Z. Zhang, and Y. Song, “PP-DBLP: Modeling and generating attributed public-private networks with dblp,” in Proceedings of the IEEE International Conference on Data Mining Workshops. Singapore: IEEE Computer Society, 2018, pp. 986–989.
[41] Y. Fang, R. Cheng, S. Luo, and J. Hu, “Effective community search for large attributed graphs,” in Proceedings of the Very Large Data Bases Endowment, vol. 9, no. 12. VLDB Endowment, 2016, pp. 1233–1244. [42] A. Epasto, H. Esfandiari, and V. Mirrokni, “On-device algorithms for public-private data with absolute privacy,” in The World Wide Web Conference, 2019, pp. 405–416. [43] J. Han, J. Pei, and Y. Yin, “Mining frequent patterns without candidate generation,” ACM sigmod record, vol. 29, no. 2, pp. 1–12, 2000. [44] J. Leskovec and J. J. McAuley, “Learning to discover social circles in ego networks,” in Advances in Neural Information Processing Systems, vol. 25. Curran Associates, Inc., 2012, pp. 548–556.