Shuai Wang

Joe Raad

Peter Bloem

Frank Van Harmelen

Refining Transitive and Pseudo-Transitive Relations at Web Scale

The publication of knowledge graphs on the Web in the form of RDF datasets, and the subsequent integration of such knowledge graphs are both essential to the idea of Linked Open Data. Combining such knowledge graphs can result in undesirable graph structures and even in logical inconsistencies. Refinement methods that can detect and repair such undesirable graph structures are therefore of crucial importance. Existing refinement methods for knowledge graphs are often domain-specific, are limited to single relations (e.g. owl:sameAs), or are limited in scale. We present a challenge consisting of a number of datasets of transitive and pseudo-transitive relations and hand-labeled gold standards, as well as baselines. We introduce an efficient web-scale knowledge graph refinement algorithm that works for such relations. Our algorithm analyses the graph structure, and allows the use of weighting schemes to heuristically determine which possibly erroneous edges should be removed to make the graph cycle free. When compared against generalpurpose graph algorithms that perform the same task, our algorithm removes the least amount of edges to make the graph of transitive relations cycle-free while maintaining a better precision in identifying erroneous edges as measured against a human gold-standard.

Introduction

The central tenet of Linked Open Data is the publication and integration of RDF datasets. Such integration can result in logical inconsistencies or undesirable graph structures. For transitive relations, this can result in chains of relation instances forming complex nested cycles involving many entities across datasets in the corresponding graph. In practice, even logically valid cycles may have negative consequences. For example, a cycle of rdfs:subClassOf triples in an intended hierarchy enforces equality of all classes in the cycle, which may prevent algorithms such as query expansion from termination. To ensure data quality, refinement methods have been developed [START_REF] Paulheim | Knowledge graph refinement: A survey of approaches and evaluation methods[END_REF]. However, these methods often depend on domain-specific functionalities [START_REF] Heist | Entity extraction from Wikipedia list pages[END_REF], or limited to a specific relation (e.g. owl:sameAs) [START_REF] Raad | Constructing and Cleaning Identity Graphs in the LOD Cloud[END_REF][START_REF] Wang | SUBMASSIVE: Resolving subclass cycles in very large knowledge graphs[END_REF] or suffer from limited scalability [START_REF] Wang | SUBMASSIVE: Resolving subclass cycles in very large knowledge graphs[END_REF]. Such limitations call for the development of scalable and domain-independent algorithms. This paper presents a new approach for detecting undesirable cycles in transitive relations. It uses graph structural characteristics and a heuristic notion of reliability of triples, without the need for any domain-dependent information such as labels, comments and other textual information in context [START_REF] Heist | Entity extraction from Wikipedia list pages[END_REF]. Our approach (i) is independent from domain and language, (ii) has a better precision than general-purpose graph-theoretical methods and (iii) maintains good scalability and efficiency.

Graph structure reflects logical properties and vice versa. For example, when a relation is asymmetric, any cycle of size two in its graph violates consistency. Similarly, for irreflexive relations any self-loop is invalid. This suggests the use of graph-theoretic algorithms to detect logical inconsistencies. In OWL, the transitivity of a relation is typically specified directly through owl:TransitiveProperty. In this work, we extend to what we call pseudo-transitive relations: that of a sub-property or the inverse of a (pseudo-)transitive relation and those whose intended semantics is assumed to be both transitive and anti-symmetric, even if not formally asserted. In this paper, we exclude equivalence relations (e.g. owl:sameAs) and those whose (pseudo-)transitivity are mistakenly asserted or implied on the LOD Cloud (e.g. foaf:knows).

Besides the graph structure, another feature to be used for the refinement of knowledge graphs that is independent from domain and language is the reliability of triples. While there can be different heuristics, we measure reliability of an edge by counting the number of the occurrences of this edge across datasets of the web-scale integrated graph (see more details in Section 5.2). For small self-sufficient datasets, this feature is not of great value because the logical foundations of knowledge graphs dictate that repeated statements in datasets are redundant. However, such feature has been shown to be useful for the ranking of documents and entities [START_REF] Harth | Using Naming Authority to Rank Data and Ontologies for Web Search[END_REF] and the identification of erroneous assertions and improvement of data quality [START_REF] Bonatti | Robust and scalable Linked Data reasoning incorporating provenance and trust annotations[END_REF] when the sources of data are present. Figure 1 is an example subgraph of skos:broader with such weights extracted from the LOD Laundromat 2015 crawl [START_REF] Beek | LOD laundromat: a uniform way of publishing other people's dirty data[END_REF]. It is more likely that dbc:Numbers is a broader than dbc:Integers (weighting 72), while it is unlikely that dbc:Integers is a broader concept for dbc:Numeral systems (weighting 1), showing that weights can indicate the reliability of edges. This example also shows that the relation between some entities can be ambiguous, making it difficult to construct a perfect gold standard. For example, some may believe that numbers are parts of numerical systems while others may think the study of numbers includes the study of numerical systems. Finally, it also indicates that the weights of edges in the neighbourhood can have an impact on the reliability of edges.

The hypotheses that we pursue in this paper are as follows:

H1: By taking graph structural properties (how edges are involved in complex nested cycles) into account, we can make knowledge graphs acyclic while removing fewer edges than graph theoretical methods. H2: Taking the reliability of triples into account improves the accuracy for identifying erroneous edges. This paper presents an algorithm to refine transitive and pseudo-transitive relations for large integrated knowledge graphs at web scale by removing as few edges as possible to obtain acyclic graphs. More specifically, the paper makes the following contributions:

1. a new metric for the hardness of resolving cycles based on strongly connected components. 2. a generic scalable approach for the refinement of (pseudo-)transitive relations using an SMT solver by exploiting Strongly Connected Components. 3. an evaluation that shows how taking into account the reliability of triples can improve the precision of the graph refinement algorithm. 4. a dataset of several widely used (pseudo-)transitive relations with their reliability weights. 5. a new gold standard of thousands of manually annotated triples to be used in the evaluation and comparison of graph refinement algorithms.

This paper is structured as follows: Section 2 and 3 discuss related work and present preliminaries. Section 4 describes the dataset and analyses its complexity. Section 5 presents our approach for refining (pseudo-)transitive relations. Section 6 presents the implementation details, our gold standard, and the conducted evaluation. Section 7 discusses the results and concludes the paper.

2 Related Work

Knowledge Graph Refinement Methods

