Computer Science
Computer Science-2021.gz:143203
Computer Science
71c65438f2553a74d5be0aa71109a638d1670370
Local Algorithms for Finding Densely Connected Clusters

Local graph clustering is an important algorithmic technique for analysing massive graphs, and has been widely applied in many research fields of data science. While the objective of most (local) graph clustering algorithms is to find a vertex set of low conductance, there has been a sequence of recent studies that highlight the importance of the inter-connection between clusters when analysing real-world datasets. Following this line of research, in this work we study local algorithms for finding a pair of vertex sets defined with respect to their inter-connection and their relationship with the rest of the graph. The key to our analysis is a new reduction technique that relates the structure of multiple sets to a single vertex set in the reduced graph. Among many potential applications, we show that our algorithms successfully recover densely connected clusters in the Interstate Disputes Dataset and the US Migration Dataset.


Introduction
Given an arbitrary vertex u of a graph G = (V, E) as input, a local graph clustering algorithm finds some low-conductance set S ⊂ V containing u, while the algorithm runs in time proportional to the size of the target cluster and independent of the size of the graph G. Because of the increasing size of available datasets, which makes centralised computation too expensive, local graph clustering has become an important learning technique for analysing a number of large-scale graphs and has been applied to solve many other learning and combinatorial optimisation problems [1,5,11,16,25,29,30, 32].

Our Contribution
We study local graph clustering for learning the structure of clusters that are defined by their inter-connections, and present two local algorithms to achieve this objective in both undirected graphs and directed ones.
Our first result is a local algorithm for finding densely connected clusters in an undirected graph G = (V, E): given any seed vertex u, our algorithm is designed to find two clusters L, R around u, which are densely connected to each other and are loosely connected to V \ (L ∪ R). The design of our algorithm is based on a new reduction that allows us to relate the connections between L, R and V \ (L ∪ R) to a single cluster in the resulting graph H, and a generalised analysis of Pagerank-based algorithms for local graph clustering. The significance of our designed algorithm is demonstrated by our experimental results on the Interstate Dispute Network from 1816 to 2010. By connecting two vertices (countries) with an undirected edge weighted according to the severity of their military disputes and using the USA as the seed vertex, our algorithm recovers two groups of countries that tend to have conflicts with each other, and shows how the two groups evolve over time.
In particular, as shown in Figures 1(a)-(d), our algorithm not only identifies the changing roles of Russia, Japan, and eastern Europe in line with 20th century geopolitics, but also the reunification of east and west Germany around 1990.
We further study densely connected clusters in a directed graph (digraph). Specifically, given any vertex u in a digraph G = (V, E) as input, our second local algorithm outputs two disjoint vertex sets L and R, such that (i) there are many edges from L to R, and (ii) L ∪ R is loosely connected to V \ (L ∪ R). The design of our algorithm is based on the following two techniques: (1) a new reduction that allows us to relate the edge weight from L to R, as well as the edge connections between L ∪ R and V \ (L ∪ R), to a single vertex set in the resulting undirected graph H; (2) a refined analysis of the ESP-based algorithm for local graph clustering. We In each case, countries in the yellow cluster tend to enter conflicts with countries in the blue cluster and vice versa. (e)-(h) Clusters found by EvoCutDirected in the US migration network. There is a large net flow from the red counties to the green counties.
show that our algorithm is able to recover local densely connected clusters in the US migration dataset, in which two vertex sets L, R defined as above could represent a higher-order migration trend. In particular, as shown in Figures 1(e)-(h), by using different counties as starting vertices, our algorithm uncovers refined and more localised migration patterns than the previous work on the same dataset [10]. To the best of our knowledge, our work represents the first local clustering algorithm that achieves a similar goal.

Related Work
Li and Peng [15] study the same problem for undirected graphs, and present a random walk based algorithm. Andersen [1] studies a similar problem for undirected graphs under a different objective function, and our algorithm's runtime significantly improves the one in [1]. There is some recent work on local clustering for hypergraphs [25], and algorithms for finding higher-order structures of graphs based on network motifs both centrally [7,8] and locally [30]. These algorithms are designed to find different types of clusters, and cannot be directly compared with ours. Our problem is related to the problem of finding clusters in disassortative networks [22,23,31], although the existing techniques are based on semi-supervised, global methods while ours is unsupervised and local. There are also recent studies which find clusters with a specific structure in the centralised setting [10,14]. Our current work shows that such clusters can be learned locally via our presented new techniques.

