Identifying similar-bicliques in bipartite graphs

It is easy to observe that maximal similar-bicliques must be contained in maximal bicliques, since every similar-biclique is also a biclique. Thus, a naive approach is first enumerating all maximal bicliques by invoking one of the existing maximal biclique enumeration algorithms, and then post-processing the detected maximal bicliques to obtain maximal similar-bicliques. Specifically, for each maximal biclique, we extract maximal similar-bicliques by imposing the similarity constraint on L-side vertices, and then eliminate all similar-bicliques that are either duplicates or non-maximal. We omit the details, since our empirical study in Sect. 7 shows that enumerating all maximal bicliques by the state-of-the-art algorithm \(\textsf{ooMBEA}\) [8] is already time consuming for large graphs.

According to the definition of similar-biclique, if we build a similarity graph \(G_s\) for \(V_L\) where two vertices of \(V_L\) are connected by an edge if their similarity is at least \(\varepsilon \), then for every (maximal) similar-biclique C, its L-side vertices \(C_L\) form a clique in \(G_s\). Moreover, once the L-side vertices \(C_L\) of a maximal similar-biclique are determined, the R-side vertices \(C_R\) can be easily obtained as the set of common neighbors of \(C_L\), i.e., \(C_R = \bigcap _{u\in C_L} N(u)\). In view of this, we propose to adopt the general backtracking framework of the Bron–Kerbosch algorithm [5] to enumerate all maximal similar-bicliques. However, there are two issues. (1) The similarity graph \(G_s\) is not available in the input. (2) The set of L-side vertices \(C_L\) of a maximal similar-biclique C is not necessarily a maximal clique in \(G_s\), though \(C_L\) is a clique in \(G_s\). This is because, a too large \(C_L\) may result in a too small \(C_R\), violating the size constraint \(\tau \) on \(C_R\).

We propose techniques to address the above issues, and the pseudocode of our algorithm is shown in Algorithm 1, denoted \(\textsf{MSBE}\). We first prune unpromising vertices by invoking \(\textsf{VReduce}\) (Lines 1–2), which will be introduced shortly in Algorithm 2; a vertex u is pruned if . For each remaining vertex \(u\in V_L\) with , we enumerate all maximal similar-bicliques containing u (Lines 3–10). To do so, we iteratively grow a partial solution \(\langle C_L, C_R\rangle \) where \(C_L\) is initialized as \(\{u\}\) (Line 4). Besides \(C_L\) and \(C_R\), we also maintain \(P_L\) and \(Q_L\) in a similar fashion to the Bron–Kerbosch algorithm [5], such that each vertex of \(P_L\cup Q_L\) is similar to all vertices of \(C_L\). Specifically, \(P_L\) is a set of candidate vertices that are used to grow \(C_L\), and \(Q_L\) is a set of previously considered candidate vertices that are used for checking the maximality of \(\langle C_L, C_R\rangle \). \(P_L\) and \(Q_L\) are initialized at Lines 5–9, after which we invoke the procedure \(\textsf{Enum}\) for enumeration (Line 10); to avoid duplicates, the similar neighbors of u with larger vertex id than u are put in \(P_L\), and those with smaller vertex id are put in \(Q_L\).

In \(\textsf{Enum}\), if the current similar-biclique \(\langle C_L,C_R\rangle \) is maximal, we report it (Lines 11–12); note that \(\langle C_L,C_R\rangle \) is maximal if and only if there is no vertex \(u\in P_L\cup Q_L\) such that \(N(u)\supseteq C_R\). Next, \(\textsf{Enum}\) iteratively adds a vertex of \(P_L\) to \(C_L\), updates the corresponding \(C_R\), \(P_L\) and \(Q_L\), and recursively invokes itself to enumerate more similar-bicliques (Lines 14–17). After processing \(u\in P_L\), we remove u from \(P_L\) and add it to \(Q_L\) (Line 18).

Vertex Reduction. As a similar-biclique needs to have at least \(\tau \) vertices on each side, each vertex u in a similar-biclique C must have at least \(\tau \) structural neighbors in C (i.e., \(|N_C(u)| \ge \tau \)). Furthermore, as all L-side vertices in a similar-biclique C are similar to each other, each L-side vertex u must have at least \(\tau -1\) similar neighbors in C (i.e., \(|\varGamma _C(u)| \ge \tau -1\)). As a result, we can exclude all vertices that violate either of these two conditions from being considered in the enumeration procedure \(\textsf{Enum}\), i.e., mark them as deleted; we call this process as vertex reduction.

We propose an algorithm \(\textsf{VReduce}\) to conduct vertex reduction, whose pseudocode is shown in Algorithm 2. Firstly, we obtain the structural degree d(u) for each vertex \(u \in V_L\cup V_R\) (Line 1), and obtain the similar degree \(\delta (u)\) for each L-side vertex \(u \in V_L\) (Line 2). Then, as long as there is a non-deleted vertex u with \(d(u)<\tau \) or a non-deleted L-side vertex u with \(\delta (u)<\tau -1\), we mark u as deleted (Line 8), decrease the structure degree of u’s structural neighbors by 1 (Line 4), and also decrease the similar degree of u’s similar neighbors by 1 if u is an L-side vertex (Lines 5–7).

Compute Similar Neighbors \(\varGamma (u)\). One fundamental operation in both Algorithm 1 and Algorithm 2 is computing \(\varGamma (u)\) for an L-side vertex u; note that \(\varGamma (u)\) is not stored with the graph G. A straightforward method to collect \(\varGamma (u)\) is computing \({\textsf{sim}} (u,v)\) for each vertex \(v\in V_L\). The time complexity would be O(|E|), as it needs to visit every edge of G. This is inefficient, by noting that Algorithm 1 and Algorithm 2 need to compute \(\varGamma (u)\) for many vertices u and multiple times.

We propose a more efficient algorithm in Algorithm 3, denoted \(\textsf{SimNei}\). Instead of blindly computing \({\textsf{sim}} (u,v)\) for each \(v \in V_L\), we only compute \({\textsf{sim}} (u,v)\) for those v with \({\textsf{sim}} (u,v) > 0\). Our main idea is to first compute the number of common neighbors c(v) between u and v for each 2-hop structural neighbor v of u (Lines 3–4). Then, \({\textsf{sim}} (u,v)\) can be calculated as \(\frac{c(v)}{d(u) + d(v) - c(v)}\) (Line 6).¹ Note that, in our implementation, to make the time complexity of \(\textsf{SimNei}\) to be independent of \(|V_L|\) which may be large, we only initialize \(c(\cdot )\) once at the beginning of the entire algorithm execution (e.g., in \(\textsf{MSBE}\)), and after using \(c(\cdot )\) at Line 4–6 of Algorithm 3 we reset those updated \(c(\cdot )\) to be 0. In addition, we also collect at Line 4 the set of vertices with non-zero \(c(\cdot )\) into a set S, such that Line 5 as well as the resetting of \(c(\cdot )\) can be conducted in O(|S|) time. As a result, the time complexity of \(\textsf{SimNei}\) is \(O(\sum _{v \in N(u)} d(v))\), which is lower than O(|E|).

Optimizations for \(\textsf{Enum}\). We further propose two optimization techniques to speed up the \(\textsf{Enum}\) procedure. Recall that, an instance of \(\textsf{Enum}\) is represented by \((C_L, C_R, P_L, Q_L)\) where \(C_R = \bigcap _{u\in C_L} N(u)\) and \(|C_R| \ge \tau \),² and aims to enumerate all maximal similar-bicliques \(C^*\) satisfying \(C_L \subset C_L^* \subseteq C_L\cup P_L\). Firstly, an enumeration instance can be terminated once we know that it will not generate any maximal similar-biclique. That is, by including any subset of vertices of \(P_L\) into \(C_L\), the resulting similar-biclique would not be maximal. This is formulated in the lemma below.

Secondly, we can reduce the number of instances generated at Line 17 of Algorithm 1, based on the concept of dominating set.

Note that, a vertex does not dominate itself.

To apply Lemma 2, we revise Line 13 of Algorithm 1 as follows: we first choose a vertex \(u^*\) from \(P_L\cup Q_L\) before the “for loop,” and then replace “\(u\in P_L\)” with “\(u\in P_L \backslash {\textsf{DomSet}} (u^*)\)” in the “for loop” statement. This means that we do not generate enumeration instances, at Line 17 of Algorithm 1, for vertices \(u \in {\textsf{DomSet}} (u^*)\). To maximize the benefit of Lemma 2, \(u^*\) is chosen as the one that minimizes \(|P_L \backslash {\textsf{DomSet}} (u^*)|\) among all vertices of \(P_L \cup Q_L\). If \(u^*\) dominates a substantial number of vertices in \(P_L\) (i.e., when the cardinality of \({\textsf{DomSet}} (u^*)\) is large), applying Lemma 2 can significantly reduce the overall running time.

