Zhi Lu

Jin-Kao Hao
email: jin-kao.hao@univ-angers.fr

Una Benlic

David Lesaint

Iterated Multilevel Simulated Annealing for Large-Scale Graph Conductance Minimization

Keywords: Combinatorial optimization, large-scale optimization, metaheuristics, heuristics, graph theory

Given an undirected connected graph G = (V, E) with vertex set V and edge set E, the minimum conductance graph partitioning problem is to partition V into two disjoint subsets such that the conductance, i.e., the ratio of the number of cut edges to the smallest volume of two partition subsets is minimized. This problem has a number of practical applications in various areas such as community detection, bioinformatics, and computer vision. However, the problem is computationally challenging, especially for large problem instances. This work presents the first iterated multilevel simulated annealing algorithm for large-scale graph conductance minimization. The algorithm features a novel solution-guided coarsening method and an effective solution refinement procedure based on simulated annealing. Computational experiments demonstrate the high performance of the algorithm on 66 very large real-world sparse graphs with up to 23 million vertices. Additional experiments are presented to get insights into the influences of its algorithmic components. The source code of the proposed algorithm is publicly available, which can be used to solve various real world problems.

Introduction

Graph partitioning problems are popular and general models that are frequently used to formulate numerous practical applications in various domains.

Given an undirected graph with a vertex set and an edge set, graph partitioning is to divide the vertex set into two or more disjoint subsets while meeting a defined objective. For example, the popular NP-hard (non-deterministic polynomial-time hardness) 2-way graph partitioning problem is to minimize the number of edges crossing the two partition subsets [START_REF] Garey | Computers and Intractability: A Guide to the Theory of NP-Completeness[END_REF].

The minimum conductance graph partitioning problem (MC-GPP) studied in this work is another typical graph partitioning problem stated as follows. Let G = (V, E) be an undirected connected graph with vertex set V and edge set E. A cut in G is a partition of its vertex set V into two disjoint subsets S and S = V \ S, while the cut-set is the set of edges that have one endpoint in each subset of the partition. By convention, a cut is denoted by s = (S, S) and its cut-set is denoted by cut(s).

Given a cut s = (S, S) from the search space Ω composed of all the possible cuts of a graph G, its conductance Φ(s) is the ratio between the number of cut edges and the smallest volume of the two partition subsets, i. The conductance of a graph G is the minimum conductance over all the cuts of the graph: Φ(G) = min s∈Ω Φ(s). In mathematics and statistical physics, the conductance is also called the Cheeger constant, Cheeger number or isoperimetric number [START_REF] Cheeger | A lower bound for the smallest eigenvalue of the laplacian[END_REF] with a different denominator that depends upon the number of vertices in S and S.

The minimum conductance graph partitioning problem (MC-GPP) is then to determine the conductance of an arbitrary graph G, i.e., find the cut s * in G such that Φ(s * ) ≤ Φ(s) for any s in Ω.

(MC-GPP) s * = arg min s∈Ω Φ(s)

In terms of the computational complexity theory, MC-GPP is known to be an NP-hard problem [START_REF] Šíma | On the NP-completeness of some graph cluster measures[END_REF], and thus computationally challenging. From a practical perspective, MC-GPP has a number of relevant applications in different fields such as clustering [START_REF] Cheng | A divide-and-merge methodology for clustering[END_REF], community detection [START_REF] Fortunato | Community detection in graphs[END_REF], bioinformatics [START_REF] Voevodski | Finding local communities in protein networks[END_REF], computer vision [START_REF] Shi | Normalized cuts and image segmentation[END_REF], and large graph size estimation [START_REF] Lu | Uniform random sampling not recommended for large graph size estimation[END_REF]. As the result, designing effective solution methods for MC-GPP is both challenging and important.

Given the relevance of MC-GPP, considerable efforts have been dedicated to developing various algorithms for solving the problem, which mainly fall into three families: exact, approximation, and heuristic algorithms. Time-efficient exact algorithms were introduced in [START_REF] Hochbaum | Polynomial time algorithms for ratio regions and a variant of normalized cut[END_REF] to solve a variant of the conductance problem and other ratio region problems in the context of image segmentation. Later, a polynomial time algorithm for the Rayleigh ratio minimization problem on discrete variables was presented in [START_REF] Hochbaum | A polynomial time algorithm for rayleigh ratio on discrete variables: Replacing spectral techniques for expander ratio, normalized cut, and cheeger constant[END_REF]. The first (and considered weak) approximation algorithm for MC-GPP was presented in [START_REF] Cheeger | A lower bound for the smallest eigenvalue of the laplacian[END_REF]. Improved approximation algorithms were studied including an O(log(|V |))-approximation algorithm [START_REF] Leighton | Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms[END_REF], and an O( log(|V |))-approximation algorithm [START_REF] Arora | Expander flows, geometric embeddings and graph partitioning[END_REF].

Several algorithms with performance guarantees for conductance minimization were also proposed for large-scale graph clustering in social and information networks. For instance, local algorithms were presented in [START_REF] Spielman | A local clustering algorithm for massive graphs and its application to nearly linear time graph partitioning[END_REF] for clustering massive graphs based on the conductance criterion. Another local algorithm was introduced in [START_REF] Zhu | A local algorithm for finding well-connected clusters[END_REF] that is able to find well-connected clusters for large graphs in terms of the clustering accuracy and the conductance of the output set. The conductance measure was used to characterize the "best" possible community in [START_REF] Leskovec | Community structure in large networks: Natural cluster sizes and the absence of large well-defined clusters[END_REF] where approximation algorithms with performance guarantee were proposed for the related graph partitioning problem over a wide range of size scales. Although these algorithms can theoretically provide provable performance guarantees on the quality of the obtained solutions, they are either designed for specific cases or require large computation time for large graphs due to the intrinsic intractability of MC-GPP.

To handle large problems that cannot be solved by exact methods, heuristic methods provide an interesting alternative approach to produce high-quality (not necessarily optimal) solutions within a reasonable amount of computation time. In particular, a number of generic metaheuristics (see e.g., [START_REF] Boussaïd | A survey on optimization metaheuristics[END_REF]) are available including single-solution based methods (e.g., simulated annealing and tabu search) and population-based methods (e.g., evolutionary algorithms and particle swarm optimization). These methods have been used to tackle various large and computationally complex problems [START_REF]Handbook of Metaheuristics[END_REF]. However, the success of these methods depends strongly on a careful design and dedicated adaptations of the methods to the problem at hand [START_REF] Blum | Metaheuristics in combinatorial optimization: Overview and conceptual comparison[END_REF]. For MC-GPP, several heuristic and metaheuristic algorithms have been proposed, which are reviewed as follows.

A max-flow quotient-cut improvement algorithm (MQI) was introduced in [START_REF] Lang | A flow-based method for improving the expansion or conductance of graph cuts[END_REF] to refine an initial cut of the Metis graph partitioning heuristic [START_REF] Karypis | Metis 5.1.0: Unstructured graphs partitioning and sparse matrix ordering system[END_REF]. This work was extended in [START_REF] Andersen | An algorithm for improving graph partitions[END_REF], which solves a sequence of minimum cut problems to find a larger-than-expected intersection with lower conductance. In [START_REF] Lim | MTP: discovering high quality partitions in real world graphs[END_REF], a minus top-k partition (MTP) method was studied for discovering a global balanced partition with low conductance. In [START_REF] Van Laarhoven | Local network community detection with continuous optimization of conductance and weighted kernel k-means[END_REF], a continuous optimization approach was proposed for conductance minimization in the context of local network community detection. The first metaheuristic algorithms for MC-GPP including simple local search and basic memetic algorithms were studied in [START_REF] Chalupa | Hybrid bridge-based memetic algorithms for finding bottlenecks in complex networks[END_REF], which were used for finding bottlenecks in complex networks. A stagnation-aware breakout tabu search algorithm (SaBTS) was presented in [START_REF] Lu | Stagnation-aware breakout tabu search for the minimum conductance graph partitioning problem[END_REF], which combines a dedicated tabu search procedure to discover high-quality solutions and a self-adaptive perturbation procedure to overcome hard-to-escape local optimum traps. Computational results were reported on real world graphs with up to 500,000 vertices. Recently, a hybrid evolutionary algorithm (MAMC) with a powerful local search and a quality-and-diversity based pool management was introduced in [START_REF] Lu | A hybrid evolutionary algorithm for finding low conductance of large graphs[END_REF], which reported new results on large graphs with up to 23 million vertices. These studies greatly contributed to better solving the given problem. However, two main limitations can be identified in the existing approaches, which motivate the current work. First, these approaches have difficulties in robustly and consistently producing high-quality solutions for large-scale graphs with more than several million vertices. Second, they may require a substantial amount of computation time to reach satisfactory solutions.

On the other hand, the multilevel approach [START_REF] Walshaw | Multilevel refinement for combinatorial optimisation problems[END_REF] is known to be a powerful framework for large graph partitioning in various domains (e.g., complex network analysis [START_REF] Valejo | A critical survey of the multilevel method in complex networks[END_REF]). However, this approach has not been investigated for solving MC-GPP. This work aims to fill in the gap by presenting an effective multilevel algorithm for MC-GPP that is able to produce high-quality solutions within a reasonable time frame for large-scale sparse graphs arising from real world applications. The contributions can be summarized as follows.

First, an iterated multilevel simulated annealing algorithm (IMSA) is introduced for MC-GPP. The algorithm consists of a novel solution-guided coarsening method and a powerful local refinement procedure to effectively sample the search space of the problem.

Second, extensive computational assessments are presented on three sets of 66 very large real-world benchmark instances (including 56 graphs from the 10th DIMACS Implementation Challenge and 10 graphs from the Network Data Repository online, with up to 23 million vertices). The computational experiments indicate a high competitiveness of the proposed IMSA algorithm compared to the existing state-of-the-art algorithms.

Third, the code of the IMSA algorithm will be publicly available, which can help researchers and practitioners to better solve various practical problems that can be formulated as MC-GPP.

The remainder of the paper is structured as follows. Section 2 presents the IMSA algorithm. Section 3 shows the computational studies and comparisons between the proposed IMSA algorithm and state-of-the-art algorithms. Section 4 provides analyses of the key algorithmic components. Section 5 presents concluding remarks and perspectives for future research.

Iterated multilevel simulated annealing

This section presents the proposed iterated multilevel simulated annealing algorithm for MC-GPP. After illustrating its general algorithmic framework, the key algorithmic components are described.