Preliminaries
Notation. For any undirected and unweighted graph G = (V G , E G ) with n vertices and m edges, the degree of any vertex v is denoted by deg G (v), and the set of neighbours of v is N G (v). For any S ⊆ V , its volume is vol G (S) v∈S deg(v), its boundary is ∂ G (S) {(u, v) ∈ E : u ∈ S and v ∈ S}, and its conductance is For disjoint S 1 , S 2 ⊂ V G , e(S 1 , S 2 ) is the number of edges between S 1 and S 2 . When G = (V G , E G ) is a digraph, for any u ∈ V G we use deg out (u) and deg in (u) to express the number of edges with u as the tail or the head, respectively. For any S ⊂ V G , we define vol out (S) = u∈S deg out (u), and vol in (S) = u∈S deg in (u).
For undirected graphs, we use D G to denote the n × n diagonal matrix with (D G ) v,v = deg G (v) for any vertex v ∈ V , and we use A G to represent the adjacency matrix of G defined by (A G ) u,v = 1 if {u, v} ∈ E G , and (A G ) u,v = 0 otherwise. The lazy random walk matrix of G is W G = (1/2) · (I + D −1 G A G ). For any set S ⊂ V G , χ S is the indicator vector of S, i.e., χ S (v) = 1 if v ∈ S, and χ S (v) = 0 otherwise. If the set consists of a single vertex v, we write χ v instead of χ {v} . Sometimes we drop the subscript G when the underlying graph is clear from the context. For any vectors x, y ∈ R n , we write x y if it holds for any v that x(v) ≤ y(v). For any operators f, g : R n → R n , we define f • g : R n → R n by f • g(v) f (g(v)) for any v. For any vector p, we define the support of p to be supp(p) = {u : p(u) = 0}. The sweep sets of p are defined by (1) ordering all the vertices such that and (2) constructing S p j = {v 1 , . . . , v j } for 1 ≤ j ≤ n. Throughout this paper, we will consider vectors to be row vectors, so the random walk update step for a distribution p is written as pW . For ease of presentation we consider only unweighted graphs; however, our analysis can be easily generalised to the weighted case. The omitted proofs can be found in the Appendix.
Pagerank. Given an underlying graph G with the lazy random walk matrix W , the personalised Pagerank vector pr(α, s) is defined to be the unique solution of the equation where s ∈ R n ≥0 is a starting vector and α ∈ (0, 1] is called the teleport probability. Andersen et al. [4] show that the personalised Pagerank vector can be written as pr(α, s) = α ∞ t=0 (1 − α) t sW t . Therefore, we could study pr(α, s) through the following random process: pick some integer t ∈ Z ≥0 with probability α(1 − α) t , and perform a t-step lazy random walk, where the starting vertex of the random walk is picked according to s. Then, pr(α, s) describes the probability of reaching each vertex in this process.
Computing an exact Pagerank vector pr(α, χ v ) is equivalent to computing the stationary distribution of a Markov chain on the vertex set V which has a time complexity of Ω(n). However, since the probability mass of a personalised Pagerank vector is concentrated around some starting vertex, it is possible to compute a good approximation of the Pagerank vector in a local way. Andersen et al. [4] introduced the approximate Pagerank, which will be used in our analysis. Definition 1. A vector p = apr(α, s, r) is an approximate Pagerank vector if p + pr(α, r) = pr(α, s). The vector r is called the residual vector.
The evolving set process. The evolving set process (ESP) is a Markov chain whose states are sets of vertices S i ⊆ V . Given a state S i , the next state S i+1 is determined by the following process: (1) choose t ∈ [0, 1] uniformly at random; (2) The volume-biased ESP is a variant used to ensure that the Markov chain absorbs in the state V rather than ∅. Andersen and Peres [2] gave a local algorithm for undirected graph clustering using the volume-biased ESP. In particular, they gave an algorithm GenerateSample(u, T ) which samples the T -th element from the volume-biased ESP with S 0 = {u}.

The Algorithm for Undirected Graphs
Now we present a local algorithm for finding two clusters in an undirected graph with a dense cut between them. To formalise this notion, for any undirected graph G = (V, E) and disjoint L, R ⊂ V , we follow Trevisan [27] and define the bipartiteness ratio Notice that a low β(L, R) value means that there is a dense cut between L and R, and there is a sparse cut between L ∪ R and V \ (L ∪ R). In particular, β(L, R) = 0 implies that (L, R) forms a bipartite and connected component of G. We will describe a local algorithm for finding almost-bipartite sets L and R with a low value of β(L, R).

The Reduction by Double Cover
The design of most local algorithms for finding a target set S ⊂ V of low conductance is based on analysing the behaviour of random walks starting from vertices in S. In particular, when the conductance Φ G (S) is low, a random walk starting from most vertices in S will leave S with low probability. However, for our setting, the target is a pair of sets L, R with many connections between them. As such, a random walk starting in either L or R is very likely to leave the starting set. To address this, we introduce a novel technique based on the double cover of G to reduce the problem of finding two sets of high conductance to the problem of finding one of low conductance. Formally, for any undirected graph G = (V G , E G ), its double cover is the bipartite graph H = (V H , E H ) defined as follows: (1) every vertex v ∈ V G has two corresponding vertices v 1 , v 2 ∈ V H ; (2) for every edge {u, v} ∈ E G , there are edges {u 1 , v 2 } and {u 2 , v 1 } in E H . See Figure 2 for an illustration. Figure 2: An example of the construction of the double cover. Now we present a tight connection between the value of β(L, R) for any disjoint sets L, R ⊂ V G and the conductance of a single set in the double cover of G. To this end, for any S ⊂ V G , we define S 1 ⊂ V H and We formalise the connection in the following lemma. Lemma 1. Let G be an undirected graph, S ⊂ V with partitioning (L, R), and H be the double cover of G. Then, it holds that Φ H (L 1 ∪ R 2 ) = β G (L, R).
Next we look at the other direction of this correspondence. Specifically, given any S ⊂ V H in the double cover of a graph G, we would like to find two disjoint sets L ⊂ V G and R ⊂ V G such that β G (L, R) = Φ H (S). However, such a connection does not hold in general. To overcome this, we restrict our attention to those subsets of V H which can be unambiguously interpreted as two disjoint sets in V G .

