Johannes Starlinger

Sarah Cohen-Boulakia

Sanjeev Khanna
email: sanjeev@cis.penn.edu

Susan B Davidson

Ulf Leser

Layer Decomposition: An Effective Structure-based Approach for Scientific Workflow Similarity

Keywords: BioConsert5, Workflow: mean -0, 4 -0, 2 0 0, 2 0, 4 0, 6 0, 8 1

Scientific workflows have become a valuable tool for large-scale data processing and analysis. This has led to the creation of specialized online repositories to facilitate workflow sharing and reuse. Over time, these repositories have grown to sizes that call for advanced methods to support workflow discovery, in particular for effective similarity search. Here, we present a novel and intuitive workflow similarity measure that is based on layer decomposition. Layer decomposition accounts for the directed dataflow underlying scientific workflows, a property which has not been adequately considered in previous methods. We comparatively evaluate our algorithm using a gold standard for 24 query workflows from a repository of almost 1500 scientific workflows, and show that it a) delivers the best results for similarity search, b) has a much lower runtime than other, often highly complex competitors in structure-aware workflow comparison, and c) can be stacked easily with even faster, structure-agnostic approaches to further reduce runtime while retaining result quality.

I. INTRODUCTION

Scientific workflow systems have become an established tool for creating and running reproducible in-silico experiments. With their increasing popularity, online repositories of scientific workflows have emerged as a means of facilitating sharing, reuse, and repurposing. Examples of such repositories include CrowdLabs [START_REF] Mates | Crowdlabs: Social analysis and visualization for the sciences[END_REF], SHIWA [START_REF]SHIWA workflow repository[END_REF], and the Galaxy repository [START_REF] Goecks | Galaxy: a comprehensive approach for supporting accessible, reproducible, and transparent computational research in the life sciences[END_REF]. Probably the largest workflow collection is myExperiment [START_REF] Roure | The design and realisation of the myexperiment virtual research environment for social sharing of workflows[END_REF], which currently contains more than 2500 workflows from various disciplines, including bioinformatics, astrophysics, and earth sciences. To make the best use of these repositories, users need support to find workflows that match their specific needs [START_REF] Cohen-Boulakia | Search, Adapt, and Reuse: The Future of Scientific Workflow Management Systems[END_REF]. However, currently these repositories only support keyword queries which are matched against textual descriptions, tags, and titles given to the workflows upon upload [START_REF]SHIWA workflow repository[END_REF], [START_REF] Goecks | Galaxy: a comprehensive approach for supporting accessible, reproducible, and transparent computational research in the life sciences[END_REF], [START_REF] Mates | Crowdlabs: Social analysis and visualization for the sciences[END_REF], [START_REF] Roure | The design and realisation of the myexperiment virtual research environment for social sharing of workflows[END_REF]. Obviously, the quality of such a search critically depends on the quality of the annotations associated with workflows.

Scientific workflows typically resemble directed acyclic graphs (DAGs) consisting of global input and output ports, data processing modules, and datalinks which define the flow of data from one module to the next. Two sample workflows from myExperiment are shown in Figure 1. Therefore, another source of information that can be exploited for search is the structure or topology of the workflow [START_REF] Goderis | Workflow discovery: the problem, a case study from e-Science and a graph-based solution[END_REF]. An obvious advantage of structure-based approaches to workflow similarity search is that they do not require any additional information to be provided by the workflow designer apart from the workflow itself. Structure-based approaches are typically used in a second search phase: First, users identify workflows which roughly match their needs using keyword search. In the second phase, users select one candidate workflow and let the system retrieve functionally similar workflows, i.e., the system performs a workflow similarity search.

Several studies have investigated different techniques for assessing workflow similarity using this structure [START_REF] Bergmann | Similarity assessment and efficient retrieval of semantic workflows[END_REF], [START_REF] Friesen | Workflow Analysis Using Graph Kernels[END_REF], [START_REF] Goderis | Workflow discovery: the problem, a case study from e-Science and a graph-based solution[END_REF], [START_REF] Santos | A First Study on Clustering Collections of Workflow Graphs[END_REF], [START_REF] Silva | Similarity-based Workflow Clustering[END_REF], [START_REF] Stoyanovich | Exploring repositories of scientific workflows[END_REF], [START_REF] Xiang | Improving the Reuse of Scientific Workflows and Their By-products[END_REF], but initial results indicate that they perform no better, and sometimes even worse, than annotation-based methods in terms of retrieval quality [START_REF] Costa | Athena: Text Mining Based Discovery of Scientific Workflows in Disperse Repositories[END_REF], [START_REF] Friesen | Workflow Analysis Using Graph Kernels[END_REF], [START_REF] Stoyanovich | Exploring repositories of scientific workflows[END_REF]. However, these comparisons were performed on very small and welldocumented workflow sets, and thus the results should not be extrapolated to the large, but shallowly annotated repositories that exist today. To verify this hypothesis, in prior work we performed a large-scale comparative evaluation of workflow similarity search algorithms [START_REF] Starlinger | Similarity Search for Scientific Workflows[END_REF]. Our results indicated that a) structure-based methods are indispensable for some current repositories which lack rich annotations, b) structure-based methods, once properly configured, outperform annotationbased methods even when such rich annotations are available, and c) any such standalone approach is further beaten by ensembles of annotation-based and structure-based methods. We also discovered that both the amount of configuration required and runtime considerations were drawbacks to such methods: Fast workflow comparison using annotations on the workflows' modules provides best results only when ubiquitous, functionally unspecific modules are removed from the workflows in a preprocessing step. The configuration of which modules are to be removed is specific to a given dataset, and is non-trivial. Methods based on workflow substructures, on the other hand, provide rather stable results across different configurations, but have prohibitive runtimes.

In this paper, we present a novel technique for measuring workflow similarity that accounts for the directed dataflow underlying scientific workflows. The central idea is the derivation of a Layer Decomposition for each workflow, which is a compact, ordered representation of its modules, suitable for effective and efficient workflow comparison. We show that the algorithm a) delivers the best results in terms of retrieval quality when used stand-alone, b) is faster than other algorithms that account for the workflows' structure, and c) can be combined with other measures to yield better retrieval at even higher speed. Furthermore, the method is essentially configuration free, which makes it applicable off-the-shelf to any workflow repository.

In the remainder of this paper, we first review related work on similarity measures for scientific workflows in Section II. In Section III, we briefly summarize results from [START_REF] Starlinger | Similarity Search for Scientific Workflows[END_REF]. Section IV introduces our Layer Decomposition algorithm for scientific workflow comparison, which we comparatively evaluate in Section V. We conclude in Section VI.

II. RELATED WORK

Existing approaches to the assessment of scientific workflow similarity are either based on the associated annotations or on the structure of the workflows themselves. We here name a number of prominent approaches in increasing order of using topological information; for a more detailed comparison see [START_REF] Starlinger | Similarity Search for Scientific Workflows[END_REF]. Using only workflow annotations, Costa et al. [START_REF] Costa | Athena: Text Mining Based Discovery of Scientific Workflows in Disperse Repositories[END_REF] derived bags of words from the descriptions of workflows to determine workflow similarity. Keyword tags assigned to workflows are explored by Stoyanovich et al. [START_REF] Stoyanovich | Exploring repositories of scientific workflows[END_REF]. The sets of modules contained in workflows have been used by Silva et al. [START_REF] Silva | Similarity-based Workflow Clustering[END_REF], Santos et al. [START_REF] Santos | A First Study on Clustering Collections of Workflow Graphs[END_REF], and Friesen et al. [START_REF] Friesen | Workflow Analysis Using Graph Kernels[END_REF]. Bergman et al. [START_REF] Bergmann | Similarity assessment and efficient retrieval of semantic workflows[END_REF] extended this idea by additionally comparing the workflows' datalinks based on semantic annotations; however, such semantic annotations are not generally available in publicly available workflow repositories. Considering workflow substructure, the use of Maximum Common Isomorphic Subgraphs (MCS) has been investigated by Goderis et al. [START_REF] Goderis | Workflow discovery: the problem, a case study from e-Science and a graph-based solution[END_REF], Santos et al. [START_REF] Santos | A First Study on Clustering Collections of Workflow Graphs[END_REF], and Friesen et al. [START_REF] Friesen | Workflow Analysis Using Graph Kernels[END_REF]: the latter also proposed using Graph Kernels derived from frequent subgraphs in a repository. Subgraph comparison has also been applied in similar domains, e.g., by Corrales et al. [START_REF] Corrales | BPEL Processes Matchmaking for Service Discovery[END_REF] to compare BPEL workflows or by Krinke [START_REF] Krinke | Identifying similar code with program dependence graphs[END_REF] to compare program dependence graphs. Finally, using the full graph structure, Xiang et al. [START_REF] Xiang | Improving the Reuse of Scientific Workflows and Their By-products[END_REF] compute scientific workflow similarity from their Graph Edit Distance.

Note that workflow provenance or semantic annotations could also be taken into account; however, we are not aware of any such data being available within current public repos-Fig. 2: Workflow comparison process, see also [START_REF] Starlinger | Similarity Search for Scientific Workflows[END_REF] itories, and therefore do not consider these methods in this paper.

III. PRELIMINARIES

In [START_REF] Starlinger | Similarity Search for Scientific Workflows[END_REF], we report on a comprehensive evaluation of previous approaches to workflow similarity search. In addition to comparing retrieval quality quantitatively, we also introduce a framework (shown in Figure 2) for qualitatively comparing different systems. This is an important tool, as the process of workflow comparison entails many steps, of which a concrete topology-comparison algorithm is just one. First, the similarity of each pair of modules from two workflows is determined using pairwise module comparison. Second, using these pairwise module similarities, a mapping of modules onto each other is established. This mapping may be influenced by the topological decomposition of the workflows imposed by the third step of topological comparison, which in turn uses the established mapping to assess the similarity of the two workflows. Finally, normalization of the derived similarity value wrt the sizes of the compared workflows may be desirable. This process of scientific workflow comparison is preceded by an (optional) additional preprocessing step. Such preprocessing may, for instance, alter the workflows' structure based on externally supplied knowledge about the elements it contains (see Section III-D).