General framework

The multilevel approach is a general framework that has shown to be very successful in tackling the classic graph partitioning problem. Generally, this approach consists of three basic phases (coarsening, initial partitioning, and uncoarsening) [START_REF] Hendrickson | A multi-level algorithm for partitioning graphs[END_REF]. During the coarsening phase, the given graph is successively reduced to obtain a series of coarsened graphs with a decreasing number of vertices. An initial partition is then generated for the coarsest graph. Finally, during the uncoarsening phase, the coarsened graphs are successively unfolded in the reverse order of the coarsening phase. For each uncoarsened graph, the partition of the underlying coarsened graph is projected back to the uncoarsened graph and then improved by a refinement procedure. This process stops when the input graph is recovered and its partition is refined.

In [START_REF] Walshaw | Multilevel refinement for combinatorial optimisation problems[END_REF], Walshaw introduced iterated multilevel partitioning (analogous to the use of V-cycles in multigrid methods [START_REF] Trottenberg | Multigrid[END_REF]) where the coarsening-uncoarsening process is iterated and the partition of the current iteration is used for the whole coarsening phase of the next iteration.

The proposed IMSA algorithm for MC-GPP is based on the ideas described above and includes two original features: 1) a solution-guided coarsening method, and 2) a powerful refinement procedure which is applied during both the coarsening and the uncoarsening phase. Fig. 1 illustrates the iterated multilevel framework adopted by the proposed IMSA algorithm, while the entire algorithmic framework is presented in Algorithm 1. Informally, IMSA performs a series of V-cycles, where each V-cycle is composed of a coarsening phase and an uncoarsening phase, mixed with local refinement for each intermediate (coarsened and uncoarsened) graph.

It is worth noting that IMSA requires a seeding partition s 0 of the input graph to initiate its first iteration (the first V-cycle). Generally, the seeding partition can be provided by any means. For instance, for the experimental studies reported in Section 3, the (fast) MQI algorithm [START_REF] Lang | A flow-based method for improving the expansion or conductance of graph cuts[END_REF] was adopted. For each subsequent iteration, the best partition found during the previous Vcycle then serves as the new seeding partition. The whole process terminates when a given stopping condition (e.g., cutoff time limit, maximum number of V-cycles) is reached and the global best partition found during the search is returned.

Solution-guided coarsening procedure

Given a graph G = (V, E) (renamed as G 0 = (V 0 , E 0 )) and the seeding partition s 0 , the solution-guided coarsening phase progressively transforms G 0 into smaller intermediate graphs

G i = (V i , E i ) such that |V i | > |V i+1 | (i = 0, . . . , m -1)
, until the last coarsened graph G m becomes sufficiently small (i.e., the number of vertices in V m is below a given threshold ct). During the coarsening process, all intermediate graphs are recorded for the purpose of uncoarsening.

Generally, to generate a coarsened graph G i+1 from G i , the coarsening process performs two consecutive steps: an edge matching step and an edge contraction step. For each V-cycle, the initial graph G 0 = (V 0 , E 0 ) is supposed to have a "unit weight" for all the vertices and edges.

The edge matching step aims to find an independent set of edges M ⊂ E i such that the endpoints of any two edges in M are not adjacent. For this purpose, IMSA adopts the fast Heavy-Edge Matching (HEM) heuristic [START_REF] Karypis | A fast and high quality multilevel scheme for partitioning irregular graphs[END_REF] with a time Algorithm 1 Iterated multilevel simulated annealing (IMSA) for MC-GPP.

Require: Graph G = (V, E), seeding partition s 0 , coarsening threshold ct. Ensure: The best partition s * found during the search. ). HEM considers vertices in a random order, and matches each unmatched vertex v with its unmatched neighbor vertex u such that 1) v and u are in the same subset of the current partition s i ; and 2) edge {v, u} has the maximum weight over all edges incident to v (ties are broken randomly). In this work, edge matching is guided by the current partition s i of G i in the sense that the cut edges in the cut-set cut(s i ) are ignored and only vertices of the same partition subset are considered for matching.

The edge contraction step collapses the endpoints of each edge {v a , v b } in M to form a new vertex v a + v b in the coarsened graph G i+1 , while vertices which are not endpoints of any edge of M are simply copied over to G i+1 . For the new vertex v a + v b ∈ V i+1 , its weight is set to be the sum of the weights of v a and v b . The edge between v a and v b is removed, and the edges incident to v a and v b are merged to form a new edge in E i+1 with a weight that is set to be the sum of the weights of the merged edges.

Once the coarsened graph G i+1 is created, the partition s i of G i is projected onto G i+1 , followed by improvement with the local refinement procedure. The improved partition is then used to create the next coarsened graph. edges M = ({a, b}, {c, d}, {e, f }) guided by s 0 . Then for each edge in M , say {a, b}, its endpoints are merged to form a new vertex a + b in G 1 with vertex weight w(a + b) = w(a) + w(b). The edge {a, b} is removed, while the edges {a, h} and {b, h} that are incident to both a and b are merged to form a new edge {a+b, h} in G 1 with edge weight w({a+b, h}) = w({a, h})+w({b, h}) = 2. The same operations are performed to merge vertices c and d, e and f . After merging all the vertices involved in the edges of M , the remaining vertices h and g which are not incident to any edge of M are simply copied to G 1 , completing the new coarsened graph G 1 .

Uncoarsening procedure

In principle, the uncoarsening phase performs the opposite operations of the coarsening phase and successively recovers the intermediate graphs G i (i = m, m-1, . . . , 0) in the reverse order of their creations. To recover G i from G i+1 , each merged vertex of G i+1 is unfolded to obtain the original vertices and the associated edges of G i . For an illustrative example, the same process applies as presented in Fig. 2 but with the reversed direction of each transition arrow. In practice, each corresponding intermediate graph recorded during coarsening is just restored.

For each recovered graph G i , the partition of G i+1 is projected back to G i and is further improved by the local refinement procedure. The uncoarsening process continues until the initial graph G 0 is recovered. At this point, IMSA terminates the current V-cycle and is ready to start the next V-cycle.

Generally, the partition quality is progressively improved throughout the uncoarsening process. Precisely, the partition quality of G i is usually better than that of G i+1 since there are more degrees of freedom for the local refinement procedure of an uncoarsened graph.

Local refinement with simulated annealing

For local refinement, IMSA mainly uses a dedicated simulated annealing procedure, which is complemented by an existing tabu search procedure.

Simulated annealing refinement procedure

Multilevel algorithms typically use pure descent algorithms for solution refinement at each level. This ensures fast convergence towards a local optimum that may be of mediocre quality compared to a global optimum. To reinforce the search capacity of the IMSA algorithm, the powerful simulated annealing method [START_REF] Kirkpatrick | Optimization by simulated annealing[END_REF] is used, which has shown its effectiveness on the popular 2-way graph partitioning problem [START_REF] Johnson | Optimization by simulated annealing: An experimental evaluation; part I, graph partitioning[END_REF]. Moreover, a solution sampling strategy specially designed for MC-GPP (Section 2.4.2) is adopted to further ensure an effective examination of candidate solutions. To avoid search stagnation in a local optimum, the SA based refinement is complemented with a tabu search procedure (see Section 2.5).