Design of the Algorithm
So far we have shown that the problem of finding densely connected sets L, R ⊂ V G can be reduced to finding S ⊂ V H of low conductance in the double cover H, and this reduction raises the natural question of whether existing local algorithms can be directly employed to find L and R in G. However, this is not the case: even though a set S ⊂ V H returned by most local algorithms is guaranteed to have low conductance, vertices of G could be included in S twice, and as such S will not necessarily give us disjoint sets L, R ⊂ V G with low value of β(L, R). See Figure 3 for an illustration. The simplify operator. To take the example shown in Figure 3 into account, our objective is to design a local algorithm for finding some set S ⊂ V H of low conductance which is also simple. To ensure this, we introduce the simplify operator, and analyse its properties.
Definition 3 (Simplify operator). Let H be the double cover of G, where the two corresponding vertices of any u ∈ V G are defined as u 1 , u 2 ∈ V H . Then, for any p ∈ R 2n ≥0 , the simplify operator is a function σ : R 2n Notice that, for any vector p and any u ∈ V G , at most one of u 1 and u 2 is in the support of σ • p; hence, the support of σ • p is always simple. To explain the meaning of σ, for a vector p one could view p(u 1 ) as our "confidence" that u ∈ L, and p(u 2 ) as our "confidence" that u ∈ R. Hence, when p(u 1 ) ≈ p(u 2 ), both (σ • p)(u 1 ) and (σ • p)(u 2 ) are small which captures the fact that we would not prefer to include u in either L or R. On the other hand, when p(u 1 ) p(u 2 ), we have (σ • p)(u 1 ) ≈ p(u 1 ), which captures our confidence that u should belong to L. The following lemma summaries some key properties of σ.
Lemma 3. The following holds for the σ-operator: ≥0 and any c ∈ R ≥0 ; While these three properties will all be used in our analysis, the third is of particular importance: it implies that, if p is the probability distribution of a random walk in H, applying σ before taking a one-step random walk would never result in lower probability mass than applying σ after taking a one-step random walk. This means that no probability mass would be lost when the σ-operator is applied between every step of a random walk, in comparison with applying σ at the end of an entire random walk process.
Description of the algorithm. Our proposed algorithm is conceptually simple: every vertex u of the input graph G maintains two copies u 1 , u 2 of itself, and these two "virtual" vertices are used to simulate u's corresponding vertices in the double cover H of G. Then, as the neighbours of u 1 and u 2 in H are entirely determined by u's neighbours in G and can be constructed locally, a random walk process in H will be simulated in G. This will allow us to apply a local algorithm similar to the one by Anderson et al. [4] on this "virtual" graph H. Finally, since all the required information about u 1 , u 2 ∈ V H is maintained by u ∈ V G , the σ-operator will be applied locally.
The formal description of our algorithm is given in Algorithm 1, which invokes Algorithm 2 as the key component to compute apr H (α, χ u 1 , r). Specifically, Algorithm 2 maintains, for every vertex u ∈ G, tuples (p(u 1 ), p(u 2 )) and (r(u 1 ), r(u 2 )) to keep track of the values of p and r in G's double cover. For a given vertex u, the entries in these tuples are expressed by p 1 (u), p 2 (u), r 1 (u), and r 2 (u) respectively. Every dcpush operation (Algorithm 3) preserves the invariant p + pr H (α, r) = pr H (α, χ v 1 ), which ensures that the final output of Algorithm 2 is an approximate Pagerank vector. We remark that, although the presentation of the ApproximatePagerankDC procedure is similar to the one in Andersen et al. [4], in our dcpush procedure the update of the residual vector r is slightly more involved: specifically, for every vertex u ∈ V G , both r 1 (u) and r 2 (u) are needed in order to update r 1 (u) (or r 2 (u)). That is one of the reasons that the performance of the algorithm in Andersen et al. [4] cannot be directly applied for our algorithm, and a more technical analysis, some of which is parallel to theirs, is needed in order to analyse the correctness and performance of our algorithm.