As each of these steps has a notable impact on the concrete values computed and thus the assessment of different algorithms, we describe them in more detail in the following. Note that our novel Layer Decomposition method (described in the next section) is a contribution dedicated to the step of topological decomposition and comparison; in Section V, we will compare different approaches to this step while keeping all other steps constant.

A. Module Comparison

Structure-based approaches to workflow similarity perform some type of comparison of the two workflow graphs. To this end, they must be able to measure the similarity of two nodes in the graphs, which represent two modules in the to-be-compared workflows. Module comparison is typically approached by comparing the values of their attributes. These range from identifiers for the type of operation to be carried out, to the descriptive label of the module given to it by the workflow's author, to rather specific attributes such as the url of a web-service to be invoked. In [START_REF] Starlinger | Similarity Search for Scientific Workflows[END_REF] we compared several combinations of attributes with different weightings and showed that choosing a suitable configuration is most crucial for result quality of structural workflow comparison. Here, we will use the following three schemes to test the impact of module comparison on the topological comparison provided by our new algorithm:

• pw0 assigns uniform weights to all attributes and compares module type, and the web-service related properties authority name, service name, and service uri using exact string matching. Module labels, descriptions, and scripts in scripted modules are compared using Levenshtein edit distance.

• pw3 compares single attributes in the same way as pw0 but uses higher weights for labels, script and service uri, followed by service name and service authority in the order listed. This weighting resembles the proposal of [START_REF] Silva | Similarity-based Workflow Clustering[END_REF].

• pll disregards all attributes but the labels and compares them using the Levenshtein edit distance, which is the approach taken in [START_REF] Bergmann | Similarity assessment and efficient retrieval of semantic workflows[END_REF].

B. Module Mapping

Structural comparison of two graphs may be carried out by comparing all nodes of one graph to all nodes of the other graph, or by first computing a node mapping which defines the set of allowed node associations (often one-to-one). Only then do graph operations such as node deletion or node insertion make sense. In [START_REF] Starlinger | Similarity Search for Scientific Workflows[END_REF] we compared different strategies to obtain such a mapping; in this work, we use two strategies, depending on the amount of topological information available:

• maximum weight matching (mw) chooses the set of oneto-one mappings that maximizes the sum of similarity values for unorderes sets of nodes.

• maximum weight non-crossing matching (mwnc) [START_REF] Malucelli | Efficient labelling algorithms for the maximum noncrossing matching problem[END_REF] requires an order on each of the two sets to be mapped to be given by the graphs' topological decompositions. Given two ordered lists of modules (m 1 , ..m i , ..m k ) and (m ′ 1 , ..m ′ j , ..m ′ l ), a mapping of maximum weight between the sets is computed with the additional constraints no pair of mappings (m i , m ′ j ) and (m i+x , m ′ j-y ) may exist with x, y ≥ 1.

C. Normalization

A difficult problem in topological comparison of workflows is how to deal with differences in workflow size. In particular, given a pair V , W of workflows where V ⊂ W and |W | >> |V |, what is their similarity? This decision typically is encoded in a normalization of similarity values wrt the sizes of the two workflows [START_REF] Starlinger | Similarity Search for Scientific Workflows[END_REF]. In this work, we use a variation of the Jaccard similarity coefficient, which measures the similarity of two sets A and B by their relative overlap: |A∩B| |A|+|B|-|A∩B| . We modify this formula because the methods for comparing modules do not create binary decisions but instead return a similarity score; details can be found in [START_REF] Starlinger | Similarity Search for Scientific Workflows[END_REF].

D. External Knowledge

When comparing two workflows, knowledge derived from the entire workflow repository or even from external sources may be taken into account. While this idea in theory could be implemented by complex inferencing processes over process ontologies and formal semantic annotations, our results in [START_REF] Starlinger | Similarity Search for Scientific Workflows[END_REF] showed that the following two simple and efficiently computable options are already quite effective:

• Importance Projection Preprocessing. Many modules in real-world workflows actually convey little information about workflow function, but only provide parameter settings, perform simple format conversions, or unnest structured data objects [START_REF] Starlinger | Re)Use in Public Scientific Workflow Repositories[END_REF]. Importance projection is the process of removing such modules from a workflow prior to its comparison, where the connectivity of the graph structure is retained by transitive reduction of removed paths between the remaining modules. Note that this method requires external knowledge given in the form of a method to assess the contribution of a given module to the workflow's function, which is a rather strong requirement. The implementation provided here relies on manual assignments of importance based on the type of operation carried out by a given module.

• Module Pair Preselection. Instead of computing all pairwise module similarities for two workflows prior to further topological comparisons, this method first classifies modules by their type and then compares modules within the same class. This reduces the number of (costly) module comparisons and may even improve mapping quality due to the removal of false mappings across types. Here, external knowledge must be given in the form of a method assigning a predefined class to each module.

IV. LAYER DECOMPOSITION WORKFLOW SIMILARITY

In this section, we present a novel approach, called Layer Decomposition (LD), for structurally comparing two workflows. The fundamental idea behind LD is to focus on the order in which modules are executed in both workflows by only permitting mappings of modules to be used for similarity assessment which respect this order (in a sense to be explained below). Two observations led us to consider execution order as a fundamental ingredient to workflow similarity. First, it is intuitive: The function of a workflow obviously critically depends on the execution order of its tasks as determined by the direction of data links; even two workflows consisting of exactly the same modules might compute very different things if these modules are executed in a different order. Nevertheless, most structural comparison methods downplay execution order. For instance, it is completely lost when only module sets are compared, and a few graph edits can lead to workflows with very different execution orders (like swapping the first and last of a long sequence of modules). Second, we observed in our previous evaluation [START_REF] Starlinger | Similarity Search for Scientific Workflows[END_REF] that approaches to topological workflow comparison which put some focus on execution order are much more stable across different configurations of the remaining steps of the workflow comparison process. In particular, comparing two graphs using their path sets, i.e., the set of all paths from a source to a sink, produced remarkably stable results both with and without the use of external knowledge. Inclusion of such knowledge in workflow comparison had among the largest impact on the overall performance of methods, but requires corpus-specific expert intervention. Based on these findings, developing methods that achieve retrieval results of high quality without requiring external knowledge seemed like a promising next step.

In the following, we first explain how LD extracts an ordering of workflow modules from the workflow DAG. We then show in Section IV-B how two workflows can be effectively compared using this partial ordering. Finally, we explain in Section IV-C how normalization is performed.

A. Topological Decomposition

The linearization (or topological sort) of a DAG is an ordering of its nodes V such that node u precedes node v in the ordering, if an edge (u, v) exists. Obviously, a DAGs linearization can be computed in linear time using topological sorting; however, it is generally not unique. As the quality of the subsequent mapping (see below) depends on the concrete linearizations chosen for the two workflows under consideration, it is important to find a good pair of linearizations, i.e., linearizations such that highly similar modules will later get mapped onto each other. Since the number of possible linearizations is Ω(n!) (where n is the number of modules in a workflow), assessing all possible pairs is generally infeasible; it is also infeasible in practice, as many real life workflows have many different linearizations (for instance, 23.5% of the 1485 Taverna workflows in our evaluation set have more than 100 different linearizations).

We tackle this problem by representing all possible linearizations of a given workflow in a concise data structure. Observe that a DAG has more than one linearization iff between two consecutive nodes in one of its linearizations no direct datalink exists, because in this case swapping the two nodes creates another linearization. In all such cases, we tie the two nodes in question into a single position in the ordering. We call such a tie at position i a layer L i . Compacting all sequences of two or more swappable nodes of a linearization in this way yields a layered ordering of the DAG which we call its layer decomposition LD = (L 1 , .., L i , .., L k ). Note that the layer decomposition of a DAG is unique, as a) layers themselves are orderless sets of modules, and b) following from the definition of the underlying linearization, for any L i and L j such that i < j, for every v ∈ L j , there is some u ∈ L i which precedes v in every linearization, which c) uniquely defines the positions of L i and L j within the decomposition. To compute a workflow's layer decomposition, we use a simple iterative algorithm. First, all modules with indegree 0 (the DAGs source nodes) form the top layer L 1 . These modules and all their outbound data links are removed from the workflow; this process is repeated until no more modules remain. Figure 3 shows the layer decompositions of the sample workflows introduced in Figure 1. In the figure, the different Fig. 4: Overview of workflow comparison applied by LD layers are visually aligned to reflect their mapping, as it is derived in the following step.

B. Topological Comparison

The layer decomposition of a workflow partitions its module set by execution order creating an ordered list of module subsets. To compare the layer decompositions LD and LD ′ of two workflows wf and wf ′ , respectively, we take a two-phase approach, sketched in Figure 4. First, pairwise similarity scores for each pair of layers (L, L ′ ) ∈ LD × LD ′ are computed from the modules they contain using the maximum weight matching (mw), based on the similarity values p(m, m ′ ) derived by a given module comparison scheme as introduced in Section III-B:

layersim(L, L ′ ) = p(m, m ′ ) | (m, m ′ ) ∈ mw(L, L ′ )
In the second phase, the ordering of the layers -and thus of the modules they are comprised of -is exploited to compute the decompositions' maximum weight non-crossing matching (mwnc) with the pairwise similarities of layers from phase one. The resulting layer-mapping serves as the basis for the overall (yet non-normalized) similarity score of the compared workflows using LD:

nnsim LD (wf, wf ′ ) = layersim(L, L ′ ) | (L, L ′ ) ∈ mwnc(LD, LD ′ )

C. Normalization

As done for all other methods we shall compare to, we normalize the similarity values computed by LD using the Jaccard variation described in Section III-C. Thus, the final, normalized LD-similarity is computed as:

sim LD (wf, wf ′ ) = nnsim LD |LD| + |LD ′ | -nnsim LD .
We

V. EVALUATION

We evaluate our novel Layer Decomposition algorithm on a gold standard corpus of workflow similarity ratings given by workflow experts. We therein use the data and setup from [START_REF] Starlinger | Similarity Search for Scientific Workflows[END_REF] 1 . The corpus contains 2424 similarity ratings from 15 experts from four countries for 485 workflow pairs from a set of 1485 Taverna workflows, given along a four step Likert scale [START_REF] Likert | A technique for the measurement of attitudes[END_REF] with the options very similar, similar, related, and dissimilar plus an additional option unsure. The ratings are grouped by 24 query workflows. Each query workflow has a list of 10 workflows compared to it, which are ranked by a consensus computed from the experts rankings using BioConsert Median Ranking [START_REF] Cohen-Boulakia | Using medians to generate consensus rankings for biological data[END_REF]. These rankings are used to evaluate the algorithms performance in workflow ranking. For 8 of the query workflows, additional expert ratings are available covering all workflows which were ranked among the top-10 most similar workflows by a selection of algorithms to be further evaluated, when run against the entire workflow corpus. These are used to assess workflow retrieval performance.

Using this corpus, we compare the LD algorithm against approaches based on Module Sets, Path Sets, Graph Edit Distance, Bags of Words, and Bags of Tags (as presented in Section II). First, we investigate the algorithms' performance in the tasks of workflow ranking (Section V-A) and workflow retrieval (V-B). Second, we compare the runtimes of the different topological comparison methods (V-C). Third, we evaluate whether the successive application of multiple algorithms in retrieval can improve result quality and its implications on runtime (V-D). Finally, in Section V-E we shall confirm the previous results on ranking performance using a second data set, from the Galaxy repository.

A. Workflow Ranking

To evaluate ranking performance, we use the measures of ranking correctness and completeness [START_REF] Bergmann | Similarity assessment and efficient retrieval of semantic workflows[END_REF], [START_REF] Cheng | Predicting partial orders: ranking with abstention[END_REF]. For ranking correctness, the order of each pair of elements in the experts' consensus ranking and the algorithmic ranking is compared, counting pairs sharing the same order and pairs that don't, to determine the correlation of the compared rankings. Values range from -1 to 1, where 1 indicates full correlation of the rankings, 0 indicates that there is no correlation, and negative values are given to negatively correlated rankings. Ranking completeness, on the other hand, measures the number of pairs of ranked elements that are not tied in the expert ranking, but tied in the evaluated algorithmic ranking. The objective here is to penalize the tying of elements by the algorithm when the user distinguishes their ranking position.

Figure 5 shows ranking performance for sim LD in direct comparison to sim M S , sim P S , sim GE , and the annotation based measures sim BW and sim BT . Results are sorted by mean ranking correctness. Each algorithm is applied in a variety of different configurations (see Sections III-A and D for options; see Table I for correctness, several observations can be made: Firstly, sim LD provides best results. Secondly, both sim LD and sim P S provide most stable results across different configurations. Performance of sim M S , on the other hand, varies with the quality of the module comparison scheme used, and especially with the use of external knowledge in terms of ip. Thirdly, while sim M S , when configured properly, can achieve ranking correctness values comparable to the best results of sim LD , sim P S is generally slighly behind sim LD . In contrast, sim GE , putting a high emphasis on overall workflow structure, does not provide competitive results; we therefore omit it in all further evaluations. As for ranking completeness, we see that both sim LD and sim P S fully distinguish all workflows in terms of their similarity to the query workflows where users make a distinction as well. The ranking provided by sim M S , on the other hand, is often only near-complete.

Figure 6 shows the results of selected ensembles of different base methods using mean similarity values. Generally, result quality improves considerably. For instance, the top performing standalone configuration of sim LD achieves a ranking correctness of 0.889, and is not only outperformed by its combination with sim BW by 2.5 %-points, but especially in terms of stability of results across different query workflows, as apparent from the standard deviations from the mean. The ensembles including sim LD deliver better results than other ensembles especially when no external knowledge is used.

B. Workflow Retrieval

Figure 7 shows mean precision at k [START_REF] Mcsherry | Computing information retrieval performance measures efficiently in the presence of tied scores[END_REF] for each position in the top-10 results returned by each of the algorithms. We focus our presentation on configurations using the pll module comparison scheme. Comparing sim M S , sim LD , and sim P S , Figure 7a shows that when treating results as relevant with a median expert rating of at least related, all algorithms deliver results of similar (very high) quality. The usage of ip and te improves results for all algorithms. While this may seem a contradiction to the more distinguished results of the workflow ranking experiment at first, it has to be kept in mind that differences in ratings between the results retrieved are not considered for evaluation of retrieval precision. This becomes more clear when inspecting algorithmic retrieval performance for a relevance threshold of similar (Fig. 7b). Here, the improved ranking of sim LD is reflected both by a slight advantage in the very top results returned, especially when ip is used, and by a more pronounced improvement of mean retrieval performance for the second half of the top-10 results.

Detailed inspection of the workflows retrieved by each of the algorithms revealed that the nature of sim LD 's topological comparision favours retrieval of perfectly matching substructures over global workflow matches with slightly reduced pairwise layer similarities, due to the way the structural complexity of the workflows is reduced to a more 'fuzzy' representation in the layers. This behaviour results in some false positive retrievals for a small fraction of the query workflows used. To account for this, we extended the original algorithm by adding a penalty for layers not matched in the maximum weight non crossing matching, when the number of such mismatched layers exceeds a configurable percentage of the layers in the larger of the compared workflows (i.e., the maximum number of layers that could possibly be matched). Setting this allowance to 25% notably improves retrieval performance of sim LD , as shown in Figure 8. Yet, selection of the right mismatch allowance to be used depends on the concrete dataset, and, as such, requires prior, in depth knowledge about the repository to be queried. We thus refrain from applying this extension in the remainder of this evaluation.

C. Runtime

It can be expected that the topological comparison performed by the Layer Decomposition algorithm entails a penalty in runtime when compared to the topology-agnostic Module Set approach. Here, we investigate how big this penalty is, how it compares to other algorithms, and how much it depends on the sizes of the compared workflows by measuring runtimes for sim LD , sim M S , and sim P S . For runtime measurement, each of the 1485 workflows in our dataset was compared against itself by each of the algorithms to obtain an unbiased sample wrt typical workflow sizes. Each comparison was done 5 times and results were averaged.

Figure 9 shows average runtimes, grouped by workflow sizes ranging from 1 to 437 modules. The average number of modules per workflow in our dataset is 11.4 (see also [START_REF] Starlinger | Re)Use in Public Scientific Workflow Repositories[END_REF], [START_REF] Wassink | Analysing Scientific Workflows: Why Workflows Not Only Connect Web Services[END_REF]). Note that the figure only shows the time taken for the actual topological comparison. Steps that can be performed offline or only have to be performed once per query execution, such as decomposition of the workflows into the sets of paths or layers, are not considered; module similarities have been precomputed and cached. While runtimes of all algorithms are comparably low for workflow sizes up to around 15 modules, clearly, the only algorithm with acceptable runtimes for larger workflows is sim M S . sim P S runtimes vary greatly, as these are dominated by the number of paths the compared workflows contain. This variance is reduced for sim LD , which only needs to compare one pair of decompositions per workflow, resulting in a substantial speedup. Yet, with increasing workflow size and increasing numbers of multi-module layers, runtimes are much higher than with simple Module Set comparison.

D. Reranked Retrieval Results

Given the findings regarding the deterred runtime of sim LD and the fact that external knowledge to be used in workflow comparison such as ip and te incurs a severe data acquisition bottleneck, we speculated whether the results of the (fast) Module Set comparison algorithm can be improved -without external knowledge -by merging them with the high-quality ranking performance of sim LD . We therefore performed an experiment where we reranked the top retrieval results of sim M S by the ensemble of sim BW and sim LD . Figure 10 shows retrieval precision for sim M S , sim LD , and sim BW on their own, and for the reranked top 24 search results of sim M S . Especially for the relevance threshold of related, reranking the results clearly improves performance and makes it comparable to that of algorithm configurations including external knowledge. For a threshold of similar, the benefit is less pronounced, yet still observable. We believe that studying in more detail such reranking methods, especially focussing on the trade-off between runtime and result quality, are a prospective venue for further research.

E. Applicability to Other Datasets

Our gold standard corpus also includes a second set of workflows from another workflow repository, namely the public Galaxy workflow repository. For 8 query workflows, rated lists of compared workflows are available to evaluate ranking performance. This dataset differs from the previous one in various respects: Galaxy workflows are exclusive to the Bioinformatics area, the repository is smaller and curated by a smaller group of people, the annotation is generally more sparse (no tags etc.), and the modules used are only local executables (no web services as frequently used in Taverna). Looking at such diverse data sets is important to show robustness of any evaluation results.

Figure 11 shows ranking correctness for sim M S , sim LD , and sim P S on this second dataset. The module comparison schemes used are gw1, comparing a selection of attributes with uniform weights, and gll, comparing only module labels by their edit distance. While results are generally less good than on the myExperiment data set, sim LD here even more clearly outperforms the other algorithms. We are currently looking to extend this dataset to be able to perform a more complete evaluation and to trace back the observed differences in ranking performance to properties of the data set.

VI. CONCLUSION