The main scheme of the SA procedure is presented in Algorithm 2. Specifically, SA performs a number of search rounds (lines 3-21) with different temperature values to improve the current solution s (i.e., a cut (S, S)). At the start of each search round, the move counter mv is initialized to 0 (line 4). The procedure enters the 'for' loop to carry out saIter iterations (saIter is a parameter) with the current temperature T (initially set to T 0 ). At each iteration, SA randomly samples a neighbor solution s of s from a set of constrained candidates (lines [START_REF] Benlic | A multilevel memetic approach for improving graph kpartitions[END_REF][START_REF] Blum | Metaheuristics in combinatorial optimization: Overview and conceptual comparison[END_REF][START_REF] Boussaïd | A survey on optimization metaheuristics[END_REF][START_REF] Chalupa | Hybrid bridge-based memetic algorithms for finding bottlenecks in complex networks[END_REF][START_REF] Cheeger | A lower bound for the smallest eigenvalue of the laplacian[END_REF][START_REF] Cheng | A divide-and-merge methodology for clustering[END_REF][START_REF] Fortunato | Community detection in graphs[END_REF][START_REF] Garey | Computers and Intractability: A Guide to the Theory of NP-Completeness[END_REF][START_REF]Handbook of Metaheuristics[END_REF][START_REF] Glaria | Compact structure for sparse undirected graphs based on a clique graph partition[END_REF][START_REF] Hamby | A review of techniques for parameter sensitivity analysis of environmental models[END_REF][START_REF] Hauck | An evaluation of bipartitioning techniques[END_REF][START_REF] Hendrickson | A multi-level algorithm for partitioning graphs[END_REF][START_REF] Hochbaum | Polynomial time algorithms for ratio regions and a variant of normalized cut[END_REF][START_REF] Hochbaum | A polynomial time algorithm for rayleigh ratio on discrete variables: Replacing spectral techniques for expander ratio, normalized cut, and cheeger constant[END_REF]. Given a set of critical vertices CV (s) (see Section 2.4.2), this is achieved by displacing a random vertex v ∈ CV (s) from its current subset to the opposite subset (lines 6-7, where s ← s ⊕ Relocate(v) denotes this move operation). The new solution s then replaces the current solution s according to the following probability (lines 8-15),

P r{s ← s } =      1 , if δ < 0 e -δ/T , if δ ≥ 0 (3)
where δ = Φ(s ) -Φ(s) is the conductance variation (also called the move gain) of transitioning from s to s .

Algorithm 2 Simulated annealing based local refinement.

Require: A better neighbor solution s in terms of the conductance (δ < 0) is always accepted as the new current solution s. Otherwise (δ ≥ 0), the transition from s to s takes place with probability e -δ/T . After each solution transition, the move counter mv is incremented. The best solution s best is updated each time a better solution is found (lines [START_REF] Hauck | An evaluation of bipartitioning techniques[END_REF][START_REF] Hendrickson | A multi-level algorithm for partitioning graphs[END_REF][START_REF] Hochbaum | Polynomial time algorithms for ratio regions and a variant of normalized cut[END_REF]. Once the number of sampled solutions reaches saIter, the temperature T is cooled down by a constant factor θ ∈ [0, 1] (θ is a parameter, line 20), and SA proceeds to the next search round with this lowered new temperature. The termination criterion (the frozen state) of SA is met when the acceptance rate becomes smaller than a threshold ar (ar is a parameter) for 5 consecutive search rounds, where the acceptance rate is defined as mv/saIter (line 21). Upon the termination of the SA procedure, the procedure returns the best recorded solution s best (line 22).

Graph G = (V, E), input
One critical issue for the SA procedure concerns the initial temperature T 0 . While a high T 0 leads to acceptance of many deteriorating uphill moves, a low initial temperature will have the same impact as a pure descent procedure resulting in the search to easily become trapped in a local optimum. To identify a suitable initial temperature, a simple binary search is used to provide a tradeoff between these two extremes. Starting from an initial temperature range T ∈ [1.0e-20, 1.0], T 0 is initialized with the median value from this range, i.e., T 0 = (1.0 + 1.0e-20)/2. If the last round of the search using the current value of T 0 resulted in an acceptance rate of 50%, the value of T 0 is left unchanged. Otherwise, the value for T 0 used in next round of the search is set to be the median value of the lower or the upper temperature range depending on whether the acceptance rate is higher or lower than 50%. This process continues until a suitable initial temperature T 0 is found for a given problem instance. The other parameters (saIter, θ, and ar) of SA are investigated in Section 4.4.

Solution sampling with critical vertices

To generate a new candidate solution s from the current solution s, the popular Relocate operator is applied that displaces a vertex from its current set to the opposite set. To avoid the generation of non-promising candidate solutions, the set of critical vertices are identified with respect to the current solution s. Specifically, let s = (S, S) be the current solution. Vertex v ∈ V is called a critical vertex if v is the endpoint of an edge in the cut-set cut(s) [START_REF] Lu | A hybrid evolutionary algorithm for finding low conductance of large graphs[END_REF]. Let CV (s) denote the set of all the critical vertices in the cut-set cut(s). Then, Relocate only operates on the vertices of CV (s). By constraining the Relocate operation to the critical vertices, the algorithm avoids sampling many non-promising candidate solutions, as demonstrated in [START_REF] Lu | Stagnation-aware breakout tabu search for the minimum conductance graph partitioning problem[END_REF].

To ensure a fast computation of the conductance variation of a neighbor solution generated by Relocate, a streamlined incremental evaluation technique [START_REF] Lu | Stagnation-aware breakout tabu search for the minimum conductance graph partitioning problem[END_REF]

Additional solution refinement with tabu search

To further reinforce the solution refinement and go beyond the local optimum attained by the SA procedure, the constrained neighborhood tabu search (CNTS) procedure of [START_REF] Lu | Stagnation-aware breakout tabu search for the minimum conductance graph partitioning problem[END_REF] is additionally applied. CNTS relies on the same constrained neighborhood defined by the critical vertices and employs a dynamic tabu list to explore additional local optima. CNTS requires two parameters: the maximum number of consecutive non-improving iterations of tabu search D, and the tabu tenure management factor α. Section 4.4 explains the procedure used to tune these parameters and analyzes their sensitivity. More details about CNTS can be found in [START_REF] Lu | Stagnation-aware breakout tabu search for the minimum conductance graph partitioning problem[END_REF]. The use of CNTS is based on the preliminary observation that it can provide performance gains especially for the class of relatively small-sized instances with vertices less than one million (such as 'ok2010', 'va2010', 'nc2010', etc. See Appendix A, Tables A.2-A.4). Generally, the CNTS component can be safely disabled for large graphs without impacting the performance of the IMSA algorithm. In terms of solution refinement, CNTS is more focused on search intensification, as opposed to the more stochastic and diversified SA procedure. In practice, CNTS plays a complementary and secondary role by performing a much shorter search (determined by the parameter D) than SA during a round of IMSA.

Complexity of the proposed algorithm

The time complexity of the local refinement procedure is first considered. The SA procedure (Section 2. In practice, as long as the graph has a low or very low density, the space requirement is approximately linear in |V |. On the contrary, for dense and very dense (near-complete) graphs, the space requirement becomes quadratic in |V |.

Computational studies

This section is dedicated to a computational assessment of the proposed IMSA algorithm based on various benchmark instances.

Benchmark instances

The assessment was based on 66 very large benchmark instances with 54,870 to 23,947,347 vertices. The first 56 instances are very large graphs from The 10th DIMACS Implementation Challenge Benchmark1 , which were introduced for graph partitioning and graph clustering [START_REF] Bader | Graph partitioning and graph clustering[END_REF]. The remaining 10 instances are large real-world network graphs [START_REF] Rossi | The network data repository with interactive graph analytics and visualization[END_REF] from The Network Data Repository online2 . These 66 instances are divided into three sets: Small set (24 instances, |V | < 500, 000), Medium set (25 instances, |V | ∈ [500, 000, 5, 000, 000], and Large set (17 instances, |V | > 5, 000, 000). Among these 66 instances, 29 DI-MACS graphs and 10 massive network graphs have previously been used for experimental evaluations in [START_REF] Lu | A hybrid evolutionary algorithm for finding low conductance of large graphs[END_REF]. Additional 27 large-scale DIMACS benchmark graphs (with 114,599 to 21,198,119 vertices) were considered to better assess the scalability of the multilevel algorithm.

Experimental setting and reference algorithms

The proposed IMSA algorithm was implemented in C++3 and compiled using the g++ compiler with the "-O3" option. All the experiments were conducted on a computer with an AMD Opteron 4184 processor (2.8GHz) and 32GB RAM under Linux operating system. This computer was previously used to perform experimental evaluations reported in [START_REF] Lu | A hybrid evolutionary algorithm for finding low conductance of large graphs[END_REF]. IMSA being a sequential Frozen state parameter of SA search 5%

D §2.5
Maximum number of consecutive non-improving iterations of tabu search 10,000

α §2.5
Tabu tenure management factor of tabu search 80

algorithm, it was run on a single core of the AMD Opteron processor, as in [START_REF] Lu | A hybrid evolutionary algorithm for finding low conductance of large graphs[END_REF].

Table 1 shows the setting of the IMSA parameters, which can be considered as the default setting of the algorithm. The procedure to tune these parameters is explained in Section 4.4. For meaningful assessments, this default setting was consistently used throughout all the experiments presented in this work.

As shown in Section 3.3, IMSA achieves highly competitive results with this unique setting. Generally, the parameters can be fined-tuned to obtain improved results. Such a practice is useful when one seeks the best possible solution for a given graph.

To evaluate the performance of IMSA, comparisons are performed against three best performing MC-GPP algorithms from the literature: the two most recent metaheuristic algorithms (i.e., the hybrid evolutionary algorithm MAMC [START_REF] Lu | A hybrid evolutionary algorithm for finding low conductance of large graphs[END_REF] and the breakout local search algorithm SaBTS [START_REF] Lu | Stagnation-aware breakout tabu search for the minimum conductance graph partitioning problem[END_REF]), as well as the popular and powerful max-flow algorithm MQI [START_REF] Lang | A flow-based method for improving the expansion or conductance of graph cuts[END_REF]. To ensure a fair comparison, all the compared algorithms were run on the same computing platform mentioned above with their default parameters setting. Each algorithm was independently executed 20 times per instance with a cutoff time of 60 minutes per run. Exactly like SaBTS and MAMC, each run of IMSA was initialized with a seeding solution provided by the MQI algorithm.

Out of the 66 benchmark instances tested in this work, the results for 39 instances (29 DIMACS graphs and the 10 massive network graphs) for the three reference algorithms are available in [START_REF] Lu | A hybrid evolutionary algorithm for finding low conductance of large graphs[END_REF]. Since these results were obtained following the same experimental protocol as in the current work, they are directly used for the comparative studies. The compared algorithms were only ran on the 27 remaining instances.

Table 2

Summary results reported by the IMSA algorithm and the three reference algorithms (MAMC [START_REF] Lu | A hybrid evolutionary algorithm for finding low conductance of large graphs[END_REF], SaBTS [START_REF] Lu | Stagnation-aware breakout tabu search for the minimum conductance graph partitioning problem[END_REF], and MQI [START_REF] Lang | A flow-based method for improving the expansion or conductance of graph cuts[END_REF]) on the three sets of 66 benchmark instances.

Computational results and comparisons with state-of-the-art algorithms

This section presents the computational results of the proposed IMSA algorithm, together with the results of the three reference algorithms (MAMC, SaBTS, and MQI) on the three sets of 66 benchmark instances.

Table 2 summarizes the overall comparison while the detailed results are listed in Appendix A (Tables A.2-A.4). Additionally, a global comparison is provided using the geometric mean metric [START_REF] Hauck | An evaluation of bipartitioning techniques[END_REF] in Table 3 (the smaller the better). Section 4.1 shows a time-to-target analysis to investigate the computational efficiency of the compared algorithms.

In Table 2, column 1 shows the benchmark sets with the number of instances Table 3 The geometric means of the best and the average conductance values (G best and G avg ) reported by the IMSA algorithm, and the three reference algorithms (MAMC [START_REF] Lu | A hybrid evolutionary algorithm for finding low conductance of large graphs[END_REF], SaBTS [START_REF] Lu | Stagnation-aware breakout tabu search for the minimum conductance graph partitioning problem[END_REF], and MQI [START_REF] Lang | A flow-based method for improving the expansion or conductance of graph cuts[END_REF]) on the three sets of 66 instances. show the number of instances on which IMSA reached a better (#Wins), worse (#Losses), or equal results (#Ties) in terms of each quality indicator. Furthermore, the last column provides the p-value of the Wilcoxon signed-rank test with a confidence level of 99% to assess whether there exists a statistically significant difference between IMSA and each reference algorithm in terms of the best and the average performances.

Table 3 shows the geometric means of each algorithm using the best and the average conductance values for the three sets of 66 instances (G best and G avg ).

The first two columns show the algorithms and the quality indicators (G best and G avg ). Columns 3-5 present the G best (or G avg ) results for each benchmark set, while the last column reports the overall G best (or G avg ) results for all the 66 instances. The best values of G best (or G avg ) across all the algorithms (the smaller the better) are highlighted in boldface.

From Tables 2, 3 and Tables A.2-A.4, the following observations can be made.

1) IMSA competes very favorably with the best existing MC-GPP algorithms in terms of solution quality, by reaching better results for more than 63% cases compared to all the reference algorithms considered jointly. Remarkably, even IMSA's average results are much better than the best results of the reference algorithms in most cases. The dominance of IMSA over the reference algorithms is better shown on medium and large instances, by reporting the best results for all but one or two instances in terms of Φ best and Φ avg . The small geometric means of IMSA further confirm its superiority over the reference algorithms.

2) IMSA is computational effective compared to the reference algorithms. Thanks to its multilevel strategy, IMSA requires similar or shorter time to find equal or better solutions for a number of medium and large graphs.

The time-to-target analysis of Section 4.1 provides more evidences. 3) Relating the results of Tables A.2-A.4 and the main features of the tested graphs shown in Table A.1, it can be concluded that IMSA is particularly suitable for massive and sparse graphs, while its performance decreases on dense graphs. This behavior is consistent with the general multilevel optimization methods for graph partitioning.

This comparative study shows that the IMSA algorithm is a valuable tool for partitioning large and sparse graphs in complement with existing methods. To understand its behavior and functioning. Section 4 shows experiments to shed light on the contributions of the key algorithmic components.

Analysis

This section presents experiments to get insights into the influences of the components of the IMSA algorithm: iterated multilevel framework, simulated annealing local refinement, and parameters.

A time-to-target analysis of the compared algorithms

To investigate the computational efficiency of the compared algorithms: IMSA, MAMC [START_REF] Lu | A hybrid evolutionary algorithm for finding low conductance of large graphs[END_REF], SaBTS [START_REF] Lu | Stagnation-aware breakout tabu search for the minimum conductance graph partitioning problem[END_REF], and MQI [START_REF] Lang | A flow-based method for improving the expansion or conductance of graph cuts[END_REF], a time-to-target (TTT) analysis [START_REF] Aiex | TTT plots: a perl program to create time-to-target plots[END_REF] is performed. This study uses visual TTT plots to illustrate the running time distributions of the compared algorithms. Specifically, the Y-axis of the TTT plots displays the probability that an algorithm will find a solution that is at least as good as a given target value within a given run time, shown on the X-axis. The TTT plots are produced as follows. Each compared algorithm is independently run E x times on each instance. For each of the E x runs, the run time to reach a given target objective value is recorded. For each instance, the run times are then sorted in an ascending order. The i-th sorted run time t i is associated with a probability p i = i/E x , and plotted as point (t i , p i ), for i = 1, . . . , E x . This TTT experiment was based on 4 representative instances: To make sure that the compared algorithms are able to reach the target objective value in each run, the target value was set to be 1% larger than the best objective value found by MQI. The results of this experiment are shown in Fig. 3. Fig. 3 clearly indicates that the proposed IMSA algorithm is always faster in attaining the given target value than the reference algorithms. The probability for IMSA to reach the target objective value within the first 100 to 200 seconds is around 90%, while MAMC, SaBTS, and MQI require much more times to attain the same result (at least 2500 seconds for the two large NLR and delaunay n24 graphs). One notices from Tables A.2-A.4 that MAMC and SaBTS show a shorter computation time for a number of instances, but they report typically worse results (especially on the medium and the large instances) than the IMSA algorithm. This indicates that IMSA can take full advantage of the allotted time budget to find solutions of better quality and avoid premature convergence. This is particularly true for large graphs. This experiment demonstrates that the IMSA algorithm is much more time efficient than the reference algorithms.

Usefulness of the iterated multilevel framework

This section assesses the usefulness of the iterated multilevel framework. For this purpose, an IMSA variant called (SA+TS) restart was created where the multilevel component was removed while keeping only the refinement procedure. To ensure a fair comparison, (SA+TS) restart was performed in a multistart way, until the cutoff time t max (60 minutes) was reached. This experiment was conducted on 20 representative instances of a reasonable size and difficulty: preferentialAttachment, smallworld, delaunay n16, delaunay n17, delaunay n18, delaunay n19, ga2010, oh2010, tx2010, wing, 144, ecology2, ecology1, thermal2, kkt power, NACA0015, M6, AS365, luxembourg, belgium. Each algorithm was independently run 20 times per instance with a cutoff time of 60 minutes per run. As a supplement, the p-values were also computed from the Wilcoxon signed-rank test in terms of the best and the average results. Fig. 4 shows the best/average conductance gap between the two algorithms on these instances. The X-axis indicates the instance label (numbered from 1 to 20), while the Y-axis shows the best/average conductance gap in percentage, calculated as (Φ A -Φ IMSA )/Φ IMSA × 100%, where Φ A and Φ IMSA are the best/average conductance values of (SA+TS) restart and IMSA, respectively.

As observed in Fig. 4, IMSA clearly dominates (SA+TS) restart in terms of the best (p-value = 1.32e-04) and the average (p-value = 1.03e-04) conductance values for the 20 instances. This experiment confirms the usefulness of the iterated multilevel framework, which positively contributes to the high performance of the algorithm.

Benefit of the SA-based local refinement

To evaluate the benefit of the SA local refinement procedure to the performance of the IMSA algorithm, an IMSA variant (denoted by IMSA descent ) was created where the SA procedure was replaced by a pure descent procedure using the best-improvement strategy. This experiment relies on the same 20 instances used in Section 4.2 and reports the same information. Fig. 5 plots the best/average conductance gap between the two algorithms on these instances. The X-axis indicates the instance label, while the Y-axis shows the best/average conductance gap in percentage. Fig. 5 shows that IMSA descent reports significantly worse results in terms of both the best (p-value = 1.32e-04) and the average (p-value = 8.86e-05) conductance values for all the instances. This indicates that the SA procedure is the key element that ensures the high performance of IMSA and disabling it greatly deteriorates the performance.

Analysis of the parameters

The proposed IMSA algorithm requires six parameters: ct, saIter, θ, ar, D, and α. ct denotes the coarsening threshold in the solution-guided coarsening phase. saIter, θ, and ar are the three parameters related to the SA local refinement, where saIter is the maximum number of iterations per temperature, θ is the cooling ratio, and ar is the frozen state parameter. D and α are the maximum number of consecutive non-improving iterations of tabu search and the tabu tenure management factor, respectively. To study the effect of these parameters on the performance of IMSA and to determine the most setting for these parameters, a one-at-a-time sensitivity analysis [START_REF] Hamby | A review of techniques for parameter sensitivity analysis of environmental models[END_REF] was performed as follows. For each parameter, a range of possible values were tested, while fixing the other parameters to their default values from Table 1. Specifically, the following values were used: ct ∈ [20000, 30000, 40000, 50000, 60000], saIter ∈ [50000, 100000, 150000, 200000, 250000], θ ∈ [0.90, 0.92, 0.94, 0.96, 0.98], ar ∈ [1%, 3%, 5%, 7%, 9%], D ∈ [5000, 10000, 15000, 20000, 25000], and α ∈ [START_REF] Walshaw | Multilevel refinement for combinatorial optimisation problems[END_REF]60,80,100,120]. This experiment was conducted on 9 representative instances from the set of instances used in Sections 4.2 and 4.3, and based on 20 independent runs per parameter value with a cutoff time of 60 minutes per run. Fig. 6 shows the average values of Φ best and Φ avg obtained for the 9 instances, where the X-axis indicates the values of each parameter and the Y-axis shows the best/average conductance values over the 9 representative instances: preferentialAttachment, smallworld, delaunay n18, delaunay n19, ga2010, oh2010, wing, 144, thermal2. Fig. 6 shows the impact of each parameter on the performance of IMSA. Specifically, for the parameter ct, ct = 60000 yields the best results for both Φ best and Φ avg . The default value of ct was set to 60000 in this study. For saIter, the value of 200000 is the best choice while a larger or a smaller value weakens the performance of IMSA. For the parameter θ, IMSA obtains the best performance with the value of 0.98 while smaller values decrease its performance. Furthermore, ar = 5% appears to be the best choice for IMSA. For the parameters D and α, the value 10000 and 80 were adopted respectively as their default values according to Fig. 6. The default values of all the parameters are summarized in Table 1.

Conclusion and future work

The iterated multilevel simulated annealing algorithm presented in this work is the first multilevel algorithm for the challenging NP-hard minimum conductance graph partitioning problem. Based on the general (iterated) multilevel framework, IMSA integrates a novel solution-guided coarsening method to construct a hierarchy of reduced graphs and a powerful simulated annealing local refinement procedure that makes full use of a constrained neighborhood to rapidly and effectively improve the quality of sampled solutions.

The performance of IMSA was assessed on three sets of 66 benchmark instances from the literature, including 56 graphs from the 10th DIMACS Implementation Challenge and 10 graphs from the Network Data Repository online, with up to 23 million vertices. Computational results demonstrated the competitiveness of the algorithm in finding high-quality partitions for largescale sparse graphs. This work proves for the first time the value of the general multilevel approach for conductance graph partitioning.

From the application perspective, MC-GPP is a general and powerful graph model able to formulate a variety of real problems related to community detection, clustering, bioinformatics, computer vision, and large graph size estimation. Consequently, researchers and practitioners working on these real world problems can benefit from the proposed approach to find improved solutions.

The availability of the source code of the algorithm will further facilitate such applications.

For future research, several directions could be followed. First, parallel computations are known to be quite useful for large graph partitioning (e.g., parallel graph partitioning for complex networks [START_REF] Meyerhenke | Parallel graph partitioning for complex networks[END_REF], distributed evolutionary partitioning [START_REF] Zheng | Towards a distributed local-search approach for partitioning large-scale social networks[END_REF] and distributed local search for partitioning large social networks [START_REF] Zheng | Towards a distributed local-search approach for partitioning large-scale social networks[END_REF]). Parallel algorithms were also integrated in popular partition packages such as ParMETIS (http://glaros.dtc.umn.edu/gkhome/views/ metis) and KaHIP (https://kahip.github.io/). It would be highly relevant to create parallel versions of the IMSA algorithm to further increase its power. Second, population-based evolutionary algorithms have been successfully employed for solution refinement under the multilevel framework [START_REF] Benlic | A multilevel memetic approach for improving graph kpartitions[END_REF]. It would be interesting to study this approach for conductance partition. Third, the current IMSA implementation is more suitable for partitioning large sparse graphs than for dense graphs. It would be useful to investigate additional strategies to be able to handle both types of graphs. In particular, other graph representations using compact structure [START_REF] Glaria | Compact structure for sparse undirected graphs based on a clique graph partition[END_REF] may be considered to reduce the space complexity of the algorithm. Fourth, in addition to the studied memetic and local search methods in the literature, it is worthy investigating other metaheuristic-based algorithms to better handle various types of graphs and further enrich the MC-GPP toolkit. Finally, given the scarcity of exact approaches to MC-GPP in the existing literature, there is clearly a lot room for research in this direction. Table A.2: Computational results on the Small set of 24 benchmark instances obtained by the IMSA algorithm and the three reference algorithms (MAMC [START_REF] Lu | A hybrid evolutionary algorithm for finding low conductance of large graphs[END_REF], SaBTS [START_REF] Lu | Stagnation-aware breakout tabu search for the minimum conductance graph partitioning problem[END_REF], and MQI [START_REF] Lang | A flow-based method for improving the expansion or conductance of graph cuts[END_REF]).

IMSA MAMC [START_REF] Lu | A hybrid evolutionary algorithm for finding low conductance of large graphs[END_REF] SaBTS [START_REF] Lu | Stagnation-aware breakout tabu search for the minimum conductance graph partitioning problem[END_REF] MQI [START_REF] Lang | A flow-based method for improving the expansion or conductance of graph cuts[END_REF] Instance [START_REF] Lu | A hybrid evolutionary algorithm for finding low conductance of large graphs[END_REF], SaBTS [START_REF] Lu | Stagnation-aware breakout tabu search for the minimum conductance graph partitioning problem[END_REF], and MQI [START_REF] Lang | A flow-based method for improving the expansion or conductance of graph cuts[END_REF]).

IMSA MAMC [START_REF] Lu | A hybrid evolutionary algorithm for finding low conductance of large graphs[END_REF] SaBTS [START_REF] Lu | Stagnation-aware breakout tabu search for the minimum conductance graph partitioning problem[END_REF] MQI [START_REF] Lang | A flow-based method for improving the expansion or conductance of graph cuts[END_REF] Instance Table A.4: Computational results on the Large set of 17 benchmark instances obtained by the IMSA algorithm and the three reference algorithms (MAMC [START_REF] Lu | A hybrid evolutionary algorithm for finding low conductance of large graphs[END_REF], SaBTS [START_REF] Lu | Stagnation-aware breakout tabu search for the minimum conductance graph partitioning problem[END_REF], and MQI [START_REF] Lang | A flow-based method for improving the expansion or conductance of graph cuts[END_REF]).

IMSA MAMC [START_REF] Lu | A hybrid evolutionary algorithm for finding low conductance of large graphs[END_REF] SaBTS [START_REF] Lu | Stagnation-aware breakout tabu search for the minimum conductance graph partitioning problem[END_REF] MQI [START_REF] Lang | A flow-based method for improving the expansion or conductance of graph cuts[END_REF] Instance

  e., Φ(s) = |cut(s)| min{vol(S), vol(S)} (1) where vol(S) = v∈S deg(v) and vol(S) = v∈S deg(v) are the volume of S and S, respectively, and deg(v) is the number of vertices incident to v in G.

Fig. 1 .

 1 Fig. 1. An illustration of the iterated multilevel framework for the proposed algorithm.

Fig. 2 Fig. 2 .

 22 Fig.2illustrates how the first coarsened graph is created from an initial graph G 0 with 8 vertices (unit weight for both vertices and edges) and the partition s 0 = ({a, b, h}, {c, d, e, f, g}) (indicated by the red dashed line). The edge matching step first uses the HEM heuristic to identify the set of independent

  is adopted. Let s = {S, S) be the current solution, s = {S , S } be the neighbor solution after relocating a vertex v of s from S to S. The conductance of s can be evaluated in O(1) time by simply updating |cut(s )|, vol(S ), vol(S ) by |cut(s )| = |cut(s)| + deg S (v) -deg S (v), vol(S ) = vol(S) -deg(v), and vol(S ) = vol(S) + deg(v), where deg S (v) (resp. deg S (v)) is the number of vertices adjacent to v in S (resp. in S). Moreover, for each vertex w adjacent to v, deg S (w) and deg S (w) can be updated in O(1) time by deg S (w) = deg S (w) -1 and deg S (w) = deg S (w) + 1.

  4) performs saIter iterations. At each iteration, SA first identifies the set of critical vertices CV (s), which can be achieved in O(|V | × deg max ) time where deg max is the maximum degree of the graph. A candidate solution is then sampled in O(1) time. When a neighboring solution s = {S , S } is obtained, the conductance variation is calculated in O(1) time. Moreover, deg S (w) and deg S (w) are updated in O(deg(v)) time. Thus, SA requires O(saIter × |V | × deg max ) time. For the CNTS procedure (Section 2.5), it can be achieved in O(D ×|V |×deg max) time [30]. Since the dominating part of the local refinement is the SA procedure, the time complexity of local refinement is O(saIter × |V | × deg max ). The whole IMSA algorithm (Algorithm 1) is composed of a series of V-cycles. For each V-cycle, the solution-guided coarsening procedure with the HEM heuristic requires O(m × |E|) time, where m is the number of levels of each V-cycle. At each level, the partition of the intermediate graph is improved by the local refinement procedure with a time complexity of O(saIter × |V | × deg max ). The uncoarsening procedure requires O(1) time, because it simply restores each corresponding intermediate graph recorded during the coarsening process, followed by the local refinement procedure. Consequently, the total time complexity of one V-cycle of the IMSA algorithm is bounded by O(m × saIter × |V | × deg max ). The space complexity of IMSA can be evaluated as follows. First, IMSA represents a graph with an adjacency list whose space complexity is O(|V | + |E|). For each level, IMSA keeps an auxiliary graph, requiring O(m × |E|) space for a V-cycle. Moreover, IMSA uses a table to maintain the sum of degrees of each vertex of G with O(m × |V |) space. Therefore, the total space complexity of the IMSA algorithm for each V-cycle is given by O(m × (|V | + |E|)).

  sc-pkustk13 (|V | = 94, 893), ga2010 (|V | = 291, 086), NLR (|V | = 4, 163, 763), delaunay n24 (|V | = 16, 777, 216) with 200 independent runs per algorithm and per instance (i.e., E x = 200).