Discussions. \(\textsf{MSBE}\) is different from both maximal clique enumeration algorithms for unipartite graphs and maximal biclique enumeration algorithms for bipartite graphs, as follows. Firstly, \(\textsf{MSBE}\) needs to compute the similar neighbors for L-side vertices, which are not required by any of the existing algorithms. Secondly, compared with maximal clique enumeration algorithms, \(\textsf{MSBE}\) needs to consider common structural neighbors \(C_R\) of \(C_L\), in addition to common similar neighbors. Thirdly, our optimization techniques for \(\textsf{Enum}\) are also different from the existing ones.

In \(\textsf{MSBE}\), we need to obtain the similar neighbors \(\varGamma (\cdot )\) of an L-side vertex multiple times, e.g., at Lines 6 and 15 of Algorithm 1 and Lines 2 and 6 of Algorithm 2. We can either invoke \(\textsf{SimNei}\) to compute \(\varGamma (u)\) every time when it is needed or store \(\varGamma (u)\) in main memory after it is computed for the first time and then directly retrieve it for all subsequent requests. We use \(\textsf{MSBE}\) to denote the algorithm that uses the first strategy, and \(\mathsf {mat\text {-}MSBE}\) the algorithm that uses the second strategy. (Here, \(\textsf{mat}\) stands for materialization.)

Let \(\varPhi _u\) be the set of 2-hop structural neighbors of u, i.e., \(\varPhi _u = \bigcup _{v \in N(u)} N(v)\). Firstly, we have the following lemma.

Based on Lemma 3, one possible indexing strategy is pre-computing and storing \({\textsf{sim}} (u,v)\) for each \(u \in V_L\cup V_R\) and each \(v \in \varPhi _u\).³ However, the space complexity of this strategy would be \(O(|V_L|^2 + |V_R|^2)\), which is prohibitively high even for moderate-sized graphs since the space requirement is essentially the same as the case of \(\mathsf {mat\text {-}MSBE}\) when \(\varepsilon \) is very small. For example, even for a moderate-sized graph with \(10^6\) vertices, the storage space would be over 2TB.

Instead of storing \(\varPhi _u\) and the structural similarities in their raw format, we summarize them into a few segments.

Given a segment \({\textsf{seg}} = \langle {\mathsf {v_{\min }}}, {\mathsf {v_{\max }}}, {\mathsf {s_{\max }}}, c\rangle \) of \(\varPhi _u\), we use \(V({\textsf{seg}})\) to denote \(\{v \in \varPhi _u \mid {\mathsf {v_{\min }}} \le v \le {\mathsf {v_{\max }}} \}\). It is immediate from the definition that \(c = |V({\textsf{seg}})|\) andThus, we say that \({\textsf{seg}} \) covers vertices \(V({\textsf{seg}})\). A set of segments \(\mathbb {S}_u = \{{\textsf{seg}} _1,\ldots ,{\textsf{seg}} _k\}\) covers \(\varPhi _u\) ifIn this work, we only consider disjoint segments, i.e., \(V({\textsf{seg}} _i) \cap V({\textsf{seg}} _j) = \emptyset \) for \(i \ne j\). Our index structure, denoted \(\mathcal {I}\), covers \(\varPhi _u\) by a set of segments, for all \(u \in V_L\cup V_R\). That is, \(\mathcal {I}\) consists of \(\mathbb {S}_u\) such that \(\mathbb {S}_u\) covers \(\varPhi _u\), for all \(u \in V_L\cup V_R\).

In this subsection, we present index-based algorithms for similar neighbor computation and for vertex reduction.

Index-based Similar Neighbor Computation. The pseudocode of using the index \(\mathcal {I}\) to efficiently obtain the similar neighbors \(\varGamma (u)\) for a vertex u is shown in Algorithm 4, denoted \(\textsf{indexedSN}\). We go through each segment \({\textsf{seg}} \in \mathbb {S}_u\) with \({\textsf{seg}}.{\mathsf {s_{\max }}} \ge \varepsilon \) (Line 2), and compute \({\textsf{sim}} (u,v)\) for each \(v \in [{\textsf{seg}}.{\mathsf {v_{\min }}}, {\textsf{seg}}.{\mathsf {v_{\max }}} ]\) (Line 3); recall that (1) \({\textsf{seg}}.{\mathsf {s_{\max }}} \) upper bounds \({\textsf{sim}} (u,v)\) for each \(v \in V({\textsf{seg}})\), and (2) \(V({\textsf{seg}})\) is not stored in the index structure \(\mathcal {I}\). As computing \({\textsf{sim}} (u,v)\) needs to intersect two sets N(u) and N(v) which is costly, we propose to first apply a filtering for the pair u and v based on an upper bound \({\textsf{ub}} (u,v)\) of \({\textsf{sim}} (u,v)\) (Line 5); if \({\textsf{ub}} (u,v) < \varepsilon \), then we have \({\textsf{sim}} (u,v) \le {\textsf{ub}} (u,v) < \varepsilon \) and thus \(v \notin \varGamma (u)\). For the similarity in Definition 1, it is easy to verify that \({\textsf{sim}} (u,v) \le \frac{\min \{d(u),d(v)\}}{\max \{d(u),d(v)\}}\); we set this as \({\textsf{ub}} (u,v)\), which can be calculated in constant time.⁴\(\textsf{indexedSN}\) is expected to run faster than \(\textsf{SimNei}\) (Algorithm 3) as the former can skip an entire segment if its \({\mathsf {s_{\max }}} \) is smaller than \(\varepsilon \).

Index-based Two-Phase Vertex Reduction. Based on \(\textsf{indexedSN}\), we can speed up \(\textsf{VReduce}\) (Algorithm 2) by invoking \(\textsf{indexedSN}\) to compute \(\varGamma (u)\). However, this is still inefficient, as \(\textsf{VReduce}\) needs to compute \(\varGamma (u)\) for all \(u \in V_L\) (see Line 2 of Algorithm 2). We propose to utilize the index \(\mathcal {I}\) to first obtain an upper bound of the similar degree for vertex reduction, as proved in the lemma below.

Consider the part of the index in Fig. 4 and suppose \(\varepsilon = 0.4\). By scanning \(\mathbb {S}_u\), we obtain an upper bound of u’s similar degree as 6, i.e., \({\textsf{seg}} _1.c+{\textsf{seg}} _3.c=6\); \({\textsf{seg}} _2\) is omitted since its \({\mathsf {s_{\max }}} \) is only 0.2.

Furthermore, we also observe that the structural degree can be obtained efficiently. Thus, we propose a two-phase approach for vertex reduction, which first conducts vertex reduction by using structural degree and upper bound of similar degree in Phase-I, and then using structural degree and similar degree in Phase-II. The pseudocode of our two-phase vertex reduction is shown in Algorithm 5, denoted \(\textsf{indexedVR}\). In Phase-I, we first obtain the structural degree d(u) for each \(u \in V_L\cup V_R\) (Line 1), and an upper bound \(\bar{\delta }(u)\) of the similar degree for each vertex \(u\in V_L\) (Line 2). Then, as long as there is a non-deleted vertex \(u\in V_L\cup V_R\) satisfying \(d(u)<\tau \) or a non-deleted vertex \(u\in V_L\) satisfying \(\bar{\delta }(u)<\tau -1\) (Line 3), we mark u as deleted and update the structural degree of its structural neighbors (Lines 4–5); note that, we do not update \(\bar{\delta }(\cdot )\) in Phase-I. In Phase-II, we first compute a progressive similar degree, denoted \(\delta _p(\cdot )\), for each non-deleted L-side vertex, by invoking \(\textsf{progressiveSN}\) (Lines 7–8). Here, \(\delta _p(u)\) is a lower bound of u’s similar degree \(\delta (u)\), and it records the number of similar neighbors that have been computed for u; our computation of \(\delta _p(u)\) ensures that \(\delta _p(u) \ge \tau -1\) if and only if \(\delta (u) \ge \tau -1\). Then, as long as there is a non-deleted vertex \(u\in V_L\cup V_R\) satisfying \(d(u)<\tau \) or a non-deleted vertex \(u\in V_L\) satisfying \(\delta _p(u) < \tau -1\), we mark u as deleted (Line 18) and update the structural degree of its structural neighbors (Line 10). Furthermore, if u is an L-side vertex, we also obtain the set \(\varGamma (u)\) of similar neighbors of u (Line 12) and update the progressive similar degree \(\delta _p(v)\) to satisfy the invariant that \(\delta _p(v) \ge \tau -1\) if and only if \(\delta (v)\ge \tau -1\) for each \(v \in \varGamma (u)\) (Lines 13–17). Note that, in our implementation, we use a queue to maintain the vertices that satisfy the condition at Line 3 or Line 9; as a result, we do not need to loop through all non-deleted vertices to find the unpromising vertices.