According to Paulheim's survey [START_REF] Paulheim | Knowledge graph refinement: A survey of approaches and evaluation methods[END_REF], there are two main goals for knowledge graph refinement methods: completing the knowledge graph with missing knowledge, and correcting asserted information. This work falls into the latter category of approaches, as we aim at refining transitive and pseudo-transitive relations by removing edges that lead to unwanted cycles and are potentially erroneous. The closest predecessor of our work is the approach by [START_REF] Wang | SUBMASSIVE: Resolving subclass cycles in very large knowledge graphs[END_REF], introduced for refining edges of rdfs:subClassOf by exhaustively listing simple cycles 1 and removing minimal edges so that the resulting graph is cycle free. However, this approach faces a combinatorial explosion when listing all simple cycles of large nested clusters, and therefore cannot be applied on some relations we study in this work. Sun et al. [START_REF] Sun | Breaking cycles in noisy hierarchies[END_REF] propose similar strategies for removing edges causing cycles in graph. However, this approach requires inferring a graph hierarchy (e.g. using a Bayesian skill rating system), and has been only tested on synthetic datasets and the Wikipedia category graph. Another recent approach that targets the refinement of categorical and list information is introduced by [START_REF] Heist | Entity extraction from Wikipedia list pages[END_REF]. To our best understanding, this graph-based refinement approach relies on external information of hypernyms, and applies only to English DBpedia categories and lists. Moreover, and similarly to the work presented in [START_REF] Fossati | Unsupervised learning of an extensive and usable taxonomy for DBpedia[END_REF], these approaches assume the existence of a hierarchy and takes advantage of pre-defined roots.

In this work, we show that such hierarchies are frequently violated in the Web, therefore the applicability of such approaches becomes limited in such context. Finally, the graph-based approach presented in this work is similar to other approaches that have also exploited the graph structure for detecting and removing different types erroneous edges at the scale of the Web, such as type [START_REF] Paulheim | Improving the quality of linked data using statistical distributions[END_REF] and identity links [START_REF] Raad | Constructing and Cleaning Identity Graphs in the LOD Cloud[END_REF].

General MWFAS Algorithms

In this section we discuss general-purpose graph algorithms for making graphs cycle-free. When restricting to a single relation, the problem of resolving cycles is identical to finding the Maximum Weighted Directed Acyclic Subgraph (MW-DAS). 2 Historically, the removed edges are also called arcs and form a feedback arc set (FAS). Therefore, the problem is equivalent to Minimum Weighted Feedback Arc Set (MWFAS), and we will use these names for the rest of the paper.

The MWFAS problem is APX-hard. Despite the hard limit on its approximability, there are polynomial-time approximation algorithms. The following summarises some algorithms that scale to at least tens of millions of edges according to [START_REF] Simpson | Efficient computation of feedback arc set at web-scale[END_REF] where more details are presented. The underlying idea of the KwikSort(KS) algorithm is to sort vertices on the number of back arcs induced, and removing the edges with many induced back arcs. The algorithm runs at O(n log n) when assuming that arc membership can be tested in constant time. In our experiments we used an optimised implementation that uses O(n log n) additional space. Since KS takes a random initial ordering, we take the best result of 200 runs.

The Greedy(GRD) algorithm greedily appends all "sink-like" vertices at the end of a sequence s and inserts the "source-like" vertices at the front of s. The implementation in [START_REF] Simpson | Efficient computation of feedback arc set at web-scale[END_REF] uses bins [START_REF] Öncü | A fast and effective heuristic for smoothing workloads on assembly lines: algorithm design and experimental analysis[END_REF] for the selection of vertices in each iteration. The bins distinguish nodes with only outgoing edges, nodes without outgoing edges, and nodes with both in-and outgoing edges. Each node falls in one of these bins.

By using s as a linear arrangement and picking all the feedback arcs, it minimize the number of arcs with different orientation. GRD runs in time O(m+ n) and uses O(m + n) space. It has a guarantee of removing no more than 1 2 |E| - 1 6 |V | edges but experiments from [START_REF] Simpson | Efficient computation of feedback arc set at web-scale[END_REF] observed that the size of FAS is drastically smaller than this worst-case bound.

For a graph G, the BergerShor(BS) algorithm begins with a random permutation over the vertices V . It then processes each vertex by comparing its in-degree and out-degree. If a vertex has more incoming arcs than outgoing ones, the incoming ones are removed and added to a set E while the outgoing arcs are removed and discarded. The collected arcs E form an acyclic graph G (its counterpart is the set of arcs removed). The algorithm runs in time O(m+n) and [START_REF] Simpson | Efficient computation of feedback arc set at web-scale[END_REF] show that the algorithm far out-performs this worst-case bound.

Finally, we can adopt a depth-first traversal(DFS) algorithm and remove all arcs that form a cycle during the search to ensure that the resulting graph is acyclic. Its runtime complexity is O(m + n). The algorithm does not make any intelligent decision nor minimize the resulting size of FAS.

Preliminaries

A knowledge graph is a directed and labelled graph G = V, E, Σ E , l E , where V is the set of vertices (nodes), E ⊆ V × V the set of relations (edges), and Σ E is the set of edge labels. l E : E → 2 Σ E is a function that assigns to each edge in E a set of labels belonging to Σ E . For a specific relation R ∈ Σ E , we denote G R = V R , E R the edge-induced subgraph that only includes those edges whose labels are R, with V R ⊆ V and E R ⊆ E. In the case of weighted graphs, we introduce an additional weight function f w : E → N that assigns to each edge a weight. In Section 5.2, we describe how these weights are calculated.

A walk in a graph G R is a sequence of vertices v 0 , v 1 , . . . , v n , with the edge (v i , v i+1 ) ∈ E R . A walk is a path if no edge is repeated. A path between two vertices is shortest if the number of vertices on the path is minimal. A path is a cycle if it is closed, i.e. v 0 = v n . Apart from reflexive relations, the smallest possible cycle involves two vertices. We denote the set of such size-two cycles by E C2 for later convenience. A graph without the corresponding edges of E C2 (and vertices if left as singletons) is denoted G = G\E C2 .

A Strongly Connected Component (SCC) of G R is a subgraph where any two of its vertices can be reached by a path (i.e. the subgraph is strongly connected) and is maximal for this property: no additional edges or vertices can be included in the subgraph without breaking strong connectivity. 3 The collection of all SCCs forms a new graph G SCC , and the set of SCCs of G is denoted κ(G). In this paper, the process of removing edges in an SCC to make it acyclic is referred to as resolving cycles, and graphs with no cycles are referred to as DAGs (directed acyclic graphs). In our datasets, there is often one SCC that is significantly larger (with the most vertices and edges) than others among all the SCCs of a graph. We refer to it as G B when discussing its properties. Figure 2 presents an example of a graph G with its introduced variants: G SCC , G , and G SCC . Note that cycles of size two are not necessarily SCCs of size two as they can be nested into other cycles and form a bigger SCC (e.g. size-two cycle between node 5 and 6).

