--- title: "Fast Algorithm for K-Truss Discovery on Public-Private Graphs" authors: - "Soroush Ebadian" - "Xin Huang" doi: "10.24963/ijcai.2019/313" url: "https://ijcai.org/proceedings/2019/313" pdf: "https://ijcai.org/proceedings/2019/0313.pdf" venue: "Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence" year: 2019 pages: "2258-2264" track: "Main track" keywords: - "Machine Learning Applications: Networks" - "Heuristic Search and Game Playing: Heuristic Search" - "Machine Learning: Data Mining" - "Multidisciplinary Topics and Applications: Social Sciences" --- # Fast Algorithm for K-Truss Discovery on Public-Private Graphs Soroush Ebadian, Xin Huang *Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence*, pages 2258-2264. DOI: [10.24963/ijcai.2019/313](https://doi.org/10.24963/ijcai.2019/313) ## Abstract In public-private graphs, users share one public graph and have their own private graphs. A private graph consists of personal private contacts that only can be visible to its owner, e.g., hidden friend lists on Facebook and secret following on Sina Weibo. However, existing public-private analytic algorithms have not yet investigated the dense subgraph discovery of k-truss, where each edge is contained in at least k-2 triangles. This paper aims at finding k-truss efficiently in public-private graphs. The core of our solution is a novel algorithm to update k-truss with node insertions. We develop a classification-based hybrid strategy of node insertions and edge insertions to incrementally compute k-truss in public-private graphs. Extensive experiments validate the superiority of our proposed algorithms against state-of-the-art methods on real-world datasets. ## Full text ## 1 Introduction Online social networks (e.g., Facebook, Twitter, Instagram, and Sina Weibo) have become vital platforms for connecting users to share information, post daily life events, and spread influence [Kempe et al., 2003; Wilder et al., 2018; Zhang et al., 2017; Zhang et al., 2018b; Li et al., 2018]. Due to privacy concerns, users tend to hide their connections, leading such private relationships not visible to other users in public but only themselves. For instance, Facebook users are likely to conceal their friend-list [Dey et al., 2012]; Weibo users may prefer using the secret following feature, which hides their interested followees. Public-private graphs are developed to model this kind of social networks [Chierichetti et al., 2015]. A public-private network contains a public graph which is visible and accessible to everyone; in addition, each vertex has a personal private graph only visible to its owner. Therefore, in the view of each user, the social network is a union of the public graph and its own private graph which can be significantly different for distinct users. Recently, many graph analytic tasks have been investigated on public-private networks, such as all-pairs shortest path distances, node similarities, and correlation clustering. Figure 1: An example of public-private graph. Black solid edges are public. Blue dashed edges are private to v5, and red dashed edges are private to v3. The gray area is a 5-truss in personalized pp-graph of v5 as gv5 . ![Image](https://ijcai.org/proceedings/2019/fulltext/313/image_000000_18ffa93b6aeba22c317d83292620438c5d70eb19dcc983077dd7add7b98e61d4.png) Dense subgraph discovery is a fundamental network analysis task. Many dense subgraphs have been proposed and investigated, e.g., clique, quasi-clique [Pei et al., 2005], n-clan [Mokken, 1979], n-club [Mokken, 1979], and k-plex [Xiao et al., 2017]. Recently, a popular notion of dense subgraphs that has been studied is k-truss. A k-truss is the largest subgraph of a graph such that each edge is contained in at least k - 2 triangles within this subgraph. Finding k-trusses has many useful applications such as community search [Jiang et al., 2018], complex network visualization [Zhao and Tung, 2012], and task-driven team formation [Huang et al., 2016]. To the best of our knowledge, finding k-truss over publicprivate networks has not yet been studied in the literature. In this paper, we formulate the problem of finding public-private k-truss as follows. Given a query vertex and parameter k, the problem is to find k-truss in the public-private graph owned by this query vertex. Efficient extraction of public-private k-truss raises significant challenges. A straightforward approach is to ignore users' private edges, which can lead to inaccurate results. Another approach is to apply truss decomposition on the publicprivate graph of the query vertex to extract the k-truss with the given parameter k. However, this method computes k-truss from scratch, which is particularly inefficient for large-scale networks. To tackle these challenges, we develop an indexbased computational paradigm to efficiently update a truss index on a public graph using the edges in a private graph, with a minimal amount of recomputation on the public graph. To summarize, we make the following contributions: - We formulate a new problem of finding k-truss over public-private graphs, that is finding k-truss in public- private graph owned by a given query vertex (Section 3). - We analyze the structural properties of k-truss on publicprivate networks. Based on the observations, we develop k-truss updating algorithm using a hybrid strategy of node/edge insertions/deletions (Section 4). - We validate the efficiency of our proposed methods through extensive experiments on real-world datasets of public-private networks (Section 5). ## 2 RelatedWork Several essential problems of graph analysis on public-private graphs have been studied in [Chierichetti et al., 2015; Archer et al., 2017], such as the size of reachability tree [Cohen and Kaplan, 2007], all-pairs shortest paths [Das Sarma et al., 2010], pairwise node similarities [Haveliwala, 2002], correlation clustering [Bansal et al., 2004]. Moreover, the publicprivate model of data summarization has been investigated and solved by a fast distributed algorithm [Mirzasoleiman et al., 2016]. In addition, several studies on k-truss mining have been investigated recently [Cohen, 2008; Zhang et al., 2018a]. Equivalent concepts of k-truss termed as different names include triangle k-core [Zhang and Parthasarathy, 2012], k-dense community [Saito et al., 2008; Gregori et al., 2011], and k-mutual-friend subgraph [Zhao and Tung, 2012]. Truss decomposition is to find the non-empty k-truss for all possible k values in a graph. Algorithms of truss decomposition have also been studied in different types of graphs (e.g., directed graphs [Takaguchi and Yoshida, 2016], uncertain graphs [Zou and Zhu, 2017], and dynamic graphs [Zhang and Parthasarathy, 2012; Huang et al., 2014]). In contrast to the above studies, finding k-truss over public-private networks is studied for the first time in this paper. ## 3 Preliminary We consider a simple and undirected graph G = (V,E) where V and E are the vertex set and edge set respectively. We define N(v) = {u ∈ V : (v, u) ∈ E} as the set of neighbors of a vertex v, and d(v) = |N(v)| as the degree of v in G. For a set of vertices S ⊆ V , the induced subgraph of G by S is denoted by G[S], where the vertex set is S and the edge set is E(G[S]) = {(v, u) ∈ E : v, u ∈ S}. ## 3.1 Public-Private Graphs We first introduce a model of public-private graph G [Chierichetti et al., 2015]. A public-private graph G consists of one public graph and multiple private graphs. Given a public graph G = (V,E), the vertex set V represents users, and the edge set E represents connections between users. For each vertex u in the public graph G, u has an associated private graph Gu = (Vu, Eu), where Vu ⊆ V are the users from public graph and the edge set Eu satisfies Eu ∩ E = ∅. The public graph G is visible to everyone, and the private graph Gu is only visible to user u. Thus, in the view of user u, she/he can see and access the structure of graph that is the union of public graph G and its own private graph Gu, i.e., G∪Gu = (V,E ∪Eu) [Huang et al., 2018]. The personalized public-private graph (a.k.a. pp-graph in short) owned by a vertex u is defined as follows. Definition 1 (Personalized PP-Graph). Given a publicprivate graph G and a vertex u, the personalized pp-graph of u is denoted by gu, where gu = G∪Gu = (V, E∪Eu). Here, Eu are the private edges only visible to u, and E ∩ Eu = ∅. ## 3.2 K-Truss A triangle is a cycle of length 3 in graphs. Given three vertices u, v,w ∈ V , the triangle formed by u, v,w is denoted by △uvw. The support of an edge is defined as follows. Definition 2 (Support). Given a subgraph H ⊆ G, the support of an edge e = (u, v), denoted by supH(e), is defined as the number of triangles containing edge e in H, i.e., supH(e) = |{△uvw : (u, v), (u, w), (v, w) ∈ E(H)}|. We drop the subscript and denote the support as sup(e), when the context is obvious. Based on the support, we give a definition of k-truss [Wang and Cheng, 2012] as follows. Definition 3 (K-Truss). A k-truss H of graph G is defined as the largest subgraph of G such that every edge e has support of at least k - 2 in this subgraph, i.e., supH(e) ≥ k - 2. ## 3.3 Problem Statement The problem of public-private k-truss discovery studied in this paper is formulated as follows. Problem formulation: Given a public-private graph G, a vertex u ∈ V , and an integer k ≥ 2, the problem is to find the k-truss in the personalized pp-graph gu where gu = G ∪ Gu. Example 1. Consider the public-private graph G in Figure 1, a query vertex v5, and k = 5. Black edges are public. Blue edges are private to v5. The answer of 5-truss in personalized pp-graph gv5 is the subgraph depicted in the gray region. ## 4 Proposed Algorithms This section introduces our algorithms for finding k-truss in personalized pp-graph gu, w.r.t. a query vertex u. We first give an overview of our ideas in Section 4.1, and then present a well thorough description of technical details afterward. ## 4.1 Solution Overview We consider two different ideas. Solution 1: online search algorithm. One intuitive approach is to apply truss decomposition on pp-graph gu to iteratively remove edges with less than k - 2 triangles and output the remaining graph as answers. However, such computing ktruss from scratch on gu for each query vertex u is obviously inefficient for big graphs with a large number of vertices. Solution 2: index-based search algorithm. Recall that personalized pp-graph gu = G ∪ Gu has a public graph G and a private graph Gu only available to u. The public graph G is available to everyone, and the structure of G is identical to each query vertex u. The idea of index-based search algorithms is to construct a structural index of public graph G offline, and then online find k-truss based on the precomputed index of G and additional graph Gu. In the following, we introduce a concept of trussness, which is useful for constructing the truss-index for k-truss discovery. Definition 4 (Trussness). Given a subgraph H ⊆ G, the trussness of H is defined as τ (H) = mine∈E(H) {supH(e)+ 2}. The trussness of an edge e ∈ H is defined as the largest number k such that a connected k-truss H′ contains e, i.e., We drop the subscript and denote τG(e) as τ(e) when the context is obvious. According to Def. 4, k-truss of G is the union of all edges e with τ(e) = k. The truss-index of public graph G keeps the trussness of all edges in G. Given a trussindex of G, the remaining issue is how to update the trussindex for pp-graph G∪Gu, w.r.t. the additional Gu. Updating truss-index using edge insertions. A simple approach is to add edges of Gu one-by-one into G and update the truss-index accordingly, by using an existing edgeinsertion algorithm [Huang et al., 2014]. However, when the number of private edges Eu is large, the adaptation of edgeinsertion may be inefficient. For example, consider the example graph G in Figure 1 and query vertex v5 with 4 private edges. It invokes the edge-insertion algorithm for 4 times. Our approach. To address the above issue, we propose a batch-update algorithm using node-insertion. The idea is to simultaneously insert a new node u with all its incident edges into graph G at the same time, and call node-insertion algorithm only once. In the above example, it needs only one node-insertion of the isolated node v5 and all of its private edges. To handle the truss-index update with node insertions efficiently, the key is to identify the affected region in the graph precisely. We provide a theoretical analysis to define the affected scope in Section 4.2, and the detailed algorithm of node-insertion in Section 4.3. However, when u has both public and private edges, we can first remove u with its public edges, and re-insert it with both public and private edges incident to u using node-insertion. This method has significant advantages outperforming edge-insertion when private edges of u are much larger than public edges of u. On other cases, edge-insertion method may perform better. Thus, we construct a classifier to determine which algorithms of nodeinsertion and edge-insertion should be applied in Section 4.4. ## 4.2 Theoretical Analysis In this section, we present useful rules for truss-index updating with node insertion/deletion. Consider a vertex v and the set of edges incident to v as E(v). In the case of node insertion, we insert a new vertex v and its incident edges E(v) into G, where E(v) ∩E(G) = ∅; in the case of node deletion, we delete vertex v and all its incident edges E(v) from G, where E(v) ⊆ E(G). We use τ(e) and ˆ τ(e) to denote trussness of edge e before and after updating operation. Motivated by [Huang et al., 2014], the following three updating rules hold. Rule 1: If new node v is inserted into graph G with ˆ τ(v) = maxe∈E(v) ˆ τ(e) = l, then ∀e ∈ E(G) with τ(e) ≥ l, ˆ τ (e) = τ(e) holds. Rule 2: If node v is deleted from graph G with τ(v) = maxe∈E(v) τ(e) = l, then ∀e ∈ E(G) \ E(v) with τ(e) > l, ˆ τ(e) = τ(e) holds. Rules 1 and 2 hold because node v is not present at any (l + 1)-truss subgraph. Rule 3 holds because for each edge, at most one triangle will be formed/deformed after one node insertion/deletion, hence sup(e) will change at most by one. In the following, we focus on node insertions. In order to apply Rule 1 for pruning, the value of ˆ τ(v) is required. However, an exact computation of ˆ τ(v) is costly expensive. Instead, we develop another rule based on an upper bound of ˆ τ(v) below. Rule 1': If node v is inserted into graph G and ˆ τ (v) ≥ ˆ τ (v), then ∀e ∈ E(G) with τ (e) ≥ ˆ τ(v), ˆ τ(e) = τ(e) holds. To desire an upper bound of ˆ τ (e), we need a new definition of (k, d)-neighborhood as follows. Definition 5 ((k, d)-neighborhood). Given a graph G, (k, d)- neighborhood of vertex v, denoted by Gk,d v , is the maximal subgraph H ⊆ G[N(v)] holding 2. dH(u) ≥ d, ∀u ∈ V (H). Lemma 1. Consider a new node v and its incident edges E(v) = {(v,w) : w ∈ N(v)} are inserted into graph G. For each new edge e = (v,w) in the new graph Gnew, the trussness of e, ˆ τ(e), satisfies klow(e) ≤ ˆ τ (e) ≤ kup(e) where and Moreover, | kup(e) - klow(e)| ≤ 1 holds. Proof. We consider an edge e∗ = (v, w∗ ) in Gnew. For simplification, we denote by klow(e∗ ) = kl and kup(e∗ ) = ku. First, we prove ˆ τ(e∗ ) ≥ klow(e∗ ) = kl. To prove it, we show that there exists a kl-truss H∗ of Gnew containing e∗ . By the definition of klow(e), there exists a kl-truss H of G, i.e., ∀e ∈ E(H), supH(e) ≥ kl - 2. Let H∗ = (V (H) ∪ {v}, E(H) ∪ {(w, v) | w ∈ Gkl,kl-2 v }), which adds vertex v and v's incident edges (w, v) with klow((w, v)) ≥ kl into H. For each edge (w, v) ∈ E(H∗ ) \E(H), w and v have at least kl - 2 common neighbors in H∗ by the second condition of Def. 5, indicating supH∗((w, v)) ≥ kl-2; moreover, for each edge e ∈ E(H∗ ) ∩ E(H) , supH∗(e) ≥ supH(e) ≥ kl - 2. As a result, H∗ is a kl-truss, and ˆ τ (e∗ ) ≥ τH∗ (e∗ ) ≥ kl. Second, we prove ˆ τ (e∗ ) ≤ kup(e∗ ) = ku by contradiction. Assume that ˆ τ(e∗ ) ≥ ku + 1, there exists a (ku + 1)-truss H containing e∗ in Gnew. We delete the node v and all its incident edges (v,w) from H, which leads to a new graph H∗ . By Rule 3, the trussness of each edge e in H∗ decreases by at most 1 after the node deletion of v, i.e., τH∗(e) ≥ ku. Let the vertex set S = V (H) ∩ N(v). Obviously, H∗ [S] = H[S]. For each edge e in H∗ [S], τG(e) ≥ τH∗(e) ≥ ku; for each vertex w in H[S], the edge (v, w) belongs to (ku + 1)- truss H, indicating w has at least ku - 1 neighbors in H and also in H[S], i.e., dH∗ [S](w) = dH[S](w) ≥ ku - 1. By Def. 5, H∗ [S] is a (ku, ku -1)-neighborhood as Gku,ku-1 v in G. Thus, max{k : w ∈ Gk-1,k-2 v } ≥ ku + 1. However, by the definition of kup(e), ku = max{k : w ∈ Gk-1,k-2 v } and ku ≥ ku + 1, which is a contradiction. ## Algorithm 1 Node-Insertion Updating Algorithm Input: G = (V, E), new node v, edge set E(v) τ (e) for each e ∈ E ∪ E(v) Output: ˆ - 1: G←G∪ (v,E(v)) - 2: Compute klow(e), kup(e) for all e ∈ E(v) by Algorithm 2 - 3: for e in E(v) do - 4: τ(e) ← klow(e) - 5: if klow(e) < kup(e) then - 6: Lklow(e) ←Lklow(e) ∪ {e} - 7: for e = (u,w) in GN(v) do - 8: if τ (e) < min{kup((u, v)), kup((w, v))} then - 9: Lτ(e) ←Lτ(e) ∪ {e} - 10: kmax ←max{kup(e) : e ∈ E(v)} then - 11: for k ← kmax -1 to 2 do - 12: UpdateTrussness(k, Lk) Third, we prove |ku - kl| ≤ 1. Obviously, kl ≤ ku and kl ≤ ku + 1. We next prove ku ≤ kl + 1. According to the definition of kup(e), we have ku = max{k : w ∈ Gk-1,k-2 v } ≤ max{k : w ∈ Gk-1,k-3 v }. Moreover, max{k : w ∈ Gk-1,k-3 v } = max{k : w ∈ Gk,k-2 v } + 1 = kl + 1 by the definition of klow(e), and we derive ku ≤ kl + 1. As a result, |ku - kl| ≤ 1. Scope of Affected Edges. Let ˆ τ(v) = max{kup(e) : e ∈ E(v)} be an upper bound of ˆ τ (v), and the weight of a triangle be the minimum trussness of edges within this triangle. 1. Node Insertion. Edge e = (x, y) ∈ E(G) ∪ E(v) with τ(e) < ˆ τ(v), may have trussness increment if (v, x, y) form a triangle of weight τ(e), or e is connected to v through a series number of adjacent triangles each with weight of τ(e). 2. Node Deletion. Edge e = (x, y) ∈ E(G) - E(v) with τ(e) ≤ max{τ(e) : e ∈ E(v)} may have trussness decrement if (v, x, y) form a triangle of weight τ(e) or e is connected to v through a series number of adjacent triangles each with weight of τ(e). ## 4.3 Node-Insertion Updating Algorithm We propose Algorithm 1 to update the truss-index with inserting node v and its incident edges E(v) to G . Lower and upper bounds of each edge can be computed by calling Algorithm 2 (line 2). According to the scope of affected edges, first, trussness of newly added edges is set to klow(e), and then candidate edges for updating are found through lines 310. Newly added edges with klow(e)+1 = kup(e) might have trussness increase which are found in lines 3-6. Furthermore, any edge in G[N(v)] that might get affected is found through lines 7-9. According to Rule 1', kmax is set to maximum of the upper bounds which results in pruning all unaffected edges which have trussness of at least kmax. The procedure of level-by-level updating truss-index (line 12) follows the edge-insertion algorithm [Huang et al., 2014]. ## Algorithm 2 Node-Insertion Bound Computing Algorithm Input: G = (V, E), new node v, edge set E(v), type ∈ {low, up} Output: {ktype(e) : e ∈ E(v)} trussness bound according to type - 1: H ←G[N(v)]; k ← 2 - 2: while H ̸= ∅ do - 3: while ∃e ∈ E(H) with τH(e) < k do - 4: Delete edge e fromH; - 5: while ∃dH(u) < (k -2 if type = low else k -1) do - 6: Delete vertex u and its incident edges fromH; - 7: ktype((v, u)) ← (k - 1 if type = low else k) - 8: k ← k +1 Computing kup(e) and klow(e). Algorithm 2 computes the upper bound kup(e) and lower bound klow(e) in Lemma 1. Computing lower bounds and upper bounds are almost the same, and the same codes can be used with passing a parameter type ∈ {low, up} to indicate which bound to compute. Consider the case where type is low and lower bound is required. It starts with an induced subgraph G[N(v)] as H, which is G2,0 v . In each iteration refines H to reach Gk,k-2 v from Gk-1,k-3 v . Assume the (k - 1)-th step has correctly stored Gk-1,k-3 v in H. It first removes edges with trussness less than k (lines 3-4), and then removes vertices with degree less than k-2 (lines 5-7), until the resulting graph H becomes Gk,k-2 v . Each node removed in this iteration is member of Gk-1,k-3 v but not Gk,k-2 v ; therefore the bound k - 1 finally found by the algorithm is the maximum possible value. ## 4.4 AClassification-based Hybrid Algorithm for Finding K-Truss in Public-Private Graphs We present a classification-based algorithm of updating trussindex from public graph G to pp-graph G ∪ Gu. The algorithm is outlined in Algorithm 3, which uses a hybrid strategy of updating with node/edge insertions/deletions. Specifically, we have two following strategies to update truss-index. - Edge-PP. Add private edges of E(Gu) one by one into G using edge-insertion algorithm [Huang et al., 2014]. - Vertex-PP. Remove vertex u with its public edges by node-deletion algorithm, then add back u with all incident edges to obtain G ∪ Gu using node-insertion algorithm in Algorithm 1. Figure 2: Win case distribution of Vertex-PP and Edge-PP for 1367 random query nodes in PP-DBLP-2013. ![Image](https://ijcai.org/proceedings/2019/fulltext/313/image_000001_2cd4c69a0252cd1366abf26ab775f3886e982c512330866adbe6ed67b74a266e.png) ## Algorithm 3 Hybrid-PP Algorithm ## Pre-process: Input: G = (V, E), truss-index {τ (e) : ∀e ∈ E} Output: Classification model C : D → {CV , CE} - 1: Training vertex set S ← sample nodes(G) - 2: for v in S do - 3: TV (v), TE(v) ←Runtime of Vertex-PP and Edge-PP on v - 4: X = [feature(v) : v ∈ S] - 5: Y = [CV if TV (v) < TE(v) else CE : v ∈ S] - 6: C ←Classifier-Construction(X,Y) ## Query: Input: query node u, private graph Gu, and integer k Output: the k-truss in G∪Gu - 1: if C.predict(feature(u)) = CV then - 2: Update index using Vertex-PP (u) - 3: else Update index using Edge-PP (u) - 4: return Query KTruss(u, k) on updated index Note that Vertex-PP can not directly add u's private edges into G, as Lemma 1 holds only for the insertion of a completely new vertex. Both algorithms update the truss-index correctly; however, the optimal choice between Edge-PP and Vertex-PP is not straightforwardly clear, because multiple aspects affect efficiency. Determining efficiency performance requires a global knowledge of the whole graph structure. Local topological properties is not sufficient to decide which algorithm works faster. For example, Figure 2 shows the distribution of cases in which Vertex-PP or Edge-PP perform at least two times faster than the other algorithm; it consists of 1367 randomly selected nodes w.r.t their public and private degrees sampled from PP-DBLP-2013 dataset [Huang et al., 2018]. It is clear by Figure 2 that the simple distinction of degree is not sufficient to make good decision upon which algorithm to use. Thus, we formulate and tackle the problem of using Edge-PP and Vertex-PP as a classification task. Algorithm 3 predicts which updating method between Vertex-PP and Edge-PP works faster in terms of the given query, and runs that algorithm to answer the query. There are two classes CV and CE that each node u ∈ V is in class CV if Vertex-PP works faster than Edge-PP to update index from public graph G to G∪Gu and the similar for CE. We present each node u using several features including: 1) public degree of u; 2) private degree of u; 3) the number of triangles containing u respectively in public graph G, private graph Gu, and pp-graph gu; and 4) the trussness sum of public edges; ## 5 Experiments Datasets: We used four public-private graphs of PP-DBLP [Huang et al., 2018] in Table 1. 1 Published articles make the public network, and ongoing collaborations form the private networks which are only known by partial authors. We also used eight real-world graphs available from SNAP [Leskovec and Krevl, 2014] shown in Table 2. 1 https://github.com/samjjx/pp-data Table 1: Network Statistics of Real-world Public-Private Graphs | Name | |V | | |E| | |Vprivate| | |Eprivate| | |--------------|------------------|-----------------|------------------------|------------------------| | PP-DBLP-2013 | 1,791,688 | 5,187,025 | 804,121 | 3,166,863 | | PP-DBLP-2014 | 1,791,688 | 5,893,083 | 669,138 | 2,491,847 | | PP-DBLP-2015 | 1,791,688 | 6,605,428 | 502,654 | 1,719,794 | | PP-DBLP-2016 | 1,791,688 | 7,378,090 | 257,129 | 719,204 | Table 2: Comparison of Node-insertion and Edge-insertion methods in terms of efficiency, by inserting Vt randomly selected nodes on real-world graphs. Here K = 103 and M = 106 . | Name | |V | | |E| | |Vt| | Avg. time per node (s) - Node-ins. | Avg. time per node (s) - Edge-ins. | Speedup | |-------------|------------------|-----------------|------------------|--------------------------------------|--------------------------------------|-----------| | EmailEuAll | 265K | 420K | 292 | 0.38 | 4.20 | 10.96 | | Wikivote | 7K | 103K | 534 | 0.73 | 28.53 | 39.10 | | EmailEnron | 36K | 367K | 485 | 0.83 | 24.10 | 29.03 | | Gowalla | 196K | 1.9M | 156 | 2.99 | 102.39 | 34.27 | | WikiTalk | 2.4M | 5M | 191 | 40.54 | 2017.26 | 49.76 | | Flickr | 80K | 11.8M | 697 | 96.30 | 2195.57 | 22.80 | | Digg | 771K | 7.3M | 471 | 142.82 | 5741.43 | 40.20 | | LiveJournal | 4M | 34.7M | 377 | 142.63 | 5515.66 | 38.67 | Compared Methods and Evaluated Metrics: To evaluate the efficiency of improved strategies proposed in this paper, we tested and compared four algorithms as follows. - Truss-Decompostion: an online search approach using truss decomposition for computing k-truss index from scratch [Wang and Cheng, 2012]. - Edge-PP: an approach using the edge-insertion algorithm for updating truss index [Huang et al., 2014]. - Vertex-PP: our approach using the node-deletion and node-insertion for updating truss-index in Algorithm 1. - Hybrid-PP: our hybrid approach using both Edge-PP and Vertex-PP for updating truss-index in Algorithm 3. After updating the index, all of the four methods mentioned above use the same query method. We compare them by reporting the running time in seconds. The less the running time is, the better the efficiency performance is. We set the parameter k = 7 by default. We also evaluate the methods by varying parameters k in {5, 7, 9, 11, 13, 15}. ## 5.1 Efficiency Evaluation on SNAP Networks To evaluate the efficiency of the node-insertion algorithm, we conducted experiments on eight SNAP graph datasets in Table 2. Due to no available private information in these networks, we randomly generated private edges as follows. We divided nodes into 40 bins by their degree and took 50 randomly selected nodes from each bin. Bin set was defined as {B1,B2, . . .B40} where Bi = {v : i-1 40 < d(v) ∆ ≤ i 40 } with ∆ = maxv∈V {d(v)}. Let G = (V,E) denote the initial graph, and Vt the set of sampled vertices. All edges with at least one end in Vt was considered to be private. We ran Truss-Decompostion on the induced subgraph of vertex set V ′ = V \ Vt, then added each node v ∈ Vt using Algorithm 1, and compared the running time with adding edges one by one using edge-insertion algorithm. In Table 2, our node-insertion algorithm significantly outperformed the edge-insertion method, which achieved 38.67 times speedup on LiveJournal. Figure 3: Average query time of different methods on PP-DBLP varied by query node degree. ![Image](https://ijcai.org/proceedings/2019/fulltext/313/image_000002_74770aa604554fe02d81d84a4249afd4120db245f256467738f5eae7fd5f15c0.png) Figure 4: Average query time of different methods on PP-DBLP varied by parameter k. ![Image](https://ijcai.org/proceedings/2019/fulltext/313/image_000003_49b0cf2d24aedd0ace408259a93253789b637f8d60183a5b97d55ee0ad2058be.png) ## 5.2 Classification Evaluation In order to choose the proper classification method to incorporate into Hybrid-PP, we tested and compared five classifiers in terms of classification accuracy and training time, as shown in Table 3. Due to the low training time, high classification accuracy, and fast query time, Random Forest was finally used as the classifier of Hybrid-PP. Table 3: Accuracy of different classifiers on PP-DBLP 2013-2016. | Classifier | Accuracy on PP-DBLP - 2013 | Accuracy on PP-DBLP - 2014 | Accuracy on PP-DBLP - 2015 | Accuracy on PP-DBLP - 2016 | Training - time (s) | |-----------------|------------------------------|------------------------------|------------------------------|------------------------------|-----------------------| | Random Forest | 84.4% | 87.0% | 86.5% | 87.8% | <1 | | Decision Tree | 84.3% | 84.6% | 84.7% | 87.4% | <1 | | SVM | 84.1% | 84.5% | 85.5% | 85.2% | 1140 | | k-NN | 76.0% | 79.6% | 78.2% | 72.7% | <1 | | Degree Baseline | 69.5% | 69.2% | 71.8% | 67.2% | <1 | ## 5.3 Efficiency Evaluation on PP-DBLP Networks We compare the efficiency of four different methods TrussDecompostion, Edge-PP, Vertex-PP, and Hybrid-PP on real-world public-private datasets of PP-DBLP. Hybrid-PP adopted a Random Forest with 51 estimators and a maximum depth of 11 to construct a classifier. The Hybrid-PP used to answer queries on each PP-DBLP dataset was trained based on runtimes of Vertex-PP and Edge-PP on sampled nodes from the other three datasets. We first divided all nodes into 100 × 100 bins by their public and private degrees, and then randomly took four nodes from each bin. Bin set was {Bi,j : 1 ≤ i, j ≤ 100} each bin defined as Bi,j = {v : i-1 100 < d(v) ∆ ≤ i 100 , j-1 100 < dp(v) ∆p ≤ j 100 } where ∆ is the maximum public degree, ∆p is the maximum private degree, and dp(v) is the private degree of node v. In total 1836 ± 58 nodes were selected on each PP-DBLP datasets. Vary Node Degree. We compared four proposed algorithms on sampled nodes. For better visualization and comparison, sampled nodes were divided into five equally sized groups by node degrees in their pp-graphs, each group taking 20% of sampled nodes, and the average query time of algorithms on each group is reported in Figure 3. On higher degree nodes, Edge-PP takes much longer than Vertex-PP, and becomes less useful for Hybrid-PP; hence the gap between Hybrid-PP and Vertex-PP decreases as Vertex-PP becomes the optimal choice for the classifier on higher degree nodes. Vary Parameter k. The average query time varied by k is reported in Figure 4. Hybrid-PP and Vertex-PP perform much better than Edge-PP and Truss-Decompostion for all k values and datasets. Hybrid-PP is the fastest due to using Edge-PP in cases where Vertex-PP works worse than Edge-PP. ## 6 Conclusions This paper studies the problem of finding k-truss on publicprivate graphs. We develop a novel hybrid algorithm of ktruss updating with node/edge insertions/deletions. This work opens up several interesting problems. First, developing further efficient and clever algorithms for finding k-truss in ppgraphs is important, instead of deleting and re-inserting nodes as Vertex-PP. Second, finding other kinds of dense subgraphs on public-private graph is also wide open. ## Acknowledgments This work is supported by the NSFC 61702435 and RGC 12200917. Xin Huang is the corresponding author. ## References 1. [Archer et al., 2017] Aaron Archer, Silvio Lattanzi, Peter Likarish, and Sergei Vassilvitskii. Indexing public-private graphs. In WWW, pages 1461-1470, 2017. 2. [Bansal et al., 2004] Nikhil Bansal, Avrim Blum, and Shuchi Chawla. Correlation clustering. Machine learning, 56(1- 3):89-113, 2004. 3. [Chierichetti et al., 2015] Flavio Chierichetti, Alessandro Epasto, Ravi Kumar, Silvio Lattanzi, and Vahab Mirrokni. Efficient algorithms for public-private social networks. In KDD, pages 139-148, 2015. 4. [Cohen and Kaplan, 2007] Edith Cohen and Haim Kaplan. Summarizing data using bottom-k sketches. In PODS, pages 225-234, 2007. 5. [Cohen, 2008] J. Cohen. Trusses: Cohesive subgraphs for social network analysis. Technical report, National Secu- rity Agency, 2008. 6. [Das Sarma et al., 2010] Atish Das Sarma, Sreenivas Golla- pudi, Marc Najork, and Rina Panigrahy. A sketch-based distance oracle for web-scale graphs. In WSDM, pages 401-410, 2010. 7. [Dey et al., 2012] Ratan Dey, Zubin Jelveh, and Keith Ross. Facebook users have become much more private: A large- scale study. In IEEE International Conference on PER- COM Workshops, pages 346-352, 2012. 8. [Gregori et al., 2011] Enrico Gregori, Luciano Lenzini, and Chiara Orsini. k-dense communities in the internet as-level topology. In International Conference on Communication Systems and Networks, pages 1-10, 2011. 9. [Haveliwala, 2002] Taher H Haveliwala. Topic-sensitive pagerank. In WWW, pages 517-526, 2002. 10. [Huang et al., 2014] Xin Huang, Hong Cheng, Lu Qin, Wen- tao Tian, and Jeffrey Xu Yu. Querying k-truss community in large and dynamic graphs. In SIGMOD, pages 1311- 1322, 2014. 11. [Huang et al., 2016] Xin Huang, Wei Lu, and Laks VS Lak- shmanan. Truss decomposition of probabilistic graphs: Semantics and algorithms. In SIGMOD, pages 77-90, 2016. 12. [Huang et al., 2018] Xin Huang, Jiaxin Jiang, Byron Choi, Jianliang Xu, Zhiwei Zhang, and Yunya Song. PP- DBLP: modeling and generating attributed public-private networks with dblp. In IEEE International Conference on Data Mining Workshops, pages 986-989, 2018. 13. [Jiang et al., 2018] Yuli Jiang, Xin Huang, Hong Cheng, and Jeffrey Xu Yu. Vizcs: Online searching and visualizing communities in dynamic graphs. In ICDE, pages 1585- 1588, 2018. 14. [Kempe et al., 2003] David Kempe, Jon Kleinberg, and Éva Tardos. Maximizing the spread of influence through a so- cial network. In KDD, pages 137-146, 2003. 15. [Leskovec and Krevl, 2014] Jure Leskovec and Andrej Krevl. SNAP Datasets: Stanford large network dataset collection. http://snap.stanford.edu/data, June 2014. 16. [Li et al., 2018] Ye Li, Chaofeng Sha, Xin Huang, and Yanchun Zhang. Community detection in attributed graphs: an embedding approach. In AAAI, 2018. 17. [Mirzasoleiman et al., 2016] Baharan Mirzasoleiman, Morteza Zadimoghaddam, and Amin Karbasi. Fast distributed submodular cover: Public-private data summarization. In NIPS, pages 3594-3602, 2016. 18. [Mokken, 1979] Robert J Mokken. Cliques, clubs and clans. Quality & Quantity, 13(2):161-173, 1979. 19. [Pei et al., 2005] Jian Pei, Daxin Jiang, and Aidong Zhang. Mining cross-graph quasi-cliques in gene expression and protein interaction data. In ICDE, pages 353-354, 2005. 20. [Saito et al., 2008] Kazumi Saito, Takeshi Yamada, and Kazuhiro Kazama. Extracting communities from complex networks by the k-dense method. IEICE Transactions on Fundamentals of Electronics, Communications and Com- puter Sciences, 91(11):3304-3311, 2008. 21. [Takaguchi and Yoshida, 2016] Taro Takaguchi and Yuichi Yoshida. Cycle and flow trusses in directed networks. Royal Society open science, 3(11):160270, 2016. 22. [Wang and Cheng, 2012] Jia Wang and James Cheng. Truss decomposition in massive networks. PVLDB, 5(9):812- 823, 2012. 23. [Wilder et al., 2018] Bryan Wilder, Nicole Immorlica, Eric Rice, and Milind Tambe. Maximizing influence in an un- known social network. In AAAI, pages 4743-4750, 2018. 24. [Xiao et al., 2017] Mingyu Xiao, Weibo Lin, Yuanshun Dai, and Yifeng Zeng. A fast algorithm to compute maximum k-plexes in social network analysis. In AAAI, 2017. 25. [Zhang and Parthasarathy, 2012] Yang Zhang and Srinivasan Parthasarathy. Extracting analyzing and visualizing trian- gle k-core motifs within networks. In ICDE, pages 1049- 1060, 2012. 26. [Zhang et al., 2017] Fan Zhang, Ying Zhang, Lu Qin, Wenjie Zhang, and Xuemin Lin. Finding critical users for social network engagement: The collapsed k-core problem. In AAAI, 2017. 27. [Zhang et al., 2018a] Fan Zhang, Conggai Li, Ying Zhang, Lu Qin, and Wenjie Zhang. Finding critical users in so- cial communities: The collapsed core and truss problems. TKDE, 2018. 28. [Zhang et al., 2018b] Ge Zhang, Di Jin, Jian Gao, Pengfei Jiao, Franc ¸oise Fogelman-Soulié, and Xin Huang. Finding communities with hierarchical semantics by distinguish- ing general and specialized topics. In IJCAI, pages 3648- 3654, 2018. 29. [Zhao and Tung, 2012] Feng Zhao and Anthony KH Tung. Large scale cohesive subgraphs discovery for social net- work visual analysis. In PVLDB, volume 6, pages 85-96, 2012. 30. [Zou and Zhu, 2017] Zhaonian Zou and Rong Zhu. Truss de- composition of uncertain graphs. Knowledge and Informa- tion Systems, 50(1):197-230, 2017.