In Algorithm 5, for an L-side vertex u, we compute \(\delta _p(u)\) instead of \(\delta (u)\). Our main motivation is that for an L-side vertex u satisfying \(d(u) \ge \tau \), we only need to compute \(\tau -1\) of its similar neighbors to certify that it is a promising vertex. That is, we stop the computation of \(\varGamma (u)\) once \(\delta _p(u) \ge \tau -1\); however, if some similar neighbors of u are later removed (i.e., marked as deleted), then we need to update \(\delta _p(u)\) by computing more similar neighbors of u (Lines 15–17 of Algorithm 5). As a result, for vertices with high similar degrees in the remaining graph (i.e., obtained by removing all unpromising vertices), we only need to compute a small portion of their similar neighbors to prevent them from being removed and thus save unnecessary similar neighbor computations. The pseudocode of computing \(\delta _p(u)\) is shown in Lines 19–26 of Algorithm 5, denoted \(\textsf{progressiveSN}\). It is invoked only when \(\delta _p(u) < \tau -1\) and there are still unchecked segments of \(\varPhi _u\). In \(\textsf{progressiveSN}\), we check the segments of \(\mathbb {S}_u\) one by one (Line 20–24) and stop once we have found enough similar neighbors for u (Line 25). We record the index of the first unchecked segment in \({\textsf{idx}} (u)\) (Line 8). Note that in Algorithm 5, a copy of \({\textsf{del}} (\cdot )\) is stored in \({\textsf{del2}} (\cdot )\) at Line 6. The usage of \({\textsf{del2}} (\cdot )\) is specific to the \(\textsf{progressiveSN}\) procedure. This distinction of \({\textsf{del}} (\cdot )\) and \({\textsf{del2}} (\cdot )\) is necessary because for each L-side vertex v, we compute its similar neighbors and thus similar degree \(\delta _p(v)\) progressively (Lines 8 and 16). When we remove an unqualified vertex u at Lines 10–18, we also decrement \(\delta _p(v)\) by one for each similar neighbor v of u (Line 14). Consequently, it is possible that u has not yet been considered in \(\delta _p(v)\) when u is removed, but \(\delta _p(v)\) is decremented by one due to the removal of u. As a remedy, \(\textsf{progressiveSN}\) considers all vertices that are alive when entering the while loop of Line 9, i.e., all vertices with \({\textsf{del2}} (\cdot )\) being \({\textsf{false}} \).

\(\textsf{indexedVR}\) is better than \(\textsf{VReduce}\) (Algorithm 2), since (1) Phase-I of \(\textsf{indexedVR}\) is lightweight but very effective at pruning vertices as demonstrated by our empirical studies, and (2) \(\textsf{indexedVR}\) uses \(\textsf{indexedSN}\) and \(\textsf{progressiveSN}\) to compute the similar neighbors.

Overall Algorithm. Our index-based \(\textsf{MSBE}\) improves on Algorithm 1 by replacing the invocation to \(\textsf{VReduce}\) at Line 2 with invoking \(\textsf{indexedVR}\) for vertex reduction, and invoking \(\textsf{indexedSN}\) to compute \(\varGamma (u)\) at Lines 6 and 15. Nevertheless, the time complexity of index-based \(\textsf{MSBE}\) remains \( {{\mathcal {O}}}(|V_L|\cdot |E|\cdot 2^{|V_L|})\) as proved in Theorem 2, by noting that the time complexity of \(\textsf{indexedSN}\) remains \( {{\mathcal {O}}}(|E|)\). Despite of having the same time complexity, our empirical studies in Sect. 7 show that the index-based approach can improve the efficiency of \(\textsf{MSBE}\) by several orders of magnitude.

In this subsection, we present two algorithms to construct the index based on the ideas of largest gap and steady segment, respectively. Note that, the indexes are constructed offline, and once constructed, they can be used to process maximal similar-biclique enumeration queries with different \(\varepsilon \) and \(\tau \) values.

Largest Gap (LG) Index. Recall that, our index structure summarizes a subset of vertices of \(\varPhi _u\) and their similarities to a vertex u by four numbers \({\textsf{seg}} = \langle {\mathsf {v_{\min }}}, {\mathsf {v_{\max }}}, {\mathsf {s_{\max }}}, c\rangle \), where \({\mathsf {s_{\max }}} \) is an upper bound of the similarity between u and each \(v \in \varPhi _u\) such that \({\mathsf {v_{\min }}} \le v \le {\mathsf {v_{\max }}} \). To obtain the similar neighbors of u that are in the range \([{\mathsf {v_{\min }}},{\mathsf {v_{\max }}} ]\), we need to go through each vertex \(v \in [{\mathsf {v_{\min }}},{\mathsf {v_{\max }}} ]\) and test its similarity with u (e.g., see Line 3 of Algorithm 4) even if \(v \notin V({\textsf{seg}})\). We call a vertex v that is in the range \([{\mathsf {v_{\min }}},{\mathsf {v_{\max }}} ]\) but not in \(V({\textsf{seg}})\) a fake vertex.

Intuitively, we should minimize the number of fake vertices when constructing the index. We call the index built by this strategy the largest gap (LG) index. It is constructed as follows. Suppose we are going to cover \(\varPhi _u\) by k segments. This is equivalent to find \(k-1\) cut points in the sequence of vertices of \(\varPhi _u\) that are ordered in increasing vertex id order; denote the sequence of vertices as \(\{v_1,v_2,\ldots ,v_{|\varPhi _u|}\}\). Note that, the vertex ids are not consecutive, i.e., it is possible that \(v_2 - v_1 > 1\). We represent the \(k-1\) cut points by \(k-1\) index values \(\{\ell _1,\cdots ,\ell _{k-1}\}\) such that \(1< \ell _1< \ell _2< \cdots< \ell _{k-1} < |\varPhi _u|\), i.e., the i-th cut point is between vertex \(v_{\ell _i-1}\) and vertex \(v_{\ell _i}\). Define \(\ell _0 = 1\) and \(\ell _k = |\varPhi _u|+1\). Then, segment \({\textsf{seg}} _i\) covers vertices \(\{v_{\ell _{i-1}},\ldots ,v_{\ell _i-1}\}\), for \(1 \le i \le k\). Let \(f_1\) be the number of fake vertices if we cover \(\varPhi _u\) by only one segment, i.e., \(f_1 = v_{|\varPhi _u|}-v_1 + 1 - |\varPhi _u|\) where \(v_{|\varPhi _u|}-v_1 + 1\) is the total number of vertices in the range \([v_1,v_{|\varPhi _u|}]\). It is easy to verify that the number of fake vertices of covering \(\varPhi _u\) by k segments with the \(k-1\) cut points \(\{\ell _1,\ldots ,\ell _{k-1}\}\) is \(f_1 - \sum _{i=1}^{k-1} (v_{\ell _i} - v_{\ell _i-1} + 1)\). As \(f_1\) is a fixed number for \(\varPhi _u\), minimizing the number of fake vertices is equivalent to maximizing \(\sum _{i=1}^{k-1} (v_{\ell _i} - v_{\ell _i-1} + 1)\).

Thus, the LG index constructs k segments to cover \(\varPhi _u\), where the \(k-1\) cut points are the \(k-1\) vertices with the largest gaps.

Choosing the number of segments to cover \(\varPhi _u\). It is easy to see that the more the number of segments, the fewer the number of fake vertices introduced by the segments. In the extreme case of covering \(\varPhi _u\) by \(|\varPhi _u|\) segments, there will be no fake vertices introduced. However, the space complexity would be too high to be practical as discussed in Sect. 5.1. Thus, we set the number of segments for covering \(\varPhi _u\) as \(\alpha \cdot \log |\varPhi _u|\) where \(\alpha \) is a user defined parameter, in viewing that a fixed number for different \(\varPhi _u\) will not work as \(|\varPhi _u|\) varies a lot across different vertices u.

Steady Segment (SS) Index. The LG index ignores the similarities (between u and different vertices) in a segment and thus may result in a very wide range of similarity values for a segment. This is not good for \(\textsf{indexedSN}\) and \(\textsf{progressiveSN}\), as they need to check all vertices covered by a segment \({\textsf{seg}} \) even if there is only one vertex in \({\textsf{seg}} \) whose similarity to u is no lower than \(\varepsilon \). Motivated by this, we aim to construct steady segments such that all similarities in a segment are close to each other.