There are efficient algorithms for computing the SCCs of a graph such as Tarjan, which take linear time O(|V |+|E|) assuming constant time for retrieving edges [START_REF] Hsu | A Comparative Study of Algorithm for Computing Strongly Connected Components[END_REF]. It is useful to observe that cycles in a graph G can never span across multiple SCCs (since if there were any such cycle, the SCCs involved would form a bigger SCC, which contradicts its maximality w.r.t. strong connectivity). Therefore, since cycles in G are always contained inside a single SCC, and since the collection of all SCCs of G form a partition of the vertices of G, we can safely divide-and-conquer the process of resolving cycles in G across all SCCs of G. This allow us to focus the cycle resolution locally in comparison with inefficiently and exhaustively listing all simple cycles as in [START_REF] Wang | SUBMASSIVE: Resolving subclass cycles in very large knowledge graphs[END_REF].

(Pseudo-)Transitive Relations in the LOD Cloud

Dataset

In this work, we use the LOD-a-lot dataset [START_REF] Fernández | LOD-a-lot[END_REF] as a representative copy of the LOD Cloud. This compressed data file of 28 billion unique triples is the result of the integration of over 650K datasets that are crawled and cleaned by the LOD Laundromat in 2015 [START_REF] Beek | LOD laundromat: a uniform way of publishing other people's dirty data[END_REF]. In the LOD-a-lot dataset, there are 2,486 relations explicitly stated as owl:TransitiveProperty, used in more than 776 million triples (2.7% of all triples). When the semantics of rdfs:subPropertyOf and owl:inverseOf is exploited, the number of (pseudo-)transitive relations increases to 8,804 relations, used in around 5.5 billion unique triples (19.5% of the triples). Our manual examination shows that a number of these properties are incorrectly asserted or inferred, such as the widely used foaf:knows relation.

For transitive relations, graph characteristics can reflect the logical properties, and vice versa. For instance, irreflexive and antisymmetric relations such as iwwem:dependsOn allow for no cycle anywhere in the graph. We consider skos:broader a pseudo-transitive relation, as it was not designed to be a transitive property despite being a subproperty of skos:broaderTransitive, which is typed owl:TransitiveProperty [START_REF] Miles | SKOS simple knowledge organization system reference[END_REF]. Unless otherwise specified, we assume that the graph of relations such as rdfs:subClassOf and geo:parentFeature should be cycle-free despite the logical validity of cycles. Our maual examination also found that many relations are defined together with their inverse (e.g. skos:broader and skos:narrower). There can also be a relation like that of equivalence (e.g. owl:sameAs, rdfs:equivalentClassOf). This paper examines a selection of 10 relations (see e.g. Figure 3 and Table 1). These are popular relations, all of them directly typed as owl:TransitiveProperty with over 100K triples. We exclude the few that actually represent equivalence relations, or whose biggest SCC has less than 10 vertices unless its inverse is to be studied.

Strongly Connected Components Analysis

To get a sense of how difficult it is to make graphs cycle-free, we introduce in this section a number of metrics. We may turn to standard metrics for the degree of transitivity of a graph, such as the transitivity index T (the number of actual triangles in a graphs as a fraction of the number of all possible triangles), the average clustering index C (the average over the local clustering coefficients of all vertices, where a local clustering coefficient of a vertex is the actual number of edges in the direct neighbourhood of the vertex divided by the possible number of such edges), or the global reaching centrality (GRC) [START_REF] Mones | Hierarchy measure for complex networks[END_REF]. These measures can be useful for the understanding of graph-theoretical properties. However, our analysis shows that none of T , C or GRC manage to capture the size of SCCs or the hardness of cycle-resolution. Thus they cannot be used as a measure for cycle resolving. We therefore introduce new quantitative measures based on SCCs.

When examining the SCCs of the LOD-a-lot knowledge graph regarding popular relations, we observe two facts: 1) cycles of size two are very common across the graphs. When not nested into other cycles, they are SCCs with two nodes (SCCs of size two), which is the most common type of SCC. This suggests the ambiguity in definition and semantics of the relation; 2) there often exist a very big SCC that covers a majority of nodes involved in the SCCs. This is very different from synthetic models typically used in the evaluation of MWFAS algorithms. The following are measures on how much the SCCs are due to size-two cycles, and other complex nested cycles.

Alpha measure. Let α be the number of edges in cycles of size two divided by the number of all edges in its SCCs

α = f α (G) = |E C2 |/|E SCC |. By definition, f α (G) = f α (G SCC
). This gives the fraction of edges that can be determined locally if given additional information (e.g. the reliability on each edge). Beta measure. Remove all the cycles of size two from G and obtain G = G\E C2 . The corresponding SCCs of G form a graph G SCC . Let β be the number of edges in G SCC divided by the number of all edges in G SCC :

β = |E SCC |/|E SCC |. Similarly, we have f β (G) = f β (G SCC
). This measures the proportion of edges to make decisions on if all edges in size-two cycles are not involved in any SCC. In other words, it gives a measure of the fraction of edges in more complex nested cases. For the graph G in Figure 2, α = 0.5 and β = 0.25. As for its biggest SCC, α = 0.4 and β = 0.3. Figure 3 reports on the α and β values for the 10 selected relations in Table 1. The figure on the left illustrates the alpha-beta measure. In general, the greater α is, the more size-two cycles there are. The smaller β is, the more likely it is to resolve the cycles by simply making decisions on the edges of cycles of size two (e.g. skos:narrower has β = 0). On the other hand, skos:broader and dbo:previousWork are examples with more complex cycles nesting into each other. An observation is that the tangent of a line crossing the origin and each point can indicate the hardness. This inspires the following definition.

Gamma measure : For an SCC G, the minimum fraction of decisions to be made to make G cycle-free can be captured by α + β. Note that an SCC G gets harder when its β is greater, or α is smaller. This can be captured by β/α or β -α. To avoid cases where α = 0 and to make γ a term between 0 and 1, we use the latter and define

γ = f γ (G) = (α + β)(1 -α + β)/2.
This gives a measure of the hardness to make an SCC cycle-free. Delta measure : Note that using the Gamma measure, we can then estimate the effort required to make each of a graph's SCCs cycle-free. For a graph

G in general, δ = f δ (G) = s∈κ(G) f γ (s) * |E|.
It is a sum over the γ value multiplied by the number of edges of each of its SCCs.

Table 1 presents key information of the graphs of the 10 selected relations, together with the values of our metrics. For instance, among the 11.8M skos:broader edges, 356.9K of them are included in a total of 6.7K SCCs. The biggest SCC, G B R , captures 227K edges, amounting to 63.6% of the edges in at least one cycle. Due to its complexity and scale, G B R has a big δ. In correspondence, that of G R Table 1: Popular transitive and pseudo-transitive relations and their measures is proportionally big. In contrast, the problem of its inverse, skos:narrower, is a much easier problem with only 48 edges involved in cycles with a very small δ value. Thus, it is possible to resolve the cycles by manually annotating each edge in its E SCC R . Comparing the entries of skos:narrower with dbo:successor, we can see that the δ measures can reflect cases where some big graphs are not necessarily harder to resolve, which is not captured by graph-theoretical measures. These new measures provide a quantitative evaluation on the hardness of cycle resolving, help to study the nature of its complexity, and serve as references for the design of algorithms, choice of parameters as well as the sampling of data.

