Maria Predari
email: maria.predari@inria.fr

Aurélien Esnard
email: aurelien.esnard@labri.fr

A k-way Greedy Graph Partitioning with Initial Fixed Vertices for Parallel Applications

Keywords: high-performance computing, graph partitioning, multi-level framework, parallel simulations

Graph partitioning is used to solve the problem of distributing computations to a number of processors, in order to improve the performance of time consuming applications in parallel environments. A common approach to solve this problem is based on a multilevel framework, where the graph is firstly coarsened to a smaller instance and then it is partitioned in a number of parts using recursive bisection (RB) based methods. However, in applications where initial fixed vertices are used to model additional constraints of the problem, RB based methods often fail to produce partitions of good quality. In this paper, we propose a new direct k-way greedy graph growing algorithm, called KGGGP, that overcomes this issue and succeeds to produce partition with better quality than RB while respecting the constraint of fixed vertices. In the experimental section, we present results which compare KGGGP against state-of-theart methods for graphs available from the popular DIMACS'10 collection.

I. INTRODUCTION

The increasing complexity of modern applications, executed on parallel architectures often dictates an efficient decomposition of the computational load in order to ensure high performance. In literature, many applications that arise in scientific computing [START_REF] Teresco | Partitioning and dynamic load balancing for the numerical solution of partial differential equations[END_REF], circuit design [START_REF] Caldwell | Hypergraph partitioning for VLSI CAD: Methodology for heuristic development, experimentation and reporting[END_REF] or database modeling [START_REF] Demir | Clustering spatial networks for aggregate query processing: A hypergraph approach[END_REF] use graph theory to describe and solve the problem of distributing computations to a number of available processors.

More precisely in a graph, a vertex represents a computation while an edge represents data dependencies between computations. Additionally, weights may be assigned to vertices and edges to further quantify their values. Hence, the problem of distributing computations becomes the partitioning problem of how to divide vertices of a graph in k parts of roughly equal size, such that the number of edges connecting vertices in different parts is minimized (edgecut minimization). Parts are then assigned to a number of available processing units in parallel computers. Nowadays, the most common approaches to solve the graph partitioning problem are based on the multilevel approach to compress the problem and on the recursive-bisection heuristic to solve it on a smaller instance.

In this paper, we focus on a variant of the classic graph partitioning problem, that is the graph partitioning problem with fixed vertices. It typically appears when the underlying application imposes additional constraints on the assignment of some computations to certain computers (processors) of the parallel environment. That is to say, some vertices of the graph, which we refer to as fixed vertices, are assigned a priori to some parts with the condition that when the partitioning is finished, they remain in place. Note also that in the remainder of the paper, we refer to vertices that are not fixed as free.

In the bibliography, problems that use the fixed vertex paradigm are drawn from various areas such as load balancing or VLSI CAD and are mainly formulated with variants of graph partitioning. For instance, a widely used algorithm for circuit design, called the top-down placement, is based on hypergraph 1 partitioning. Related study [START_REF] Caldwell | Hypergraph partitioning for VLSI CAD: Methodology for heuristic development, experimentation and reporting[END_REF] demonstrates the importance of modeling the above problem with fixed vertices, proposing new partitioning heuristics which account for extra constraints. The authors suggest that the presence of fixed vertices models external dependencies or estimates on the positions of unplaced terminals reflecting more accurately the complex nature of the problem.

Moreover, a well-known example where the paradigm of fixed vertices occurs is the load balancing of adaptive scientific computations [START_REF] Hendrickson | Dynamic load balancing in computational mechanics[END_REF]. In such applications the discretization of the computational domain changes over time, leading to imbalanced load even for initially well-balanced simulations. The above feature gives rise to the repartitioning problem that is the problem of how to maintain dynamically changing load balance in a parallel application. The additional requirement of repartitioning is to minimize the migration volume for moving data among processors (parts). For this reason, the graph is enriched with one fixed vertex per part, along with (migration) edges connecting each fixed vertex with all the free vertices of its respective part. Thus, a good approach to solve the repartitioning problem is to perform a biased partitioning of the enriched graph, minimizing migration costs [START_REF] Aykanat | Adaptive decomposition and remapping algorithms for object-space-parallel direct volume rendering of unstructured grids[END_REF], [START_REF] Catalyurek | A repartitioning hypergraph model for dynamic load balancing[END_REF].

A. Contributions

Our main contribution is a new algorithm, KGGGP, inside a multilevel framework that finds a direct k-way graph partitioning, extending a classic greedy approach for bipartitioning. Though KGGGP addresses the general problem of graph partitioning, its merit results appear mainly when fixed vertices are used during the partitioning procedure. Indeed, in the graph partitioning problem with initial fixed vertices, KGGGP exhibits the best partitioning quality (on edgecut computations) compared to state-of-the-art partitioning tools, that often use Recursive Bisection (RB) based techniques. For classic graph partitioning, RB remains one of the best choices.

The rest of the paper is organized as follows. In section II, we first give a motivating example, that illustrate why RBbased methods fail to handle fixed vertices. Then, in section III we review state-of-the-art partitioning techniques as well as existing work for partitioning with fixed vertices. In section IV, we present the KGGGP algorithm and in section V we confirm our observations presenting experiments performed on well known graph benchmarks. Finally, we conclude our results in section VI.

II. ISSUES OF RECURSIVE BISECTION IN PARTITIONING

WITH FIXED VERTICES The motivation behind our study comes from the observation that RB based algorithms perform rather poorly when the fixed vertex paradigm is involved, a remark which is also mentioned in [START_REF] Aykanat | Multi-level direct k-way hypergraph partitioning with multiple constraints and fixed vertices[END_REF]. Here, we attempt to further explain the above behavior.

In particular, RB based methods work as follows: the original graph is first split in two parts (bisection) and the above procedure is recursively repeated until the desired number of parts is acquired. Note that at each step of the recursion, a bisection is computed by placing parts together based on an inherent numbering constraint. The constraint implies that at each t step, two part subsets are created that contain parts [1, 2 t-1 ] and [2 t-1 + 1, 2 t ] respectively. However, when the part numbering of fixed vertices opposes to that of RB, the method can not successfully respect both the inherent numbering constraint and the additional constraint of fixed vertices leading to largely disjoint parts.

In Figure 1, we illustrate a simple but compelling example that exhibits the partitioning issues emerging when a RB algorithm is used within fixed vertices. More precisely, as one may see in 1a, we use a simple two-dimensional grid (of dimensions 1000 × 1000) with an initial part numbering of fixed vertices, such that vertices near the corners are assigned accordingly to 4 different parts. We consider the rest of the vertices as free (part -1). Following, we partition the whole graph in 4 parts. We compare two different methods, within the SCOTCH multilevel framework [START_REF] Pellegrini | SCOTCH[END_REF], tuned with the same parameters. Both of them directly find a k-way partition during the initial partitioning phase of the framework (see III-B) but the first one uses a RB based partitioning method (implemented by SCOTCH) while the second one uses the KGGGP method provided by the authors.

In figures 1b, we present the results before the uncoarsening (refinement) phase obtained by the RB partitioning tool, while in 1c, one may see the same results obtained by our own KGGGP algorithm. Here, one may clearly see that during the first recursion level of RB it is not possible to select a good bisection between parts [START_REF] Teresco | Partitioning and dynamic load balancing for the numerical solution of partial differential equations[END_REF][START_REF] Caldwell | Hypergraph partitioning for VLSI CAD: Methodology for heuristic development, experimentation and reporting[END_REF] and [START_REF] Demir | Clustering spatial networks for aggregate query processing: A hypergraph approach[END_REF][START_REF] Berge | Graphs and Hypergraphs[END_REF] that also respect the constraint of initial fixed vertices. Note that even after the uncoarsening phase, where the refinement algorithm takes place, the final partition quality will remain considerably poor for the RB based method. Note that the above example is just an illustration of the problematic behavior of RB methods with initial fixed vertices. Further experiments that confirm our observations follow in section V.

III. RELATED WORK

In this section, we first present useful graph definitions and formal statements concerning the partitioning problem, and then we review existing related studies about the graph partitioning problem with fixed vertices.

A. Graph Definitions

Consider a graph G = (V, E) where V is the set of vertices and E is the set of edges. Each vertex u ∈ V has a weight w(u) representing the computational load at each processor, while each edge e ∈ E has a weight w(e) representing the communication cost between different processors.