The first term, \(\max _{v \in V({\textsf{seg}})} {\textsf{sim}} (u,v)\), is exactly \({\textsf{seg}}.{\mathsf {s_{\max }}} \). For ease of presentation, we denote the second term, \(\min _{v\in V({\textsf{seg}})} {\textsf{sim}} (u,v)\), by \({\textsf{seg}}.{\mathsf {s_{\min }}} \), the smallest similarity value. A segment \({\textsf{seg}} \) is steady if \({\textsf{seg}}.{\mathsf {s_{\max }}}- {\textsf{seg}}.{\mathsf {s_{\min }}} \le \gamma \). The main advantage of a steady segment is that if \({\textsf{seg}} \) is steady and satisfies \({\textsf{seg}}.{\mathsf {s_{\max }}} \ge \varepsilon \), then it is likely that many vertices of \(V({\textsf{seg}})\) have similarity values to u no lower than \(\varepsilon \), and thus, most of the computation will not be wasted.

Ideally, we would like to find the minimum number of steady segments to cover \(\varPhi _u\). However, the number of steady segments required could be very large. For example, if the steady threshold \(\gamma \) is very close to 0 and all vertices of \(\varPhi _u\) have different similarity values to u, then the number of required steady segments to cover \(\varPhi _u\) is \(|\varPhi _u|\). Thus, we instead construct a fixed number of steady segments to cover as many vertices of \(\varPhi _u\) as possible and then cover the remaining uncovered vertices of \(\varPhi _u\) by as few segments as possible by ignoring the difference between the similarity values.

Given \(\gamma \) and k, our problem is to find k steady segments to cover as many vertices of \(\varPhi _u\) as possible. We first construct, for each vertex \(v \in \varPhi _u\), a maximal steady segment \({\textsf{seg}} _v\) that starts at v (i.e., \({\textsf{seg}} _v.{\mathsf {v_{\min }}} = v\)), and then select k segments \(\mathbb {S}^*\) from \(\{{\textsf{seg}} _v \mid v\in \varPhi _u\}\) such that \(\left|\bigcup _{v \in \mathbb {S}^*} V({\textsf{seg}} _v)\right|\) is maximized. This is an instance of the maximum k-coverage problem which is NP-hard [40]. We select the k segments in a greedy manner. That is, the k segments are selected one-by-one. Let S be the starting vertices of the currently selected segments. Then, the next segment to be added to S is \(\textstyle \arg \max _{v \in \varPhi _u} \left|\bigcup _{v' \in S\cup \{v\}} V({\textsf{seg}} _{v'}) \right|. \) As this function is submodular, the greedy approach achieves an approximation ratio of \(1-\frac{1}{e}\) [17].

The pseudocode is shown in Algorithm 6, denoted \(\textsf{consSS}\). For each vertex u, we first compute its 2-hop structural neighbors \(\varPhi _u\) and their similarities to u (Line 2) and then invoke \(\textsf{MaximalSteadySegments}\) to compute maximal steady segments that start at each vertex \(v_i \in \varPhi _u\) (Line 3). In \(\textsf{MaximalSteadySegments}\), the maximal steady segment \({\textsf{seg}} _{v_i}\) that starts at \(v_i\) is computed by iteratively trying to add the next vertex to the segment (Lines 19–27). Next, we iteratively add to \(\mathbb {S}_u\) the segment of \(\mathbb {C}\) that covers the largest number of uncovered vertices of \(\varPhi _u\) (Lines 4–12); as a result, after adding a segment into \(\mathbb {S}_u\), we also need to update the remaining segments of \(\mathbb {C}\) to be disjoint from the segments of \(\mathbb {S}_u\) (Lines 8–12). During this process, for time efficiency consideration, we do not maintain \({\textsf{seg}}.{\mathsf {s_{\max }}} \); instead, we compute \({\textsf{seg}}.{\mathsf {s_{\max }}} \) for each segment \({\textsf{seg}} \in \mathbb {S}_u\) later (Line 13). Finally, we create the minimum number of segments to cover all vertices of \(\varPhi _u\) that are not covered by \(\mathbb {S}_u\) (Lines 14–15).

Time complexity of \(\textsf{consSS}\). For each vertex \(u \in V_L\cup V_R\), Line 2 of Algorithm 6 takes \(O(\sum _{v \in N(u)} d(v))\) time, and Line 3 takes \(O(|\varPhi _u|^2)\) time. The while loop at Line 5 runs for at most \(\alpha \cdot \log |\varPhi _u|\) iterations, and each iteration takes \(O(|\varPhi _u|)\) time. Lines 13–15 take \(O(|\varPhi _u|)\) time. Thus, the total time complexity of \(\textsf{consSS}\) isComputing all maximal steady segments in linear time. From the above time complexity analysis of \(\textsf{consSS}\), we can see that the time complexity of computing the initial maximal steady segments for all vertices dominates the total time complexity of \(\textsf{consSS}\). In view of this, we propose an efficient algorithm to compute the maximal steady segments for all vertices in linear time, i.e., \(O(|\varPhi _u|)\). The general idea is based on the following lemma.

Following Lemma 5, we use two pointers, i and j, to compute the maximal steady segments for all vertices of \(\varPhi _u\). Here, i is the index of the start vertex and j is 1 plus the index of \({\textsf{seg}} _{v_i}.{\mathsf {v_{\max }}} \) in \(\varPhi _u\). We will increase i from 1 to \(|\varPhi _u|\); according to Lemma 5, j will not decrease. For initialization, both i and j are set as 1. To compute \({\textsf{seg}} _{v_i}\), we iteratively increase j by 1 until either \(j = |\varPhi _u|+1\) or the segment covering vertices \(\{v_i,\ldots ,v_j\}\) is not steady; when this process finishes, we set \({\textsf{seg}} _{v_i}.{\mathsf {v_{\max }}} = v_{j-1}\). After computing \({\textsf{seg}} _{v_i}\), we continue to compute the maximal steady segment for the next vertex by increasing i by 1. Note that we do not reset j after increasing i; this is correct according to Lemma 5. For example, for \(\varPhi _u\) in Fig. 7, when \(i=1\), we have \(j=3\) and thus \({\textsf{seg}} _{v_1}.{\mathsf {v_{\max }}} = v_{j-1} = v_2\); when \(i=2\), we have \(j=5\) and thus \({\textsf{seg}} _{v_2}.{\mathsf {v_{\max }}} = v_4\). Since both i and j are non-decreasing, the time complexity would be \(c\cdot |\varPhi _u|\) where c is the time complexity of checking whether the segment covering a given set of consecutive vertices is steady or not.

To check whether the segment covering a given set S of consecutive vertices of \(\varPhi _u\) is steady or not, all we need to obtain are \(\min _{v \in S} {\textsf{sim}} (u,v)\) and \(\max _{v \in S} {\textsf{sim}} (u,v)\). Since S consists of consecutive vertices of \(\varPhi _u\), we could use some advanced data structures (e.g., segment tree or the one presented in our conference version [52]) to obtain \(\min _{v \in S} {\textsf{sim}} (u,v)\) and \(\max _{v \in S} {\textsf{sim}} (u,v)\) in \(\log |\varPhi _u|\) time. In this work, we propose to use a simple data structure (specifically, a queue) to achieve this in amortized constant time. We focus our discussion on how to obtain \(\min _{v \in S} {\textsf{sim}} (u,v)\); note that \(\max _{v \in S} {\textsf{sim}} (u,v)\) can be obtained in a similar way. Our data structure stores vertices of S that are not min-dominated by other vertices of S.