Relation (R) G R SCCs of G R G B R (the biggest SCC) |E R | |V R | |E SCC R | |V SCC R | |κ(G R )| δ |E B R | |V B R |

Algorithms

Algorithms for Cycle Resolving

We aim to design an algorithm that deals with knowledge graphs of (pseudo-) transitive relations that (i) does not rely on a ranking of nodes; (ii) captures the transitivity of relations; (iii) is capable of handling the complex structure resulted from large amount of nested cycles (graphs with high γ values); (iv) is as conservative as possible in removing edges when resolving the cycles; and (v) is extendable to capture other logical and graph properties. The following section presents our algorithm with an evaluation.

We present Algorithm 1 as a general purpose cycle-resolving method for refinement. The algorithm exploits off-the-shelve technology for SMT solvers (Satisfiability Modulo Theories) [START_REF] Bjørner | Engineering theories with Z3[END_REF]. The algorithm does not deal with reflexive edges as they can be processed trivially and in linear time. There are three main steps in the algorithm. We first compute the SCCs of the input graph (line 3). Then, we perform partitioning over big SCCs to a given bound b 1 (line 4). This is due to the limit of SMT solvers' capability to handle large amount of clauses. Finally, we sample some cycles and repeatedly call an SMT solver to identify edges to be removed (line 5-17). In the following, we discuss the strategies adopted to deploy it at web scale.

Strategies for Graph Partition. The graph partition problem is well-studied in graph theory. The minimum k-cut problem requires finding a set of edges Algorithm 1: General-purpose algorithm for cycle resolving 1 Input: a graph G with no reflexive edges, its weight function fw (optional), a bound b1 for the number of maximum nodes for each SCC, and a bound b2 for the number of hard clauses. Result: a cycle-free graph H and a set of edges removed A. whose removal partitions the graph to at least k connected components. There exist efficient algorithms and open-source implementations. However, our experiments show that breaking an SCC s into k partitions directly results in a significant amount of edges being removed, whereas our goal is to be as conservative as possible in our repair strategy. For reducing the amount of edges to be removed, our Strategy P1 partitions the graph into two subgraphs and then computes the SCCs. This process is repeated until each of the resulting SCCs are within the size bound b 1 . For weighted graphs (see the next section for how weights are computed), we can adopt a Strategy P2 by first removing the edges with the lower weights in size-two cycles, and then use Strategy P1.

Strategies for Cycle Sampling. The bottleneck for the earlier work in [START_REF] Wang | SUBMASSIVE: Resolving subclass cycles in very large knowledge graphs[END_REF] was the combinatorial explosion when exhaustively listing all cycles of a graph. We therefore focus on sampling an amount of cycles in each iteration that balances the tradeoff between representative capacity and redundancy. Strategy S1 focuses on the edges: choose a random edge (s, t) in an SCC, then compute the shortest path from (t, s). This forms a cycle. In total we collect b 2 such cycles. As an alternative strategy, we can adopt the Strategy S2 that selects two nodes randomly and computes the shortest path from one to the other, and back.

Resolving Cycles with an SMT solver. This section gives details of the interaction with the SMT solver (line 9 and 13 in the algorithm). The SMT solver is used for two purposes: to satisfy all hard constraints and to satisfy the maximal amount of soft constraints. 4 The use of an SMT solver makes it possible to easily extend the current algorithm to weighted cases. In each iteration, for every s ∈ S , we introduce a propositional variable p e for each edge e. When there is a cycle v 1 , . . . .v k , we add a hard clause [¬p (v1,v2) ∨ . . . ∨ ¬p

(v k-1 ,v k ) ∨ ¬p (v k ,v1) ]
to the SMT solver (accumulated in conjunction). The clause is satisfied when at least one of the p i,j is assigned False in the returned model of the solver, which indicates the removal of the edge (i, j). To keep the maximal amount of edges, we add a soft clause [p e ] for each edge e. The SMT solver performs a constrained optimisation process within a bounded time. The result of this is a near-optimal solution with the least amount of propositional variables set to False. From the model, we can retrieve edges to be removed to resolve all the encoded cycles. We repeat this process until all the SCCs are resolved and return the DAG and the removed edges. This approach can be easily extended to weighted cases, with the weight for each soft clause as the reliability for each edge.

Weights

Due to the logical foundation of knowledge graphs, repetition of statements is ignored because of the idempotency of the conjuction operator: (φ ∧ φ) ↔ φ. Nevertheless, we believe that there is an important signal to be gained: the occurrence of the same triple in multiple knowledge graphs is an informal signal that multiple information providers have expressed support for. Thus, the chance that a statement is erroneous decreases with the number of knowledge graphs including this statement. Our algorithm takes the two kinds of weights for soft constraints (Algorithm 1, line 12). Counted Weights: the simplest way to obtain the weight of a triple is to count the number of occurrences across the graphs. The LOD-a-lot file consists of 650K datasets (graphs), making it feasible to compute such weights for popular relations; Inferred Weights: inspired by the observation and analysis in Section 4.1, we take advantage of the logical redundancy between implied properties to compute weights. If a triple (A rdfs:subClassOf B) is present in the integrated graph, and there is also an equivalence relation (A owl:equivalentClass B) or (B owl:equivalentClass A), then we make its weight 2 (i.e. we give more credence to (A rdfs:subClassOf B), otherwise 1).

For skos:broader, we can take advantage of its inverse relation skos:narrower.

If together with the triple (A skos:broader B) the triple (B skos:narrower A) exists in the dataset, then we assign weight 2 to the triple (A skos:broader B), otherwise 1. While counted weights always exist, inferred weights are more restricted and less common and requires some manual examination. Still, we experiment different weighting scheme for the sake of comparison in evaluation.

6 Experiments and Evaluation

Implementation and Parameter Settings

We implemented our algorithm5 in Python. We adopt the Python binding of METIS6 , a graph partitioning package based on the multilevel partitioning paradigm providing quick and high-quality partitioning. We use Z37 as SMT solver [START_REF] Bjørner | Engineering theories with Z3[END_REF], and the networkx package8 for the handling of graphs and SCCs.

Based on some trial-and-error experience, in the following experiments we set b 1 = 15, 000 (i.e. maximum size of an SCC before requiring graph partitioning), and apply Strategy P1 with k = 2. To balance the trade-off between efficiency against accuracy, we obtain b 2 = 3, 000 clauses at most and set the time limit for the SMT solver to 10 seconds for each SCC.