P = (V 1 , V 2 , . . . , V k ) is a k-way partition of G if the following conditions hold: each part V i , 1 ≤ i ≤ k is a non empty subset of V , parts are pairwise disjoint (V i ∩ V l = ∅ for all 1 ≤ i, l ≤ k) and union of k parts is equal to V . When a vertex v is assigned to a part V i , we note part[v] = i its part number.
A partition is considered balanced if each part V i respects the balance criterion:

W i ≤ W avg (1 + ) for i = 1, . . . , k.
Weight W i is defined as the total vertex weight in part V i while W avg = ut∈V w(u t )/k represents the perfect load balance for all parts in G. Note that denotes the maximum imbalance tolerance allowed, where a typical value is = 5% of the ideal weight. The edgecut of a partition is the weight sum of all edges whose incident vertices belong to different parts. The edgecut metric is known to approximate the total communication volume [START_REF] Hendrickson | Graph partitioning models for parallel computing[END_REF].

Hence, the classic objectives of a graph partitioning problem is to minimize the edgecut of the graph, while the balance constraint is satisfied for all parts.

B. Multilevel Framework

Despite the computational complexity of the graph partitioning problem (NP-complete [START_REF] Garey | Computers and Intractibility: A Guide to the Theory of NP-Completeness[END_REF]), many heuristic algorithms have been proposed in the past that find reasonably good partitions. Among them, greedy algorithms that add one by one vertices to parts or spectral methods [START_REF] Hendrickson | An improved spectral graph partitioning algorithm for mapping parallel computations[END_REF] that use algebraic properties to perform the partitioning.

However, nowadays the most common approaches to solve the graph partitioning problem are based on a multilevel framework, where the initial graph is approximated by a sequence of smaller graphs [START_REF] Leland | A multilevel algorithm for partitioning graphs[END_REF]. The algorithm is divided in three phases: the coarsening, the initial partitioning and the uncoarsening phase. The main idea of the multilevel framework is to reduce the size of the graph, find a partition for the coarsest graph and project it back to the original one. Here, we give a brief description of the multilevel framework, also called V-cycle.

During the coarsening phase, a sequence of smaller graphs

G 1 , G 2 , . . . , G t is constructed from the original graph G = G 0 = (V 0 , E 0 ), such that |V i | < |V i-1 | for i = 1, . . . , t.
The goal is to contract edges, merging the adjacent vertices into a new supervertex and update the weights in the coarser graph. The above phase terminates when the reduction of successively coarser graphs becomes small enough (e.g.,

|V i | ≤ 10 × k).
The time complexity of this step is O(|E|) for the mainly used heavy edge matching heuristic [START_REF] Karypis | Multilevel k-way partitioning scheme for irregular graphs[END_REF].

The algorithm that is used to partition the coarsest graph during the multilevel framework can be any partitioning algorithm, including bisection methods, spectral methods, greedy methods or geometric ones. The time complexity of this phase is often considered negligible compared to the other phases, since the size of the coarsest graph is smaller (O(k)).

Finally, the uncoarsening of a partition is quite simple since we just need to assign a vertex of the finer graph to the same part as its counterpart vertex in the coarser graph. However since finer graphs in the sequence have more degree of freedom implying further edge cut minimization, we usually apply local refinement algorithms (bisection refining). A class of local refinements that have good results and thus being used widely in partitioning tools is based on the algorithm of Kernighan-Lin (KL) [START_REF] Kernighan | An efficient heuristic procedure for partitioning graphs[END_REF] and Fidducia-Mattheyses (FM) [START_REF] Fiduccia | A linear-time heuristic for improving network partitions[END_REF], known to have a time complexity in O(|E|) for the best methods.

Initially, the multilevel framework was only used to compute a 2-way partitioning (bisection) faster, by compressing the initial problem to solve a smaller one. Subsequently, the same scheme was applied recursively on each subgraph in order to compute a k-way partitioning. This multilevel recursivebisection framework (MLRB) was first introduced in [START_REF] Leland | A multilevel algorithm for partitioning graphs[END_REF] and requires log 2 (k) steps to compute the final k-way partition and a total of k -1 V-cycles (assuming k is a power of 2). The time complexity of MLRB is O(log(k)|E|).

More recently, another class of multilevel algorithms, called multilevel k-way (MLKW), propose to construct a k-way partitioning of a graph directly, that is, within the initial partitioning phase of the multilevel framework. Here, there is a single V-cycle: after the coarsening phase, the coarsest graph is directly partitioned into k parts and then it is projected back to the original graph. Note that refining a k-way partitioning is considerably more complicated than local 2way refinement, so the uncoarsening phase of k-way direct partitioning algorithms is usually more time consuming [START_REF] Karypis | Multilevel k-way partitioning scheme for irregular graphs[END_REF]. More precisely, the time complexity for MLKW is dominated by the uncoarsening step, that is O(k|E|) in general and O(|E|) for KMETIS thanks to an highly-optimized k-way FM refinement heuristic [START_REF] Karypis | Multilevel k-way partitioning scheme for irregular graphs[END_REF].

C. Graph Partitioning Algorithms with Fixed Vertices

In Table I, we present some useful information about widely used graph and hypergraph partitioning tools, such as SCOTCH, METIS or PATOH. Our first remark is that despite the research interest on the graph partitioning problem with initial fixed vertices, more than half of the given tools do not handle at all the above problem. Note that this is especially true for graph partitioning tools. More importantly, as it is shown in the motivating example in Sec. II, we notice that even the tools which provide such algorithms do not successfully minimize the edgecut, resulting most of the times in low quality partitions. As we mentioned before, we locate the problem in the extended use of RB based algorithms in many partitioning tools, which work fine in the classic graph partitioning problem but fails to properly handle the fixed vertex paradigm.

Nevertheless, there are some interesting studies about partitioning algorithms that successfully handle initial fixed vertices, and we briefly review them here.

First, we review the work introduced in KPATOH [START_REF] Aykanat | Multi-level direct k-way hypergraph partitioning with multiple constraints and fixed vertices[END_REF], where a multilevel direct k-way hypergraph partitioning with fixed vertices is detailed. The authors identify the inferior performance of RB when fixed vertices are involved, mentioning the problem of relabeling parts during partitioning and they propose a new multilevel direct k-way algorithm that correct the above deficiency. They start by modifying the coarsening phase in order to respect initial fixed vertices, such that fixed vertices assigned to different parts can not be matched together. During the initial partitioning phase, the main idea is to remove completely the fixed vertices, partition the coarsest graph with RB and reassign them to the [START_REF] Karypis | METIS[END_REF] graph no no MLRB -source KMETIS [START_REF] Karypis | Multilevel k-way partitioning scheme for irregular graphs[END_REF] graph no no MLKW RB source ParMetis [START_REF] Karypis | METIS[END_REF] graph no yes MLKW RB source Scotch [START_REF] Pellegrini | SCOTCH[END_REF] graph yes no MLKW RB source PT-Scotch [START_REF] Pellegrini | SCOTCH[END_REF] graph no yes MLRB -source RM-Metis [START_REF] Aykanat | Adaptive decomposition and remapping algorithms for object-space-parallel direct volume rendering of unstructured grids[END_REF] graph only k no MLKW greedy no KaFFPa [START_REF] Sanders | Think Locally, Act Globally: Highly Balanced Graph Partitioning[END_REF] graph no no MLKW RB source Chaco [START_REF] Leland | A multilevel algorithm for partitioning graphs[END_REF] graph no no MLRB spectral source HMetis [START_REF] Karypis | METIS[END_REF] hypergraph yes no MLRB -binary KHMetis [START_REF] Karypis | METIS[END_REF] hypergraph no no MLKW RB binary PATOH [START_REF] Aykanat | PaToH: A Multilevel Hypergraph Partitioning Tool[END_REF] hypergraph yes no MLRB -binary KPATOH [START_REF] Aykanat | Multi-level direct k-way hypergraph partitioning with multiple constraints and fixed vertices[END_REF] hypergraph yes no MLKW RB no ZOLTAN (PHG) [START_REF]Zoltan: Parallel partitioning, load balancing and data-management services[END_REF] Another related algorithm that addresses the repartitioning problem is proposed in RM-METIS, where the adaptive object space decomposition is modeled as a graph instance [START_REF] Aykanat | Adaptive decomposition and remapping algorithms for object-space-parallel direct volume rendering of unstructured grids[END_REF].