We introduced Layer Decompositon (LD), a novel approach for workflow comparison specifically tailored to measuring the similarity of scientific workflows. We comparatively evaluated this algorithm against a set of state-of-the art contenders in terms of workflow ranking and retrieval. We showed that LD provides the best results in both tasks, and that it does so across a variety of different configurations -even those not requiring extensive external knowledge. Results in ranking could be confirmed using a second data set. Considering runtime, we not only showed our algorithm to be faster than other structureaware approaches, but demonstrated how different algorithms can be combined to reduce the overall runtime while achieving comparable, or even improved result quality.

Fig. 1 :

 1 Fig. 1: Sample scientific workflows from the myExperiment repository: (a) ID: 1189, Title: KEGG pathway analysis, (b) ID: 2805, Title: Get Pathway-Genes by Entrez gene id.

Fig. 3 :

 3 Fig. 3: Sample layer decomposition and layer mapping of scientific workflows (a) 1189, (b) 2805; see also Fig. 1).

  analogously normalize layersim(L, L ′ ) by |L| and |L ′ |. This way, if two workflows are identical, each layer has a mapping with a similarity value of 1. Then nnsim LD = |mwnc(LD, LD ′ )| = |LD| = |LD ′ |, and sim LD = 1.

Fig. 5 :

 5 Fig. 5: Mean ranking correctness (bars) with upper and lower stddev (errorbars), and mean ranking completeness (black squares) over 24 lists of 10 workflows for different algorithms and configurations (see Table I for notation).

Fig. 6 :

 6 Fig. 6: Mean ranking results for ensembles of BW and structural algorithms (a) without and (b) with ip and te, each using pll module comparison.

Fig. 7 :Fig. 8 :

 78 Figure5shows ranking performance for sim LD in direct comparison to sim M S , sim P S , sim GE , and the annotation based measures sim BW and sim BT . Results are sorted by mean ranking correctness. Each algorithm is applied in a variety of different configurations (see Sections III-A and D for options; see TableIfor notation overview). Regarding ranking

Fig. 9 :

 9 Fig. 9: Algorithm runtimes by workflow size.

TABLE I :

 I Algorithm shorthand notation overview

		Notation	Description
		LD	Layer Decomposition topological comparison
	Algorithms	MS PS GE BW	Module Sets topological comparison Path Sets topological comparison Graph Edit Distance topological comparison Bag of Words annotation based comparison
		BT	Bag of Tags annotation based comparison
		np	No structural preprocessing of workflows
	Configurations	ip ta te pw0 pw3	Importance projection workflow preprocessing No module pair preselection for comparison Type equivalence based module pair preselection Module comparison with uniform attribute weights Module comparison on tuned attribute weights
		pll	Module comparison by edit distance of labels only

ACKNOWLEDGMENT

This work was partly funded by DFG grant GRK1651, DAAD grants D1240894 and 55988515, and PHC Procope grant. Work of SCB partly done in the context of the Institut de Biologie Computationnelle, Montpellier, France.

Though we did consider runtimes, our evaluation clearly focusses on the quality of ranking and retrieval. Real-time similarity search at repository-scale will require further efforts in terms of properly indexing workflows. Such indexing of workflows is straightforward when considering only their modules (like in sim M S ), but requires more sophisticated methods when also topology should be indexed. Therefore, our approach of stacking Layer Decomposition-based ranking onto workflow retrieval by modules provides a good starting place for applying structure-based workflow similarity to scientific workflow discovery to scale.


Keith Head
email: keith.head@ubc.ca

Thierry Mayer

John Ries
email: john.ries@ubc.ca

Gilles Duranton

Diego Puga

The erosion of colonial trade

published or not. The documents may come

Introduction

The dismantling of European empires after World War II led to sweeping changes in the governance of developing countries in Africa and Asia. Recent research in economics has investigated the long-run consequences of colonial rule. La [START_REF] Porta | Law and finance[END_REF] argue that the British endowed their colonies with a legal system that produces superior economic outcomes. [START_REF] Acemoglu | The Colonial Origins of Comparative Development: An Empirical Investigation[END_REF][START_REF] Acemoglu | Reversal of Fortune: Geography and Institutions in the Making of the Modern World Income Distribution[END_REF] find that colonizers were more likely to establish pro-growth institutions in sparsely populated areas with lower settler mortality. [START_REF] Banerjee | History Institutions and Economic Performance: The Legacy of Colonial Land Tenure Systems in India[END_REF] find that 50 years after India abolished land revenue systems imposed in the mid-19th by British rules, their "institutional overhang" can be seen in agricultural productivity differences. In this paper, we investigate a different legacy of colonial rule: the bias in post-colonial bilateral trade patterns.

Algeria's trade with France offers prima facie evidence of large post-colonial trade erosion. In 1962, the year of independence, Algeria accounted for 8.84% of French imports, a share that had been stable over the 14-year period preceding independence for which we have data. The share fell by two thirds over the next two decades (to 2.72% in 1984) and another two thirds over the succeeding two decades, reaching 0.96% in 2006. A variety of potential explanations for this fact suggest themselves. First, it might reflect poor economic performance over the last four decades by Algeria, which may have reduced its exports to all markets. Second, Algeria's abandonment of the Franc in 1964 may have raised currency transaction costs. Third, France's participation in GATT and the European Community probably redirected its import purchasing patterns, lowering the share taken by any absolute level of imports from Algeria. Fourth, deterioration of business networks and trade-creating institutions may have raised bilateral trade costs.

Utilizing data encompassing almost every country in the world from 1948 and 2006, we identify the impact of independence based on within variation in bilateral trade. We estimate a semi-parametric specification, dividing years since independence into seven 1 intervals. Unlike the work cited in the opening paragraph, we will take as a given any changes in per capita incomes caused by changing internal institutions. We also control for formal external institutions (membership in regional trade agreements, GATT, and currency unions). This allows us to focus on the effects of unobserved informal external institutions such as the business networks emphasized by [START_REF] Rauch | Networks Versus Markets in International Trade[END_REF].

Our results show that three decades after independence, trade between colony and metropole has fallen by more than 60%. Trade between colonies of the same empire falls even more. There is little evidence of corresponding diversion of trade to other countries.

We also investigate the mechanisms that underlie the post-independence erosion of trade with the metropole. We exploit a data set showing the number of French nationals living in different countries which we consider as a proxy for the metropole's social and business network. We find the population of French expatriates in former colonies declines in much the same way as bilateral trade. The shrinking expatriate presence partially explains the diminished trade between France and its former colonies. An alternative explanation of falling trade after separation is that wars of independence caused permanent tradereducing antipathy between the metropole and former colony. Categorizing independence events into amicable and hostile separations, we find that the latter are more immediately destructive to trade but both lead to large trade erosion in the long run.

Countries in colonial empires choose if and when to separate, raising the concern of endogeneity bias. As we discuss in Section 2, historical accounts suggest a significant random component to independence events. Nevertheless, systematic determinants of independence are a possible source of bias. The political and economic attributes of the colonizer (metropole) and colony, as well as the strength of their bilateral association, may affect the likelihood of independence. We remove these factors, however, in specifications that eliminate time-varying country effects and non-time varying bilateral effects. Timevarying bilateral effects remain as a potential source of bias. For example, declining trade prospects may have induced metropoles to relinquish control of colonies. We will argue that our results showing little short-run and substantial long-run bilateral trade erosion subsequent to independence do not support this reverse causation hypothesis.

Instead, they are consistent with the proposition that independence led to deterioration of trade-creating capital such as institutions and networks.

The paper proceeds as follows. In the next section, we describe our panel of independence events and bilateral trade data. Section 3 specifies a gravity model employing country-pair (dyad) fixed effects. Due to the computational difficulties of estimating country-year fixed effects to capture multilateral resistance terms, we eliminate them by implementing a method of "tetrads" that takes the ratio of ratios of trade flows. Our results on the impact of independence on bilateral trade are presented in section 4. The concluding section summarizes and discusses potential welfare implications.

Data on independence and trade

The principal variable of interest is the timing of independence events. We do not consider the end of a military occupation as being sufficient condition for an independence event.

Thus France does not become independent from Germany in 1945 in our data set. Rather, independence arises following a colonial period which should involve long-term, civilian administration that includes significant settlement. Information on colonial relationships comes from a variety of sources but we used the CIA World Factbook as the primary authority for independence dates.

There are 253 country pairs with colonial histories, of which 33 remain current. 4 in the data appendix lists independence events since 1900 as well as the continuing colonial relationships for which we have trade data. The timing of the independences shown in Figure 1 reflect a variety of political and economic forces. Historical accounts point to an important role for idiosyncratic events.

For example, France's President De Gaulle first threatened to cut ties (and aid) to African colonies that voted to leave the "French Community." However, after Guinea declared sovereignty in 1958, De Gaulle reversed position and offered economic cooperation agreements to all countries that voted for independence. Fourteen colonies promptly gained independence in 1960. Rothermund (2006, p. 153) remarks that "in 1960 the French almost had to impose independence on a reluctant Gabon" because De Gaulle "did not tolerate exceptions to the granting of independence in 1960." This was despite oil and uranium resources that "the French were interested in keeping under their control." In contrast to the wave of independence for French colonies in the 1960s, Portugal adamantly clung to its five "overseas provinces" in Africa until after the Salazar dictatorship was replaced with a democratic and pro-decolonization government in 1974.

To estimate the influence of the independence events on bilateral trade, we use the The data base we compiled is larger than most comparable work using DOTS. Our typical regression includes around 620,000 observations. [START_REF] Glick | Does a currency union affect trade? The time-series evidence[END_REF] study of currency unions uses DOTS but has about 220,000 observations in part because their study ends in 1997 and their main specification averages bilateral exports and imports. [START_REF] Baier | Do Free Trade Agreements Actually Increase Members' International Trade?[END_REF] also use DOTS (without averaging) but only at 5 years intervals (9 different years starting in 1960), which reduces their sample to 47,081 observations. As emphasized by [START_REF] Baldwin | An evidence based analysis of the trade effects of the euro[END_REF], considering the direction of trade is important to maintain a connection to the underlying theory. It is important for us to have annual data to be able to estimate the extent that trade changes in the first years after independence.