Analysis of the Algorithm
To prove the correctness of our algorithm, we will show two complementary facts which we state informally here: 1. If there is a simple set S ⊂ V H with low conductance, then for most u 1 ∈ S, the simplified approximate Pagerank vector p = σ • apr(α, χ u 1 , r) will have a lot of probability mass on a small set of vertices.
2. If p = σ • apr(α, χ u 1 , r) contains a lot of probability mass on some small set of vertices, then there is a sweep set of p with low conductance.
Algorithm 1: LocBipartDC Input: A graph G, starting vertex u, target volume γ, and target bipartiteness β Output: Two disjoint sets L and R Set α = β 2 378 , and = 1 20γ Input: Starting vertex v, parameters α and Output: Approximate Pagerank vector apr H (α, As we have shown in Section 3.1, there is a direct correspondence between almost-bipartite sets in G, and low-conductance and simple sets in H. This means that the two facts above are exactly what we need to prove that Algorithm 1 can find densely connected sets in G. We will first show in Lemma 4 how the σ-operator affects some standard mixing properties of Pagerank vectors in order to establish the first fact promised above. This lemma relies on the fact that S ⊂ V G corresponds to a simple set in V H . This allows us to apply the σ-operator to the approximate Pagerank vector apr H (α, χ u 1 , r) while preserving a large probability mass on the target set.
Lemma 4. For any set S ⊂ V G with partitioning (L, R) and any constant α ∈ [0, 1], there is a subset S α ⊆ S with vol(S α ) ≥ vol(S)/2 such that, for any vertex v ∈ S α , the simplified approximate Pagerank on the double cover p = σ • (apr H (α, χ v 1 , r)) satisfies To prove the second fact, we show as an intermediate lemma that the value of p(u 1 ) can be bounded with respect to its value after taking a step of the random walk: pW (u 1 ).
Lemma 5. Let G be a graph with double cover H, and apr(α, s, r) be the approximate Pagerank vector defined with respect to H. Then, p = σ • (apr(α, s, r)) satisfies that p( Notice that applying the σ-operator for any vertex u 1 introduces a new dependency on the value of the residual vector r at u 2 . This subtle observation demonstrates the additional complexity introduced by the σ-operator when compared with previous analysis of Pagerank-based local algorithms [4]. Taking account of the σ-operator, we further analyse the Lovász-Simonovits curve defined by p, which is a common technique in the analysis of random walks on graphs [17]: we show that if there is a set S with a large value of p(S), there must be a sweep set S p j with small conductance.
We have now shown the two facts promised at the beginning of this subsection. Putting these together, if there is a simple set S ⊂ V H with low conductance then we can find a sweep set of σ • apr(α, s, r) with low conductance. By the reduction from almost-bipartite sets in G to low-conductance simple sets in H our target set corresponds to a simple set S ⊂ V H which leads to Algorithm 1 for finding almost-bipartite sets. Our result is summarised as follows.
The quadratic approximation guarantee in Theorem 1 matches the state-of-the-art local algorithm for finding a single set with low conductance [5]. Furthermore, our result presents a significant improvement over the previous state-of-the-art by Li and Peng [15], whose design is based on an entirely different technique than ours. For any ∈ [0, 1/2], their algorithm runs in time O 2 β −2 γ 1+ log 3 γ and returns a set with volume O γ 1+ and bipartiteness ratio O β/ . In particular, their algorithm requires much higher time complexity in order to guarantee the same bipartiteness ratio O √ β .

The Algorithm for Digraphs
We now turn our attention to local algorithms for finding densely-connected clusters in digraphs. In comparison with undirected graphs, we are interested in finding disjoint L, R ⊂ V of some digraph G = (V, E) such that most of the edges adjacent to L ∪ R are from L to R. To formalise this, we define the flow ratio from L to R as where e(L, R) is the number of directed edges from L to R. Notice that we take not only edge densities but also edge directions into account: a low F (L, R)-value tells us that almost all edges with their tail in L have their head in R, and conversely almost all edges with their head in R have their tail in L. One could also see F (L, R) as a generalisation of β(L, R). In particular, if we view an undirected graph as a digraph by replacing each edge with two directed edges, then β(L, R) = F (L, R). In this section, we will present a local algorithm for finding such vertex sets in a digraph, and analyse the algorithm's performance. Figure 4 for illustration. 1 It is worth comparing this reduction with the one for undirected graphs:

The Reduction by Semi-Double Cover
• For undirected graphs, we apply the standard double cover and every undirected edge in G corresponds to two edges in the double cover H; • For digraphs, every directed edge in G corresponds to one undirected edge in H. This asymmetry would allow us to "recover" the direction of any edge in G. Figure 4: An example of a digraph and its semi-double cover.
We follow the use of S 1 , S 2 from Section 3: for any The lemma below shows the connection between the value of F G (L, R) for any L, R and Φ H (L 1 ∪ R 2 ).

Design and Analysis of the Algorithm
Our presented algorithm is a modification of the algorithm by Andersen and Peres [2]. Given a digraph G as input, our algorithm simulates the volume-biased ESP on G's semi-double cover H. Notice that the graph H can be constructed locally in the same way as the local construction of the double cover. However, as the output set S of an ESP-based algorithm is not necessarily simple, our algorithm only returns vertices u ∈ V G in which exactly one of u 1 and u 2 are included in S. The key procedure for our algorithm is given in Algorithm 4, in which the GenerateSample procedure is the one described at the end of Section 2.

Algorithm 4: EvoCutDirected (ECD)
Input: Due to this asymmetry, Algorithm 4 takes a parameter i ∈ {1, 2} to indicate whether the starting vertex is in L or R. If it is not known whether u is in L or R, two copies can be run in parallel, one with i = 1 and the other with i = 2. Once one of them terminates with the performance guaranteed in Theorem 2, the other can be terminated. Hence, we can always assume that it is known whether the starting vertex u is in L or R.
Now we sketch the analysis of the algorithm. Notice that, since the evolving set process gives us an arbitrary set on the semi-double cover, in Algorithm 4 we convert this into a simple set by removing any vertices u where u 1 ∈ S and u 2 ∈ S. The following definition allows us to discuss sets which are close to being simple.
Definition 4 ( -simple set). For any set S ⊂ V H , let P = {u 1 , u 2 : u ∈ V G , u 1 ∈ S and u 2 ∈ S}. We call set S -simple if it holds that vol(P ) vol(S) ≤ .
The notion of -simple sets measures the ratio of vertices in which both u 1 and u 2 are in S. In particular, any simple set defined in Definition 2 is 0-simple. We show that, for any -simple set S ⊂ V H , one can construct a simple set S such that Φ(S ) ≤ 1 1− · (Φ(S) + ). Therefore, in order to guarantee that Φ(S ) is small, we need to construct S such that Φ(S) is small and S is -simple for small . Because of this, our presented algorithm uses a lower value of T than the algorithm in Andersen and Peres [2]; this allows us to better control vol(S) at the cost of a slightly worse approximation guarantee. Our algorithm's performance is summarised in Theorem 2. To the best of our knowledge, this is the first local algorithm for digraphs that approximates a pair of densely connected clusters, and demonstrates that finding such a pair appears to be much easier than finding a low-conductance set in a digraph; in particular, existing local algorithms for finding a low-conductance set require the stationary distribution of the random walk in the digraph [3], the sublinear-time computation of which is unknown [9]. However, knowledge of the stationary distribution is not needed for our algorithm.
Further Discussion. It is important to note that the semi-double cover construction is able to handle directed graphs which contain edges between two vertices u and v in both directions. In other words, the adjacency matrix of the digraph need not be skew-symmetric. This is an advantage of our approach over previous methods (e.g., [10]), and it would be a meaningful research direction to identify the benefit this gives our developed reduction.
It is also insightful to discuss why Algorithm 1 cannot be applied for digraphs, although the input digraph is translated into an undirected graph by our reduction. This is because, when translating a digraph into a bipartite undirected graph, the third property of the σ-operator in Lemma 3 no longer holds, since the existence of the edge {u 1 , v 2 } ∈ E H does not necessarily imply that {u 2 , v 1 } ∈ E H . Indeed, Figure 5 gives a counterexample in which (σ • (pW )) (u) ≤ ((σ • p)W ) (u). This means that the typical analysis of a Pagerank vector with the Lovász-Simonovitz curve cannot be applied anymore. In our point of view, constructing some operator similar to our σ-operator and designing a Pagerank-based local algorithm for digraphs based on such an operator is a very interesting open question, and may help to close the gap in the approximation guarantee between the undirected and directed cases. In addition, we underline that one cannot apply the tighter analysis of the ESP process given by Andersen et al. [5] to our algorithm. The key to their analysis is an improved bound on the probability that a random walk escapes from the target cluster. In order to take advantage of this, they use a larger value of T in the algorithm which relaxes the guarantee on the volume of the output set. Since our analysis relies on a very tight guarantee on the overlap of the output set with the target set, we cannot use their improvement in our setting.

Experiments
In this section we evaluate the performance of our proposed algorithms on both synthetic and real-world data sets. For undirected graphs, we compare the performance of our algorithm against the previous state-of-the-art [15], through the synthetic dataset with various parameters and apply the real-world dataset to demonstrate the significance of our algorithm. For directed graphs, we compare the performance of our algorithm with the state-of-the-art non-local algorithm since, to the best of our knowledge, our local algorithm for digraphs is the first such algorithm in the literature. All experiments were performed on a Lenovo Yoga 2 Pro with an Intel(R) Core(TM) i7-4510U CPU @ 2.00GHz processor and 8GB of RAM. Our code can be downloaded from https://github.com/pmacg/local-densely-connected-clusters.

Experiments on Synthetic Data
We first compare the performance of our algorithm, LocBipartDC, with the previous state-of-the-art given by Li & Peng [15], which we refer to as LP, on synthetic graphs generated from the stochastic block model (SBM). Specifically, we assume that the graph has k = 3 clusters {C j } 3 j=1 , and the number of vertices in each cluster, denoted by n 1 , n 2 and n 3 respectively, satisfy n 1 = n 2 = 0.1n 3 . Moreover, any pair of vertices u ∈ C i and v ∈ C j is connected with probability P i,j . We assume that P 1,1 = P 2,2 = p 1 , P 3,3 = p 2 , P 1,2 = q 1 , and P 1,3 = P 2,3 = q 2 . Throughout our experiments, we maintain the ratios p 2 = 2p 1 and q 2 = 0.1p 1 , leaving the parameters n 1 , p 1 and q 1 free. Notice that the different values of q 1 and q 2 guarantee that C 1 and C 2 are the ones optimising the β-value, which is why our proposed model is slightly more involved than the standard SBM.
We evaluate the quality of the output (L, R) returned by each algorithm with respect to its β-value, the Adjusted Rand Index (ARI) [12], as well as the ratio of the misclassified vertices defined by |L C 1 |+|R C 2 | |L∪C 1 |+|R∪C 2 | , where A B is the symmetric difference between A and B. All our reported results are the average performance of each algorithm over 10 runs, in which a random vertex from C 1 ∪ C 2 is chosen as the starting vertex of the algorithm.
Setting the parameter in the LP algorithm. The LP algorithm has an additional parameter over ours, which we refer to as LP . This parameter influences the runtime and performance of the algorithm and must be in the range [0, 1/2]. In order to choose a fair value of LP for comparison with our algorithm, we consider several values on graphs with a range of target volumes.
We generate graphs from the SBM such that p 1 = 1/n 1 and q 1 = 100p 1 and vary the size of the target set by varying n 1 between 100 and 10, 000. For values of LP in {0.01, 0.02, 0.1, 0.5}, Figure 6(a) shows how the runtime of the LP algorithm compares to the LocBipartDC algorithm for a range of target volumes. In this experiment, the runtime of the LocBipartDC algorithm lies between the runtimes of the LP algorithm for LP = 0.01 and LP = 0.02. However, Figure 6(b) shows that the performance of the LP algorithm with LP = 0.01 is significantly worse than the performance of the LocBipartDC algorithm and so for a fair comparison, we set LP = 0.02 for the remainder of the experiments. Comparison on the Synthetic Data. We now compare the LocBipartDC and LP algorithms' performance on graphs generated from the SBM with different values of n 1 , p 1 and q 1 . As shown in Table 1, our algorithm not only runs faster, but also produces better clusters with respect to all three metrics. Secondly, since the clustering task becomes more challenging when the target clusters have higher β-value, we compare the algorithms' performance on a sequence of instances with increasing value of β. Since q 1 /p 1 = 2(1 − β)/β, we simply fix the values of n 1 , p 1 as n 1 = 1, 000, p 1 = 0.001, and generate graphs with increasing value of q 1 /p 1 ; this gives us graphs with monotone values of β. As shown in Figure 7(a), our algorithms performance is always better than the previous stat-of-the-art. Thirdly, notice that both algorithms use some parameters to control the algorithm's runtime and the output's approximation ratio, which are naturally influenced by each other. To study this dependency, we generate graphs according to n 1 = 100, 000, p 1 = 0.000015, and q 1 = 0.00027 which results in target sets with β ≈ 0.1 and volume γ ≈ 6, 000, 000. Figure 7(b) shows that, in comparison with the previous state-of-the-art, our algorithm takes much less time to produce output with the same ARI value.

Experiments on the Real-world Dataset
We demonstrate the significance of our algorithm on the Dyadic Militarised Interstate Disputes Dataset (v3.1) [19], which records every interstate dispute during 1816-2010, including the level of hostility resulting from the dispute and the number of casualties, and has been widely studied in the social and political sciences [18,20] as well as the machine learning community [13,21,26]. For a given time period, we construct a graph from the data by representing each country with a vertex and adding an edge between each pair of countries weighted according to the severity of any military disputes between those countries. Specifically, if there's a war 2 between the two countries, the corresponding two vertices are connected by an edge with weight 30; for any other dispute that is not part of an interstate war, the two corresponding vertices are connected by an edge with weight 1. We always use the USA as the starting vertex of the algorithm, and our algorithm's output, as visualised in Figure 1

Results for Digraphs
Next we evaluate the performance of our algorithm for digraphs on synthetic and real-world datasets. Since there are no previous local digraph clustering algorithms that achieve similar objectives to ours, we compare the output of Algorithm 4 (ECD) with the state-of-the-art non-local algorithm proposed by Cucuringu et al. [10], and we refer this to as CLSZ in the following.
Synthetic Dataset. We first look at the cyclic block model (CBM) described in Cucuringu et al. [10] with parameters k, n, p, q, and η. In this model, we generate a digraph with k clusters C 1 , . . . , C k of size n, and for u, v ∈ C i , there is an edge between u and v with probability p and the edge direction is chosen uniformly at random. For u ∈ C i and v ∈ C i+1 mod k , there is an edge between u and v with probability q, and the edge is directed from u to v with probability η and from v to u with probability 1 − η. Throughout our experiments, we fix p = 0.001, q = 0.01, and η = 0.9.
Secondly, since the goal of our algorithm is to find local structure in a graph, we extend the cyclic block model with additional local clusters and refer to this model as CBM+. In addition to the parameters of the CBM, we introduce the parameters n , q 1 , q 2 , and η . In this model, the clusters C 1 to C k are generated as in the CBM, and there are two additional clusters C k+1 and C k+2 of size n . For u, v ∈ C k+i for i ∈ {1, 2}, there is an edge between u and v with probability p and for u ∈ C k+1 and v ∈ C k+2 , there is an edge with probability q 1 ; the edge directions are chosen uniformly at random. For u ∈ C k+1 ∪ C k+2 and v ∈ C 1 , there is an edge with probability q 2 . If u ∈ C k+1 , the orientation is from v to u with probability η and from u to v with probability 1 − η and if u ∈ C k+2 , the orientation is from u to v with probability η and from v to u with probability 1 − η . We always fix q 1 = 0.5, q 2 = 0.005, and η = 1. Notice that the clusters C k+1 and C k+2 form a "local" cycle with the cluster C 1 .
In Table 2, we report the average performance over 10 runs with a variety of parameters. We find that CLSZ can uncover the global structure in the CBM more accurately than ECD. On the other hand, CLSZ fails to identify the local cycle in the CBM+ model, while ECD succeeds.  [10] and construct the digraph as follows: every county in the mainland USA is represented by a vertex; for any vertices j, , the edge weight of (j, ) is given by where M j, is the number of people who migrated from county j to county between 1995 and 2000; in addition, the direction of (j, ) is set to be from j to if M j, > M ,j , otherwise the direction is set to be the opposite.
For CLSZ, we follow their suggestion on the same dataset and set k = 10. Both algorithms' performance is evaluated with respect to the flow ratio, as well as the Cut Imbalance ratio used in their work. For any vertex sets L and R, the cut imbalance ratio is defined by CI(L, R) = 1 2 · e(L,R)−e(R,L) e(L,R)+e(R,L) , and a higher CI(L, R) value indicates the connection between L and R is more significant. Using counties in Ohio, New York, California, and Florida as the starting vertices, our algorithm's outputs are visualised in Figures 1(e)-(h), and in Table 3 we compare them to the top 4 pairs returned by CLSZ, which are shown in Figure 8. Our algorithm produces better outputs with respect to both metrics.
These experiments suggest that local algorithms are not only more efficient, but can also be much more effective than global algorithms when learning certain structures in graphs. In particular, some localised structure might be hidden when applying the objective function over the entire graph.

A Omitted detail from Section 3
In this section, we present all the omitted details from Section 3 of our paper. We formally introduce the Lovász-Simonovits curve and use it to analyse the performance of the LocBipartDC algorithm for undirected graphs.
The Lovász-Simonovits Curve. Our analysis of the LocBipartDC algorithm is based on the Lovász-Simonovits curve, which has been used extensively in the analysis of local clustering algorithms [4,32]. Lovász and Simonovits [17] originally defined the following function to reason about the mixing rate of Markov chains. For any vector p ∈ R n ≥0 , we order the vertices such that and define the sweep sets of p as S p j = {v 1 , . . . , v j } for 1 ≤ j ≤ n. The Lovász-Simonovits curve, denoted by p[x] for x ∈ [0, vol(V )], is defined by the points p[vol(S p j )] p(S p j ), and is linear between those points for consecutive j. Lovász and Simonovits also show that Proposition 1. For any p ∈ R n ≥0 and any S ⊆ V , it holds that p(S) ≤ p[vol(S)] .
Double Cover Reduction. The following two proofs establish the reduction from almost-bipartite sets to sets with low conductance in the double cover and follow almost directly from the definition of the bipartiteness ratio and conductance.
Proof of Lemma 1. Let S = L 1 ∪ R 2 , and by definition we have that vol G (S) = vol H (S ). On the other hand, it holds that which proves the statement.
Proof of Lemma 2. The statement follows by Lemma 1.
The simplify operator. We now study the σ-operator to establish the properties given in Lemma 3. Recall that the lazy random walk matrix for a graph is defined to be W = 1 2 (I + D −1 A). Proof of Lemma 3. For any u 1 ∈ V H , we have by definition that and similarly we have σ • (c · p)(u 2 ) = c · σ • p(u 2 ). Therefore, the first property holds. Now we prove the second statement. Let u 1 , u 2 ∈ V H be the vertices that correspond to u ∈ V G . We have by definition that where the last inequality holds by the fact that max(0, x + y) ≤ max(0, x) + max(0, y) for any x, y ∈ R. For the same reason, we have that Combining these proves the second property of σ.
Finally, we will prove the third property. By the definition of matrix W , we have that , .
Analysis of ApproximatePagerankDC. The following lemma shows that dcpush maintains that throughout the algorithm, [p 1 , p 2 ] is an approximate Pagerank vector on the double cover with residual [r 1 , r 2 ]. Proof. After the push operation, we have where W is the lazy random walk matrix on the double cover of the input graph. Then we have where we use the fact that pr(α, ·) is linear and that pr(α, s) = αs + (1 − α)pr(α, sW ), which follows from the fact that pr(α, The following lemma shows the correctness and performance guarantee of the ApproximatePagerankDC algorithm. Lemma 9. For a graph G with double cover H and any v ∈ V G , ApproximatePagerankDC(v, α, ) runs in time O( 1 α ) and computes p = apr H (α, χ v 1 , r) such that max u∈V H r(u) deg(u) < and vol(supp(p))) ≤ 1 α . Proof. By Lemma 8, we have that p = apr H (α, χ v 1 , r) throughout the algorithm and so this clearly holds for the output vector. By the stopping condition of the algorithm, it is clear that max u∈V H r(u) deg(u) < . Let T be the total number of push operations performed by ApproximatePagerankDC, and let d j be the degree of the vertex u i used in the jth push. The amount of probability mass on u i at time j is at least d j and so the amount of probability mass that moves from r i to p i at step j is at least α d i . Since r 1 1 + r 2 1 = 1 at the beginning of the algorithm, we have that α T j=1 d j ≤ 1, which implies that Now, note that for every vertex in supp(p), there must have been at least one push operation on that vertex. So, Finally, to bound the running time, we can implement the algorithm by maintaining a queue of vertices satisfying r(u) d(u) ≥ and repeat the push operation on the first item in the queue at every iteration, updating the queue as appropriate. The push operation and queue updates can be performed in time proportional to d(u) and so the running time follows from (4).
Analysis of LocBipartDC. We will make use of the following fact proved by Andersen et al. [4] which shows that the approximate Pagerank vector will have a large probability mass on a set of vertices if they have low conductance.
The following proof generalises this result to show that applying the σ-operator to the approximate Pagerank vector maintains this large probability mass, up to a constant factor.
Proof of Lemma 4. By Lemma 1 and Proposition 2, there is a set S α ⊆ S with vol(S α ) ≥ vol(S)/2 such that it holds for v ∈ S α that Therefore, by the definition of p we have that which proves the statement of the lemma.
For the proof of Lemma 5, we need to carefully analyse the effect of the σ-operator on the approximate Pagerank vector, and in particular notice the effect of the residual vector r.
We now turn our attention to the Lovász-Simonovits curve defined by the simplified approximate Pagerank vector p = σ • apr(α, s, r). We will bound the curve at some point by the conductance of the corresponding sweep set with the following lemma. apr(α, s, r)). It holds for any j ∈ [1, n − 1] that Since vol(S p j ) ± ∂(S p j ) = vol(S p j )(1 ± Φ(S p j )), this tells us that when the conductance of the sweep set S p j is large, the Lovász-Simonovits curve around the point vol(S p j ) is close to a straight line. For the proof of Lemma 10, we will view the undirected graph H instead as a digraph, and each edge {u, v} ∈ E H as a pair of directed edges (u, v) and (v, u). For any edge (u, v) and vector p ∈ R 2n ≥0 , let and for a set of directed edges A, let

Now for any set of vertices
Additionally, for any simple set S ⊂ V H , we define the "simple complement" of the set S by S = {u 2 : u 1 ∈ S} ∪ {u 1 : u 2 ∈ S}.
We will need the following property of the Lovász-Simonovitz curve with regard to sets of edges.
Lemma 11. For any set of edges A, it holds that Proof. For each u ∈ V , let x u = |{(u, v) ∈ A}| be the number of edges in A with the tail at u. Then, we have by definition that the statement follows from equation (2).
We will also make use of the following lemma from [4]. We now have all the pieces we need to prove the behaviour of the Lovász-Simonovits curve described in Lemma 10.
Proof of Lemma 10. By definition, we have that where the first inequality follows by Lemma 5 and the last inequality follows by Lemma 12. Now, recall that p vol(S p j ) = p(S p j ) and notice that vol S p j = vol S p j holds by the definition of S. Hence, using Lemma 11, we have that It remains to show that in(S p j ) ∩ out(S p j ) = vol(S p j ) − ∂(S p j ) , and in(S p j ) ∪ out(S p j ) = vol(S p j ) + ∂(S p j ) .
The first follows by noticing that in(S p j ) ∩ out(S p j ) counts precisely twice the number of edges with both endpoints inside S p j . The second follows since and both the second and third terms on the right hand side are equal to ∂(S p j ) .
To understand the following lemma, notice that since p[0] = 0 and p[vol(H)] = 1, if the curve were simply linear then it would be the case that p[k] = k vol(H) and so the following lemma bounds how far the Lovász-Simonovits curve deviates from this line. In particular, if there is no sweep set with small conductance, then the deviation must be small. Proof. For ease of discussion we write k j = vol(S p j ) and let k j = min(k j , vol(H) − k j ). For convenience we will write We will prove by induction that for all t ≥ 0, For the base case, this equation holds for t = 0 for any φ. Our proof is based on a case distinction: (1) For any integer k ∈ [1, vol(H) − 1], The base case follows since f 0 is concave, and p[k] is linear between integer values. Now for the inductive case, we assume that the claim holds for t and will show that it holds for t + 1. It suffices to show that the following holds for every j ∈ [1, |supp(p)|]: The theorem will follow because this equation holds trivially for j = 0 and j = n and p[k] is linear between k j for j ∈ {0, n} ∪ [1, |supp(p)|].
For any j ∈ [1, |supp(p)|], it holds by Lemma 10 that where the second line uses the fact that r[k j ] ≤ k j and the last line uses the concavity of p[k] and the fact that Φ(S p j ) ≥ φ. By the induction hypothesis, we have that Now, using the Taylor series of √ 1 + φ at φ = 0, we see the following for any x ≥ 0 and φ ∈ [0, 1].
Applying this with x = k j , we have which completes the proof.
The next lemma follows almost directly from Lemma 13 by carefully choosing the value of t.
Proof of Lemma 6. Let H c be a weighted version of the double cover with the weight of every edge equal to some constant c. Let k = vol Hc (S) and k = min(k, vol(H c ) − k). Notice that the behaviour of random walks and the conductance of vertex sets are unchanged by re-weighting the graph by a constant factor. As such, p = σ • apr Hc (α, s, r) and we let φ = min j Φ Hc (S p j ). Hence, by Lemma 13 it holds for any t > 0 that Letting v = vol(H c ) we set t = 8 φ 2 ln 2 √ v/2 δ . Now, assuming that we have We set c such that By the definition of φ, there must be some S p j with the desired property.
Finally, we prove the performance guarantees of Algorithm 1 in the following theorem.
Let p = σ • (apr H (α, χ v , r)) be the simplified approximate Pagerank vector computed in the algorithm, which satisfies that max v∈V H r(v) d(v) ≤ , and let C = L 1 ∪ R 2 be the target set in the double cover. Hence, by Lemma 4 we have that Notice that, since C is simple, we have that vol(C ) vol(V H ) ≤ Since such a S p j is a simple set, by Lemma 1, we know that the sets L = {u ∈ V G : u 1 ∈ S p j } and R = {u ∈ V G : u 2 ∈ S p j } satisfy β((, L) , R ) ≤ β. For the volume guarantee, Lemma 9 gives that vol(supp(p)) ≤ 1 α = γ β .
Since the sweep set procedure in the algorithm is over the support of p, we have that vol(L ∪ R ) ≤ vol(supp(p)) ≤ β −1 γ.
Now, we will analyse the running time of the algorithm. By Lemma 9, computing the approximate Pagerank vector p takes time Since vol(supp(p )) = O 1 α , computing σ • (p ) can also be done in time O β −1 γ . The cost of checking each conductance in the sweep set loop is O(vol(supp(p)) ln(n)) = O β −1 γ ln(n) . This dominates the running time of the algorithm, which completes the proof of the theorem.

B Omitted detail from Section 4
In this section, we present all the omitted details from Section 4 of our paper. We will use the evolving set process to analyse the correctness and performance of the EvoCutDirected algorithm.
The evolving set process. To understand the ESP update process, notice that χ v W χ S i is the probability that a one-step random walk starting at v ends inside S i . Given that the transition kernel of the evolving set process is given by K(S, S ) = P[S i+1 = S |S i = S], the volume-biased ESP is defined by the transition kernel K(S, S ) = vol(S ) vol(S) K(S, S ) We now give some useful facts about the evolving set process which we will use in our analysis of Algorithm 4. The first proposition tells us that an evolving set process running for sufficiently many steps is very likely to have at least one state with low conductance.
If (X 0 , X 1 , . . . , X T ) is a lazy random walk Markov chain with X 0 = x then for any set A ⊆ V H and integer T , let esc(x, T, A) P   T j=0 X j ∈ A   be the probability that the random walk leaves the set A in the first T steps. We will use the following results connecting the escape probability to the conductance of the set A and the volume of the sets in the evolving set process. Then, by Proposition 4 we have that esc(x, T, C) ≤ T φ = 1 100 φ 1/3 . Hence, by Proposition 5, with probability at least 9/10, max t≤T vol(S t \ C) vol(S t ) ≤ 10 · esc(x, T, C) ≤ 1 10 · φ 1/3 Applying the union bound on these two events proves the statement of the lemma.
Now we combine everything together to prove Theorem 2.
Proof of Theorem 2. By Lemma 15, we know that, with probability at least 7/9, the set S computed by the algorithm will satisfy vol(S ∩ C) ≥ 1 − 1 10 φ 1 3 vol(S).
Finally, the running time of the algorithm is dominated by the GenerateSample method, which was shown in [6] to have running time O vol(C)φ − 1 2 ln