All experiments were conducted on a 2.2 GHz Quad-Core i7 laptop with a 16GB memory running Mac OS. All reflexive edges were eliminated in preprocessing.

Gold Standard

For the evaluation of hypothesis H2, we annotated a number of statements from the two most frequent (pseudo-)transitive relations (rdfs:subClassOf and skos:broader, according to Table 1). For each relation, we have two gold standards. In the first gold standard G1, we randomly pick 500 edges from E SCC R . The second gold standard separates SCCs of two nodes (G2-a, 200 edges) from the rest (G2-b, 500 edges). When sampling G2-b, we first assign a number on each SCC according to their δ-value and then sample the amount of edges assigned to each SCC randomly, thus providing an evaluation set for edges in complex nested cases. There are 1,199 unique edges in the gold standard of skos:broader with a total of 632 (52%) annotated 'remain' in contrast to 401 (33%) 'remove'. This analysis suggests that its under-specified definition caused confusion and subsequently resulted in a complex faulty graph structure. The great proportion of unknown entries for rdfs:subClassOf is discussed in Section 7.2.

The annotation process was conducted using the platform ANNit9 . These gold standard datasets are online10 together with detailed criteria, analysis and limitations. Its consistency was validated manually and by a Python script.

Efficiency Evaluation

In this section, we compare our refinement algorithm against other MWFAS algorithms. Table 2 presents the results of the number of edges removed for ten subgraphs of LOD-a-lot, both overall and within the SCCs. The highlighted cells show that our approach removes fewer edges during refinement. The result supports our Hypothesis H1. Both approaches are fast: general-purpose MWFAS algorithms take 2-12 seconds except KS, which may take up to 1 minute. Our algorithm takes 8-115 seconds except for skos:broader, which can take up to 8 minutes. Details of benchmarks are included in the repository of gold standard. The results in Table 2 are the best records of three runs. Finally, the results are validated to be free from SCCs except singletons.

Accuracy Evaluation

As for Hypothesis H2, we evaluate our algorithm's unweighted version against the two weighted versions (counted and inferred weights), as well as the MW-FAS algorithms. Table 3 presents the precision (p) and recall (r) as well as the number of removed edges (|A|) for skos:broader and rdfs:subClassOf. Each entry represents the average of three runs. Taking weights into account (especially counted weights) has a positive impact on precision while maintaining a similar recall. Our approach achieves the best precision among all methods while removing the least amount of edges. As for rdfs:subClassOf, the impact on precision can be positive but unstable due to the limits to be discussed in the next section. When weights are not provided, P1S1 removes the least amount of edges. Otherwise, P2S1 is more optimal for our approach considering the balance between efficiency and accuracy. Overall, this evaluation gives positive support to our Hypothesis H2 and further enhances our conclusion for Hypothesis H1.

7 Discussion and Future Work

Summary

This paper presented a new algorithm for the refinement of transitive relations and pseudo-transitive relations in very large knowledge graphs. We employed an SMT solver in implementation and evaluated on 10 datasets and validated our Hypothesis H1. As a proof-of-concept, we extended our work to weighted knowledge graphs and evaluated on our gold standard. The results provided positive support for our Hypothesis H2 and we also showed that taking weights into account during refinement has a good potential.

Discussion

The graph of rdfs:subClassOf has 4.4 million triples, of which 1.4K are in SCCs. Only 17 triples have inferred weights greater than 1, while 292 triples have such counted weights. The skos:broader graph has 11.8 million triples, of which 265.9K are among SCCs. There are only 39 triples with inferred weights of 2 compared to 284.6K for counted cases. It is clear that far fewer triples are assigned inferred weights than counted weights, making it a less general weighting scheme. Table 3 shows that inferred weights have no significant impact on the results due to their small number. The following focuses on counted weights. Figure 4 plots the frequency distribution of counted weights for both datasets. It shows a power law distribution for the weights of skos:broader, implying that some relation instances have been stated repeatedly across the web. This justifies the use of frequency of triples as a heuristic for reliability. In comparison, rdfs:subClassOf is less popular and its frequency distribution is less clear and thus less reliable for decision making.

Finally, the unstable result of rdfs:subClassOf is mostly due to the biggest SCC which has 780 edges, amounting to 52% of all the edges in SCCs. All these edges come from a single big faulty dataset, and are all annotated 'unknown'. This explains the big variance for precision and recall as in Table 3. The algorithm essentially grounds relations to propositional logic, thus making it possible to combine it with additional logical constraints with optimisation in the future.

For symmetric relations, we can map the vertices in size-two cycles to one in a new graph while keeping track of the correspondence between the new graph and the original graph. If an edge in the new graph is removed, we remove the corresponding edges of the original graph.

Graph partition is an imprecise step in the algorithm. For example, among the 121.2K edges removed in the case of skos:broader, around 99.6K were identified during the graph partitioning step, amounting to 82.2%. Future work may optimise the parameters to balance the trade-off between accuracy and efficiency.

Figure 4 shows that the frequency distribution of skos:broader follows a power-law distribution. It can mislead the algorithm when an edge with a great weight is actually erroneous. Different weighting scheme can be explored such as that in [START_REF] Hertling | WebIsALOD: providing hypernymy relations extracted from the web as linked open data[END_REF]. Another possible way to improve the accuracy of weights and reduce the number of ties of weights in size-two cycles is by taking the reliability or centrality of sources into account as in [START_REF] Bonatti | Robust and scalable Linked Data reasoning incorporating provenance and trust annotations[END_REF] for example. General-purpose MWFAS algorithms can be adapted to their weighted cases for future evaluation.

Our recall is limited due to the small amount of edges removed. In Section 6.4, we restricted to these two relations due to their popularity and the great effort required for manual annotation. We plan to extend the gold standard to relations with different alpha-beta measures.

Fig. 1 :

 1 Fig. 1: An example subgraph of skos:broader with weights.

Fig. 2 :

 2 Fig.2: An example graph and its variants (from left: G, G SCC , G , G SCC ).

Fig. 3 :

 3 Fig. 3: The Alpha-Beta measures of representative relations

Method s k o

  s : b r o a d e r r d f s : s u b C l a s s O f d b o : i s P a r t O f s k o s : n a r r o w e r d b o : p r e v i o u s W o r k d b o : s u b s e q u e n t W o r k d b o : s u c c e s s o r d b o : p r e d e c e s s o r d b o : p a r e n t s i o c : p a r e

Fig. 4 :

 4 Fig. 4: The frequency distribution of counted weights in SCCs

2

  Initiate A as an empty set; 3 Compute the set of SCCs as S; 4 Follow a graph partitioning strategy and reduce the size of S to bound b1 as S with removed edges collected and added to A; 5 while S is not empty do Follow a sampling strategy, and obtain cycles C from s with |C| < b2;

	6	Initiate S as an empty set;
	7	foreach s ∈ S do
	8