Specification

In order to estimate the effects of independence, we need a benchmark for the amount of trade expected had independence not occurred. We will follow the common practice of modeling "expected" bilateral trade using a specification based on the gravity equation.

All the well-known empirical and theoretical formulations of the gravity equation can be represented in the following equation for the value of x ij , the exports from supplying country i to importing country j:3

x ij = GS i M j φ ij . (1)
In this equation, S i and M j are indexes of the attributes of supplier i and importer j, and G is a factor that does not vary across countries (but can vary across time periods).

Variation in bilateral trade intensity enters through φ ij . We refer to S i and M j as monadic effects and φ ij as the dyadic effect.

The general approach to estimation is to take logs to obtain an equation that is linear in the parameters.

ln x ij = ln G + ln S i + ln M j -ln φ ij . (2)
Then the researcher chooses proxies for the monadic and dyadic effects and inserts an error term to represent remaining variation in trade. The next two subsections explain how we model the monadic (ln S i and ln M j ) and dyadic effects (ln φ ij ).

Monadic issues

In many empirical applications, which we will refer to as the "simple gravity" approach, the exporter and importer attributes are assumed to be given by S i = N α 1 i y α 2 i and M j = N α 3 j y α4 j , where N represents population and y is GDP per capita. 4 Plugging in these monadic effects we re-express equation (2) as

ln x ij = ln G + α 1 ln N i + α 2 ln y i + α 3 ln N j + α 4 ln y j -ln φ ij . (3)
Theoretical derivations of the gravity equation imply that the monadic factors also depend on non-linear functions of the dyadic part of (1). This occurs for two main reasons. In The solution proposed in [START_REF] Anderson | Gravity With Gravitas: A Solution to the Border Puzzle[END_REF] requires that a structural model be used to specify the monadic effects as a function of GDPs and the dyadic vector. There are three problems. First, the results may depend on the structure. While there are multiple micro-foundations for equation (1), they differ in terms of the underlying monadic terms. Second, the monadic terms depend upon the whole dyadic vector including the "internal" distances of countries. Applications suggest that results are not robust to alternate ways of calculating "internal" distances. Third, the method presents computational difficulties.

An alternative estimates the monadic effects ln S i and ln M j in equation (2) using fixed effects for i and j. With a balanced panel of bilateral exports, a within transformation can be used for removing the monadic effects. Due to missing data, zeros, and variation in the number of partner trade for each reporting country, actual bilateral data sets are almost never balanced. Baltagi (1995, p. 160) points out that the within transformation does not work with unbalanced two-way panels. One should therefore use the least squares dummy variable (LSDV) method. Since DoTS has close to 200 trade entities and over 50 years of trade, the LSDV approach involves about 20,000 dummies. This presents computational difficulties of a different kind: programming is trivial but the execution requires a massive matrix inversion. [START_REF] Baier | Bonus Vetus OLS: A Simple Approach for Addressing the Border Puzzle and other Gravity-Equation Issues[END_REF] offer a third approach they call bonus vetus OLS. It is based on a linear approximation around a centering point and is implemented via demeaning transformations of the dyadic variables. Their approach assumes that all determinants of trade costs are observed so that they can be incorporated into the approximation. Unobserved multilateral and bilateral trade costs that are correlated with colonial separations would bias the estimates of independence effects.

We apply a different approach to estimation. It takes advantage of the multiplicative structure of equation ( 1) and then takes the ratio of ratios to eliminate the monadic effects (including the multilateral resistance terms). This requires a set of four trading partners. For that reason, we call it the method of tetrads.

Consider four countries indexed i, j, k, and . Using (1), the ratio of i's exports to j over its exports to importer k is given by

R i{jk} = x ij x ik = M j φ ij M k φ ik . (4)
We have canceled out G, and more importantly, S i , the exporter fixed effect. The M j /M k ratio remains problematic for estimation however, and we now need an expression parallel to (4) containing M j /M k that we can divide R i{jk} by in order to cancel out these remaining monadic terms. This can be achieved by picking a reference exporter and calculating the corresponding ratio to the same pair of importers:

R {jk} = x j x k = M j φ j M k φ k . ( 5
)
Taking the ratio of ratios we can define the tetradic term

r {i }{jk} = R i{jk} R {jk} = x ij /x ik x j /x k = φ ij /φ ik φ j /φ k , (6)
where the tetrad comprises two exporters, {i }, and two importers, {jk}. Taking logs, we have

ln r {i }{jk} = ln φ ij -ln φ ik -ln φ j + ln φ k . (7)
We now specify φ ij to show how the r {i }{jk} can be used to estimate the parameters determining bilateral trade intensity. The log dyadic effect is given by

ln φ ij = βB ij + u ij (8)
The B ij and u ij in this equation represent respectively observed and unobserved bilateral linkages. Plugging this expression back into equation ( 7), we have

ln r {i }{jk} = β(B ij -B ik -B j + B k ) + u ij -u ik -u j + u k . (9)
For binary linkage variables, the sum above can take on five possible values: 2, 1, 0, -1

and -2, depending on the pattern of linkages within the tetrad.