Fig. 3 .

 3 Fig. 3. Probability distributions of the run time (in seconds) needed to attain a given target objective value by each algorithm on the 4 representative instances.

Fig. 4 .

 4 Fig. 4. Comparisons of the IMSA algorithm with a multi-start simulated annealing plus tabu search (denoted by (SA+TS) restart ) on the 20 representative instances.

Fig. 5 .

 5 Fig. 5. Comparisons of the IMSA algorithm with an IMSA variant where the SA-based local refinement is replaced by a descent search (denoted by IMSA descent ) on the 20 representative instances.

Fig. 6 .

 6 Fig.6. Analysis of the parameters (ct, saIter, θ, ar, D, α) on its performance of the proposed IMSA algorithm.

  solution s, initial temperature T 0 , move counter mv, maximum number of iterations per temperatures saIter, cooling ratio θ, frozen state parameter ar. Ensure: Best partition s best found during the search.

	1: T ← T 0
	2: s best ← s
	3: repeat
	4:	mv ← 0
	5:	for iter = 1 to saIter do
	6:	v ← a random vertex from CV (s)
	7:	s ← s ⊕ Relocate(v)	/ * Section 2.4.2 * /
	8:	if δ(v) < 0 then
	9:	s ← s
	10:	mv ← mv + 1
	11:	else
	12:	With probability defined in Equation (3)	/ * Section 2.4.1 * /
	13:	s ← s
	14:	mv ← mv + 1
	15:	end if
	16:	if Φ(s) < Φ(s best ) then
	17:	s best ← s
	18:	end if
	19:	end for
	20:

T ← T * θ / * Cooling down the temperature * / 21: until Acceptance rate (mv/saIter) is below ar for 5 consecutive rounds 22: return s best

Table 1

 1 The parameters setting of the IMSA algorithm.

	Parameter Section Description

Table A .

 A 1 Main features of the 66 benchmark instances from "The 10th DIMACS Implementation Challenge Benchmark" and "The Network Data Repository online".

	Instance	|V |	|E|	Density	Instance	|V |	|E|	Density
		Small set (24)			delaunay n20	1,048,576	3,145,686	5.72e-06
	sc-nasasrb	54,870	1,311,227	8.71e-04	inf-roadNet-PA	1,087,562	1,541,514	2.61e-06
	wing	62,032	121,544	6.32e-05	thermal2	1,227,087	3,676,134	4.88e-06
	delaunay n16	65,536	196,575	9.15e-05	belgium	1,441,295	1,549,970	1.49e-06
	sc-pkustk13	94,893	3,260,967	7.24e-04	G3 circuit	1,585,478	3,037,674	2.42e-06
	preferentialAttachment 100,000	499,985	1.00e-04	kkt power	2,063,494	6,482,320	3.04e-06
	smallworld	100,000	499,998	1.00e-04	delaunay n21	2,097,152	6,291,408	2.86e-06
	luxembourg	114,599	119,666	1.82e-05	netherlands	2,216,688	2,441,238	9.94e-07
	delaunay n17	131,072	393,176	4.58e-05	M6	3,501,776	10,501,936	1.71e-06
	144	144,649	1,074,393	1.03e-04	333SP	3,712,815	11,108,633	1.61e-06
	web-arabic-2005	163,598	1,747,269	1.31e-04	AS365	3,799,275	11,368,076	1.58e-06
	soc-gowalla	196,591	950,327	4.92e-05	venturiLevel3	4,026,819	8,054,237	9.93e-07
	delaunay n18	262,144	786,396	2.29e-05	NLR	4,163,763	12,487,976	1.44e-06
	ok2010	269,118	637,074	1.76e-05	delaunay n22	4,194,304	12,582,869	1.43e-06
	va2010	285,762	701,064	1.72e-05	hugetrace00	4,588,484	6,879,133	6.53e-07
	nc2010	288,987	708,310	1.70e-05	channel	4,802,000	42,681,372	3.70e-06
	ga2010	291,086	709,028	1.67e-05		Large set (17)
	cnr-2000	325,557	2,738,969	5.17e-05	hugetric00	5,824,554	8,733,523	5.15e-07
	mi2010	329,885	789,045	1.45e-05	hugetric10	6,592,765	9,885,854	4.55e-07
	mo2010	343,565	828,284	1.40e-05	italy	6,686,493	7,013,978	3.14e-07
	oh2010	365,344	884,120	1.32e-05	adaptive	6,815,744	13,624,320	5.87e-07
	soc-twitter-follows	404,719	713,319	8.71e-06	hugetric20	7,122,792	10,680,777	4.21e-07
	pa2010	421,545	1,029,231	1.16e-05	great-britain	7,733,822	8,156,517	2.73e-07
	il2010	451,554	1,082,232	1.06e-05	delaunay n23	8,388,608	25,165,784	7.15e-07
	soc-youtube	495,957	1,936,748	1.57e-05	germany	11,548,845	12,369,181	1.85e-07
		Medium set (25)		asia	11,950,757	12,711,603	1.78e-07
	soc-flickr	513,969	3,190,452	2.42e-05	hugetrace10	12,057,441	18,082,179	2.49e-07
	delaunay n19	524,288	1,572,823	1.14e-05	road central	14,081,816	16,933,413	1.71e-07
	ca-coauthors-dblp	540,486	15,245,729	1.04e-04	hugetrace20	16,002,413	23,998,813	1.87e-07
	soc-FourSquare	639,014	3,214,986	1.57e-05	delaunay n24	16,777,216	50,331,601	3.58e-07
	eu-2005	862,664	16,138,468	4.34e-05	hugebubbles00	18,318,143	27,470,081	1.64e-07
	tx2010	914,231	2,228,136	5.33e-06	hugebubbles10	19,458,087	29,179,764	1.54e-07
	ecology2	999,999	1,997,996	4.00e-06	hugebubbles20	21,198,119	31,790,179	1.41e-07
	ecology1	1,000,000	1,998,000	4.00e-06	road usa	23,947,347	28,854,312	1.01e-07
	NACA0015	1,039,183	3,114,818	5.77e-06