Here, the solution proposed is a multilevel direct k-way graph repartitioning approach, that handles fixed vertices, and that is not based on RB for the initial partitioning phase. As the previously mentioned approach, they reformulate the coarsening phase to respect fixed vertices and during the uncoarsening phase they use k-way refinements. However, during the initial partitioning phase, they employ a greedy graph growing approach using k -1 growing parts and a shrinking one. Note that RM-METIS has limitations to the number of initial fixed vertices that may be used during the partitioning, namely one per each part, whereas KGGGP has no such restrictions. Unfortunately, like with KPATOH, the implementation of RM-METIS is not publicly available as far as we know.

IV. THE KGGGP ALGORITHM

In this section, we describe a direct k-way graph partitioning algorithm, called KGGGP (k-way greedy graph growing partitioning), which can be easily integrated in a multilevel framework and that successfully handles any number of initial fixed vertices.

To begin with, we briefly describe here the standard greedy approach for bipartitioning [START_REF] Ciarlet | On the validity of a front-oriented approach to partitioning large sparse graphs with a connectivity constraint[END_REF][START_REF] Battiti | Differential greedy for the 0-1 equicut problem[END_REF][START_REF] Jain | Greedy algorithms for k-way graph partitioning[END_REF], that has served as key idea for many partitioning algorithms and particularly for KGGGP. The standard greedy algorithm starts by placing two random "seed" vertices into the two parts. Subsequently, the vertices are added alternately to the parts, selecting each time the vertex whose displacement results in minimizing a selected criterion.

A. Algorithmic description of KGGGP

The KGGGP algorithm is an extension of the standard greedy bipartitioning algorithm for a k-way graph partitioning, where a partitioning of k parts (instead of just two) is directly computed. In a certain way, KGGGP can be seen as a k+1 FM (Fidducia-Mattheyses) refinement where the additional part, called shrinking part and denoted as -1, initially contains all (free) vertices and has to be empty at the end. Here, we give the detailed description of KGGGP in Figure IV-A.

As we mentioned above, greedy algorithms often use seeds to initiate the partitioning procedure, usually based on BFS (breadth first search) [START_REF] Diekmann | Shapeoptimized mesh partitioning and load balancing for parallel adaptive FEM[END_REF], however in KGGGP, the use of seeds is optional. As an alternative, the selected minimization criterion determines the first vertex displacement for each part.