It is easy to see that \(\min _{v'\in S} {\textsf{sim}} (u,v')\) is equal to \({\textsf{sim}} (u,v)\) for v being the smallest vertex of S that is not min-dominated by other vertices of S. We store in a queue \(\mathcal {Q}_{\min }\) the list of vertices of S that are not min-dominated by other vertices of S; note that storing all the vertices (instead of just the smallest such vertex) that are not min-dominated will make our maintaining of \(\mathcal {Q}_{\min }\) easy. As vertices in \(\mathcal {Q}_{\min }\) are stored in increasing id order, their similarities to u are also strictly increasing. Suppose \(S = \{v_i,\ldots ,v_j\}\) and \(\mathcal {Q}_{\min }\) currently stores the non-min-dominated vertices of S. To maintain \(\mathcal {Q}_{\min }\) for \(S' = \{v_{i+1},\ldots ,v_{j'}\}\) where \(j' \ge j\), we only need toWe note that all these operations can be conducted in amortized constant time, which will be discussed shortly.

The pseudocode of our linear-time algorithm for computing all maximal steady segments is shown in Algorithm 7. Same as \(\textsf{MaximalSteadySegments}\) in Algorithm 6, we first sort vertices of \(\varPhi _u\) into increasing vertex id order (Line 2); let \(\{v_1,v_2,\ldots ,v_{|\varPhi _u|}\}\) be the vertices in sorted order. We initialize the two pointers i and j to both be 1 (Line 3) and initialize two queues \(\mathcal {Q}_{\min }\) and \(\mathcal {Q}_{\max }\) (used for obtaining the minimum and the maximum similarity in a segment, respectively) by \(v_1\) (Line 4). Then, we iteratively compute the maximal steady segment for \(v_i, 1 \le i \le |\varPhi _u|\) (Lines 5–19). To compute the maximal steady segment for \(v_i\), we first pop the front element from \(\mathcal {Q}_{\min }\) and \(\mathcal {Q}_{\min }\) if it is smaller than \(v_i\) (Lines 6–7), and then keep increasing j if the segment covering vertices \(\{v_i,\ldots ,v_j\}\) is still steady (Lines 8–16). The testing of whether the segment covering vertices \(\{v_i,\ldots ,v_j\}\) is still steady or not is achieved by comparing \({\textsf{sim}} (u, \mathcal {Q}_{\max }.front()) - {\textsf{sim}} (u,\mathcal {Q}_{\min }.front())\) with \(\gamma \) (Line 8); as discussed above, \(\mathcal {Q}_{\min }.front()\) stores the vertex that has the lowest similarity to u among vertices of \(\{v_i,\ldots ,v_j\}\) while \(\mathcal {Q}_{\max }.front()\) stores the one with the highest similarity. Note that we consistently have \(j\ge i\) throughout the entire computation since the segment covering one vertex is trivially steady. After increasing j (Line 9) and j still being no larger than \(|\varPhi _u|\), we update \(\mathcal {Q}_{\min }\) and \(\mathcal {Q}_{\max }\) to store all the non-min-dominated and non-max-dominated vertices of \(\{v_i,\ldots ,v_j\}\), respectively (Lines 11–16). Specifically, to update \(\mathcal {Q}_{\min }\), we first remove from it all vertices that are min-dominated by \(v_j\) (Lines 11-12), and then push \(v_j\) to the back of \(\mathcal {Q}_{\min }\) (Line 13); \(\mathcal {Q}_{\max }\) is updated similarly. Once we reach a j such that either \(j > |\varPhi _u|\) (Line 10) or the segment covering vertices \(\{v_i,\ldots ,v_j\}\) is no longer steady, we set the maximal steady segment \({\textsf{seg}} _{v_i}\) of \(v_i\) to be \(\langle v_i,v_{j-1},{\textsf{null}},j-i\rangle \) (Line 17) and add it to \(\mathbb {C}\) (Line 18).

Lines 5–19 of Algorithm 7 run in \(O(|\varPhi _u|)\) time, since (1) j will increase for \(|\varPhi _u|\) times and (2) each vertex of \(\varPhi _u\) will be inserted into and popped from \(\mathcal {Q}_{\min }\) (resp. \(\mathcal {Q}_{\max }\)) at most once. Note that, in our implementation, we also store the similarities into \(\mathcal {Q}_{\min }\) and \(\mathcal {Q}_{\max }\) such that the similarity between u and any vertex at the front or back of \(\mathcal {Q}_{\min }\) and \(\mathcal {Q}_{\max }\) can be retrieved in constant time. Thus, the total time complexity of Algorithm 7 is dominated by Line 2 which takes \(O(|\varPhi _u| \log |\varPhi _u|)\) time. By invoking Algorithm 7 at Line 3 of Algorithm 6, the time complexity of Algorithm 6 becomes \(O\Big (\sum _{u \in V_L \cup V_R} \big (\alpha |\varPhi _u| \log |\varPhi _u| + \sum _{v \in N(u)} d(v)\big ) \Big )\).

Our index construction algorithms can be easily parallelized, since processing \(\varPhi _u\) is totally independent from processing \(\varPhi _{u'}\) for \(u \ne u'\). Thus, we propose to further speed up the index construction with shared-memory parallelization (i.e., handling different vertices concurrently with multiple threads). Specifically, we use OpenMP to parallelize the “for loop” at Line 1 of Algorithm 6 in our parallel implementation.

Let (u, v) be the edge that is removed from G. Let \(\varPhi _u\) and \(\varPhi _v\) be the sets of 2-hop neighbors of u and v, respectively, in the graph G before removing the edge (u, v). After removing edge (u, v), among \(\{N(w) \mid w \in V_L\cup V_R\}\), only N(u) and N(v) change. Thus, only similarities in \(\{{\textsf{sim}} (u,w) \mid w \in \varPhi _u\}\cup \{{\textsf{sim}} (v,w') \mid w' \in \varPhi _v\}\) will change their value. For presentation simplicity, we assume that \(\varPhi _w\) does not change for any \(w \in V_L\cup V_R\); that is, even if the similarity \({\textsf{sim}} (w,w')\) decreases from a positive value to 0, we still consider \(w'\) to be in \(\varPhi _w\). Thus, we have the following lemma.

In the following, we only discuss the index maintenance for \(\mathbb {S}_u\) and \(\mathbb {S}_w\) where \(w \in \varPhi _u\); note that \(\mathbb {S}_v\) and \(\mathbb {S}_{w'}\) for \(w' \in \varPhi _v\) can be maintained similarly. For any vertex \(w\in \varPhi _u\), we also have \(u \in \varPhi _w\) and thus there must exist a segment \({\textsf{seg}} \in \mathbb {S}_w\) that covers u before the update, i.e., \({\textsf{seg}}.{\mathsf {v_{\min }}} \le u\le {\textsf{seg}}.{\mathsf {v_{\max }}} \). Consequently, we only need to update \({\textsf{seg}}.{\mathsf {s_{\max }}} \) as \(\max \{{\textsf{sim}} (u,w),{\textsf{seg}}.{\mathsf {s_{\max }}} \}\), where \({\textsf{sim}} (u,w)\) is the updated similarity between u and w. Note that if \({\textsf{sim}} (u,w) < {\textsf{seg}}.{\mathsf {s_{\max }}} \), it is also possible to decrease \({\textsf{seg}}.{\mathsf {s_{\max }}} \); but for updating efficiency consideration, we do not decrease \({\textsf{seg}}.{\mathsf {s_{\max }}} \). For the same reason, we also do not update (i.e., decrease) \({\textsf{seg}}.c\). For vertex u, \(\mathbb {S}_u\) can be updated in a similar way; that is, for each vertex \(w\in \varPhi _u\), we find the segment \({\textsf{seg}} ' \in \mathbb {S}_u\) that covers w and update \({\textsf{seg}} '.{\mathsf {s_{\max }}} \) as \(\max \{{\textsf{sim}} (u,w),{\textsf{seg}} '.{\mathsf {s_{\max }}} \}\). Note that, we only need to update one segment for \(\mathbb {S}_w\), but we may need to update multiple segments for \(\mathbb {S}_u\).

Optimization. In the above process, if \({\textsf{sim}} (u,w)\) becomes smaller after the update, then we actually do not update the segment that covers u or w. Thus, we can skip all such \(w \in \varPhi _u\) that \({\textsf{sim}} (u,w)\) is smaller after removing the edge (u, v). Fortunately, this set of vertices can be easily characterized by the following lemma.

Following Lemma 7, when we process a 2-hop neighbor \(w\in \varPhi _u\) of u, we first check if \((w,v)\in E\). If \((w,v)\in E\), we know that the similarity between u and w must be decreasing and thus do nothing. The pseudocode of our algorithm for handling edge deletion is shown in Algorithm 8. We first invoke \({\textsf{UpdateDeletion}} \) to update \(\{\mathbb {S}_w \mid w \in \varPhi _u \cup \{u\}\}\) (Line 1), then invoke \({\textsf{UpdateDeletion}} \) again (but with different arguments) to update \(\{\mathbb {S}_w \mid w \in \varPhi _v \cup \{v\}\}\), and finally remove the edge (u, v) from the graph. The pseudocode of the procedure \(\textsf{UpdateDeletion}\) is shown in Lines 4–11 of Algorithm 8. We first invoke a variant of \({\textsf{SimNei}} \) to compute u’s old 2-hop neighbors (i.e., before removing (u, v)) and to compute the new (i.e., updated) similarity between u and each \(w \in \varPhi _u\) (Line 4); this can be done in a similar way to Algorithm 3, and we omit the details. Then, for each vertex \(w\in \varPhi _u\), if \((w,v)\in E\), we know from Lemma 7 that \({\textsf{sim}} (w,u)\) must be decreasing and we skip w (Lines 6–7); otherwise, we update the index \(\mathbb {S}_w\) and index \(\mathbb {S}_u\) (Lines 8–11). Specifically, we search for the segment in \(\mathbb {S}_w\) that covers u and update its \({\mathsf {s_{\max }}} \) (Lines 8–9). Then, we search for the segment in \(\mathbb {S}_u\) that covers w and update its \({\mathsf {s_{\max }}} \) (Lines 10–11).

Let (u, v) be the edge that is inserted into G. Let \(\varPhi _u\) and \(\varPhi _v\) be the sets of 2-hop neighbors of u and v, respectively, in the graph G after adding the edge (u, v). After adding edge (u, v), among \(\{N(w) \mid w \in V_L\cup V_R\}\), only N(u) and N(v) change. Thus, only similarities in \(\{{\textsf{sim}} (u,w) \mid w \in \varPhi _u\}\cup \{{\textsf{sim}} (v,w') \mid w' \in \varPhi _v\}\) will change their value. Thus, we have the following lemma.

In the following, we only discuss the index maintenance for \(\mathbb {S}_u\) and \(\mathbb {S}_w\) where \(w \in \varPhi _u\); \(\mathbb {S}_v\) and \(\mathbb {S}_{w'}\) for \(w'\in \varPhi _v\) can be maintained similarly. To update \(\mathbb {S}_w\) for \(w \in \varPhi _u\), we first try to find the segment in \(\mathbb {S}_w\) that covers u (i.e., \({\textsf{seg}} \in \mathbb {S}_w\) s.t. \({\textsf{seg}}.{\mathsf {v_{\min }}} \le u\le {\textsf{seg}}.{\mathsf {v_{\max }}} \)). If there is such a segment \({\textsf{seg}} \), then we update \({\textsf{seg}}.{\mathsf {s_{\max }}} \) as \(\max \{{\textsf{sim}} (u,w),{\textsf{seg}}.{\mathsf {s_{\max }}} \}\) and increase \({\textsf{seg}}.c\) by 1 if the only common neighbor of u and w is v. Otherwise, there is no segment of \(\mathbb {S}_w\) covering u (this means that u is a new 2-hop neighbor of w), then we create a new segment for u and add it into \(\mathbb {S}_w\). The updating of \(\mathbb {S}_u\) is conducted in a similar way.

Optimization. Similar to the optimization in Sect. 6.1, we can skip all such \(w \in \varPhi _u\) that \({\textsf{sim}} (u,w)\) becomes smaller after adding the edge (u, v). This set of vertices is characterized by the following lemma.

Following Lemma 9, we only need to update the index for \(w \in \varPhi _u\) such that \((w,v) \in E\). Thus, we can design an algorithm \(\mathsf {EdgeInsert^*}\) in a similar way to \(\mathsf {EdgeDelete^*}\) (Algorithm 8); that is, similar to Lines 6–7 of Algorithm 8, we skip the processing of w if \((w,v) \notin E\). We omit the pseudocode of \(\mathsf {EdgeInsert^*}\). This can significantly improve the updating time. Nevertheless, we can do even better, by noting that \(\{w \in \varPhi _u \mid (w,v) \in E\}\) is the same as N(v). Thus, instead of first generating \(\varPhi _u\) and then skipping non-neighbors of v from \(\varPhi _u\), we only process neighbors of v. The pseudocode of our further optimized algorithm is shown in Algorithm 9, denoted \(\mathsf {EdgeInsert\text {-}Opt}\). We first insert the edge (u, v) into the graph, then invoke \({\textsf{UpdateInsertion}} \) to update \(\{\mathbb {S}_w \mid w \in \varPhi _u\cup \{u\}\}\), and finally invoke \({\textsf{UpdateInsertion}} \) again (but with different arguments) to update \(\{\mathbb {S}_w \mid w \in \varPhi _v\cup \{v\}\}\). The pseudocode of the procedure \({\textsf{UpdateInsertion}} \) is shown in Lines 4–17 of Algorithm 9. In \(\textsf{UpdateInsertion}\), for each vertex \(w\in N(v)\) (Line 4), we first compute \({\textsf{sim}} (u,w)\) (Line 5) by computing the number of common neighbors of u and w, denoted \({\textsf{ComNei}} (u,w)\), and then update the index \(\mathbb {S}_w\) (Lines 6–11) and the index \(\mathbb {S}_u\) (Lines 12–17). Specifically, to update \(\mathbb {S}_w\) by u and \({\textsf{sim}} (u,w)\), we search for the segment \({\textsf{seg}} _i\) in \(\mathbb {S}_w\) that covers u and update \({\textsf{seg}} _i.{\mathsf {s_{\max }}} \) if necessary (Lines 6–8). If the number of common neighbors between u and w is 1, we know that u is w’s new 2-hop neighbor and we thus increase \({\textsf{seg}} _i.c\) by 1 (Line 8); note that, even if \(\mathbb {S}_w\) has a segment covering u, it is still possible that u is w’s new 2-hop neighbor because segments contain fake vertices. If \(\mathbb {S}_w\) has no segment covering u (this means that u is w’s new 2-hop neighbor), we create a new segment for u and add it to \(\mathbb {S}_w\) (Lines 9–11). Update \(\mathbb {S}_u\) by w and \({\textsf{sim}} (u,w)\) is conducted similarly.

\(\mathsf {EdgeInsert^*}\) vs \(\mathsf {EdgeInsert\text {-}Opt}\). Both \(\mathsf {EdgeInsert^*}\) and \(\mathsf {EdgeInsert\text {-}Opt}\) have their advantages and disadvantages. \(\mathsf {EdgeInsert^*}\) needs to construct the full set \(\varPhi _u\) of u’s 2-hop neighbors and compute the similarity between u and each vertex \(w \in \varPhi _u\). The set \(\varPhi _u\) could be large compared with N(v) that is processed by \(\mathsf {EdgeInsert\text {-}Opt}\). Nevertheless, the similarity between u and each \(w \in N(v)\) is potentially computed more efficiently in \(\mathsf {EdgeInsert^*}\), since it invokes \({\textsf{SimNei}} \) to compute all the similarities at the same time which enables computation sharing among the similarity computation of different vertices. In contrast, \(\mathsf {EdgeInsert\text {-}Opt}\) needs to conduct set intersection to compute \(N(u)\cap N(w)\) which is used in calculating \({\textsf{sim}} (u,w)\). Our empirical study shows that \(\mathsf {EdgeInsert\text {-}Opt}\) performs better in practice.

To achieve high updating efficiency, our index maintenance strategy discussed above only maintains a relaxed version of our index. For example, \({\textsf{seg}}.{\mathsf {s_{\max }}} \) is only guaranteed to be an upper bound (i.e., can be larger than) \(\max _{v \in V({\textsf{seg}})} {\textsf{sim}} (u,v)\); this is because we didn’t update \({\textsf{seg}}.{\mathsf {s_{\max }}} \) when the similarity between u and a vertex covered by \({\textsf{seg}} \) becomes smaller. Also, after inserting an edge (u, v), when we cannot find a segment in \(\mathbb {S}_u\) that covers u’s new 2-hop neighbor w, we create a new segment for w and insert this segment into \(\mathbb {S}_u\). As a result, the effectiveness of using our index to speed up query processing may deteriorate when a large number of updates has occurred. In view of this, we propose to reconstruct the index from scratch when the number of updates exceeds a threshold. To achieve this, we record the number of updates that have occurred, including vertex insertion/deletion and edge insertion/deletion. We reconstruct the entire index structure from scratch once this number is larger than \(\zeta \times |E|\), where \(\zeta \) is the parameter to control the frequency of index rebuilding and |E| is the number of edges in the bipartite graph for which the index was last time reconstructed. Note that, when we reconstruct the index from scratch, we also reassign the vertex id to make sure that vertices of \(V_L\) take (integer) ids from \(\{1,2,\ldots ,|V_L|\}\), and vertices of \(V_R\) take ids from \(\{1+|V_L|,2+|V_L|,\ldots ,|V_R|+|V_L|\}\).

In this subsection, we evaluate the query efficiency of our algorithms. Note that, we also implemented a version of \(\textsf{MSBE}\) without the optimizations of \(\textsf{Enum}\) proposed in Sect. 4.2; it is omitted from the experiments since it times out in almost all the testings.

Running time on all graphs. The running time of the five algorithms on all graphs with default \(\varepsilon \) and \(\tau \) is illustrated in Fig. 8. We can see that \(\mathsf {mat\text {-}MSBE}\) slightly improves upon \(\textsf{MSBE}\) when it is feasible to store the similar neighbors of all vertices in main memory. However, \(\mathsf {mat\text {-}MSBE}\) remains notably slow, primarily attributed to the substantial computational cost involved in computing similar neighbors for L-side vertices and constructing the similarity graph \(G_s\). Additionally, \(\mathsf {mat\text {-}MSBE}\) encounters out-of-memory issues on BS, CU, and DI, as marked by “oom” in Fig. 8; for example, the memory consumption on BS would be over 400GB. Note that the memory consumption of \(\mathsf {mat\text {-}MSBE}\) mainly depends on the structure, rather than the size, of the input graph, and thus \(\mathsf {mat\text {-}MSBE}\) does not run out-of-memory on other larger graphs. Our two index-based algorithms, \(\mathsf {LG\text {-}MSBE}\) and \(\mathsf {SS\text {-}MSBE}\), are the fastest and they outperform the other two index-free algorithms by up to 5 orders of magnitude. \(\mathsf {SS\text {-}MSBE}\) is generally faster than \(\mathsf {LG\text {-}MSBE}\). Compared with the state-of-the-art maximal biclique enumeration algorithm \(\textsf{ooMBEA}\), \(\mathsf {SS\text {-}MSBE}\) is up to 6 orders of magnitude faster. Thus, we exclude \(\textsf{ooMBEA}\) from our remaining evaluations.

Running time by varying \(\varepsilon \) and \(\tau \). The running time of our four algorithms on IM and FL by varying \(\varepsilon \) and \(\tau \) are shown in Fig. 9. We can see that the running time of \(\mathsf {LG\text {-}MSBE}\) and \(\mathsf {SS\text {-}MSBE}\) decreases when either \(\varepsilon \) or \(\tau \) increases. This is because, more vertices will be pruned by \(\textsf{indexedVR}\) when either \(\varepsilon \) or \(\tau \) increases, and thus the enumeration process of \(\mathsf {LG\text {-}MSBE}\) and \(\mathsf {SS\text {-}MSBE}\) run faster. Also, \(\textsf{indexedVR}\) runs faster when \(\varepsilon \) or \(\tau \) increases, as can be seen from Fig. 10. In contrast, the running time of \(\textsf{MSBE}\) and \(\mathsf {mat\text {-}MSBE}\) is not so sensitive to \(\varepsilon \) or \(\tau \), as the dominating part of these two algorithms is computing similar neighbors for vertices.

Efficiency of \(\textsf{indexedVR}\). In this experiment, we evaluate the efficiency of \(\textsf{indexedVR}\) for our two index structures. Recall that \(\textsf{indexedVR}\) (Algorithm 5) has two phases. Thus, we separately report the results of each phase. The running time on IM and FL are shown in Fig. 10a and b. We can see that the two index structures take almost the same time for the first phase, while the second phase of SS index-based \(\textsf{indexedVR}\) is much faster than LG index-based. This can partially be explained by the number of vertices that need to be pruned in the second phase, as reported in Fig. 10c and d. We remark that, for a fixed \(\varepsilon \) and \(\tau \), the total number of pruned vertices by different indexes are the same, and also the same as that pruned by the index-free approach \(\textsf{VReduce}\). Thus, from the number of vertices that are pruned in Phase-II as shown in Fig. 10, we can conclude that SS index prunes much more vertices than LG index in Phase-I. For example, for dataset FL and \(\varepsilon =0.4\), SS index prunes 467, 329 vertices in Phase-I and 9, 691 vertices in Phase-II, while LG index prunes 449, 195 vertices in Phase-I and 27, 825 vertices in Phase-II. As the second phase dominates the running time, SS index is superior.

Evaluate the optimizations for \(\textsf{Enum}\). In this experiment, we evaluate the performance of our two optimization techniques (i.e., Lemma 1 and Lemma 2) on the \(\textsf{Enum}\) procedure. The results are reported in Fig. 11. Specifically, we use our fastest algorithm \(\mathsf {SS\text {-}MSBE}\) to evaluate these two optimization techniques. Note that \(\mathsf {SS\text {-}MSBE}\) applies both optimizations. For this testing, we also implement \(\mathsf {SS\text {-}MSBE\text {-}v1}\) that adopts neither of the two optimizations, \(\mathsf {SS\text {-}MSBE\text {-}v2}\) that adopts only Lemma 1, and \(\mathsf {SS\text {-}MSBE\text {-}v3}\) that adopts only Lemma 2. From Fig. 11, we can see that \(\mathsf {SS\text {-}MSBE\text {-}v1}\) cannot finish in a reasonable time due to lacking of these optimization techniques, and both \(\mathsf {SS\text {-}MSBE\text {-}v2}\) and \(\mathsf {SS\text {-}MSBE\text {-}v3}\) run significantly faster than \(\mathsf {SS\text {-}MSBE\text {-}v1}\) demonstrating that both Lemma 1 and Lemma 2 significantly improved the performance. We can also observe that the improvements of \(\mathsf {SS\text {-}MSBE}\) over \(\mathsf {SS\text {-}MSBE\text {-}v2}\) and over \(\mathsf {SS\text {-}MSBE\text {-}v3}\) are not that significant. This is because the additional improvements brought by Lemma 2 over Lemma 1 and brought by Lemma 1 over Lemma 2 are not that significant. Nevertheless, \(\mathsf {SS\text {-}MSBE}\) consistently runs faster than \(\mathsf {SS\text {-}MSBE\text {-}v2}\) and \(\mathsf {SS\text {-}MSBE\text {-}v3}\); thus we apply both Lemmas in our algorithm.

Index size and construction time on all graphs. The size of the two indexes on all graphs are shown in the fourth column and last column of Table 2. As a comparison, we also report the graph size in the second column of Table 2. We can see that in most cases, the sizes of the two indexes are similar to each other and are at the same level as the graph size, and thus they are affordable to be stored in main memory.

The running time of our index construction algorithms \(\textsf{consLG}\), \(\textsf{consSS}\), \(\mathsf {consSS^*}\) and \(\mathsf {consSS\text {-}Opt}\) are reported in the third, fifth, sixth and seventh columns of Table 2, respectively. Here, \(\mathsf {consSS^*}\) uses a similarity tree to compute all the maximal steady segments at Line 3 of Algorithm 6; the details can be found in our preliminary version [52]. \(\mathsf {consSS\text {-}Opt}\) invokes \(\textsf{TPA}\) (Algorithm 7) to compute all the maximal steady segments. We can see that \(\textsf{consLG}\) runs the fastest due to its simplicity. By applying our novel optimization technique, \(\mathsf {consSS\text {-}Opt}\) is much faster than \(\textsf{consSS}\) and \(\mathsf {consSS^*}\) and is only slightly slower than \(\textsf{consLG}\). We omit \(\mathsf {consSS^*}\) from all the remaining testings.

Index performance by varying \(\alpha \). In this experiment, we evaluate the effect of \(\alpha \) on the index size, index construction time and efficiency of \(\textsf{MSBE}\). The results are shown in Fig. 12. Recall that \(\alpha \) controls the number of segments constructed for \(\varPhi _u\). As expected, the index size and index construction time increase along with the increasing of \(\alpha \), as shown in Fig. 12a and b. When \(\alpha \) is no larger than 1, the index size is at most at the same level as the graph size, but when \(\alpha \) reaches 100, the index size can be much larger than the graph size. As shown in Fig. 12c and d, the running time of both \(\mathsf {LG\text {-}MSBE}\) and \(\mathsf {SS\text {-}MSBE}\) decreases when \(\alpha \) increases. This is because the more the number of segments, the fewer the number of fake vertices. To strike a balance between index size and efficiency of \(\textsf{MSBE}\), we recommend to set \(\alpha \in [0.1, 10]\).

Efficiency of \(\mathsf {SS\text {-}MSBE}\) by varying \(\gamma \). In this experiment, we evaluate the performance of \(\mathsf {SS\text {-}MSBE}\) for different \(\gamma \) values. Note that the index size and index construction time of \(\mathsf {consSS\text {-}Opt}\) are almost not affected by \(\gamma \); thus, we omit these results. This is because \(\mathsf {consSS\text {-}Opt}\) selects a fixed number of steady segments (i.e., \(\alpha \log |\varPhi _u|\)) to cover as many vertices of \(\varPhi _u\) as possible, and then, it covers all remaining uncovered vertices of \(\varPhi _u\) by using the fewest number of disjoint segments. Thus, the total number of segments generated for \(\varPhi _u\) is at most \(2\alpha \log |\varPhi _u|+1\), which is independent of \(\gamma \). Figure 13 shows the running time of \(\mathsf {SS\text {-}MSBE}\) by varying \(\gamma \) from 0.1 to 0.9. We can see that when \(\gamma \) is small (e.g., \(\gamma <0.3\)), the performance of \(\mathsf {SS\text {-}MSBE}\) is not good. The main reason is that when \(\gamma \) is small, a steady segment will cover fewer vertices due to the tighter constraint. As a result, more vertices need to be covered by the ordinary segments, which then results in introducing more fake vertices. Also, when \(\gamma \) is large, the performance of \(\mathsf {SS\text {-}MSBE}\) becomes worse. This is because for large \(\gamma \) (e.g., \(\gamma =1\)), a steady segment is no longer steady and degenerates to the ordinary segment. This motivates us to introduce steady segment. We recommend the value of \(\gamma \) to be in [0.3, 0.5].

Parallel index construction. In this experiment, we evaluate the parallelized version of our index construction algorithm \(\mathsf {consSS\text {-}Opt}\) by varying the number of CPU cores from 1 to 16 on our largest datasets DE and OR. This experiment was conducted on a machine with an Intel(R) 2.6GHz CPU and 16 cores. As shown in Fig. 14, \(\mathsf {consSS\text {-}Opt}\) has a near-linear speedup by using multiple CPU cores. For example, on OR, the running time of \(\mathsf {consSS\text {-}Opt}\) decreases from 21, 101 seconds (around 6 hours) to 2, 084 seconds (around 0.5 hour) when we increase the core number from 1 to 16. This demonstrates that the index construction can be easily parallelized, and our index can be constructed more efficiently with the help of multiple CPU cores which makes our index more attractive.

Efficiency of index maintenance. In this experiment, we evaluate the performance of our index maintenance algorithms. For edge deletion, we randomly delete 1, 000 edges from the graph one by one and report the average processing time. For comparison, we also implement a version of \(\mathsf {EdgeDelete^*}\) that does not performance the optimization (i.e., Lemma 7), denoted \(\textsf{EdgeDelete}\). The average processing time of \(\mathsf {EdgeDelete^*}\) and \(\textsf{EdgeDelete}\) for handling edge deletions is reported in Fig. 15a. We can see that the running time of \(\mathsf {EdgeDelete^*}\) is at millisecond-level. For example, when deleting an edge from DB, the maintenance of the index can be completed in less than 0.1 ms. However, the effectiveness of optimization technique is not obvious, i.e., \(\mathsf {EdgeDelete^*}\) performs similarly to \(\textsf{EdgeDelete}\). This mainly because the number of u’s 2-hop neighbors that are adjacent to v is much smaller than the total number of u’s 2-hop neighbors; thus, the pruning at Lines 6–7 of Algorithm 8 is not very effective.

For edge insertion, we randomly insert 1, 000 new edges into the graph one by one and report the average processing time. We compare \(\mathsf {EdgeInsert\text {-}Opt}\) with \(\mathsf {EdgeInsert^*}\) and its non-optimized version \(\textsf{EdgeInsert}\). The results are reported in Figure 16. We can see that \(\mathsf {EdgeInsert^*}\) runs significantly faster than \(\textsf{EdgeInsert}\) due to the optimization technique described in Lemma 9. Nevertheless, \(\mathsf {EdgeInsert\text {-}Opt}\) runs the fastest, since it only processes the neighbors of u and v for the newly inserted edge (u, v).

Index size and query efficiency w.r.t. the number of updates. In this experiment, we evaluate the index size and query efficiency w.r.t. the number of updates. In our index maintenance algorithms, for time efficiency consideration, we do not update a segment if one or more similarities in the segment decrease, and we also do not enforce the steady requirement of a segment. As a result, it is expected that the query efficiency will deteriorate when the index has been updated by a lot of edge insertions and deletions. The results for edge deletion on IM and FL are shown in Fig. 16a and b, respectively; here, the query time is the running time of \(\mathsf {SS\text {-}MSBE}\) under the default setting (i.e., \(\varepsilon =0.5\) and \(\tau =3\)). We can see that the index size remains steady; this is because deleting edges will not bring new segments to our index. However, the query time increases when the number of updates is over \(10^5\). The results for edge insertion on IM and FL are shown in Fig. 16c and d, respectively. We can see that both the index size and query time increase significantly when the number of inserted edges is over \(10^5\). This is because new segments are also created for handling edge insertions. From this experiment, we recommend to reconstruct the index from scratch when the number of updates has reached \(0.1\times |E|\).

Average Jaccard similarity. We compare the average Jaccard similarity between L-side vertices in a maximal (similar-)biclique. Specifically, for each maximal (similar-)biclique C, we compute the average of the Jaccard similarity between all pairs of vertices from \(C_L\), and then the average result of all maximal (similar-)bicliques is reported in Fig. 17. We can see that vertices in a similar-biclique are much more similar to each other than in a biclique.

Number of maximal similar-bicliques. The number of maximal similar-bicliques for different \(\varepsilon \) and \(\tau \) values are shown in Fig. 18. We can see that the number of maximal similar-bicliques decreases with the increase of either \(\varepsilon \) or \(\tau \), which is as expected. This is because the number of similar neighbors for a vertex decreases with the increase of \(\varepsilon \). Thus, more and more similar-bicliques disappear under a larger \(\varepsilon \). It is worth mentioning that even under a high \(\varepsilon \) value of 0.7, there is still quite a few similar-bicliques, which exhibit a high level of consistence among members from the same side.

Case study 1: anomaly detection. In this case study, we compare similar-biclique with other dense bipartite subgraph models, biclique, \((\alpha ,\beta )\)-core [24] and k-biplex [54], on anomaly detection in e-commerce applications. As mentioned in the Introduction, to improve the ranking of certain products, e-business owners may employ a set of fraudulent users to purchase a set of designated products. The fraudsters will also purchase other honest products trying to look “normal”; this is called “camouflage” in the literature. We consider a camouflage attack in the same way as [18] on “Amazon Review Data” (Magazine Subscriptions) ,⁶ which contains 65, 546 reviews on 2, 316 magazines by 53, 617 users, by injecting 100 fraudulent users and 100 fraudulent products with various edge densities. The amount of camouflage (i.e., edges linking to honest products) added per fraudulent user is equal to the amount of fraudulent edges for that user. We adopt F-score, \(\frac{2\times \text {precision}\times \text {recall}}{\text {precision}+\text {recall}}\), to evaluate the accuracy of detecting suspicious users and products. We apply the size constraint \(\tau \) to all the models, where \(\alpha =\beta =\tau \) for the \((\alpha ,\beta )\)-core model; for our similar-biclique model, \(\varepsilon \) is set as 0.2. The results by varying \(\tau \) and varying the density of the injected subgraph are shown in Fig. 19. We can see that similar-biclique always achieves the highest accuracy. This is due to the similarity constraint imposed on users by similar-biclique, which naturally captures the reality that fraudulent users usually display a high level of synchronized behavior with each other. In contrast, biclique, 1-biplex, and \((\alpha ,\beta )\)-core all have a low precision and thus low F-score.

Case study 2: interesting pattern detection on Unicode . We also conduct a case study on the Unicode dataset [25] to illustrate the hierarchical structure of similar-bicliques by varying the similarity threshold \(\varepsilon \). Unicode captures the languages that are spoken in a country. The three similar-bicliques detected for \(\varepsilon = 0.7\), 0.4, 0.01 are reported in Fig. 20, where the entire result corresponds to \(\varepsilon =0.01\); the similarity constraint is imposed on the countries and \(\tau =2\). We have the following observations. Firstly, the five countries in the similar-biclique for \(\varepsilon =0.7\) are all located in the Caribbean Sea Area with English and Spanish being their main language (around \(90\%\) population speak English and Spanish). Secondly, more countries from Latin America, e.g., Argentina and Chile, are included in the similar-biclique for \(\varepsilon =0.4\), and the newly added four countries speak more diverse languages. For example, in Sint Maarten, besides English and Spanish, around \(8\%\) population speak Virgin Islands Creole English and \(4\%\) population speak Dutch .⁷ Lastly, when \(\varepsilon \) is 0.01, similar-biclique degenerates to biclique, and more countries are included, e.g., America and Germany. This demonstrates that similar-biclique can detect interesting patterns.

Case study 3: research group identification in DBLP . Our similar-biclique model also supports the case that not all vertices in a side share a common neighbor. In this case study, we show the similar-bicliques in a researcher-write-paper bipartite graph DBLP ⁸ by using different size constraints \(\tau _L\) and \(\tau _R\) on the two sides. The results for \(\varepsilon =0.6\), \(\tau _L=6\), and \(\tau _R=0\) are illustrated in Table 3; thus, researchers in a similar-biclique are not necessarily co-authors of the same paper. We find that the detected similar-bicliques corresponds to research groups in different institutes.