Our approach can be seen as an extension of existing ratio approaches that take advantage of the multiplicative functional form of the gravity equation to get rid of either the exporters' [START_REF] Anderson | Insecurity and the Pattern of Trade: An Empirical Investigation[END_REF] or importers' (Head and[START_REF] Head | Non-Europe : The Magnitude and Causes of Market Fragmentation in the EU[END_REF][START_REF] Martin | Make Trade not War?[END_REF] fixed effects. Combining the two approaches yields a specification free of any monadic term.5 Two recent papers also employ the ratio of ratios to eliminate the monadic terms. [START_REF] Romalis | NAFTA's and CUSFTA's Impact on International Trade[END_REF] estimates the response of US imports from Canada and Mexico to NAFTA tariff reductions. [START_REF] Hallak | Product quality and the direction of trade[END_REF] uses the approach to quantify the economic magnitude of coefficients obtained from fixed effects gravity equations.

The method presents two special issues. First, one needs to select the reference countries k and in order to do the tetrad calculations. 6 In their single-ratio methods, [START_REF] Anderson | Insecurity and the Pattern of Trade: An Empirical Investigation[END_REF] and [START_REF] Martin | Make Trade not War?[END_REF] take the United States as the reference country. The EU is the reference importer and the rest of the world is the reference exporter in [START_REF] Romalis | NAFTA's and CUSFTA's Impact on International Trade[END_REF]. We employ three pairs of reference countries to examine robustness. First, we take the two big colonizers over our sample, France and the United Kingdom. We then use two of the biggest exporters, Germany and the US.

Finally, we consider two economies that did not have colonial relationships during our sample, Canada and Switzerland.

A second issue concerns the independence of the observations. As represented in (9), the error terms u k , u ik , and u j , appear repeatedly across observations. Indeed, u k is contained in each observation. We will use year dummies to account for u k but are still left with correlated errors as a consequence of u ik , and u j . The appropriate form of clustering is more complex than usual here, since the repeated presences of u ik and u j call for both exporter-year and importer-year clusters, which are non-nested. We therefore use multi-way clustering of the kind described in [START_REF] Cameron | Robust Inference with Multi-way Clustering[END_REF]. We implement their estimation method using three-way clustering: it, jt, and ij.7

Dyadic issues

Another concern in this study is that the vector of linkage variables, B ij , is necessarily incomplete. This means unobserved dyadic (ij) linkages will contaminate the error term.

That is, even if we control for importer and exporter effects there are unobserved bilateral influences on both trade and the decision to become independent. With panel data, one can remove the unobserved but fixed component of bilateral linkages using dyadic (country-pair) fixed effects. This identifies the effect of independence based on time series variation. We will therefore also use this type of specification, and follow [START_REF] Baier | Do Free Trade Agreements Actually Increase Members' International Trade?[END_REF] and [START_REF] Glick | Does a currency union affect trade? The time-series evidence[END_REF] who underscore the importance of capturing policy changes using time-series rather than cross-sectional variation.

Finally we need to specify the set of observable linkages between country pairs in our sample. Using abbreviations, we specify the linkages vector in year t as

B ijt = {ln D ij , Lang ij , Legal ij , Colony ij , RTA ijt , GATT ijt , CU ijt , Indep ijt }
which controls for distance, common language, having common legal origins in national law, the existence of a historical colonial relationship, belonging to a common regional trade arrangement, both countries belonging to GATT/WTO, belonging to a currency union, and independence. Of these, distance, common language, shared legal origins, and colonial history do not vary over time and drop out in specifications with dyadic fixed effects. We also employ year indicator variables to capture changes in average trade propensities over time.

To measure the effect of independence, we employ seven indicator variables corresponding to years subsequent to independence: 1-2, 3-6, 7-11, 12-19, 20-29, 30-49 and 50 or more years. The advantage of this semi-parametric specification is its flexible treatment of how trade evolves subsequent to independence. For example, if networks underlie the reason why countries with colonial ties trade more with each other, we would expect a gradual decline in these networks over time once independence is achieved. The specification can capture a short-run disruption in trade followed by long-run return to pre-independence levels. It also allows for permanent reductions that are achieved immediately following independence. The omitted category for the independence indicators is the year of independence and previous years. 8

Results

Before proceeding to the regression analysis, it is instructive to examine two cases. in distances between colonies and metropoles seem negligible. Furthermore, changes in multilateral resistance indices should be fairly similar.9 If colonial ties did not influence trade, we would expect that the ratio of exports to France to exports to the UK (shown with x-marked lines) to be approximately equal to the relative size of their markets. Similarly, relative imports from the two sources (solid lines) would be equal to their relative production. Using GDP as the measure of relative market and production size, we would expect all four trade lines to be close to the France-to-UK GDP ratio (black dashed line).

Instead, we see large gaps on both sides.

France's former colony Ivory Coast trades much more with its former metropole than 8 There are only 1474 positive trade values for colonial trade prior to independence.

France's relative size would imply. The ratio of export ratios to GDP ratios is 79.3 in the year it became independent. By 2006, the ratio had fallen to 5.9. Its imports also begin heavily biased towards France (ratio of 38.6) and, while the import bias also declines, it persists at 11.7 in 2006. On the other hand, Ghanaian trade exhibits bias towards the UK. The ratios of relative trade to relative GDP are 13.4 (exports) and 23.1 (imports) in 1957. Their decline in recent years has been remarkable and the bias has fallen to 1.9

(exports) and 1.3 (imports) in 2006. Even these numbers should be seen as impressive:

Forty-six years after independence Ghana still exports about 90% more to its former ruler than a simple gravity model would predict. From our gravity estimates below, this is larger than if Ghana and the UK belonged to a regional trade agreement, or a currency union.10

Another interesting illustration can be made using two comparable countries, where one gained independence, while the other remained part of national territory of the colo- The number of observations in his study, 234,597 in the baseline regression, is less than half the 618,233 observations in our analysis. Likewise, Baier and Bergstrand (2007, Table 4, column 2) obtain RTA coefficients of 0.27 for pooled OLS, considerably smaller than our 0.96 estimate. They use 1960They use , 1970They use , 1980They use , 1990They use , 2000 data and 96 countries and thus only have 47,081 observations. Column (2) takes into account unobserved persistent dyadic influences using random effects. Random effects is a GLS transformation of the data in which each variable z ijt is replaced by z ijt -θij zij . Thus the variables are being quasi-differenced by the dyadic means. If θij = 1, then this specification would be the fixed effects within transformation.

Instead, random effects estimates θij based on the number of observations per dyad and the relative variances of the between and within dimensions of the data. In these estimations the median θij is 0.8, which helps to explain why the results look very similar to those shown in column (3) for fixed effects. Given this similarity, we will not comment on them except for the estimate for colonial history. That variable has no within-dyad variation (it is coded so as to equal one if ever the country pair were in a colonial relationship). To assess the influence of a colonial relationship after a certain number of years, one should subtract the relevant independence coefficient from the estimate of colonial history obtained in this specification, 2.6. This coefficient implies that countries in ongoing colonial relationships have, on average, 13.5 (= e 2.6 ) times more trade than other country pairs.

Column (3) introduces dyadic fixed effects and thus estimates are based on time-series variation within dyads. Linkage variables that do not vary over time (distance, shared language, colonial history, and shared legal origins) are captured by the dyadic fixed effects. In comparison to the column (1) pooled OLS estimates, the coefficients fall but remain statistically significant. The GATT effect of 0.16 is almost the same as the 0.15 estimate that Rose obtains when he employs dyadic fixed effects. The RTA estimate of 0.52 is relatively close to Baier and Bergstrand's comparable estimate of 0.68.11 The effect of currency unions, 0.49, is somewhat lower than the 0.65 found in [START_REF] Glick | Does a currency union affect trade? The time-series evidence[END_REF] using the same method.

In the final three specifications, the tetrad method removes all (time-varying) monadic effects (e.g., population, per capita income, and multilateral resistance terms). We also employ tetradic fixed effects which eliminate non-time varying bilateral linkage variables.

Looking across columns ( 4)-( 6), regressions that use Great Britain-France, the United States-Germany, and Switzerland-Canada as reference countries, we find that the signs of estimated coefficients on RTA, GATT, and currency union are the same as those listed in column (3) but the magnitudes vary somewhat. The RTA estimates are smaller than those shown in column (3) whereas the estimates of GATT membership are slightly larger.

The estimates for currency union are quite similar to those estimated by random or fixed effects, but lower than OLS estimates.

Table 2 lists estimates of the seven independence variables corresponding to trade at increased intervals since liberation: 1-2 years, 3-6 years, 7-11 years, 12-19 years, 20-29 years, 30-49 years, and 50+ years. Column (1) exhibits the pooled OLS results. For the newly independent (the first ten years), independence is associated with higher trade although the effects are only marginally significant. Evidently, trade between colony and colonizer shortly after independence was higher than colonial trade for existing colonies and colonies that were independent for longer periods of time. Of course, it may be the case that these newly independent countries' trade with their colonizer was higher than average before independence as well. For this reason, we prefer the estimates in the ensuing columns that emphasize within-dyad variation over time. The dyadic and tetradic fixed effects regressions purge observations of average country-pair trade and estimates are based on time-series changes in trade. Given the high values of θij , random effects largely removes mean dyad effects. 1) and (2). Columns (3) to ( 5) use three-way clustering by dyad, i-year, and j-year using [START_REF] Cameron | Robust Inference with Multi-way Clustering[END_REF] method. All columns report coefficients from the same regressions as the ones with identical numbering in Table 1.

Columns ( 4)-( 6) show the tetrad results and corroborate the findings of large declines in trade after two decades of independence. The point estimates vary somewhat depending on the choice of reference countries, with larger estimates obtained in in column

(5) using USA and Germany and smaller estimates found for Switzerland-Canada and Britain-France.

Three alternative explanations for observed reductions in trade with the metropole after independence are (1) reverse causation, (2) the cessation of formal trade preferences, and (3) the deterioration of trade-promoting capital such as common institutions and business networks. Reverse causation arises if metropoles relinquish control of colonies once they have exploited all the trading opportunities (e.g., extracted all the natural resources). Trade reduction, therefore, would have occurred even without independence.

In the cases of reverse causation and cessation of preferential trade policies, we would expect trade reductions to occur soon after the country gained sovereignty. In the preferred estimates in the last four columns of Table 2 that employ dyad fixed effects, there is limited evidence of significant trade erosion in the first six years. Trade levels persisting many years after independence are inconsistent with explanations (1) and (2).

We observe that independence reduces colony trade with the metropole. But what happens to colonial trade with other countries in the colonial empire (siblings) as well as rest-of-world (RoW) countries? As is the case with trade with the metropole, trade between siblings may decline suddenly due to trade preference cessation or gradually due to deterioration in colonial networks and institutions. There are a couple of reasons to expect that trade might increase with RoW countries. First, rising trading costs with the metropole and siblings could divert trade to other countries. Second, the metropole might have constrained the ability of colonies to trade with RoW countries prior to independence. 15 To measure the impact of years of independence on trade with each type of country, we estimate distinct independence effects for a colony's trade with metropole, siblings, and RoW countries. We deem a sibling relationship to be severed when the first of a pair of siblings gains independence. Years since independence for a sibling dyad is calculated as the current year minus the year of severance. For colony-RoW dyads, years since independence is the current year minus the year that the colony became 16 Some countries were colonized by a succession of metropoles. For example, Papua New Guinea (PNG) became independent from Great Britain in 1901, Germany in 1915, and Australia in 1975. For PNG-RoW dyads, years since independence is the current year minus 1975, the year it was no longer subject to colonial rule. column (3) of Tables 1 and2, rather than the tetrad method. The tetrad method eliminates monadic effects, which reflect a country's general trading propensity in a given year. However, it is the changes in a colony's general trading propensity following independence that we intend to capture using the RoW independence variables. The figure shows each of the seven independence intervals as a step function and also shows the 95% confidence interval around the point estimate. The left axis shows the coefficient estimate and the right axis converts the estimate to the ratio of post-independence trade to pre-independence trade.

The coefficients for trade with the metropole are similar to those from Table 2: After about a decade in which trade does not change significantly, a gradual erosion begins that results in a more than 60% reduction in trade after three decades of independence.17

For siblings we find strong trade erosion as well. In contrast to trade with the metropole, however, statistically significant reductions in trade occur in the first and second year post-independence. The reductions strengthen for two decades before flattening out at almost 80% below the level seen at and before the year of independence. In the case of colony trade with RoW, Figure 5 reveals small, significant increases in trade in the first decade after independence-a 14% increase in the 7-11 years interval-that becomes negative and significant for 20-50 years after independence. In the long run (more than 50 years) RoW trade is not significantly different from the year of independence.

We interpret the gradual trade erosion observed between siblings as evidence that the trade-enhancing "capital" (networks and institutions) associated with empires encouraged inter-sibling trade and that this capital depreciates after independence. The estimates of larger trade contraction for siblings than metropoles is surprising. However, the confidence intervals for metropole and sibling independence estimates overlap with each other 30 years after independence. Contrary to the hypothesis that empires acted as constraints on pre-independence trade diversification of colonies, we find only modest and transitory increases with RoW countries.

Previous research has shown that immigrants are associated with increased trade with their countries of birth (see [START_REF] Gould | Immigration Links to the Home Country: Empirical Emplications for U.S. Bilateral Trade Flows[END_REF] and [START_REF] Head | Immigration and Trade Creation: Econometric Evidence from Canada[END_REF] for early evidence).

The interpretation of this result is that immigrant networks mitigate "informational" barriers to trade. The pattern of independence effects may result from the gradual decline of expatriate populations, leading to the erosion of business networks. We scrutinize this proposition by compiling data on French nationals living abroad. 18 The data covers expatriates in 153 countries over the 1965-2006 period. Substantial numbers of French nationals resided in France's colonies. For instance, in 1965, there were about 137,000, 90,000, and 60,000 expatriates in Morocco, Algeria and Madagascar, respectively.

To investigate the hypothesis that declining networks underlie the observed trade erosion, we first examine how expatriate populations in the French Empire change subsequent to independence and then add expatriate populations as an additional covariate in bilateral trade regressions. The first three columns of Table 3 focus on colony-metropole relations and the second three columns focus on sibling relations. In all specifications, we exclude observations involving RoW countries (those outside the French Empire).

Columns (1) and (4) display estimates of the effects of independence on expatriate populations. The other columns use bilateral trade as the dependent variable. All specifications include fixed effects for dyads and years and the control variables reported in column (3) of Table 1.

Column (1), where the dependent variable is specified as the log of the expat population, reveals that the number of French living in colonies falls steadily after independence. French expat data is only available after independence so here the reference period is the population of expats 1-2 years after independence. The effects cumulate Note: Expats measured as the log of expat population in the colony in columns (1) and

(3) and the sum of the log expat populations in columns ( 4) and ( 6). Standard errors in parentheses with a , b and c respectively denoting significance at the 1%, 5% and 10% levels. All specifications include the full set of controls, dyad fixed effects, and dyad-clustered standard errors.

over time, bottoming out 30-49 years after independence, when expat populations are 13% (= exp(-2.058)) of their average level in the reference period.

Trade between France and its colonies exhibits independence effects that are very similar in magnitude and timing to the declines seen for expats. As shown in column (2)

of Table 3, the reduction in trade is strongest after three decades, with the former colony trading just 17% of the level in the reference period. This trade erosion is larger than the amount estimated for the full sample (shown in Figure 5), where the estimated coefficients imply that three decades after independence trade has eroded to 30% of the level 1-2 years after independence. Column (3) reveals that declining expat populations account for some of the decline in trade after independence. The coefficient on the log of the expat population is significant and equal to 0.290, implying a 10% reduction in expats leads to about a 3% reduction in bilateral trade. This estimate lies within the range obtained in the immigration and trade literature. 19 The coefficients on the independence intervals fall in column (3) relative to column (2). After accounting for the effect of declines in expats, the reduction in trade due to 30 years of independence falls from 83% to 70%.

The relationships between expats, trade, and independence extend to siblings. Each observation used in the specifications in the last three columns of the table consists of a pair of French colonies. Here we are interested in how French expatriates affect trade between the countries in which they reside. 20 To take into account expat populations in both siblings, we redefine the expat variable as the sum of the logs of each sibling's population of French nationals. 21 Column (4) shows that the redefined variable falls steadily after independence. Recall that we designate the year the first colony leaves the empire as the independence date for the sibling pair. Unlike the colony-metropole regressions in the previous three columns, we do not observe any transitions from 1-2 years of independence to 3-6 years of independence, and thus our reference group in now the period 3-6 years after independence. Columns ( 5) and ( 6) reveal that declines in expat populations explain some of the trade erosion between siblings. In column (6), the coefficient on log expats is 0.206, one-third smaller than the coefficient in column (3).

As a consequence, expat populations account for a smaller amount of trade erosion. The reduction in trade between siblings due to 30 years of independence (relative to the 3-6 year reference group) falls from 67% to 63%.

The gradual decline in trade cumulating over three decades, may be a result of a similar declines in business networks, for which expat populations may constitute an important

19 See Table 1 of [START_REF] Wagner | Immigration and the Trade of Provinces[END_REF]. 20 This exercise is similar to that of [START_REF] Rauch | Ethnic Chinese Networks in International Trade[END_REF] who find that overseas Chinese populations promote trade, particularly for differentiated products, which they interpret as a network effect. 21 We also redefine population and per-capita income as the sum of the logs of each sibling pair.

element. Table 3 reveals that trade and expat populations follow correlated patterns of decline in the wake of independence. Explicitly including expats into a trade regression reduces, but does not eliminate, the trade erosion captured by the independence intervals.

The circumstances of the dissolution of colonial ties varied greatly. Some colonies fought wars to obtain their independence whereas others exited from empires with minimal acrimony. For example, Algeria's independence from France in 1962 involved a protracted conflict whereas Senegal's 1960 independence occurred peacefully. We would expect hostile independence events to cause more trade disruption than amicable ones.

Indeed, it is possible that amicable separations do not depress trade at all and that the results we have obtained so far are averages of negative consequences of hostile separations and zero effects for amicable ones. We test these propositions by categorizing the independence events as peaceful or hostile. Of the 220 independence events in our data set, we categorized 154 as amicable and 66 as hostile.22 However, limiting the sample to events that provide times series information in our period of study, those occurring after 1900, we have 131 amicable and 43 hostile separations.

Figure 6 presents estimated independence coefficients for separations involving conflicts in panel (a), whereas panel (b) shows the results for non-hostile separations. The first result to note is that hostile separations lead to larger declines in trade with the metropole than amicable separations. The dynamics differ as well. Hostile separations have larger immediate effects-which are statistically significant just two years after independence. In contrast, it takes more than two decades for amicable separations to lead to statistically significant trade reductions with the metropole. These findings are consistent with our network capital explanation of independence effects. We interpret hostile separations as abruptly destroying social capital between the two countries. In contrast, amicable separations seem to reduce trade via gradual depreciation.

Conclusion

We find that independence reduces colonial trade with the metropole and other countries in the colonial empire. On average, trade between a colony and its metropole and siblings is reduced by more than 60% after 30 years of independence. The trade erosion is even more pronounced in the case of hostile separations. The trade deterioration associated with independence, however, only partially offsets the long-term advantage of having a colonial history with a trading partner.

If the newly established government of an independent country implemented traderestricting commercial policies, we would expect an immediate and permanent reduction in trade. We do not observe immediate reductions in trade with the metropole. The observed erosion in trade that cumulates over an extended time period subsequent to independence suggests other forces at work. In particular, trade networks embodied in individuals with knowledge of trading opportunities may have deteriorated over time.

Our evidence showing that decreases in the number of French living abroad explain a portion of the post-independence trade deterioration supports this view.

The observed erosion in colonial trade can be explained by higher trade costs, arguably due to the deterioration of trade networks. Higher trade costs reduce welfare for the former colony via two channels. First, consumers pay higher prices for imports.

Second, producers have less access to markets (referred to as market potential in the economic geography literature). Welfare costs of higher trade costs within the former empire would have been mitigated, if there were easily accessible alternative sources of supply and demand. Our results show little evidence of expanded trade by former colonies with the rest of the world. Thus, the long-run contraction of trade of former colonies suggests deleterious welfare effects of independence. A full accounting of welfare changes would require a structural model as well as consideration of the internal consequences of independence.

  Figure 1 displays the number of countries that gained independence since 1900, a total of 174. 1 The two main colonizers in this sample, the UK and France, are shown in red and 1 Table

Figure

  Figure 1: Independence events since 1900

the

  [START_REF] Anderson | Gravity With Gravitas: A Solution to the Border Puzzle[END_REF] derivation, for instance, the basic reason why M j depends on the whole set of dyadic variables and parameters is that the consumer's allocation of income depends on relative prices. The reason why the exporter's monadic effect S i depends on the dyadic vector is the market-clearing requirement. This condition says that total sales in all markets from exporter i should equal the supplier's aggregate output. Anderson and van Wincoop call the terms involving the whole vectors of dyadic φ ij "multilateral resistance indices." Their omission in equation (3) has the potential to bias estimates.

  Figure 3 shows Ivorian (I) and Ghanaian (G) trade patterns with France (F ) and the United Kingdom (U ). The figure reports the ratio of the two countries' trade flows to and from France divided by the corresponding flow with the UK (x IF /x IU , x F I /x U I , and x GF /x GU , x F G /x U G ). The Ivory Coast was a colony of France until 1960 and Ghana a colony of the UK until 1957. Ghana and the Ivory Coast make a useful case study since they are adjacent, comparable in size, and yet were colonized by different countries. Differences

Figure 3 :

 3 Figure 3: Trade of Ivory Coast and Ghana with their respective metropoles

Figure 4 :

 4 Figure 4: Trade of Reunion and Mauritius islands with their respective metropoles

Figure 5 :

 5 Figure 5: Independence effects on colonial trade with metropole, "siblings," and the rest of the world

Figure 6 :

 6 Figure 6: Independence effects depend on type of separation

Table 1

 1

		: Gravity regression control variables
		(1)	(2)	(3)	(4)	(5)	(6)
	ln Pop, i	0.978 a	0.893 a	0.290 a
		(0.006)	(0.009)	(0.046)
	ln Pop, j	0.837 a	0.835 a	0.962 a
		(0.006)	(0.008)	(0.040)
	ln GDP/Pop, i	1.118 a	0.921 a	0.732 a
		(0.007)	(0.010)	(0.015)
	ln GDP/Pop, j	0.945 a	0.702 a	0.634 a
		(0.007)	(0.010)	(0.015)
	ln Dist (avg)	-1.035 a	-1.197 a
		(0.014)	(0.015)
	Shared Language	0.506 a	0.522 a
		(0.034)	(0.038)
	Shared Legal Origins 0.313 a	0.160 a
		(0.026)	(0.029)
	Colonial History	1.560 a	2.605 a
		(0.380)	(0.206)
	RTA	0.958 a	0.593 a	0.521 a	0.400 a	0.411 a	0.317 a
		(0.044)	(0.026)	(0.027)	(0.029)	(0.034)	(0.033)
	Both GATT	0.125 a	0.155 a	0.159 a	0.244 a	0.368 a	0.206 a
		(0.020)	(0.016)	(0.017)	(0.038)	(0.041)	(0.042)
	Currency union	0.688 a	0.483 a	0.486 a	0.499 a	0.469 a	0.309 a
		(0.091)	(0.064)	(0.068)	(0.047)	(0.056)	(0.089)
	Tetrads:				GBR,FRA USA,DEU CHE,CAN
	Fixed Effects:	None Dyads(RE) Dyads	Tetrads	Tetrads	Tetrads
	# Obs.	618233	618233	618233	665531	651603	633190
	RMSE	2.165	1.480	1.473	1.677	1.722	1.832
	Note: Standard errors in parentheses with a , b and c respectively denoting significance at the 1%,
	5% and 10% levels. Standard errors are corrected to take into account correlation of errors
	within dyads in columns (1) to (3). Columns (4) to (6) use three-way clustering by dyad,
	i-year, and j-year using Cameron et al. (2006) method.

Table 2 :

 2 Independence effects on bilateral trade flows Standard errors in parentheses with a , b and c respectively denoting significance at the 1%, 5% and 10% levels. Standard errors are corrected to take into account correlation of errors within dyads in columns (

		(1)	(2)	(3)	(4)	(5)	(6)
	1-2 Years	0.607	0.106	0.114	0.080	-0.129	-0.359 c
		(0.379)	(0.183)	(0.191)	(0.085)	(0.186)	(0.194)
	3-6 Years	0.611	0.082	0.082	0.126 c	-0.307 c	-0.200
		(0.382)	(0.192)	(0.201)	(0.076)	(0.164)	(0.217)
	7-11 Years	0.629 c	0.066	0.047	0.137 c	-0.453 a	-0.216
		(0.381)	(0.197)	(0.205)	(0.076)	(0.157)	(0.219)
	12-19 Years	0.318	-0.239	-0.255	-0.017	-0.705 a	-0.195
		(0.382)	(0.204)	(0.213)	(0.077)	(0.165)	(0.212)
	20-29 Years	0.058	-0.536 a	-0.565 a	-0.249 a	-0.929 a	-0.324
		(0.382)	(0.203)	(0.211)	(0.079)	(0.174)	(0.217)
	30-49 Years	-0.464	-0.919 a	-0.946 a	-0.544 a	-1.467 a	-0.799 a
		(0.388)	(0.203)	(0.213)	(0.081)	(0.174)	(0.227)
	50+ Years	-1.157 a	-0.808 a	-0.756 a	-0.663 a	-1.320 a	-0.764 a
		(0.389)	(0.233)	(0.254)	(0.106)	(0.216)	(0.282)
	Tetrads:				GBR,FRA USA,DEU CHE,CAN
	Fixed Effects: None Dyads(RE) Dyads	Tetrads	Tetrads	Tetrads
	# Obs.	618233	618233	618233	665531	651603	633190
	RMSE	2.165	1.480	1.473	1.677	1.722	1.832

Note:

Table 3 :

 3 French expatriates and trade within the French Empire

		(1)	(2)	(3)	(4)	(5)	(6)
	Sample:	Colony-Metropole		Siblings
	Depvar:	Expats Trade	Trade Expats Trade	Trade
	3-6 Years	-0.484 c -0.462 c -0.324
		(0.263) (0.254) (0.272)
	7-11 Years	-0.570 b -0.502 b -0.341 -0.022 -0.021	-0.064
		(0.253) (0.239) (0.254) (0.065) (0.184)	(0.183)
	12-19 Years -0.713 b -0.923 a -0.718 b -0.175 b -0.845 a	-0.871 a
		(0.285) (0.291) (0.315) (0.084) (0.278)	(0.276)
	20-29 Years -1.317 a -1.263 a -0.885 a -0.830 a -1.232 a	-1.169 a
		(0.371) (0.323) (0.343) (0.115) (0.317)	(0.319)
	30-49 Years -2.058 a -1.787 a -1.198 a -1.618 a -1.399 a	-1.219 a
		(0.518) (0.399) (0.401) (0.137) (0.365)	(0.373)
	50+ Years	-1.785 a -1.698 a -1.190 b -1.333 a -1.109 a	-0.995 b
		(0.576) (0.453) (0.464) (0.158) (0.40)	(0.405)
	Expats			0.290 a			0.206 a
				(0.077)			(0.072)
	N	1153	2299	2299	13319	15549	15549
	R 2	0.354	0.592	0.605	0.395	0.181	0.184
	RMSE	0.414	0.651	0.640	.538	1.642	1.639

Although the DOTS contains both zeros and missing data, inspection of the data shows many examples with zero reports that should be positive.

See Anderson and van Wincoop (2003),[START_REF] Eaton | Technology, Geography, and Trade[END_REF][START_REF] Eaton | Technology, Geography, and Trade[END_REF][START_REF] Chaney | Distorted gravity: Heterogeneous Firms, Market Structure and the Geography of International Trade[END_REF].

Alternatively, one can substitute GDP for population which will result in different coefficient estimates but with identical fit.

The computational benefits of the tetrads approach would be even greater for commodity level trade since monadic terms are presumed to be good-specific.

Generating all possible tetrad combinations would involve dealing with literally billions of observations in our case.

 7 Stata programs are available at http://strategy.sauder.ubc.ca/head/sup/.

A surge in Nigerian GDP would have approximately the same effect on Ghana and Ivory Coast, whereas a surge in German GDP would have similar effects on the UK and France.

Column (3) of Table1states that the effect of signing either type of agreement is to create roughly exp(0.5) -1 = 65% more trade.

Their estimate falls to 0.46 when monadic fixed effects are introduced.

[START_REF] Bonfatti | Decolonization: the Role of Changing World Factor Endowments[END_REF] develops a Heckscher-Ohlin model of trade between a colony, metropole, and third country that predicts that independence is more likely for colonies with good trading opportunities with the rest of world. An implication of the analysis is that independence should be accompanied by increased

The coefficients for the control variables differ very little from the estimates report in column (3) of Tables 1.

We are very grateful to Bernard Gentil for making this data from the French Ministry of Foreign Affairs available to us and helping us with the extraction and understanding of this data.

We started with information listed in the "Territorial Change" database[START_REF] Tir | Territorial Changes, 1816-1996[END_REF] from the Correlates of Wars project and used internet sources (the CIA Factbook, BBC country briefs, and Wikipedia) to complete the classification, shown in Table4.

was close to a factor of 200 in 1968, it falls gradually over time, so that Mauritian exports to UK and France in the 2000s are roughly the same, as expected. Figures 3 and4 both portray an erosion of colonial trade subsequent to independence. To see if this picture extends generally, we turn to the regression results.

Tables 1 and2 contain estimation results. We report results for six specifications and present estimates of the control variables in the first table and the independence variables in the second table. The first three columns portray results where exporter and importer population and per capita GDP proxy for exporter-specific and importer-specific effects. In the ensuing three columns, these effects are eliminated by creating tetradic trade flows. This requires choosing reference countries. To investigate the robustness of the method, we employ three country pairs-Great Britain-France, the United States-Germany, and Switzerland-Canada-as the reference countries (designated k and in the previous section) and report estimates for all three. All specifications include year dummies that are not reported in the table.

The first specification pools data, allowing us to compare results for our large panel to those in the literature. The results, listed in column (1), show that increases in exporterand importer-country per capita income and population promote bilateral trade with elasticities close to one (as predicted in most theoretical derivations). Distance between partners reduces trade and the estimated elasticity is very close to one (the typical finding). The linkages variables-colonial history, common language, GATT membership, RTAs, and currency union-increase trade and all estimates are highly statistically significant. This specification recognizes the possibility of correlated observations within dyads by clustering the standard errors according to ij directional pairs. Interestingly, the pooled OLS coefficients for RTA and GATT are higher than in published studies. [START_REF] Rose | Does the WTO Really Increase Trade?[END_REF] tends to find negative and insignificant GATT effects in his study of 178 countries over the 1948-1998 period when dyadic effects are excluded.

Columns (2) and (3) reveal that, with dyadic random or fixed effects, independence is estimated to have small and insignificant positive effects on trade in the first decade.

Then it turns negative, becoming significantly negative in the 20-29 year interval. Trade with the metropole is minimized in the 30-49 year interval. 12 Using the column (3) estimate, independence for 30-49 years contracts bilateral trade to 39% (e -0.946 ) of its independence-year level. The small rebound in bilateral trade estimated for 50 or more years does not arise in all specifications and is not statistically significant in any specification (except OLS).

Given the finite span of our trade data, we do not observe all bilateral relationships passing through each interval since independence. Thus, since the Soviet Union collapsed in 1991, post-USSR trade flows contribute to the estimates of the first four intervals, but not the later ones. However, unreported regressions on the first three columns of Tables 1 and2 show very little difference in the coefficients estimated when we omit former Soviet Republics from the regressions. 13 The random effects specification reported in column (2) allows us to compare trade of countries that have been independent for very long periods with those that remain colonies to this day. 14 The effect of being in a colonial relationship is estimated to be 2.605, whereas 50 years of independence has a coefficient of -0.808. Thus, even in the long-run, countries that once had a colonial relationship trade six times (e 2.6-0.8 ) more than other dyads. If one includes the effects of a common language and legal system, which many former colonies retained centuries after independence, the total long-run impact of colonization on trade rises to a factor of 12 (= e 2.6+0.5+0.2-0.8 ).

12 We also estimated a specification with the first four intervals given by 1-4, 5-9, 10-14, and 15-19. The column (3) results become 0.125, 0.138 c , -0.095, -0.284 a , -0.527 a , -0.908 a , and -0.716 a . Thus we still see small positive effects in the first decade, followed by increasingly negative and significant coefficients, with the largest estimated reduction at 30-49 years.

13 Taking column (3) as an example, the independence coefficients are 0.166, 0.087, 0.054, -0.233, -0.536 b , -0.911 a , and -0.725 a . Therefore 30 to 49 years of independence reduces trade to 40% of its initial level in this sample, against 39% when including the former USSR in the regression.

14 Fixed effects drops the colony history dummy because it is not time-varying within dyads.

Appendix: Gravity controls and independence dates