dataesr/scientific-paragraphs-categorization huggingface dataset:
ElPiGraph combines several concepts previously discussed, including elastic energy functional and topological graph grammars  [10, 20]. However, it improves significantly over existing methodology and implementations, making it capable of effectively modeling real-word applications with datasets containing large numbers of data points. In ElPiGraph, we introduced several improvements related to scalability, robustness to noise (both sampling and background type), ability to construct non tree-like data approximators, and direct control over the complexity of the principal graph. To achieve this result, we introduced the elastic matrix and Laplacian-based penalty (see Methods section) in order to completely vectorize the algorithm's implementation which is essential for modern programming languages.
ElPiGraph is currently implemented in five programming languages (R, MATLAB, Scala, Java, Python with possibility to use Graphical Processor Units (GPUs)), which makes it easily applicable across scientific domains. One of the major areas for application of principal graphs is modern molecular biology. For example, recently obtained snapshot distributions of single cells of a developing embryo or an adult organism, when looked in the space of their omics profiles, display complex multidimensional patterns  [37] [38] [39] , reflecting continuous changes in the regulatory programs of the cells and their bifurcations during complex cell fate decisions. The existence and biological relevance of such patterns was clearly demonstrated while studying development  [40] , cellular differentiation  [41] [42] [43] , and cancer biology  [44].
Then, for example, the graph is characterized by a  () = 10 contribution to the elastic energy. The graph with one star will be characterized by a  () = 10 + 3 penalty, by  () = 10 + 6, and by  () = 10 + 8. If α = 0 branching is not penalized, while larger values progressively penalize branching, with α ≈ 1 resulting in branching being effectively forbidden. Supplementary Figure  S1  illustrates, using the standard iris and a synthetic dataset, how changing this parameter eliminates non-essential branches of a fitted principal tree, up to prohibiting them and simplifying the principal tree structure graph is characterized by a U φ E (G) = 10λ contribution to the elastic energy. The graph with one star node, to which all other nodes are connected). Let deg(vi) denote a function returning the order k of the star with the central node vi and 1 if vi is a terminal node.
Then, for example, the graph is characterized by a  () = 10 contribution to the elastic energy. The graph with one star will be characterized by a  () = 10 + 3 penalty, by  () = 10 + 6, and by  () = 10 + 8. If α = 0 branching is not penalized, while larger values progressively penalize branching, with α ≈ 1 resulting in branching being effectively forbidden. Supplementary Figure  S1  illustrates, using the standard iris and a synthetic dataset, how changing this parameter eliminates non-essential branches of a fitted principal tree, up to prohibiting them and simplifying the principal tree structure will be characterized by a U φ E (G) = 10λ + 3α penalty, node, to which all other nodes are connected). Let deg(vi) denote a function returning the order k of the star with the central node vi and 1 if vi is a terminal node.
Then, for example, the graph is characterized by a  () = 10 contribution to the elastic energy. The graph with one star will be characterized by a  () = 10 + 3 penalty, by  () = 10 + 6, and by  () = 10 + 8. If α = 0 branching is not penalized, while larger values progressively penalize branching, with α ≈ 1 resulting in branching being effectively forbidden. Supplementary Figure  S1  illustrates, using the standard iris and a synthetic dataset, how changing this parameter eliminates non-essential branches of a fitted principal tree, up to prohibiting them and simplifying the principal tree structure by U φ E (G) = 10λ + 6α, and node, to which all other nodes are connected). Let deg(vi) denote a function returning the order k of the star with the central node vi and 1 if vi is a terminal node.
Then, for example, the graph is characterized by a  () = 10 contribution to the elastic energy. The graph with one star will be characterized by a  () = 10 + 3 penalty, by  () = 10 + 6, and by  () = 10 + 8. If α = 0 branching is not penalized, while larger values progressively penalize branching, with α ≈ 1 resulting in branching being effectively forbidden. Supplementary Figure  S1  illustrates, using the standard iris and a synthetic dataset, how changing this parameter eliminates non-essential branches of a fitted principal tree, up to prohibiting them and simplifying the principal tree structure by U φ E (G) = 10λ + 8α. If α = 0 branching is not penalized, while larger values progressively penalize branching, with α ≈ 1 resulting in branching being effectively forbidden. Supplementary Figure  S1  illustrates, using the standard iris and a synthetic dataset, how changing this parameter eliminates non-essential branches of a fitted principal tree, up to prohibiting them and simplifying the principal tree structure to a principal curve.
Without this penalty term, extensive branches can appear in the regions of data distributions which can be characterized by a 'thick turn', i. e. , when the increased local curvature of the intrinsic underlying manifold leads to increased local variance of the dataset (Supplementary Figure  S1 ). Entropy 2020, 22, 296 6 of 27 Note that U φ R (G) can be re-written as U φ R (G) = S ( j) µ j deg(S ( j) (0)) deg(S ( j) (0)) i=1 φ S ( j) (0) -φ S ( j) (i) 2 - S ( j) µ j (deg(S ( j) (0))) 2 deg(S ( j) (0)) i=1,p=1,i<>p φ S ( j) (i) -φ S ( j) (p) 2 (4) i. e. , the term U φ R (G) can be considered as a sum of the energy of elastic springs connecting the star centers with its neighbors (with elasticity moduli µ j /deg(S (j) )) and the energy of negative (repulsive) springs connecting all non-central nodes in a star pair-wise (with negative elasticity moduli-µ j /(deg(S (j) )) 2 ).
However, these data points might appear at a distance smaller than R 0 at the next algorithm iteration: therefore, it is not equivalent to permanently pre-filtering 'outliers'. The approach is similar to the 'data-driven' trimmed k-means clustering  [50]. Alternative ways of constructing robust principal graphs include using piece-wise quadratic subquadratic error functions (PQSQ potentials)  [51] , which uses computationally efficient non-quadratic error functions for approximating a dataset. These two approaches will be implemented in the future versions of ElPiGraph. The objective of the basic optimization algorithm is to find a map ϕ:V→ R m such that U ϕ (X,G) → min over all possible elastic graph G injections into R m. In practice, we are looking for a local minimum of U ϕ (X,G) by applying the standard splitting-type algorithm, which is described by the pseudo-code provided below.
Determining a globally optimal injection of a graph with a given topology is usually challenging, because of the energy landscape complexity. This means that, in practice, one has to use an optimization approach in which both graph topology and the injection map should be learned simultaneously. A graph grammar-based approach for constructing such an algorithm was suggested  [17]. The algorithm starts from an initial graph G 0 and an initial map ϕ 0 (G 0 ). In the simplest case, the initial graph can be initialized by two nodes and one edge and the map can correspond to a segment of the first principal component. Then a set of predefined grammar operations which can transform both the graph topology and the map, is applied starting from a given pair {G i , ϕ i (G i )}. Each grammar operation Ψ p produces a set of new graphs and their injection maps possibly taking into account the dataset X D k , φ(D k ) , k = 1.
s s × O(Nsm) = O Nms 3. It remains linear with the number of points N and dimensionality m but is polynomial with the number of nodes s, which is caused by testing a large number of candidate graph structures in the process of gradient descent-like search for the optimal topology. In practical applications, when there is a need to construct large principal graphs for big datasets, the polynomial complexity of ElPiGraph can be prohibitive. In this case, there exist multiple options (besides application of GPUs) to speed up the algorithm, some of which are listed below: (1) Effective reduction of the number of points in the dataset, e. g. , by applying pre-clustering. The new datapoints represent the centroids of clusters weighted accordingly to the number of points in each cluster. Alternatively, ElPiGraph can use stochastic approximation approach, by exploiting a subsample of data at each step of growth.
Choice of the Core ElPiGraph Parameters The core ElPiGraph algorithm uses four parameters with well-defined effect on its behavior: λ-coefficient of 'stretching' elasticity; µ-coefficient of 'bending' elasticity; α-parameter controlling graph complexity; R 0 -trimming radius for MSE-based data approximation term. Base parameters of elasticity control the general regular properties of the graph injection map. λ effectively constraints the total length of edges in the graph as well as penalizes the deviation from the uniform edge length distribution. µ penalizes deviations of graph k-stars from harmonicity. For linear branches this means deviation from linearity, therefore large values of µ lead to graphs having piece-wise linear injection maps with close to harmonic k-stars. The values of λ and µ are dimensionless and normally do not depend on scaling the dataset variables.
In this case it explores the dataset starting from a small fragment of it by 'crawling' to the neighbor data points simultaneously fitting the local features of data topology. With properly chosen R 0 , the ElPiGraph algorithm can tolerate significant amount of uniformly distributed background noise (see Figure  2C ) and even deal with self-intersecting data distributions (Figure  2D ). ElPiGraph includes a function for estimating the coarse-grained radius of the data based on local analysis of density distribution, which can be used as an initial guess for the R 0 value. An alternative initial guess for the trimming radius can be obtained by taking the median of the pairwise data point distances distribution. Here, a reference branching dataset  [32]  is downsampled to 50 points (middle) or oversampled by sampling 20 points randomly placed around each point of the original dataset.
More systematic study of the down/over-sampling effect on robustness of the principal graph is shown in Supplementary Figure  S2. (B) ElPiGraph is able to capture non-tree like topologies. Here, the standard set of principal tree graph grammars was applied to a graph initialized by four nodes connected to a ring. (C) ElPiGraph is robust to large amounts of uniformly distributed background noise. Here, the initial dataset from Figure  1  is shown as black points, and the uniformly distributed noisy points are shown as grey points. ElPiGraph is blindly applied to the union of black and grey points. (D) ElPiGraph is able to solve the problem of learning intersecting manifolds. On the left, a toy dataset of three uniformly sampled curves intersecting in many points is shown. ElPiGraph starts by learning a principal curve using the local version several times, each time on a complete dataset.
However, for each iteration, ElPiGraph is initialized by a pair of neighboring points not belonging to points already captured by a principal curve. The fitted curves are shown in the middle of the point distribution by using different colors, and the clustering of the dataset based on curve is shown on the right. (E) Approximating a synthetic ten-dimensional dataset with known branch structure (with different colors indicating different branches), where one of the branches (blue one) extrude into higher dimensions and collapses with other branches when projected in 2D by principal component analysis (left). Middle, being applied in the space of two first principal components, ElPiGraph does not recover the branch, while it is captured when the ElPiGraph is applied in the complete 10-dimensional dataset (right).
Principal Graph Eensembles and Consensus Principal Graph Resampling techniques are often used to determine the significance of analyses applied to complex datasets  [54]. ElPiGraph can be also used in conjunction with resampling (i. e. , random sampling of p% of data points and applying ElPiGraph k times) to explore the robustness of the constructed principal graph. Resampling produces a principal graph ensemble, i. e. , a set of k principal graphs. Figure  1C  shows a simple example of using data resampling in order to construct multiple principal trees (k = 100 and p = 90%). From this example, it is possible to judge how a different level of uncertainty is associated with different parts of the tree and to explore the uncertainty associated with branching points. Besides resampling, other approaches can be applied in order to build the principal graph ensemble.
For example, it can be built from multiple initializations of the graph structure, or by varying the parameters of ElPiGraph in certain range as it is illustrated in Section 3. 4. In complex examples, a principal graph ensemble can be used to infer a consensus principal graph, i. e. , a principal graph obtained by recapitulating the information from the graph ensemble, and to discover in such a way emergent complex topological features of the data. For example, a consensus principal graph constructed by combining an ensemble of trees may contain loops, which are not present in any of the constructed principal trees (Figure  5 ). ElPiGraph package contains a set of functions to assemble consensus principal graphs which uses simple graph abstraction approach. Briefly, the currently implemented approach consists in (1) generating a certain number of elastic principal graphs using resampling strategy; (2) matching the nodes from multiple principal graphs and combining them into node clusters such that each cluster would contain certain minimal number of nodes; (3) connecting the node clusters using the edges of individual principal graphs, such that each edge in the consensus principal graph aggregates a certain minimal number of individual principal graph edges; (4) removing isolated nodes from the consensus graph; (5) delete too short or too long edges from the consensus graph preserving the graph connectivity.
Code Availability The ElPiGraph method is implemented in several programming languages: A Java implementation of ElPiGraph is available as part of VDAOEngine library (https: //github. com/auranic/VDAOEngine/) for high-dimensional data analysis developed by AZ. The Java implementation of ElPiGraph is not actively developed and the implementation of ElPiGraph in Java does not scale as good as other implementations. A Scala implementation is available from https://github. com/mraad/elastic-graph. All the implementations contain the core algorithm as described in this paper. However, the different implementations differ in the set of functionalities improving the core algorithm such as robust local version of the algorithm, explicit complexity control, multicore, or GPU support. In the future, ElPiGraph implementation in Python will serve as the reference one, and a regular effort will be made to synchronize the ElPiGraph R version with the reference implementation.
Approximating Complex Data Topologies in Synthetic Examples To showcase the flexibility, robustness, and scalability of ElPiGraph, we applied it to different use cases. First, we considered a synthetic 2D dataset describing a circle connected to a branching structure. ElPiGraph was able to recover the target structure when the appropriate grammar rules are specified (Figure  2B ). The possibility to use various grammar combinations and initial approximations gives ElPiGraph flexibility in approximating datasets with complex topologies. In the simplest case, it requires the a priori defined topology type (e. g. , curve, circular, tree-like) of the dataset to approximate. As discussed later, ElPiGraph is able to construct an appropriate data approximator when no information is available on the underlying topology of the data by using the consensus principal graph approach.
Use of non-local graph grammars can in principle make learning complex data topologies more efficient, which will be the subject of our future work. It should be noted that such approaches must be accompanied by efficient ways to penalize excessive complexity of principal graphs as discussed in  [17] : otherwise, the complexity of the data approximator might easily become comparable with the complexity of the data point cloud itself. We explored the robustness of ElPiGraph to down-and oversampling. For a simple benchmark example of a branching data distribution in 2D (Figure  2A ), we selected a fraction of data points (15%) or generated 20× more points around each of the existing ones in the original dataset. Our algorithm is able to properly recover the structure of the data, regardless of the condition being considered, with only minimal differences in the position of the branching points due to the loss of information associated with downsampling.
The intrinsic rigidity of elastic graph in combination with a trimmed approximation error enables ElPiGraph to solve the Travel Maze problem quite naturally. This is possible because the local version of the elastic graph algorithm is characterized by a certain persistency in choosing the direction of the graph growth. Indeed, when presented with a dataset corresponding to a group of three threads intersecting on the same plane, ElPiGraph is able to recognize them and cluster the data points accordingly, hence associating different paths to the different threads (Figure  2D ). As demonstrated by the widespread use of tools like PCA, tSNE, LLE, or diffusion maps, dimensionality reduction can be a powerful tool to better visualize the structure of data. However, some data features can be lost as the dimension of the dataset is being reduced.
This can be particularly problematic if dimensionality reduction is used as an intermediate step in a long analytical pipeline. To illustrate this phenomenon, we generated a 10-dimensional dataset describing an a priori known branching process. When the points are projected into a 2D plane induced by the first two principal components, one of the branches collapses and becomes indistinguishable (Figure  2E ). This effect is due to the branch under consideration being essentially orthogonal to the plane formed by the first two principal components. As expected, ElPiGraph is unable to capture the collapsed branch, when it is used on the 2D PCA projection of the data. However, the branch is correctly recovered when ElPiGraph is run using all 10 dimensions. In this particular case, applying non-linear dimensionality reduction (e.
Benchmarking ElPiGraph The core functionality of ElPiGraph is based on a fast optimization Algorithm 1 which allows the method to scale well to large datasets. ElPiGraph can also take advantage of multiprocessing to further speed up the computation if necessary. When run on a single core, ElPiGraph is able to reconstruct principal curves in few minutes for tens of thousands points in tens of dimensions (Figure  3A ). The new Python implementation of ElPiGraph is able to use a combination of CPU and GPU which gives significant benefit in computational performance starting from 10,000 data points in relatively high dimension: we can observe several-fold acceleration for a large dataset compared to the previously published R version using only CPU, see Figure  3B. Running ElPiGraph to construct large graphs with several hundreds of nodes showed polynomial dependence of the computational time vs.
Empirically, however, the scaling of the heuristic was superquadratic which was probably caused by some overheads related to dealing with large graphs (e. g. , their slower convergence or superquadratic cost of solving the large systems of linear equations). (A) Time required to build principal curves and trees (y-axis) with a different number of nodes (x-axis) using the default parameters across synthetic datasets containing different numbers of points having a different number of dimensions (color scale), using single CPU. (B) Demonstrating computational advantages of using a combination of GPU and CPU in ElPiGraph computations. Starting from 10k data points, using GPU becomes advantageous. The computational experiment was done using Google Colab environment. (C) Empirical performance scaling of ElPiGraph on a 12k data points in 5D example.
For single cell genomic data several comprehensive efforts have been made in order to compare existing approaches, based on synthetic or real data. As a nonspecialized machine learning method, ElPiGraph performed well in the recent large-scale benchmarking of cell trajectory inference methods in three categories (linear, circular, tree-like topology), using synthetic datasets with known ground-truth underlying data topology  [35]. However, in these tests ElPiGraph was used with the initialization from the simplest graph, without trying to guess the structure adapted to the data. As a part of STREAM pipeline, which provided more advanced initial graph structure guess, ElPiGraph was competitive compared to 10 recently suggested approaches when applied to several real-life datasets  [33]. Here, we developed an approach to compare ElPiGraph, as a general-purpose machine learning method, with its closest principal graph approach, without taking into account the specifics of single (A) Time required to build principal curves and trees (y-axis) with a different number of nodes (x-axis) using the default parameters across synthetic datasets containing different numbers of points having a different number of dimensions (color scale), using single CPU.
Such benchmarking is inevitably specific to the nature of the data and the type of distributions; therefore, base algorithms should be tested together with domain-specific data pre-processing steps. For single cell genomic data several comprehensive efforts have been made in order to compare existing approaches, based on synthetic or real data. As a non-specialized machine learning method, ElPiGraph performed well in the recent large-scale benchmarking of cell trajectory inference methods in three categories (linear, circular, tree-like topology), using synthetic datasets with known ground-truth underlying data topology  [35]. However, in these tests ElPiGraph was used with the initialization from the simplest graph, without trying to guess the structure adapted to the data. As a part of STREAM pipeline, which provided more advanced initial graph structure guess, ElPiGraph was competitive compared to 10 recently suggested approaches when applied to several real-life datasets  [33].
ElPiGraph is being used as part of STREAM  [33] , an integrated analysis tool that provides a set of preprocessing steps and a powerful interface to analyze scRNA-Seq or other single cell data to derive, for example, genes differentially expressed across the reconstructed paths. An extensive benchmarking of the ability of ElPiGraph in dealing with biological data as part of the STREAM pipeline is discussed elsewhere  [33]. MERLOT represents another use of ElPiGraph as a part of scRNA-Seq data analysis pipeline  [34]. In order to illustrate the work of ElPiGraph on real-life datasets, here we will showcase application of it to the analysis of scRNA-Seq dataset related to hematopoiesis  [59] , which was not published before. Hematopoiesis is an important biological process that depends on the activity of different progenitors.