9 Initiate an SMT solver o; 10 Introduce to o a set P of propositional variable pe for each edge e of s; 11 Encode cycles in C as hard constraints in o; 12 Add to o a clause of each variable pe ∈ P soft constraint with weight fw(e) if fw is present, otherwise 1; 13 Run the solver o for optimal solution and decode the output model m; 14 From the model m, collect the edges E to remove and let A := A ∪ E; 15 Obtain a graph s from s with E removed; 16 Compute the SCCs N of s and update S := S ∪ N ; 17 S := S ; 18 Remove edges A from G and obtain H.

Table 2 :

 2 The number of removed edges (with best results highlighted)

Table 3 :

 3 Number of removed edges |A|, precision p, and recall r for refinement

				skos:broader					rdfs:subclass
	Method	|A|	p	G1 r	p	G2-a r	p	G2-b r	|A|	p	G1 r	p	G2-a r	p	G2-b r
	BS	1.1M 0.32 0.85 0.68 0.72 0.31 0.91 4.3M 0.40 0.74 0.40 0.67 0.54 0.79
	GRD	493.1K 0.42 0.22 0.71 0.50 0.40 0.26 25.3K 0.42 0.40 0.35 0.45 0.57 0.21
	KS	5.9M 0.33 0.52 0.74 0.53 0.28 0.46 2.1M 0.38 0.43 0.43 0.55 0.54 0.53
	DFS	125.6K 0.35 0.37 0.68 0.49 0.34 0.34 529	0.43 0.42 0.49 0.63 0.55 0.29
	P1S1-unweighted 114.8K 0.32 0.26 0.73 0.52 0.30 0.28 330 0.50 0.51 0.45 0.57 0.40 0.11
	P1S2-unweighted 142.6K 0.32 0.35 0.73 0.52 0.31 0.37 350	0.49 0.44 0.45 0.57 0.58 0.15
	P1S1-inferred	115.0K 0.31 0.25 0.73 0.52 0.30 0.28 330 0.50 0.51 0.45 0.57 0.40 0.11
	P1S2-inferred	143.8K 0.33 0.38 0.73 0.52 0.30 0.36 354	0.49 0.46 0.45 0.57 0.60 0.14
	P2S1-inferred	114.8K 0.31 0.25 0.73 0.50 0.30 0.29 330 0.50 0.51 0.45 0.57 0.40 0.11
	P2S2-inferred	142.7K 0.33 0.35 0.73 0.52 0.31 0.37 356	0.50 0.47 0.45 0.57 0.58 0.15
	P1S1-counted	95.4K 0.40 0.33 0.78 0.55 0.34 0.26 335	0.53 0.49 0.45 0.57 0.67 0.16
	P1S2-counted	98.3K 0.42 0.38 0.78 0.55 0.34 0.28 354	0.51 0.45 0.45 0.57 0.70 0.20
	P2S1-counted	93.4K 0.43 0.32 0.78 0.55 0.34 0.26 335	0.53 0.49 0.45 0.57 0.67 0.16
	P2S2-counted	94.6K 0.44 0.35 0.78 0.55 0.32 0.24 357	0.50 0.45 0.45 0.57 0.66 0.17

A simple cycle is a cycle in which the only repeated vertices are the first and last vertices.

Note that the resulting graph may not be a spanning tree but a set of directed acyclic graphs (DAGs). Therefore this problem cannot be solved by minimum spanning tree algorithms.

All SCCs in this paper are assumed to have more than one node.

A sub-optimal result is returned when an SMT solver reaches timeout.

https://github.com/shuaiwangvu/Refining-Transitive-Relations

https://github.com/inducer/pymetis

https://github.com/Z3Prover/z3

https://networkx.github.io

https://github.com/shuaiwangvu/ANNit

https://zenodo.org/record/4610000


Eugene V Koonin
email: koonin@ncbi.nlm.nih.gov

Mart Krupovic
email: mart.krupovic@pasteur.fr

Valerian V Dolja

The global virome: how much diversity and how many independent origins?

Viruses are considered to be the most abundant biological entities on earth. They also display striking genetic diversity as emphatically demonstrated by the recent advances of metagenomics and metatranscriptomics. But what are the limits of this diversity, that is, how many virus species in the earth virome? By combining the available estimates of the number of prokaryote species with those of the virome size, we obtain back-of-the-envelope estimates of the total number of distinct virus species, which come out astronomically large, from about 10 7 to about 10 9 . The route of virus origins apparently involved non-viral replicators capturing and exapting various cellular proteins to become virus capsid subunits. How many times in the history of life has this happened? In other words, how many realms of viruses, the highest rank taxa that are supposed to be monophyletic, comprise the global virome? We argue that viruses emerged on a number (even if far from astronomical) independent occasions, so the number of realms will considerably increase from the current 6, by splitting some of the current realms, giving the realm status to some of the currently unclassified groups of viruses and discovery of new distinct groups.

Viruses are often considered to be the most numerous entities in the global biosphere. The most common estimates suggest that there are on the order of 10 31 virus particle on the planet at any given moment, about an order of magnitude greater than the total number of cells [START_REF] Mushegian | Are There 10(31) Virus Particles on Earth, or More, or Fewer?[END_REF]. To the best of our current understanding, all organisms on earth are hosts to multiple viruses, with the possible exception of some endosymbiotic bacteria [START_REF] Koonin | Global Organization and Proposed Megataxonomy of the Virus World[END_REF]. Empirical observations on the ubiquity of viruses are buttressed by theoretical argument on the inevitable emergence of genetic parasites in any replicator system [START_REF] Koonin | Inevitability of the emergence and persistence of genetic parasites caused by evolutionary instability of parasite-free states[END_REF]. Virus genomes are also extremely diverse, and the ongoing metagenomic-metatranscriptomic revolution reveals the vast scale of that diversity [START_REF] Dutilh | Metagenomic ventures into outer sequence space[END_REF][START_REF] Dolja | Metagenomics reshapes the concepts of RNA virus evolution by revealing extensive horizontal virus transfer[END_REF]. The case of RNA viruses can serve as an apt illustration. Astonishingly, analysis of a single metatranscriptome, apparently coming from an environment rich in unicellular eukaryotes hosting RNA viruses, resulted in a twofold expansion of the known RNA virome [START_REF] Wolf | Doubling of the known set of RNA viruses by metagenomic analysis of an aquatic virome[END_REF]. Three independent subsequent studies exploring thousands of metatranscriptomes from diverse environments [START_REF] Edgar | Petabase-scale sequence alignment catalyses viral discovery[END_REF][START_REF] Neri | Expansion of the global RNA virome reveals new clades of bacteriophages[END_REF][START_REF] Zayed | Cryptic and abundant marine viruses at the evolutionary origins of Earth's RNA virome[END_REF] each led to further, several fold increase in the number of known distinct RNA viruses (distinct, in this case, means not too closely related to each other, more specifically, clusters of genomes with similar sequences that roughly correspond to a virus species level), which combined, would amount to a more than an order of magnitude expansion. Rarefaction analysis shows that saturation of the RNA virus diversity is not yet in sight [START_REF] Neri | Expansion of the global RNA virome reveals new clades of bacteriophages[END_REF]. Metagenomic studies indicate that the case of DNA viruses is similar, and expansion of some groups, for instance, tailless bacteriophages [START_REF] Kauffman | A major lineage of non-tailed dsDNA viruses as unrecognized killers of marine bacteria[END_REF]Yutin et al., 2018a), or tailed phages of the expansive order Crassvirales [START_REF] Guerin | Biology and Taxonomy of crAss-like Bacteriophages, the Most Abundant Virus in the Human Gut[END_REF]Yutin et al., 2018b;[START_REF] Yutin | Analysis of metagenome-assembled viral genomes from the human gut reveals diverse putative CrAsslike phages with unique genomic features[END_REF] has been even more dramatic.