Table A .

 A 3: Computational results on the Medium set of 25 benchmark instances obtained by the IMSA algorithm and the three reference algorithms (MAMC

https://www.cc.gatech.edu/dimacs10/downloads.shtml

http://networkrepository.com/index.php

The code of the IMSA algorithm will be made publicly available at: http://www. info.univ-angers.fr/pub/hao/IMSA.html

Acknowledgment

The authors are grateful to the reviewers for their useful comments and suggestions which helped us to significantly improve the paper. Support from the China Scholarship Council (CSC) (No.: 201606070096) for the first author is also acknowledged.

A Appendix

This appendix reports the detailed results of the proposed IMSA algorithm and the three reference algorithms (MAMC [START_REF] Lu | A hybrid evolutionary algorithm for finding low conductance of large graphs[END_REF], SaBTS [START_REF] Lu | Stagnation-aware breakout tabu search for the minimum conductance graph partitioning problem[END_REF], and MQI [START_REF] Lang | A flow-based method for improving the expansion or conductance of graph cuts[END_REF]) on the three sets of 66 benchmark instances whose main features are shown in Table A

According to the experimental protocol of Section 3.2, each algorithm was run with its default parameters setting and executed 20 times per instance with a cutoff time of 60 minutes per run. The results of 39 small and medium instances (29 DIMACS graphs and the 10 massive network graphs) for the three reference algorithms were extracted from [START_REF] Lu | A hybrid evolutionary algorithm for finding low conductance of large graphs[END_REF]. The results of the compared algorithms on the remaining instances were obtained with the above protocol. Tables A.2-A. [START_REF] Bader | Graph partitioning and graph clustering[END_REF] show the computational results of the compared algorithms.

In Tables A.2-A.4, columns 1 and 2 indicate the name and the number of vertices |V | for each instance. The remaining columns show the results reached by IMSA and the reference algorithms (MAMC, SaBTS, and MQI): the best conductance (Φ best ), the average conductance (Φ avg ), the number of times Φ best was reached across 20 independent runs (hit), and the average computation time per run in seconds to reach the final solution (t(s)). The best of the Φ best (or Φ avg ) values among all the compared algorithms for each instance is highlighted in boldface. An asterisk ( * ) indicates a strictly best solution among all the results. Bold and asterisked values thus correspond to the best upper bounds for the associated graphs.

Note that it is meaningful to compare the computation times of two algorithms on a graph only if they report the same objective value. Given that IMSA reached better results on many instances, the timing information is provided for indicative purposes. For a meaningful comparison of computational efficiency of the algorithms, the reader is referred to the time-to-target analysis shown in Section 4.1.


MD MSc Jolene H Fisher
email: jolene.fisher@uhn.ca

MD Vincent Cottin
email: vincent.cottin@chu-lyon.fr.

Care-delivery models and interstitial lung disease: the role of the specialized center

Keywords:

Interstitial lung disease

INTRODUCTION

The field of interstitial lung disease (ILD) is rapidly evolving and multifaceted with patients that experience debilitating symptoms and poor prognosis. Care delivery models that utilize specialized centers with access to ILD specific resources have emerged as a way to provide comprehensive care to these patients with complex diseases. The goals of the specialized center are multifold and centered around providing timely access to an accurate diagnosis and effective care plan. Other deliverables include management of treatment side effects and patient comorbidities, patient education and support groups, medical education of both practicing clinicians and trainees and access to clinical trials, lung transplant and end of life care. A multidisciplinary team is integral to providing such complex care delivery and requires access to pulmonology, rheumatology, pathology, thoracic surgery/interventional pulmonology, radiology, palliative care, lung transplant, pharmacy, nursing, social work and administrative support (both clinical and research), with ILD expertise (Figure 1).

Universal access to these highly specialized centers with optimal resources and expertise remains a significant challenge that requires innovative strategies to overcome. The aims of this chapter are to (1) summarize the key components of ILD care, (2) describe the role of the specialized center in the delivery of each component of ILD care, and (3) identify the current challenges facing ILD care delivery models and propose viable strategies to overcome these gaps. Key messages are summarized in Table 1.

KEY COMPONENTS OF ILD CARE AND THE ROLE OF THE SPECIALIZED CENTER IN

DELIVERY

Diagnosis

ILD subtypes have variable epidemiology, clinical course and management. A timely and accurate ILD diagnosis is critical for clinical decision making, patient counseling and advancing research. The current gold standard for ILD diagnosis is multidisciplinary discussion (MDD) between 'experts' that integrate clinical, radiologic and where available, pathologic features in order to reach a consensus diagnosis. [START_REF] Raghu | Diagnosis of Idiopathic Pulmonary Fibrosis. An Official ATS/ERS/JRS/ALAT Clinical Practice Guideline[END_REF][START_REF] Raghu | An official ATS/ERS/JRS/ALAT statement: idiopathic pulmonary fibrosis: evidence-based guidelines for diagnosis and management[END_REF][START_REF] Travis | An official American Thoracic Society/European Respiratory Society statement: Update of the international multidisciplinary classification of the idiopathic interstitial pneumonias[END_REF][START_REF] Johannson | Evaluation of patients with fibrotic interstitial lung disease: A Canadian Thoracic Society position statement[END_REF] Within the tripod of clinical, radiologic and pathologic features, the MDD further incorporates a variety of information that contribute to diagnosis, including autoimmune serology, precipitins, clinical or molecular biology genetic information, molecular classifiers, or reports from other healthcare providers (e.g. occupational medicine specialist, domiciliary visit looking for exposures that may cause hypersensitivity pneumonitis, etc). Utilization of MDDs have been shown to improve diagnostic confidence and decrease inter observer variability. [START_REF] Prasad | The interstitial lung disease multidisciplinary meeting: A position statement from the Thoracic Society of Australia and New Zealand and the Lung Foundation Australia[END_REF][START_REF] Jo | Evaluating the interstitial lung disease multidisciplinary meeting: a survey of expert centres[END_REF][START_REF] Flaherty | Idiopathic interstitial pneumonia: what is the effect of a multidisciplinary approach to diagnosis?[END_REF][START_REF] Sadeleer | Diagnostic Ability of a Dynamic Multidisciplinary Discussion in Interstitial Lung Diseases: A Retrospective Observational Study of 938 Cases[END_REF] MDDs, at minimum, include a pulmonologist and radiologist with ILD expertise and depending on the individual case, other specialty involvement, such as, pathology and rheumatology. [START_REF] Furini | The Role of the Multidisciplinary Evaluation of Interstitial Lung Diseases: Systematic Literature Review of the Current Evidence and Future Perspectives[END_REF] Specialized diagnostic resources, including extensive autoimmune serology and histopathology obtained by videothoracoscopic surgical lung biopsy (SLB) or cryobiopsy, may be needed to make an accurate diagnoses. MDD groups that do not include all ILD specific experts benefit from access to larger and more versed MDDs for their more complex cases as the quality of MDD is dependent on experience. [START_REF] Cottin | Should Patients With Interstitial Lung Disease Be Seen by Experts?[END_REF] Widespread availability of safe and accurate diagnostic testing for ILD remains a significant challenge. Although decreased by the use of video assisted techniques and appropriate patient selection, SLB is still associated with high morbidity and mortality, [START_REF] Hutchinson | In-Hospital Mortality after Surgical Lung Biopsy for Interstitial Lung Disease in the United States. 2000 to 2011[END_REF] particularly in centers with less experience. [START_REF] Fisher | Procedure volume and mortality after surgical lung biopsy in interstitial lung disease[END_REF] In addition, there can be significant inter observer variability in histopathology interpretation. [START_REF] Lettieri | Discordance between general and pulmonary pathologists in the diagnosis of interstitial lung disease[END_REF] While less invasive, similar issues have been identified with the use of transbronchial lung cryobiopsy. [START_REF] Johannson | Diagnostic Yield and Complications of Transbronchial Lung Cryobiopsy for Interstitial Lung Disease. A Systematic Review and Metaanalysis[END_REF][START_REF] Iftikhar | Transbronchial Lung Cryobiopsy and Video-assisted Thoracoscopic Lung Biopsy in the Diagnosis of Diffuse Parenchymal Lung Disease. A Meta-analysis of Diagnostic Test Accuracy[END_REF][START_REF] Sethi | Are Transbronchial Cryobiopsies Ready for Prime Time?: A Systematic Review and Meta-Analysis[END_REF] Such 'volumeoutcome' relationships have been described across a variety of medical and surgical specialties and used to support the regionalization of specialty care. [START_REF] Birkmeyer | Hospital volume and surgical mortality in the United States[END_REF][START_REF] Halm | Is volume related to outcome in health care? A systematic review and methodologic critique of the literature[END_REF] Awareness of the risk and limitations associated with SLB has contributed to efforts aimed at improving ILD diagnosis in its absence, such as developing the concept of a working/provisional diagnosis, the probable usual interstitial pneumonia definition and a molecular classifier. [START_REF] Raghu | Diagnosis of Idiopathic Pulmonary Fibrosis. An Official ATS/ERS/JRS/ALAT Clinical Practice Guideline[END_REF][START_REF] Ryerson | A Standardized Diagnostic Ontology for Fibrotic Interstitial Lung Disease. An International Working Group Perspective[END_REF][START_REF] Lynch | Diagnostic criteria for idiopathic pulmonary fibrosis: a Fleischner Society White Paper[END_REF][START_REF] Raghu | Use of a molecular classifier to identify usual interstitial pneumonia in conventional transbronchial lung biopsy samples: a prospective validation study[END_REF] The expertise of an ILD center may reduce the number of cases in which a biopsy is contemplated and performed, as compared to centers with less ILD familiarity.

The complexities surrounding ILD diagnosis have led to increasing regionalization of care with a push to refer to expert centers. While these regional, expert centers can increase diagnostic accuracy for ILDs, they can also be disadvantaged by limited accessibility.

Delayed access to an ILD center is associated with increased mortality, independent of disease severity. [START_REF] Lamas | Delayed access and survival in idiopathic pulmonary fibrosis: a cohort study[END_REF] Disparate access varies widely and can result from geography, marginalization and lack of healthcare resources. These specific barriers are dependent on jurisdiction with issues such as geography typically more relevant in places like Canada and Australia as opposed to Europe. Innovative strategies are needed to overcome these barriers and increase access to MDDs and specialized diagnostic testing for patients with ILD.

Management

The comprehensive management of ILD is complex and rapidly evolving with both pharmacologic and non-pharmacologic components. [START_REF] Assayag | Comprehensive management of fibrotic interstitial lung diseases: A Canadian Thoracic Society position statement[END_REF][START_REF] Richeldi | Pharmacological management of progressive-fibrosing interstitial lung diseases: a review of the current evidence[END_REF][START_REF] Wijsenbeek | Spectrum of Fibrotic Lung Diseases[END_REF][START_REF] Wijsenbeek | Comprehensive Supportive Care for Patients with Fibrosing Interstitial Lung Disease[END_REF] The are several reasons for this complexity. ILDs include multiple conditions with variable disease behavior and therefore different goals of therapy. Some of these conditions are potentially reversible or partially reversible such as non-fibrotic hypersensitivity pneumonitis while others, such as idiopathic pulmonary fibrosis (IPF), are progressive. Treatment decisions regarding ILD medications can be nuanced given that many therapies are aimed at slowing disease progression as opposed to disease reversal, necessitating careful consideration of the risk versus benefit profile in each patient. While there has been a recent increase in quality data for the treatment of non-IPF ILD, [START_REF] Flaherty | Nintedanib in Progressive Fibrosing Interstitial Lung Diseases[END_REF][START_REF] Maher | Pirfenidone in patients with unclassifiable progressive fibrosing interstitial lung disease: a double-blind, randomised, placebo-controlled, phase 2 trial[END_REF] more is required, and treatment decisions for conditions such as hypersensitivity pneumonitis and unclassifiable ILD are often heavily influenced by 'expert opinion'. In the absence of management guidelines, decisions regarding treatment of connective tissue disease (CTD)-ILD are best done in conjunction with rheumatology to identify therapies that ideally treat both pulmonary and non-pulmonary disease manifestations.

Comprehensive management further includes access to pulmonary rehabilitation, lung transplant, symptom management/palliative care, advanced care planning and patient education, support and advocacy. [START_REF] Wijsenbeek | Comprehensive Supportive Care for Patients with Fibrosing Interstitial Lung Disease[END_REF][START_REF] Jo | Treatment of idiopathic pulmonary fibrosis in Australia and New Zealand: A position statement from the Thoracic Society of Australia and New Zealand and the Lung Foundation Australia[END_REF][START_REF] Kreuter | Palliative care in interstitial lung disease: living well[END_REF] The infrastructure of specialized ILD centers are typically best equipped to deliver such comprehensive care, with access to the required resources often limited outside of these select programs.

Longitudinal monitoring

Longitudinal monitoring of ILD patients is central to informing management decisions. [START_REF] Wijsenbeek | Spectrum of Fibrotic Lung Diseases[END_REF][START_REF] Fisher | Long-term monitoring of patients with fibrotic interstitial lung disease: A Canadian Thoracic Society Position Statement[END_REF][START_REF] Travis | An official American Thoracic Society/European Respiratory Society statement: Update of the international multidisciplinary classification of the idiopathic interstitial pneumonias[END_REF][START_REF] Wells | Any fool can make a rule and any fool will mind it[END_REF] Regular clinical assessments provide a mechanism to monitor symptoms, screen for disease progression, and identify treatment side effects and/or comorbidities. Information obtained from these interactions guide decisions related to treatment initiation, alteration, or discontinuation and appropriate timing of lung transplant referral, and/or end-of-life planning. In patients with provisional or working diagnoses, longitudinal monitoring provides an opportunity to reconsider the diagnosis which can become clearer overtime (e.g. development of extrapulmonary CTD symptoms). While the specialized center often plays an important role in the long-term monitoring of fibrotic ILD, access to a local pulmonologist has several advantages. Disease behavior is widely variable among patients with ILD, and access to an expedited clinical assessment is ideal in the event of acute deterioration. Shared-care models can facilitate faster access to appropriate expertise for patients. Local care providers can liaise with 'expert' ILD centers on a patient's behalf in order to make timely care decisions. This type of care delivery model has the additional advantage of 'off-loading' ILD centers with long waiting lists of some follow-up visits, allowing them to efficiently focus their expertise where it provides the most added value.

Medical education

ILD-related continuing medical education for trainees, general practitioners, radiologists, pulmonologists, thoracic surgeons/interventional pulmonologists, pathologists and rheumatologists, is an essential component of ILD care delivery. ILD patients frequently report a lack of ILD awareness among their health care providers which results in delayed specialist referral, diagnosis and treatment. [START_REF] Bonella | European IPF Patient Charter: unmet needs and a call to action for healthcare policymakers[END_REF][START_REF] Cosgrove | Barriers to timely diagnosis of interstitial lung disease in the real world: the INTENSITY survey[END_REF] 'Real world' registry data has shown high rates of SLBs (even in those with a definite usual interstitial pneumonia pattern on high resolution computed tomography) and corticosteroid use with lower than expected rates of antifibrotic therapy in patients with IPF. [START_REF] Behr | Management of patients with idiopathic pulmonary fibrosis in clinical practice: the INSIGHTS-IPF registry[END_REF] These findings are not necessarily surprising, given the complexity and rapid evolution of ILD diagnosis and management, and implies there is a need for ongoing ILD related knowledge translation and dissemination to the medical community. There is data to support such endeavors with a national French survey of physicians caring for IPF patients showing improved knowledge and management of IPF after implementation of an education outreach program. [START_REF] Cottin | Adherence to guidelines in idiopathic pulmonary fibrosis: a follow-up national survey[END_REF] Specialized ILD centers are typically equipped with the necessary infrastructure, such as staff and accreditation, required to deliver these programs.

It is also important to recognize that clinical feedback to physicians referring to ILD centers provides a mechanism for informal medical education. For example, a referring pulmonologist would typically propose a first-choice diagnosis, which may or may not be modified by the MDD at the ILD center. These clinical feedback loops have important educational roles. The MDD has an additional training effect on participating physicians, whether trainees or more senior members. [START_REF] Sadeleer | Diagnostic Ability of a Dynamic Multidisciplinary Discussion in Interstitial Lung Diseases: A Retrospective Observational Study of 938 Cases[END_REF][START_REF] Cottin | Should Patients With Interstitial Lung Disease Be Seen by Experts?[END_REF]37 Ensuring pulmonology trainees gain competence in the diagnosis and management of ILD is an integral component of improving ILD care delivery. The specialty clinic plays an important role in trainee education, providing a mechanism for high volume ILD clinical exposure. A survey of British Thoracic Society trainee members found that the majority felt their ILD training was inadequate. [START_REF] Sharp | UK trainee experience in interstitial lung disease: results from a British Thoracic Society survey[END_REF] Additional studies identifying specific barriers to trainee ILD education and mechanisms for improvement are required. The ILD specialty clinic is also a key component of ILD subspecialty clinical and research training programs.

Patient education, support and advocacy

Many ILDs are progressive conditions associated with poor quality of life and limited life expectancy. ILD patients and caregivers frequently report inadequate emotional and psychological support. [START_REF] Bonella | European IPF Patient Charter: unmet needs and a call to action for healthcare policymakers[END_REF] A survey of patient perspectives on the benefits of a specialized ILD center found patients placed a high value on gaining a better understanding of their disease and access to a specialized nurse that provided education and support, [START_REF] Mclean | Priorities and expectations of patients attending a multidisciplinary interstitial lung disease clinic[END_REF] reenforcing the importance of patient education, support and advocacy as key components of ILD care delivery. Patients frequently search the Internet for information related to their disease, yet ILD websites are often inaccurate and outdated. [START_REF] Fisher | Accuracy and Reliability of Internet Resources for Information on Idiopathic Pulmonary Fibrosis[END_REF] Specialized ILD clinics can provide highly valued disease related education to patients through many avenues, including direct discussion at clinic visits with an ILD physician and/or nurse educator, provision of disease specific education handouts, lists of reliable online resources and formal education programs. Specialized clinics can also facilitate patient and caregiver support groups that provide additional psychosocial and emotional support for patients and families dealing with ILD.

Specialized ILD clinics can promote community engagement through relationships with non-medical partners, such as patient foundations or patient associations. ILD physicians or nurses from the specialized center may take an active role in the scientific committee of a patient foundation. Here the role of the ILD center goes beyond providing education to the patient during a clinic visit or a specific educational activity, by delivering important educational messages that will be conveyed by the patient foundation. These relationships are a key component of ILD care delivery and provide valuable platforms for education, fundraising and research advancement. They also give the patient a seat at the table, helping identify and advocate for patient relevant outcomes.

Research and access to clinical trials

There has been significant advancement in drug therapies for ILD and ongoing rapid development of new drugs that require rigorous testing. In many cases of fibrotic ILD, current therapies only offer a slowing of disease progression as opposed to reversal or cure. Subsequently, the ability to offer and effectively conduct clinical trials is a key component of ILD care delivery. Without this ability, drug development will be stifled and we will fall short of our ability to find effective therapies to advance the field of ILD.

There are several barriers to physician and patient participation in clinical trials, including access to the required organizational structure, which is often only available at specialized centers. Components often needed include access to a MDD, research personnel (such as trial coordinators), institutional infrastructure (such as research ethics boards), and clinics with a high volume of ILD patients.

Specialized ILD clinics can facilitate other important forms of research that require access to high volumes of ILD patients, such as prospective patient registries. This 'real world' data on epidemiology, disease course, treatments, and outcomes is especially valuable when studying heterogeneous and less common diseases like ILDs. Large, national patient registries have published findings on ILD natural history, treatment and outcomes that would be challenging to obtain by other research avenues. [START_REF] Behr | Management of patients with idiopathic pulmonary fibrosis in clinical practice: the INSIGHTS-IPF registry[END_REF][START_REF] Jo | Baseline characteristics of idiopathic pulmonary fibrosis: analysis from the Australian Idiopathic Pulmonary Fibrosis Registry[END_REF][START_REF] Jo | Disease progression in idiopathic pulmonary fibrosis with mild physiological impairment: analysis from the Australian IPF registry[END_REF] In addition, registry research can give patients a voice [START_REF] Mclean | Priorities and expectations of patients attending a multidisciplinary interstitial lung disease clinic[END_REF] and provide opportunities to study and develop useful patient centered outcomes. [START_REF] Tsai | Minimum important difference of the EQ-5D-5L and EQ-VAS in fibrotic interstitial lung disease[END_REF]

CHALLENGES FACING ILD CARE DELIVERY MODELS AND PROPOSED SOLUTIONS

Specialized centers are generally highly appreciated by both referring physicians and patients, playing a central role in ILD care delivery. However, limitations of these models can include a lack of widespread and timely access for patients. Disparities in accessing the specialized center can exist due to long waiting lists, marginalization and geography.

Innovative strategies that leverage technology are required to bridge these gaps.

Multidisciplinary discussion

Limited availability of MDD is a key barrier to accurate and timely ILD diagnosis. Access to MDD can be increased by utilizing various virtual platforms, including remote chart and imaging review, telemedicine and video conferencing. A retrospective, crosssectional study from Canada showed that remotely accessed MDDs are feasible, decrease waiting time and frequently lead to a change in diagnosis and management. [START_REF] Grewal | Role of a Regional Multidisciplinary Conference in the Diagnosis of Interstitial Lung Disease[END_REF] In addition, referring physicians report satisfaction with the process and improvement in their own assessment and management of ILD patients. While routine use of a remote MDD will benefit from additional study and validation, it is likely to have an increasing place in ILD care delivery. However, the organization of virtual MDD remains a barrier to use in many centers due to lack of secure virtual platforms for data sharing, the time commitment required, absence of remuneration/funding for this type of care model and the importance of an in-person assessment for determining CTD features, antigenic exposures and frailty. Virtual consultations with patients may overcome some of these barriers.

Virtual MDDs may not solve the issue of patient volume 'overload' experienced at some ILD centers. Additional strategies to most efficiently utilized MDD resources can be considered in this setting. For example, ILD cases may be triaged to follow a specific MDD 'path' according to complexity. Similar approaches have been successfully used in other disciplines, such as Oncology. [START_REF] Selby | The Value and Future Developments of Multidisciplinary Team Cancer Care[END_REF] In the case of ILD, a patient with a UIP pattern, no identifiable cause for ILD and over the age of 65 may not require a full MDD discussion, in contrast to more complex cases, such as, unclassifiable ILD or chronic hypersensitivity pneumonitis without an identified antigen.

Longitudinal monitoring

Longitudinal monitoring of ILD patients solely at specialized centers has several disadvantages. First, many specialized centers do not have the capacity to see new referrals in a timely fashion and to conduct all follow-up visits. Second, attending ongoing follow-up visits can be a significant burden for patients that have to travel far distances. Third, it may be challenging (both for the patient and ILD clinic) to accommodate urgent assessments in the event of a clinical deterioration. Lastly, for successful collaboration, it is important to respect the pre-existing patient-doctor relationship of referring physicians, who are intellectual and financial stakeholders in patient care. There are several viable strategies that can be used to circumvent some of these issues. Certain follow-up visits can be done remotely using phone or videoconference by the ILD physician or nurse. Blood work and pulmonary function testing can be done locally with results sent to specialized centers and prescription renewals can be done remotely.

Home-based patient monitoring programs that incorporate home spirometry have emerged as viable vehicles for ILD care delivery. [START_REF] Moor | Home Monitoring in Patients with Idiopathic Pulmonary Fibrosis. A Randomized Controlled Trial[END_REF] These programs utilize eHealth technology to monitor patients remotely. Patient reported outcomes and physiologic data, such as spirometry, are collected and transmitted real time to ILD care providers.

Home spirometry has shown promise for detecting ILD progression and use as a clinical trial endpoint. [START_REF] Russell | Daily Home Spirometry: An Effective Tool for Detecting Progression in Idiopathic Pulmonary Fibrosis[END_REF][START_REF] Johannson | Home monitoring improves endpoint efficiency in idiopathic pulmonary fibrosis[END_REF] Home-based monitoring programs can decrease cumbersome travel for patients and empower them to take an active role in their disease management, while allowing their physicians to do more frequently monitoring.

In many cases, it is helpful for the patient to have a local pulmonologist who can alternate follow-up visits with the ILD center. There are several advantages to this model including decreasing travel burden on patients, off-loading ILD centers with long waiting lists and local access to an expedited assessment in the event of a clinical deterioration. While the ILD center often plays a central role in confirming or changing the diagnosis and treatment plan, local pulmonologists can provide valuable ongoing monitoring and liaise with expert centers on behalf of their patient in the event of a clinical change. Some ILD centers provide expert opinions to local pulmonologists without directly seeing patients. The best care pathway and balance between remote, in-person and shared follow-up varies between centers and is dependent on local needs and priorities.

Racial, ethnic and gender disparities and ILD care delivery

Racial, ethnic and gender disparities are well described determinants of health and healthcare access. [START_REF] Bach | Primary care physicians who treat blacks and whites[END_REF][START_REF]Medicine Io. Unequal Treatment: Confronting Racial and Ethnic Disparities in Health Care[END_REF][START_REF] Shannon | Gender equality in science, medicine, and global health: where are we at and why does it matter?[END_REF] It is not known how these characteristics influence access to specialized ILD care or its delivery. Patient gender has been shown to significantly influence whether a patient receives an IPF diagnosis, suggesting gender bias may exist amongst ILD physicians. [START_REF] Assayag | Patient gender bias on the diagnosis of idiopathic pulmonary fibrosis[END_REF] In addition, a patient's ILD care needs, expectations and goals may vary according to culture and region of origin and are factors that need to be considered when delivering care. [START_REF] Kreuter | Palliative care in interstitial lung disease: living well[END_REF] Research studies evaluating the role that race, ethnicity and gender play in how specialized ILD care is accessed and delivered are urgently required.

Future of ILD care delivery

With the exponential pace of knowledge generation, medicine is becoming increasingly subspecialized. ILD specifically has seen many changes in the past decade, with ongoing new discoveries. With such rapid advances, effective knowledge translation and dissemination becomes an increasingly daunting task as care delivery becomes more complex. As a field, the ILD community can leverage collective international expertise to continuously improve ILD care delivery. There are many opportunities for integrating both national and international expertise into local care delivery models. One example would be providing the ability to bring exceptional cases to a national or international MDD. The framework for these types of endeavors already exists in some places, with the European Research Network (ERN-LUNG, https://ern-lung.eu/) being one example. Such frameworks can be expanded upon to include other jurisdictions. Infrastructure for national and international clinical care collaborations can also provide a mechanism for less formal interactions, such as asking for advice on a specific aspect of a case (i.e. chest computed tomography or histopathology slides). These types of collaborations can increase access to highly specialized ILD care for both remote and marginalized communities and provide additional platforms for education and research. Establishing funding structures that support the time and resources needed to deliver this complex care is critical.

SUMMARY

In summary, comprehensive ILD care delivery has several key components including diagnosis, treatment, monitoring, support/advocacy, education and research. The role of the specialized center in care delivery is multifaceted (Figure 1), with an overarching goal of improving patient care and advancing the field of ILD. The current role of the specialized center in ILD care delivery models faces significant feasibility and generalizability challenges. Creative and innovative strategies are needed to find ways to optimally deliver ILD care to the highest number of patients possible. • MDD requires access to specialty resources that are typically only available at specialized ILD centers.

Clinics Care Points:

Management

• ILD management is multifaceted with pharmacologic and nonpharmacologic components.

• Treatment decisions can be nuanced and are often guided by expert opinion given that many cases do not fall into existing management guidelines.

• The infrastructure needed to provide comprehensive ILD management is typically limited outside of the specialized center.

Longitudinal monitoring

• Longitudinal monitoring of ILD patients is essential to informing management decision making. • The infrastructure, momentum and commitment to research required to conduct clinical trials in ILD is typically available at specialized centers.

CHALLENGES AND SOLUTIONS FACING ILD CARE DELIVERY

Challenge Key messages

Multidisciplinary discussion

• Limited access to an ILD center and a specialized MDD is a barrier to a timely diagnosis and effective treatment plan for patients with ILD.

• Using virtual MDDs are a strategy to increase MDD access.

Figure 1 .

 1 Figure 1. Key components of interstitial lung disease care delivery. CME, continuing

••••

  A 'shared-care' model between local pulmonologists and ILD centers can facilitate timely access to care, minimize patient travel and 'offload' specialty clinics. Medical education • ILD related medical education for clinicians and trainees is a key component of ILD care delivery. Additional research on ILD knowledge gaps and effective education strategies are required. Patient education, support and advocacy Patient education, support and advocacy is a key component of ILD care delivery.• Specialized ILD clinics facilitate patient education, support and advocacy through direct patient interaction and community engagement.Research and access to clinical trials Access to clinical trials is an important part of ILD care delivery.

•

  Longitudinal monitoring• Remote monitoring and shared care models with local physicians can decrease travel burden for ILD patients, provide timely access to care, off-load specialized clinics and contribute to the continuing medical education of referring physicians.Racial, ethnic and gender disparities and ILD care delivery Research on race, ethnic and gender disparities in ILD care access and delivery is urgently needed.Future of ILD care delivery • International collaborations and networks are the future of ILD care delivery.

Table 1 . Summary of Key Messages KEY COMPONENTS OF ILD CARE AND THE ROLE OF THE SPECIALIZED CENTER IN DELIVERY Care delivery component Key messages

 1 Diagnosis• Accurate and timely ILD diagnosis is a key component of ILD care.

Monitoring