The KGGGP algorithm selects the best global displacement (v, p), among all free vertices and all possible parts. Note that we consider all vertices in part -1 as candidates to move to any of the k parts and we choose the best displacement, based on an edgecut minimization criterion (gain), that must also respect the balance constraint. Despite the existence of multiple minimization criteria, in KGGGP we use the classic gain formula (# of internal edges -# of external edges) also used in k-way FM refinement method [START_REF] Karypis | Multilevel k-way partitioning scheme for irregular graphs[END_REF]. Additionally to the above criteria, the algorithm enforces the selection of displacements where v is connected with vertices in p (connectivity constraint).

In order to quickly locate the best displacement, we use a similar data structure as in FM, adapted here for k parts. This structure, called gain bucket data structure, maintains a sorted list of displacement gains. To implement the bucket we use an array, whose i th entry contains a doubly-linked list of all displacements with gain currently equal to i. Additionally, an array containing references of all displacements is used to perform quick gain updates, in the same way as in FM. More precisely, in KGGGP, a two dimensional array is employed which can be accessed by vertex and part numbering (v, p) allowing in constant time the updates of neighbor vertices after a displacement.

The KGGGP algorithm uses three instances of the gain bucket structure to store and select displacements: H REG initially contains all possible displacements while H N CC and H N BC store displacements that do not respect the connectivity and balance constraint respectively. Note that H N BC and H N CC are at first empty. In the main loop of the algorithm, we search initially for displacements in H REG and each time we encounter a displacement that do not respect the connectivity or the balance constraint we move it to the appropriate bucket (H N CC and H N BC respectively). It is expected that at a given time, bucket H REG will become empty while buckets H N CC and H N BC contain the rest of possible displacements. In this case, until the algorithm terminates, we repeat the above procedure searching displacements first in H N CC and if necessary move them in bucket H N BC . Finally, when H N CC becomes empty, we select accordingly displacements only from H N BC . Once a displacement (v, p) is chosen (line 31), v is moved to the corresponding part p (line 33) and then (v, p) is removed from the respective bucket (line 35). Additionally, we other possible displacements of the same vertex from any bucket (line 36) and we update the selection criterion of its neighbors as in the FM algorithm (line 39). Finally, since a vertex is moved to a part, we need to redetermine if displacements of neighboring vertices respect once more the connectivity constraint. In that case, those displacements are moved from H N CC back to H REG (line 44).

In figure IV-A, we illustrate the evolution of the part growing when a simple 100 × 100 grid is partitioned into 4 parts, using the KGGGP algorithm without a multilevel framework. As one may see, the algorithm aims to respect both the balance and the connectivity constraints leading to a rather balanced and connected partition even with no refinements 4d.

B. Fixed Vertex Management

As most greedy algorithms, KGGGP may easily handle initial fixed vertices. More precisely, fixed vertices in KGGGP are directly placed in their respective parts before the selection of displacements starts and are simply not considered as candidates in the initial gain bucket H REG , remaining always in place.

C. KGGGP in a Multilevel Framework

The KGGGP algorithm can be easily integrated in a multilevel framework with some simple adjustment regarding the initial fixed vertices. Firstly, during the coarsening phase, an extra constraint is added, so that fixed vertices which belong to different parts can not be matched together, while they may be directly matched with free vertices. Following, we partition the coarsest graph with KGGGP as it is described above and we continue with the uncoarsening phase, where several kway FM refinements (KFM) are performed for further edgecut minimization. Note that during this phase, we maintain all fixed vertices locked, forcing them to remain in place.

D. Time and Space Complexity

As the time complexity is concerned, the main steps of KGGGP algorithm consist of initializing displacements in O(k|V |), selecting displacements in O(|V |) and updating the bucket structures in O(k|E|), for it is required to visit the neighborhood of each selected vertex for all parts. Therefore, the total complexity of KGGGP is O(k|E|), considering that |V | is dominated by |E|. As a reminder, the time complexity of RB is O(log(k)|E|). Finally, the memory complexity is mainly due to saving all possible displacements in the gain bucket data structure, which is O(k|V |).

E. Optimization: Local Greedy Approach

In order to reduce the total time complexity of KGGGP, we implement a second version of the method, where we enforce local selection of displacements instead of the global selection described above. The key idea here is to search for upcoming displacements only in the neighborhood of vertices that belong already to a part. This approach is similar to the one used in KMETIS to optimize the k-way FM refinement heuristic [START_REF] Karypis | Multilevel k-way partitioning scheme for irregular graphs[END_REF].

As a result, we do not need to initialize the H REG bucket structure by computing a priori the gain value for all possible displacements. Instead, after a displacement (v, k) is chosen, we dynamically insert in H REG new displacements (v , k) for all neighboring vertices v of v, that remain free. If H REG becomes empty while the partition is not complete, the method switches back to the global approach for all the remaining free vertices, given a time complexity of O(k|E|) in the worst case and O(|E|) in the best case.

V. EXPERIMENTS

In this section, we present the experimental results of KGGGP algorithm2 and we compare them with some widely used partitioning tools, already described on Table I.

To do so, we implement two versions of the KGGGP algorithm inside the SCOTCH multilevel framework, one that follows the global greedy approach (KGGGP G) and one with local greedy approach (KGGGP L) as it is described in section IV-E. The two implementations of KGGGP use exactly the same partitioning parameters 3 as the other partitioning tools with which we compare our results. For some special parameters only available on certain tools, we keep the default values. The imbalance factor is set universally to 5%, as it is considered a rather acceptable imbalance tolerance.

Furthermore, we perform experiments on the partitioning quality and the time performance of KGGGP G and KGGGP L and compare them to SCOTCH 6.0.4 and KMETIS 5.1.0 when fixed vertices are not involved in the partitioning, and equally, to SCOTCH 6.0.4, PATOH 3.0 and ZOLTAN 3.81 (SIMPI) when fixed vertices are involved. Note that for the latter case (with fixed vertices), as far as we know, we compare KGGGP with all the available partitioning tools that solve the problem. Since we develop KGGGP G and KGGGP L inside the SCOTCH framework and since SCOTCH provides partitioning solution for fixed vertices problem, we decide to compare all our results relatively to SCOTCH. To perform the experiments, we use graphs from real life numerical applications of DIMACS'10 collection [START_REF] Bader | Benchmarking for graph clustering and partitioning[END_REF], a publicly available collection for experimentation on graph partitioning and graph clustering problems. One finds in Table II some useful information, such as the total number of vertices or the average degree of the graphs used in our experiments.

For the sake of brevity and readability of our experimental results, each bar of the charts in Figures 4 and5 represents the average value of each result for all graphs in our data set. Additionally, note that each experiment is performed 10 times for every graph. In the charts, we present results on edgecut and execution time, while the number of desired parts increases from 10 to 100.

In the first experiment (Fig. 4), we compare the KGGGP algorithms to SCOTCH and KMETIS on the classic graph partitioning problem, that is without using initial fixed vertices. The purpose of this experiment is to exhibit that even though KGGGP is not the best algorithm for the classic problem, the results we obtain are quite good. More precisely, KMETIS produces partitions with minimized edgecut followed by SCOTCH with a 5% increase of edgecut which overall, confirms (as expected) that RB based methods perform better than the greedy ones for this problem. However the edgecut increase for both KGGGP G and KGGGP L is also less than 5% more than that of SCOTCH which proves that KGGGP can be a fine partitioning choice even for classic graph partitioning problems. Additionally, on the results of the execution time, one may notice that the performance of KGGGP G and KGGGP L compared to SCOTCH and KMETIS becomes slower as the number of parts increases which is not surprising if we recall its time complexity compared to RB based algorithms. However, note that KGGGP L obviously successes to reduce the execution time compared to KGGGP G and is not much slower than SCOTCH or KMETIS.

Following, we present results with fixed vertices in Figure 5 from two experimental cases, each representing a different way to distribute the initial fixed vertices to the graph, before the partitioning. We denote schemes bubble and repart. In the bubble scheme, we simply compute k initial seeds as explained before (based on BFS [START_REF] Diekmann | Shapeoptimized mesh partitioning and load balancing for parallel adaptive FEM[END_REF]), and we use each one as the center of a bubble in order to add more fixed vertices. Particularly each bubble, which may be seen as an initial part of fixed vertices, grows using the levelset algorithm until it reaches 20% of the desired part size. For the repart scheme, we follow the repartitioning scheme proposed by ZOLTAN [START_REF] Catalyurek | A repartitioning hypergraph model for dynamic load balancing[END_REF], where an initial partition is used, and its total vertex weight is randomly modified in order to obtain 50% of load imbalance. Based on the above imbalanced partition, we build an enriched graph adding one single fixed vertex per part along with the migration edges that connect it with its respective part. Note that PATOH, and ZOLTAN are hypergraph partitioning tools, and do not handle simple graph structure. For these purpose we convert our test graphs to hypergraphs, but as expected we do not take into account this overhead in the total execution time of the algorithms. Consequently, KGGGP G and KGGGP L have the best partitioning quality among the other tools and obtain up to 20% increase on edgecut minimization for bubble scheme and around 10% for repart scheme compared to SCOTCH. Furthermore, ZOLTAN produces partitions with slightly better quality than SCOTCH for the bubble scheme, but exhibit a 10% increase of edgecut compared to SCOTCH for the repart scheme. As one may see, PATOH does not give good results for any of the experiments with fixed vertices. Regarding the performance results, one may notice that KGGGP L is most of the times the fastest tool, except when the number of parts becomes large enough. Note also that KGGGP G is always slower than KGGGP L while PATOH and ZOLTAN are more than two times slower than the SCOTCH reference. The obvious reason for the above results is the more complicated structure of hypergraphs which impose the use of more time consuming partitioning algorithms.

VI. CONCLUSION AND FUTURE DIRECTIONS

In this paper, we revisit the belief that RB based methods, which are extensively used for classic graph partitioning problem, fall short when initial fixed vertices are involved in the partitioning. Considering the above argument, we present here a new graph partitioning method integrated in the SCOTCH multilevel framework that solves the above problem.

More particularly, the KGGGP algorithm is a direct k-way greedy graph growing partitioning algorithm that successfully handles initial fixed vertices and produces partitions of better quality. Indeed, after performing experiments on real-life graph applications, where we evaluated all available partitioning tools that handle fixed vertices, we concluded that KGGGP manages to minimize the edgecut and achieve, almost always, good execution time. The above results lead us to believe that RB based algorithms are not suitable for partitioning with initial fixed vertices, despite their good performance. Thus, we believe that k-way direct graph growing algorithms, like KGGGP should be used instead. Finally, one of our future goals is to apply the KGGGP algorithm for the load-balancing of complex coupled simulation, using a recent technique proposed by the authors in [START_REF] Predari | Coupling-aware graph partitioning algorithms: Preliminary study[END_REF], that is based on biased partitioning with fixed vertices. Since KGGGP is the most suitable partitioning algorithm for such problems, we expect better load-balancing results for coupled simulations.

Fig. 1 .

 1 Fig.1. Given initial fixed vertices, comparison of two different initial partitioning methods (RB and KGGGP) in a multilevel framework, before the refinement phase. Partition in 4 of a simple two-dimensional grid: the RB method fails to extend an initial partition when the part numbering is not appropriate, while the KGGGP method succeeds.

Fig. 2 .

 2 Fig. 2. The KGGGP algorithm. Input: graph G = (V, E) Input/Output: partition array part[] (of size |V |), initialized with fixed and vertices 1: % initialization step of gainbucket structures (H REG , H N CC and H N BC ) 2: H REG ← initialize with all displacements (v, p) of any free vertices v to any parts p 3: H N BC ← ∅ 4: H N CC ← ∅ 5: % main loop 6: while there are free vertices do 7: % select the best displacement 8: repeat 9: if H REG is not empty then 10: (v, p) ← consider a displacement with maximum gain from H REG 11: if part p is empty then 12: choose (v, p) 13: else if balance constraint is not respected for displacement (v, p) then 14: move (v, p) from H REG to H N BC 15: else if connectivity constraint is not respected for displacement (v, p) then 16: move (v, p) from H REG to H N CC 17: else 18: choose (v, p) 19: end if 20: else if H N CC is not empty then 21: (v, p) ← consider a displacement with maximum gain from H N CC 22: if balance constraint is not respected for displacement (v, p) then 23: move (v, p) from H N CC to H N BC 24: else 25: choose (v, p) 26: end if 27: else if H N BC is not empty then 28: (v, p) ← consider a displacement with maximum gain from H N BC 29: choose (v, p) 30: end if 31: until a displacement (v, p) is chosen 32: % perform the chosen displacement (v, p) 33: part[v] ← p 34: % update buckets 35: remove (v, p) from gain bucket structures 36: remove (v, p ) where p = p from gain bucket structures 37: for all vertex v adjacent to v do 38: for all parts p do 39: update the gain of displacement (v , p ) in gain bucket structures 40: if (v , p ) ∈ H N CC and p = p then 41: move (v , p ) from H N CC to H REG 42: end if 43: end for 44: end for 45: end while

Fig. 3 .

 3 Fig. 3. Steps of KGGGP while partitioning a simple grid in 4 parts.

Fig. 4 .

 4 Fig. 4. All experimental results on classic partitioning (without fixed vertices) on quality and performance of KGGGP and other partitioning tools.

Fig. 5 .

 5 Fig. 5. All experimental results on partitioning with fixed vertices on quality and performance of KGGGP and other partitioning tools.

TABLE I GRAPH

 I AND HYPERGRAPH PARTITIONING TOOLS.

	Tools	Type	Fixed	Parallel Scheme Initial Part. Available
	METIS

  They formulate the problem of reassigning fixed vertices to parts as a maximum weight bipartite graph matching problem, where the edge cut remains minimized. We refer to this method in table I as RB . Finally, they use k-way refinements during the uncoarsening phase with the condition that fixed vertices are locked to their parts. Their experiments with fixed vertices show an edgecut improvement compared to the multilevel RB-based method used in PATOH. However, as it is mentioned in table I their implementation, KPATOH is not publicly available, therefore in the experiments we can only compare their result indirectly with PATOH.

	hypergraph	yes	yes	MLRB	-	source
	resulting partition.

TABLE II LIST

 II OF GRAPHS USED FOR EXPERIMENTS FROM THE POPULAR DIMACS'10 COLLECTION.

	group	graph	# vtx	# edges avg d •	min d •	max d •
	walshaw	fe rotor	99 617	662 431	13.30	5	125
	walshaw	144	144 649	1 074 393	14.86	4	26
	walshaw	wave	156 317	1 059 331	13.55	3	44
	walshaw	m14b	214 765	1 679 018	15.64	4	40
	matrix	audikw1	943 695 38 354 076	81.28	20	344
	matrix	ecology1	1 000 000	1 998 000	4.00	2	4
	matrix	thermal2	1 227 087	3 676 134	5.99	2	10
	matrix	af shell10	1 508 065 25 582 130	33.93	14	34
	numerical NACA0015 1 039 183	3 114 818	5.99	3	10
	numerical 333SP	3 712 815 11 108 633	5.98	2	28
	numerical NLR	4 163 763 12 487 976	6.00	3	20
	numerical adaptive	6 815 744 13 624 320	4	2	4

  % initialization step of gain bucket structures (H REG , H N CC and H N BC ) 2: H REG ← initialize with all displacements (v, p) of any free vertices v to any parts p 3: H N BC ← ∅ 4: H N CC ← ∅ 5: % main loop 6: while there are free vertices do else if balance constraint is not respected for displacement (v, p) then 14: move (v, p) from H REG to H N BC 15: else if connectivity constraint is not respected for displacement (v, p) then 16: move (v, p) from H REG to H N CC N CC is not empty then 21: (v, p) ← consider a displacement with maximum gain from H N CC 22: if balance constraint is not respected for displacement (v, p) then 23: move (v, p) from H N CC to H N BC

	7:	% select the best displacement
	8:	repeat
	9:	if H REG is not empty then
	10:	(v, p) ← consider a displacement with maximum gain from H REG
	11:	if part p is empty then
	12:	choose (v, p)
	13:
	17:	else
	18:	choose (v, p)
	19:	end if
	20: else if H 24: else
	25:	choose (v, p)
	26:	end if
	27:	else if H N BC is not empty then
	28:	(v, p) ← consider a displacement with maximum gain from H N BC
	29:	choose (v, p)
	30:	end if
	31:	until a displacement (v, p) is chosen
	32:	% perform the chosen displacement (v, p)
	33:	part[v] ← p
	34:	% update buckets
	35:	remove (v, p) from gain bucket structures
	36:
		REG
	42:	end if
	43:	end for
	44:	end for
	45: end while

remove (v, p ) where p = p from gain bucket structures 37:

for all vertex v adjacent to v do 38:

for all parts p do 39:

update the gain of displacement (v , p ) in gain bucket structures 40:

if (v , p ) ∈ H N CC and p = p then 41: move (v , p ) from H N CC to H

Hypergraph is a generalization of graph wherein edges may connect more than two vertices[START_REF] Berge | Graphs and Hypergraphs[END_REF].

The code of KGGGP is publicly available in MetaPart library http: //metapart.gforge.inria.fr.

Parameters:

iterations of initial partitioning, HEM for coarsening, maximum coarsest graph size equal to 30 × k, FM refinement with 10 passes and a maximum number of negative moves allowed set to 100 for each refinement pass.


Proposition d'article pour Antonin Cohen, Bernard Lacroix et Philippe Riutort (coord.), Manuel de science politique, coll. « Grands repères », Paris, La Découverte, 2015 (encadré) L'administration et le quotidien Jean-Marc Weller La science politique invite depuis longtemps à s'intéresser à la conduite ordinaire des administrations, avec leurs fonctionnements informels et autres jeux de pouvoir. Avec la sociologie des organisations et la sociologie des politiques publiques, une littérature impressionnante par sa fécondité a même pu faire que tout avait été dit à propos de l'administration, de sa bureaucratie, de ses capacités d'innovation ou de résistance au changement. Et pourtant. Dans ce champ parfaitement balisé, Michael Lipsky introduit, au début des années quatre-vingt, une perspective inédite en s'intéressant à la « street level bureaucracy » [START_REF] Lipsky | Street Level Bureaucracy : dilemnas of the individual in public services[END_REF], ces scènes de guichets, de boxes d'accueil et de comptoirs qu'il explore en tant que politiste, pour montrer qu'elles constituent un maillon incontournable de la production de l'action publique.

Ce renouvellement a fait écho, en France, aux recherches menées sur l'administration depuis une vingtaine d'années [START_REF] Weller | La modernisation des services publics par l'usager : une revue de la littérature (1986-1996)[END_REF]. Confrontés à la fois au management public consacrant la relation de service comme un élément majeur de sa « modernisation », et inspirés par l'essor des approches microsociologiques dans les sciences sociales, les chercheurs ont fait du rapport aux usagers un objet d'investigation privilégié pour rendre compte, au-delà des interactions ordinaires qu'il s'y déploie, du sens et des transformations des institutions publiques [START_REF] Warin | Les usagers dans l'évaluation des politiques publiques. Etude des relations de service[END_REF]. Deux démarches méritent d'être distinguées.

La première s'inscrit dans la longue tradition de l'observation ethnographique (Beaud et [START_REF] Weber | Guide de l'enquête de terrain[END_REF] consistant, par immersion sur le terrain, à faire émerger des manières de voir et de penser propres aux petits bureaucrates que le chercheur accompagne, à l'épreuve du guichet. C'est, parmi les travaux récents sur le monde de l'administration, les recherches d'inspiration bourdieusienne qui ont mené le plus loin cette investigation. Qu'il s'agisse des guichetiers des caisses d'allocations familiales [START_REF] Dubois | La vie au guichet. Relation administrative et raitement de la misère[END_REF], des facteurs [START_REF] Cartier | Les facteurs et leurs tournées. Un service public au quotidien[END_REF], des fonctionnaires des préfectures [START_REF] Spire | Les métamorphoses de la Poste. Professionnalisation des conseillers financiers[END_REF], des employés de la poste (Siblot, 2006) ou du travail social [START_REF] Serre | Les coulisses de l'Etat. Enquête sur les signalements d'enfants en danger[END_REF], étudier le quotidien de l'administration, c'est s'interroger sur les habitudes, les dispositions, les mentalités de ces agents de base dans leur confrontation au public. A propos des pauvres, des étrangers ou des classes populaires, le chercheur s'intéresse alors à la variabilité des pratiques locales des guichetiers et aux ajustements qu'ils déploient à l'endroit des usagers, compte tenu de la place qu'ils occupent et de leur propre trajectoire biographique, tout en considérant les transformations engagées par le management. Car la question centrale est bien ici de décrire le rapport, socialement construit, qui se noue -ou se dénoue -entre l'Etat et les usagers, depuis la scène ordinaire où se joue leur rencontre, de part et d'autre des guichets.

La seconde démarche prolonge également la tradition de l'observation ethnographique mais en focalisant l'attention sur l'action en train de se faire [START_REF] Piette | Ethnographie de l'action. L'observation des détails[END_REF]. L'essor des approches pragmatiques de l'action publique ou le renouvellement des analyses de la sociologie du travail contribuent, de ce point à de vue, à s'intéresser à l'administration depuis les activités réellement accomplies par ses agents. Qu'il s'agisse des techniciens des caisses de Sécurité Sociale [START_REF] Weller | L'Etat au guichet. Sociologie cognitive du travail et modernisation administrative des services publics, coll. sociologie économique[END_REF] ou des magistrats du Conseil d'Etat (Latour, 2003), l'enjeu n'est pas tant ici de saisir la rencontre entre des agents et des usagers aux plus bas de l'échelle que de suivre le cours d'une décision publique, depuis la lente et patiente fabrication des dossiers. Dès lors, c'est l'épaisseur du travail administratif qui intéresse ici, au guichet comme au bureau, avec ce qu'il engage comme activités d'écriture, de calcul, de signature, de manipulation de papiers et de fichiers, et dont l'enjeu porte sur la qualification juridique des faits [START_REF] Munoz | Prendre en charge un accident du travail : une activité de qualification à l'épreuve de la précarisation[END_REF][START_REF] Fraenkel | Le travail des huissiers : transformations d'un métier de l'écrit[END_REF]. La consistance, ou le délitement possible, des institutions ne renvoie pas nécessairement au rapport social qui se joue dans le face-à-face du bureaucrate et de l'usager, et dont le dénouement reposerait sur des dispositions d'arrière plan. Elle renvoie plutôt à la manière dont la longue chaîne sociotechnique de guichets, de bureaux, de commissions, de front office et de back offices est concrètement agencée (Hanique, 2004 ;[START_REF] Weller | L'Etat au guichet. Sociologie cognitive du travail et modernisation administrative des services publics, coll. sociologie économique[END_REF], et dont procède aussi bien la consistance des fictions politiques dont se réclament les fonctionnaires que le sens même de leur travail. 00.-Bien plus que des oppositions stériles d'école, ces deux démarches témoignent avant tout de perspectives différentes qui, parfois, se rejoignent. C'est le cas de l'intérêt que l'une, comme l'autre, porte aujourd'hui à la dimension historique. Cet enjeu peut consister, pour la première, et dans le cadre d'une démarche qualifiée de « socio-historique » (Payre et Pollet, 2013), à restituer les pratiques administratives des bureaucrates à partir des archives ou des témoignages, compte tenu du statut des employés, de leur dispositions ou des politiques locales (Buton, 2008), et plus largement de la construction des identités professionnelles des agents par lesquels l'Etat s'incarne et de leur transformation (Vezinat, 2012). Ce même enjeu conduit, pour la seconde, à mobiliser les travaux rassemblés sous l'étiquette commode des sciences and technology studies (STS)


Wm Dennis Par

Emmanuel Huber

Charrier

JD, DBA, CPA, CFE Wm Dennis Huber

Emmanuel Charrier

PARTIE III EXPERTISE, JUSTICE, JURICOMPTABILITÉ IS IT TIME TO REGULATE FORENSIC ACCOUNTING?

Both * in US common law or in French codified law, Forensic Accountants aim to serve justice 1 , by illuminating technical, financial facts in the context of a dispute or a trial 2 .

fraud and special investigation" 4 . French Forensic expertise is called "Expertise comptable judiciaire". The main difference is due to the fact that French experts are chosen by the judge to help him, whilst US experts are chosen by litigants. Beyond the procedural specificities there is much in common between the two practices: quantification of damages, business valuation, fraud investigation, and knowledge of the rules of evidence and procedure are the main specialized knowledge of both US and French Forensic Accountants 5 .

Prof. Huber has been involved for many years in studying US Forensic Accounting and especially professionalism, ethics, certifications, training and standard-setting in the field. He has published several articles 6 , and coordinated a 4 -AICPA, FVS Practice Aid 10-1 : Serving as an expert witness or consultant, 2010.

5 -See Charrier E., "L'expert-comptable judiciaire et le Certified Fraud Examiner", Institut France-Amériques and Cnecj, "Recherche et détection des fraudes : un défi pour l'institution judiciaire", oct. 2014, Paris (actes à venir), and Blaise N. et al., Manuel d'expertise judiciaire comptable, Anthemis, Bruxelles, 2011. See also Labelle R., Saboly M., « Forensic accounting in France, emergence and development », Journal of Forensic Accounting, 9(1), 2008, 83.

6 -W.D. Huber, "A comparison of Forensic accounting corporations in the USA", Journal of Accounting, Ethics & Public Policy, 12(3), 2011, 301 [2011] ; "Is Forensic Accounting in the United States Becoming a Profession?", Journal of Forensic & Investigative Accounting, 4(1), 2012, 255 [2012] ; « Should the forensic accounting profession be regulated?", Research in Accounting Regulation, 25, 2013, 123 [2013a] ; "Forensic accounting corporations' codes of ethics and standards of practice -a comparison", Interna-Forensic Accounting anglo-saxonne et expertise comptable judiciaire sont bien plus proches qu'on le pense souvent.

special issue of the Journal of Forensic and Investigative Accounting about international forensic systems.

The following article follows an interview of Dennis Huber by Emmanuel Charrier in July, 2014 in Paris.

E. Charrier (EC) -Professor Huber: in the USA, anybody can state that he is a Forensic Accountant, and offer such services, isn't it? This practice isn't regulated? D. Huber (DH) -No, it isn't. It is really common because private initiative and free competition are major policy principles in the United States. Professional associations have therefore supported these services. Furthermore US trial rules are based on orality -that means that the so called forensic accountant must be able to testify and his credibility and his knowledge will be challenged by opposing counsel in front of the Court.

EC -But you suggest that the current private regulation system fails to support the strong values requested by the Courts, and you conclude that it is time for States to be concerned about this activity. DH -in the common law system, forensic accounting services are usually solicited by lawyers and lawyers pay attention to the qualifications of the experts 8 . Actually, it is important that the expert authority is well recognized in front of the Court, because the more he is recognized the more his analysis and his opinion will be received by the judge and the jury. Now a forensic accountant must not only master the accounting techniques but also specific forensic techniques -quantification of damage, etc.and, moreover, the rules of procedure and evidence. That is why it is relevant for an expert to be a member of a recognized forensic organization, and better, to hold a certification issued by this organization.

But nowadays, in the United States, there is no less than seven specialized forensic organizations, offering six forensic accounting certifications (see Table 1). This is not healthy because these associations suffer many amazing ambiguities: many of them are "for-profit" and hardly mention it and in any case do not publish their accounts; many of the leaders of these associations have no recognized qualification in forensic accounting (academic degrees ...).Many of these organizations do not have a code of ethics and / or are not able to make it effective 9 (see EC -So, in your view, private organizations regulating forensic accounting fail to be transparent about their operations. Does it question the benefits expected by their members? DH -Yes. Such transparency requirement is more precisely the requirement of behaviour alignment of these associations' officers with the goals given to them. The survey I conducted in 2011 revealed that these requirements (officers' qualification, status, etc…) are shared by the vast majority of these associations' members, although some of them may be misinformed about the reality of their organization (e.g., the for-profit status: experts see more sense to a non-for-profit status). As Mason writes 2010: "[C]ompliance with standards and ethics is the most deadly cross-examination subject. If expert witnesses appear to be unable or unwilling to accounting oversight have endorsed a label called "IFA", which is only for CPA (with credentials and examination), and has enacted standards which are audited during the quality reviews. Since the ICCA (now-called "CPA Canada") entered into an agreement in 2014 with the AICPA, the CA-IFA label still isn't supported. Canadian CPA-IFA will qualified as CPA-CFF. 10 -Table 2

from [2011], [2013b], [2013c].
follow their own profession's rules, how can the trial court accept that the testimony they provide is actually independent and objective?"

11 . Forensic accountants are certified by associations whose status is contrary to what forensic accountants consider important (non-for-profit status is the right status for public service).

Is the system different in France?

EC -Really different. The "Judicial expert" status comes from the inscription on the list of judicial experts12 maintained by the Courts of Appeal, which enroll few new experts every year and carry a five-year review of the lists. A lot of applicants, few enrolled, at the discretion of the Courts, considering their needs, and both the experience and the reputation of the candidate 13 . 15 . The title is well-recognized but it isn't a profession, only a "function".

organization
14 -The expert is quite a delegate of the judge, and must follow specific proceedings rules. The judge is free not to use the report of the expert. See Conseil national des compagnies d'experts de justice (CNCEJ) « Brochure Europe » (French and English), retrieved from http://www.cncej.org/documents/uploads/315_Brochure%2 0Europe.pdf, 31 Aug. 2015. The CNCEJ is the federal organization of forensic associations. This private organization is enacted to serve de public judicial interest. For each forensic specialty, one can find a not-for-profit association. Two associations focus on finance and accounting. Around 2/3 of judicial experts are members of one association. These associations promote ethical standards, organize continuous training and various meetings between experts and judges. These associations don't issue certification but a few of them organize a two-three years training for applicants 17 . The associations are not disciplinary: the experts' discipline is ruled by the Courts, and could strongly impact a forensic accountant. Exclusions are rare, but inquiries are not 18 . Beyond that, French proceedings don't include examination nor cross-examination of experts in front of the court. But, before reporting to the court, the expert has to discuss a draft of his report with litigants. It's an effective way to DH -regulating an activity is necessary when it impacts legal rights, and when it disturbs the effective market competition. Nowadays the forensic accounting market is around $ 5,000m a year and this market is growing 19 . The fact that the AICPA launched its own certification in 2011 -a very rare event in this organization! -and the decision of the AAA 20 to launch a new academic journal dedicated to the specialty, confirm that the forensic services has grown significantly in the accounting and financial matters. The specialty is no longer a branch of public accounting, it definitely meets all the criteria to qualify as a profession: specialized body of knowledge, governing admission standards, code of conduct, formal membership, performance of the service with the aim to serve common good ... only altruism is not clear but this requirement is no longer valid in contemporary sociology (Brante, Pavalko 21 ...). In this context, the ambiguities about values, and the conflicts 22 between associations, should be not normal. According to Williams 23 the public interest is particularly involved in forensic accounting, and it would be helpful if States shall 19 -Tysiac, K., "Demand strong for forensic accountants in wake of financial crisis", CPA Insider, 2012. Available from http://www.cpa2biz.com/Content/media/producer_ content/Newsletters/Articles_2012/CPA/SEP/ForensicAcco unting.jsp) 20 -The American Accounting Association is the largest Anglo-American academic association in audit and accounting matters. The AAA publishes well-recognized journals (The Accounting Review, Auditing -a journal of practice and theory, Accounting Horizons, Issues in Accounting Education, Journal of Information Systems,…), quite involved in statistical causal analysis and modelling. See authorize the use of this title under the conditions discussed above.

EC -I think that many French legal professionals agree with this conclusion. According to Garapon and Papadopoulos 24 , matters of general interest are a monopoly of the French State. But for many years, at the same time one notices less State rules. For example, the criminal policy has changed. There are fewer criminal expert investigation. Then the police have to succeed in technical matters that they didn't used to manage. Or the litigants themselves have to pay for private investigation 25 . In civil and commercial matters 26 , the Supreme Court recently ruled that the report of a forensic counsel (a private expert) named by a litigant (and not by a judge) can now be taken into account as an offer of evidence by the judges, except if there is no other evidence to support the report 27 . As a result, private expertises increase. A recent study valuates the French financial forensic market 28 around € 500m 29 . Several categories of experts act as forensic counsels : judicial experts; specialized experts (insurance experts, ...); Economists, CPA, Business consultants... These counsels examine the offer of proof. They could also assist the litigants during the course of the judicial expertise… 24 -Garapon A., Papadopoulos I., Juger en Amérique et en France, Odile Jacob, 2003. 25 -Compagnie des Conseils et Experts financiers, conference, Le juge, l'avocat et l'expert de partie : quelles évolutions dans la gestion des litiges ?, Paris, Oct. 2011. 26 -The French system encompasses the civil and commercial, the criminal, and the administrative cases. The criminal order is largely an inquisitorial system, the civil and commercial one is an adversarial system, and the administrative order (litigation involving a public body) is largely an adversarial system. 27 -Cour de Cassation (France), Ch. Mixte, 28 sept. 2012, 11-18.710, Huk Coburg c. Trigano. See CNCEJ, Newsletter, 2013, n.47, 4. 28 -i.e. judicial expertise (« expertise de justice ») and forensic counsel (« expertise de partie »). 29 -Durand-Barthez P., Langlart F., Choisir son droit. Conséquences économiques du choix du droit applicable dans les contrats internationaux, L'Harmattan, 2012. That means $5,000m/300m people = 17,000 per 1,000 Americans, vs $600m/60m people = 10,000 per 1,000 French people. It's important to note that in France court expertises are no more than a third of these figures, see Pelisse et al., op. cit. L'intérêt général est aujourd'hui en jeu en matière de Forensic Accounting. La régulation doit désormais passer par les États.

DH -The same in the USA. Crumbley 30 summarized that by stating that forensic accountant haven't to follow GAAP -the monopoly of CPAs.

EC -Indeed: the issue was discussed last year and it was stated that judicial accounting experts don't need to be registered as CPA 31 . Accounting and financial assistance is not under the monopoly of French CPAs.

DH -It seems that US and French forensic accounting services are closer than one thinks, isn't it? Except for the fact that it's less common that US courts name experts to assist them; US forensic accountants usually are named by litigants as expert witnesses, but must act in the interest of justice even if this could be contrary to the interest of their client. How do French forensic counsels play with truth? EC -the issue stirred the world of expertise two years ago. The editor of a specialized journal, often (but wrongly) equated to forensic associations, signed a vigorous editorial 32 , arguing that what distinguishes the forensic counsel (the private expert) from the judicial expert is its right to lie ... then the journal welcomed un article 33 claiming that a court expert can't, in a private mission, behave other than he would have done as a judicial expert, and the President of the Paris' Court of Appeals said that if he caught such a fault from a court expert, it would have to meet in disciplinary proceedings. The editorial was a provocation however it expressed, in my view, what many technicians feel in contact with belligerents and lawyers, who see in the forensic counsel a "fighter" to their sides. And the issue is difficult: lawyers lack the technical expertise to appreciate what accounting and financial points must be questioned, highlighted, discussed, analyzed, or according 30 -Crumbley, D. L., "So what is forensic accounting?" The ABO Reporter, 2009, Fall (9). 31 -Millot P.A., "l'expert-comptable, expert judicaire, face à de nouvelles missions » and « Le congrès de Lyon », Revue française de comptabilité, 2014, Oct., 21 and Dec., 22. 32 -Peckels B., « Editorial », Revue Experts, 2011, Déc. 33 -Fassio F., Kerisel J.B., Loeper P., « Non l'expert de justice ne peut mentir ! », Revue Experts, 2012, Février. The authors were the president and past-presidents of the CNECJ (see note 15).

to what timing it makes sense to do so. It is therefore tempting to associate the forensic counsel to this legal strategy. It seems complicated, moreover, that the lawyer hires two experts, one for advises him and the other to reflect his objective opinion. DH -but the expert leaves the passive mode that the judge is waiting after, to check the technical facts.

EC -with this difference that in French proceedings, the court expert can contradictorily discuss with counsels during the expertise meetings, so that the evidence is gradually cobuilt, and to some extent collegially stated 34 . Furthermore it has been observed that judges cultivate an "art of the draw" by selecting in the forensic expert's report such items they needed 35 . Are expert witnesses not exposed to the solicitations -e.g. to discuss the discovery or to suggest questions to ask during the crossexamination? DH -this "strategic contribution" seems smaller because ultimately the expert's objectivity will be weighed in front of the court, by the public cross-examination. Moreover in some courts exchanges between the expert and the lawyer may be discovered.

EC -but a large part of affidavits are closed before being stated in Court, right?

DH -Right. Not in France?

EC -There are no statistics in such matters. But a lot of judicial expertises are decided before the plain trial 36 and a large part of such expertises are not followed by a plain trial. That suggests that well-managed forensic expertises give an end to a significant part of litigations. It comes back to the question of behaviour and transparency ... but you mentioned the sociological studies relating to professions. Several sociological studies are really critical about forensic expertise, analyzing that as a "small world" closing its field and promoting or stig-34 -Charrier E., Pelisse J., "Conventions at Work: On Forensic Accountant's Intermediation", Economic Sociology -ESEEN, vol. 14 (1), 2013, 31. 35 -Dumoulin L., "L'expertise judiciaire dans la construction du jugement, de la ressource à la contrainte", Droit et Société, 44/45, 2000, 199. 36 -Pre-trial proceedings ("art. 145 CPC") or urgent proceedings ("référés"). It must be noted that these proceedings aren't similar to discovery.

Le développement, en France, de l'expertise de partie (forensic counsel), fait bouger les lignes de l'expertise judiciaire (judicial expertise).

Comment traiter du rapport de l'expert à la vérité ?

Numéro 3 -Les Cahiers du Chiffre et du Droit -2015 matizing behaviours according to powers views rather than the public interest's service. Critics often involve psychological matters in criminal cases 37 where the judicial expert (sometimes a "serial expert"38 ) could be seen as a fighter of the judge. But technical expertise (construction, engineering, IT, accounting) could be criticized too, because there a many "grey areas" in these techniques, and the judicial expert is often questioned about good practices -not scientific rules. Sociologists question the rhetoric of power of judicial experts, following studies about lawyers [START_REF] Sarat | Law and Strategy in the Divorce Lawyer's Office[END_REF] . Are the Daubert and Kumho Tire cases [START_REF] Dow Pharmaceuticals | [END_REF] effective in this matter?

DH -These court decisions changed the forensic practices: techniques used by the experts have, now, to be based on published, tested and shared references. This has undoubtedly contributed to develop forensic organizations, and increased technical and scientific publications related to the forensic services in the accounting journals. It probably also favored the rise of new journals: Journal of Forensic Accounting (no longer published), Journal of Forensic and Investigative Accounting, Journal of Forensic Studies in Accounting and Business 41 … In my view, the specific body of knowledge of a profession which deals with the public interest must be analyzed, discussed, and shared. 46 : Stone and Miller reduce forensic accounting to financial fraud issues (excluding judicial matters, damages quantification, wit-nessing…), with an emphasis on the role of auditors. To analyze current publications, they do not include non-AAA journals (JFA, JFIA, JFSAB). These studies postulate that accounting research journals don't publish professional studies nor include professional in editorial boards. Defining "forensic accounting research that matters" without seeking professionals is problematic according to the fact that profes- La jurisprudence Daubert est-elle la réponse aux attentes en matière de transparence de l'expertise ? sionals don't read academic journals 47 . It is also noteworthy that the well-recognised AAA journals 48 , gradually concentrated towards econometric or statistical publications for a specialized academic readership. If the aims of the AAA, and academics is to contribute to a better knowledge of the techniques, issues and challenges of forensic accounting, we have to reconsider these pitfalls.

EC -According to our discussion on ethics and quality, one can conclude that studies and debates just begin about forensic accounting services and that we need in-depth comparison to assess the models 49 . The following table could be a synthesis, and a proposal, to think about the quality issues 50 . Thank you for this interview, Pr. Huber. DH -My pleasure. Thank you.

  17 -See Pelisse J. et al., Des chiffres, des mots et des lettres, sociologie des experts judiciaires, Armand Colin, 2012. The three forensic associations are : Cnecj (« compagnie nationale des experts comptables de justice »), Cnejfd (« compagnie nationale des experts judiciaires en finance et diagnostic ») and Cneact (« compagnie nationale des experts en activités commerciales et techniques »). 18 -See Dumoulin, op. cit.

  [2014b].21 -Brante, T., "Sociological Approaches to the Profession", Acta Sociologica 31(2), 1988, 119 ; Pavalko, R.M. Sociology ofOccupations and Professions, 1988, 2nd ed. Peacock Publishers, Inc. See [2012].22 -See [2013a], 12723 -Williams, J. W., Playing the corporate shell game: The forensic accounting and investigation industry, law, and the management of organizational appearances. Doctoral Dissertation, Dissertation Abstracts International. Toronto: York University.

  42 -Bouchon F., L'évaluation des préjudices subis par les entreprises, Litec, 2002 is the main French book in such matter. Articles are published in the magazine of the forensic accountant association (Cnecj) and in few business magazines (Décideurs-Strategie Finance Droit, Option Finance) and law journals (Gazette du Palais, JCP). Les Cahiers du Chiffre et du Droit aim to publish forensic articles.43 -Nowadays, Cnecj is the main organization for forensic financial trainings and conferences.44 -Comp about the French CPA profession, Ramirez C., "la règle et la norme : des grands cabinets d'audit multinationaux et de la place qu'ils occupent dans la profession comptable libérale », in Gadéa C., Demazière D. (eds), Sociologie des groupes professionnels, LaDécouverte, 2009, 129. 45 -[2014b].46 -Stone D.N., Miller T.C., "The states of, and the prospects for, forensic and fraud research that matters", Journal ofForensic and Investigative Accounting, 4(2), 2013, 35.

Table 1 7

 1 -US organizations and certifications

	tional Journal of Auditing, Accounting and Performance
	Evaluation, 9(2), 2013, 126 [2013b] ; "Forensic Account-
	ants, Forensic Accounting Certifications, and Due Dili-
	gence"; Journal of Forensic & Investigative Accounting, 5(1),
	2013, 182 [2013c]; Forensic Accounting: An Anglo-
	American Comparison -Forensic Accounting in the

U.S.A.", Journal of Forensic & Investigative Accounting, 6(3), Special International Issue, 2014, 154 [2014a]

; Research in forensic accounting -what matters?", with J.A. DiGabriele, Journal of Theoretical Accounting

Research, 10(1), 2014, 40 [2014b]

. These papers follow fieldwork researches.

7 -

Table 1 from [2013a], [2013b], [2014].

  15 -For example : « Emmanuel Charrier, expert près la Cour d'appel de Paris » 16 -From Leclerc G. et al., Expertise de justice et juricomptabilité, Thomson-Yvon Blais, 2012. There are around 1,000 French Forensic Accountants registered by a Court of Appeals (and few others financial specialists such registered: bank experts…). See Pelisse et al., op. cit. There is no statistic about Forensic Counsels. For a presentation, see Leaders League, Guide Décideurs Risk Management Contentieux et Assurances, 2014/2015.

Table 3

 3

	16 -an international comparison

  EC -Which brings us to one last topic, what body of knowledge do we need to share? In France the specialized technical literature is quite limited. Publications are mainly oriented towards the knowledge of the rules of procedure and evidence, which are significantly different from trade communication in the business world or in public life. That makes sense that lawyers are often mandatory in judicial matters.

	But the specific technical issues of dispute
	situations are analyzed as an implicit knowledge
	of well-recognized experts. Books and journals
	articles are very rare	42 , and forensic accounting
	knowledge is mainly shared during symposia or
	seminars issued by forensic associations 43 . One
	can suggest that the field is fenced by the actors,
	promoting their identification 44 ... what about
	the USA?
	DH -It is the subject of a recent debate initi-
	ated by the American Accounting Association.
	The AAA decided in 2011 that a specialized
	academic journal could be launched. Its first
	issue is not yet published. I recently argue, with
	James A. DiGabriele 45 , that the project lacked of
	analysis, like the study published by Stone and
	Miller on "forensic accounting research that mat-
	ters"

Table 4 -

 4 enhancing quality of forensic accounting 47 -[2014b]. 48 -E.g. The Accounting Review, see note 204. 49 -One can note such a way in Europe: for 4 years, the Council of Europe have included a chapter about forensic services in its report on "Evaluation of judicial systems" conducted by the European Commission for Efficiency of Justice (Cepej). http://www.coe.int/t/dghl/cooperation/cepej/evaluation/def ault_en.asp. 50 -J.A. DiGabriele, « An Empirical View of the Transparent Objectivity of Forensic Accounting Expert Witnesses. », SSRN, 2010.

	Comment partager les connaissances
	importantes -et quelles connaissances -
	en matière de Forensic accounting ?
			forensic accounting
			quality:
		sponsored by a			guaranteed by an
		valuable			audited practice
		organisation
	competent and	Statement and	judicial control:	accreditation	peri odi ca l re-	reports and file
	transparent	enforcement of	labelling the	bas ed on proved	accreditation, and	works periodically
	governa nce	ethics	accreditation,	experience and	continuous	audited, according
			register the	theori ca l	specific training	such standards
			experts	knowleddge

Numéro 3 -Les Cahiers du Chiffre et du Droit -2015

-Mason, M., "Daubert challenges increase when forensics enter the valuation process". Business ValuationUpdate, 16(8), 2010

. 12 -A law was enacted 10 Apr. 2014 in Belgium (C. 2014/09214, published 19 Dec. 2014), stating a similar list of judicial experts. This system is promoted in Europe by the European Expertise & Expert Institute (EEEI), Expertise de justice -quel avenir pour l'Europe, Bruylant,

2014. 13 -See Heugas-Darraspens H., "Harmonisation du contrôle de la motivation du refus d'inscription initiale sur les liste d'experts judiciaires ?", AJDI, 2014(11), 757 about the Courts' criterias to refuse a candidate, and Dumoulin L. L'expert en justice, de l'invention d'une figure à ses usages, Economica, 2007 about the figure of the judicial expert.

-One can remember the French case « Outreau » (Besnier C. (dir.), "Parole(s): l'affaire d'Outreau", Droit et Cultures, 55-1, special issue, 2008).

-Protais C., Sous l'emprise de la folie. La restriction du champ de l'irresponsabilité psychiatrique enFrance (1950France ( - 2007)), thèse pour le doctorat en sociologie, Paris, EHESS, 2011.