So how many distinct viruses, or virus species, are there in the global virome altogether? Given that metagenomic and metatranscriptomic analyses (below we refer to these collectively as metaviromics insofar as applied to virus discovery)

are not yet approaching saturation, this number cannot be inferred by extrapolation from available data. However, to obtain a rough, back of the envelope estimate, we can take a different approach modeled over that employed previously to estimate the number of unique microbial genes [START_REF] Wolf | Two fundamentally different classes of microbial genes[END_REF]. The great majority of viruses on earth are tailed and tailless phages infecting bacteria; viruses of archaea and eukaryotes are only relatively small additions. Let us conservatively assume that there are 10 6 to 10 7 bacterial species on earth [START_REF] Curtis | Estimating prokaryotic diversity and its limits[END_REF] (some estimates are orders of magnitude higher [START_REF] Locey | Scaling laws predict global microbial diversity[END_REF]). Most if not all bacteria are hosts to multiple viruses. For Escherichia coli alone, about a hundred bacteriophages have been identified [START_REF] Maffei | Systematic exploration of Escherichia coli phage-host interactions with the BASEL phage collection[END_REF], whereas for Mycobacterium smegmatis mc2155, more than 10,000 individual mycobacteriophages have been isolated, although only 2,100 of these have been sequenced and thus it remains to be determined how many different virus species they represent [START_REF] Hatfull | Mycobacteriophages: From Petri dish to patient[END_REF]. Furthermore, analysis of CRISPR spacers, the majority of which appear to be virusderived but do not match known viruses, implies large, host species-specific viromes [START_REF] Shmakov | Mapping CRISPR spaceromes reveals vast host-specific viromes of prokaryotes[END_REF]. Let us assume 10 to 100 virus species per host species as a conservative estimate. Then, the size of the global virome can be crudely estimated at 10 7 to 10 9 distinct virus species -obviously, even the low bound in this range, probably, a vast underestimate, is a huge number. The upper bound appears more realistic, so there is likely to be about a billion virus species if not more on earth -evidently, a long way to go from the currently recognized 10 4 species [START_REF] Walker | Recent changes to virus taxonomy ratified by the International Committee on Taxonomy of Viruses[END_REF] until we know them all.

As a bonus, we can also roughly estimate the size of the virus pangenome, in other words, the total number of genes in the virosphere. Large viruses encompass many poorly conserved, speciesspecific genes that obviously represent the bulk of the virus pangenome. Assuming 10 such unique genes per virus species, there would be 10 8 to 10 10 unique virus genes altogether, a vast gene repertoire, to put it modestly.

Having obtained some striking, even if rough numbers characterizing the vastness of the virosphere, we now ask a different question that is likely to appear burning to anyone interested in virus diversity and evolution: how many times have viruses evolved independently? Recent analyses of the provenance of virus hallmark genes (VHG) encoding the key proteins involved in virus replication and virion formation suggest the principal route of virus origin: non-viral selfish replicators capture of host proteins that are exapted (repurposed) to become virion components, in particular, capsid proteins (CP) [START_REF] Krupovic | Multiple origins of viral capsid proteins from cellular ancestors[END_REF][START_REF] Krupovic | Origin of viruses: primordial replicators recruiting capsids from hosts[END_REF][START_REF] Koonin | The logic of virus evolution[END_REF]. This chimeric origin scenario, most likely, applies to the ultimate origin of viruses concomitant with the earliest stages of the evolution of cells and was recapitulated at least several times at later stages. But how many times did it happen, actually? Is origin of viruses by this chimeric route a common, routine or an extremely rare event? A single common origin of viruses appears to be out of the question, simply, because viruses do not share a single universally conserved gene [START_REF] Koonin | Global Organization and Proposed Megataxonomy of the Virus World[END_REF]. This is a sharp contrast with cellular life forms which all share about 100 universal genes and are confidently traced back to the Last Universal Cellular Ancestor (LUCA) [START_REF] Koonin | Comparative genomics, minimal gene-sets and the last universal common ancestor[END_REF]. Clearly, there has been no last universal virus ancestor and viruses were already quite diverse at the time of LUCA [START_REF] Krupovic | The LUCA and its complex virome[END_REF]. But then, how many independent ancestors for the contemporary global virome? In the comprehensive hierarchical virus taxonomy recently adopted by the International Committee on Virus Taxonomy (ICTV), there are 6 taxa at the highest level, realms, each of which is thought to be monophyletic (International Committee on Taxonomy of Viruses Executive Committee, 2020; [START_REF] Koonin | Global Organization and Proposed Megataxonomy of the Virus World[END_REF]. In this respect, each realm is equivalent to the entirety of cellular life forms: there is a conserved core of VHG that defines the identity of the respective realm, even if it consists of a single gene.

There are four expansive realms of viruses: Riboviria, Monodnaviria, Duplodnaviria and Varidnaviria, each including a huge diversity of viruses that is rapidly growing through large scale metaviromics studies [START_REF] Koonin | Global Organization and Proposed Megataxonomy of the Virus World[END_REF]. The realm Riboviria includes viruses with positivesense, negative-sense and double-strand (ds) RNA genomes, together with the reverse-transcribing viruses that possess either RNA or DNA genomes. The viruses in this vast realm are unified by the homologous RNA-dependent RNA polymerases (RdRPs) and reverse transcriptases (RTs). The realm Monodnaviria consists of single-stranded (ss) DNA viruses and small dsDNA viruses (papillomaviruses and polyomaviruses), largely, with circular genomes. The single hallmark gene that holds this realm together encodes a distinct endonuclease (or its inactivated derivative) that is involved in the initiation of the genome replication, mostly, via the rolling circle replication mechanism. The realm Duplodnaviria includes tailed bacterial and archaeal viruses with dsDNA genomes, along with animal herpesviruses and the recently discovered mirusviruses [START_REF] Gaïa | Plankton-infecting relatives of herpesviruses clarify the evolutionary trajectory of giant viruses[END_REF]. All these viruses share a distinct structural gene module that encodes the HK97-fold major capsid protein (MCP), genome packaging ATPasenuclease (terminase), portal protein and capsid maturation protease. The second realm of viruses with dsDNA genomes, Varidnaviria, consists of diverse viruses infecting bacteria, archaea and eukaryotes that are unified by the vertical jelly-roll MCPs. Most viruses in this realm belong to the kingdom Bamfordvirae and possess double jellyroll (DJR) MCP, but viruses in the smaller kingdom Helvetiavirae feature two MCPs each consisting of a single vertical jelly-roll domain. In addition, two small virus realms, Adnaviria and Ribozyviria, were recently formally recognized by the ICTV. The realm Adnaviria consists of filamentous and rodshaped viruses that infect hyperthermophilic archaea of the phylum Thermoproteota and encapsidate linear dsDNA in the A-form [START_REF] Krupovic | Adnaviria: a new realm for archaeal filamentous viruses with linear A-form double-stranded DNA genomes[END_REF]. The realm Ribozyviria includes human hepatitis delta virus and its relatives infecting other animals [START_REF] Hepojoki | Create one new realm (Ribozyviria) including one new family (Kolmioviridae) including genus Deltavirus and seven new genera for a total of 15 species. International Committee on Taxonomy of Viruses Taxonomic Proposal. International Committee on Taxonomy of Viruses Executive Committee (2020) The new scope of virus taxonomy: partitioning the virosphere into 15 hierarchical ranks[END_REF]. The genomes of the ribozyviruses are viroid-like circular RNAs encoding a nucleocapsid protein (Delta antigen).

The virus realms are supposed to be monophyletic, that is, to have evolved from a single common ancestor virus. However, even apart from the fact that the monophyly hinges only on a few or even one VHG, this is not actually the case for at least three of the four current major realms. In particular, although the two kingdoms of the realm Riboviria share a homologous replicative enzyme, the origins of the viruses themselves, resulting from the recruitment of distinct capsid proteins, were clearly independent (Figure 1). Thus, under the premise that taxa should be strictly monophyletic, the realm Riboviria ought to be split into two or even three separate realms, given that two groups of Pararnavirae, namely, Ortervirales and Blubervirales, apparently evolved from distinct retrotransposons [START_REF] Gong | Insect Retroelements Provide Novel Insights into the Origin of Hepatitis B Viruses[END_REF][START_REF] Krupovic | Ortervirales: New virus order unifying five families of reverse-transcribing viruses[END_REF]. The case of the realm Monodnaviria is even more striking: viruses that currently comprise this realm evolved on at least four independent occasions via parallel routes, namely, capture, by small rolling-circle plasmids, of either a virus gene encoding a CP or cellular genes repurposed as CPs [START_REF] Kazlauskas | Multiple origins of prokaryotic and eukaryotic single-stranded DNA viruses from bacterial and archaeal plasmids[END_REF] (Figure 1). In the realm Varidnaviria, the two single jellyroll vertical CPs of helvetiaviruases initially were presumed to be an ancestral form of the MCP, giving rise to the DJR MCP through gene fusion. However, recent analysis of the evolution of the vertical jelly-roll MCPs from cellular ancestors that revealed independent capsid origins in Bamfordvirae and Helvetiavirae, strongly suggests a split of this realm [START_REF] Krupovic | Cellular homologs of the double jellyroll major capsid proteins clarify the origins of an ancient virus kingdom[END_REF]. The monophyly of the remaining three virus realms, Duplodnaviria, Adnaviria and Ribozyviria, seems to hold for the time being. However, there are already a number of viruses that appear to be unrelated to the established realms and hence probably evolved independently, thus being candidates for new, small realms. These distinct enigmatic viruses include several virus families infecting archaea, in particular, viruses with lemon-shaped virions [START_REF] Krupovic | Unification of the globally distributed spindleshaped viruses of the Archaea[END_REF][START_REF] Wang | Spindle-shaped archaeal viruses evolved from rod-shaped ancestors to package a larger genome[END_REF]; animal anelloviruses that have small ssDNA genomes but appear to lack the hallmark rolling-circle endonuclease which unifies the members of Monodnaviria [START_REF] Taylor | The enigmatic roles of Anelloviridae and Redondoviridae in humans[END_REF]; large dsDNA viruses of the class Naldaviricetes (baculo-like viruses) infecting diverse arthropods [START_REF] Petersen | The naked truth: An updated review on nudiviruses and their relationship to bracoviruses and baculoviruses[END_REF]; and a variety of viruses with circular RNA genomes, discovered mostly by metatranscriptome mining, that resemble viroids but encode proteins unrelated to the nucleocapsid protein of ribozyviruses [START_REF] Linnakoski | Armillaria root rot fungi host single-stranded RNA viruses[END_REF][START_REF] Lee | A vast world of viroid-like circular RNAs revealed by mining metatranscriptomes[END_REF]. Thus, clearly, although new viruses do not emerge "every other day", there have been many points of virus origin. It is not inconceivable that, before we are done with the global virome, the number of distinct, independently evolving groups of viruses that, at least in principle, have to be classified as realms will far exceed the current six. Virus taxonomists, then, will face the burning question: classify viruses into realms in a strict adherence to the monophyly criterion or lump together some groups that share core VHG but evolved independently, for the sake of tradition and convenience? In any case, the question on the diversity and evolution of the virosphere remain burning, but thanks to the remarkable advances of metaviromics and the concerted efforts in comparative genomics, we are starting to glean interesting answers.

Figure 1 .

 1 Figure 1. Independent emergence of major groups of viruses: the realms and their possible split. Virogenesis involves acquisition by non-viral replicators, such as plasmids and transposons, of cellular genes which are exapted to form viral capsids. Potential independent routes of virogenesis from non-viral replicators are shown for three of the six realms, with the highest monophyletic taxa indicated. Non-viral DNA and RNA replicators are depicted in grey and black, respectively. Different colors show independent ancestors of capsid proteins. Abbreviations: CP, capsid protein; RdRP, RNA-dependent RNA polymerase; RT, reverse transcriptase.

Acknowledgements E.V.K. is supported by the funds of the Intramural Research Program of the National Institutes of Health of the USA. V.V.D. was partially supported by NIH/NLM/NCBI Visiting Scientist Fellowship.

Author contributions

M.K., V.V.D and E.V.K. researched data for article, substantially contributed to the discussion of the content, and wrote the manuscript.

Competing interests

The authors report no competing interests.