Today, about 60% of High-Performance Computing (HPC) workload performs computational chemistry and material sciences tasks. These undertakings open the door to the discovery of new materials, enhance our understanding of biological mechanisms, and potentially allow for the discovery of new drugs.
One popular and straightforward technique for performing such computations is Molecular Dynamics (MD). MD computations follow trajectories of atoms over an extended period of time thereby providing detailed physical information as well as quantitative data on the chemical system at hand. Developed in the early 1950s, the technique has since increased in systems complexity with the increase in computational power afforded by Moore's law. Larger and larger molecular trajectories can be achieved over longer periods of time.
HPC and computational chemistry developments have been intertwined over the years. On a generic hardware level, HPC architectures have evolved tremendously over the past 60 years as an answer to larger system computations. In parallel, the discovery of new algorithms has allowed ever faster implementations of these simulations (eg. Fast Multipole Method [1] ). Eventually, specific elements of the computation pipeline have been required to speed up some aspects of these simulations (e.g. Gravity Pipe (GRAPE) [2] or more recently Anton [3] ). While the bulk of the computation is focused on obtaining trajectories, a real insight can only come through the analysis of said trajectories which in and of itself may require large resources. In particular, making sure that the different states of a protein have been explored is a significant task. Biomolecular systems such as viruses are made of atoms constantly moving. They can take different shapes called conformations. Identifying transitions from one conformation to another one is of biological interest. Indeed conforma-tional changes link the structure of a biomolecule to its function within an organism. Thus, knowing these transitions is key in the design of new drugs.
As the number of atoms studied has grown bigger, larger data streams are being produced at every timestep of these simulations. As a result, conformational changes can be tricky to identify, especially for large molecular systems, as changes can sometimes be very local. Processing and memory limitations are also in the way of understanding these transitions as they require full trajectories to be post-processed. Detecting these changes is expensive and performed by batch thereby requiring many computational resources.
Machine learning techniques have been adapted to MD for a more agile, online process. Notably, Trstanova, Leimkuhler, and Lelièvre [4] implemented Diffusion Maps (DMaps), a dimensionality reduction technique, to enhance the exploration of the conformational spaces of molecules in MD. However, the use of this algorithm may not be the most effective way to identify conformational changes, compared to the use of techniques designed for similar tasks.
Change point detection focuses on detecting abrupt changes in time series, with applications in meteorology, finance, medicine, and entertainment. These methods may be limited by computational power as well as the dimensionality of the data considered. Keriven, Garreau and Poli [5] introduced the No-prior-knowledge Exponential Weighted Moving Average (NEWMA) algorithm, a model-free online detection algorithm which appears suited to the analysis of MD trajectories.
Contributions and outline In this paper, we focus on using NEWMA and optical random features to analyse MD trajectories, and propose a strategy coupling NEWMA and DMaps to make analysing MD simulations more effective. We start by introducing the problem from a MD point of view and the value of DMaps in Section 2. We then explore NEWMA as a method to study conformational changes and propose to combine DMaps and NEWMA in Section 3. Section 4 compares the numerical results obtained using NEWMA to various methods. Additionally, we argue on the use of optical random features over silicon hardware. We present our conclusion remarks in Section 5.
We encourage the reader of this article to explore our publicly-available code used at https://github.com/ lightonai/newma-md.
In this section, we introduce some of the key challenges of MD simulations, and detail how DMaps can be used to tackle these issues.
MD simulates the natural behavior of a system to discover physical properties of atoms and molecules. Its goal is to explore the conformational space of large molecules, i.e. all its possible structures. The challenge is sampling the free energy landscape of our molecule that varies with changes in conformations. It informs on the equilibrium thermodynamics and dynamical properties of the system, as well as offering an atomic-scale insight. Typically, MD simulations output time frames F t ∈ R 3n at different timesteps t ∈ N. These frames are vectors storing the three-dimensional coordinates of the n atoms of a molecular system. However, there are still two main factors limiting the reliability of these methods.
The first is known as the force field problem: it is difficult to know accurately the potential energy function associated with the forces applied to the system. Figure 2 : Rémy the rat in his holey world, before exploration (top) and after (bottom). We pour water in the holes to help him get out of them whenever he is stuck.
The second is the length of the simulations: the timestep ∆t used in integration solvers is limited by the highest frequency vibration of the system. More precisely, MD simulations solve Newton's laws of motion for a group of many atoms. Since they all move around constantly, their bonds fluctuate and some can do so at high frequency. In most cases, the Carbon-Hydrogen bond stretching puts an upper bound on that frequency thereby requiring integration steps ∆t's to be of the order of the femtosecond.
In the lower frequency range, the different conformations of a protein corresponding to local minima (see for example Figure 1 ) -or metastable states -are separated by high-energy barriers. As a result, transitions between such structures are rare events that occur on a timescale of the microsecond and sometimes up to the millisecond. In order to see a single change in the free energy landscape, we potentially need to perform a sequential integration of Newton's equations more than a billion times.
To counter this issue, enhanced sampling methods, such as metadynamics [6] , have been developed in theoretical chemistry. The idea behind such strategies is to modify the potential energy of a molecule by adding an extra term called bias. This bias will decrease the energy barrier between conformations, forcing the system out of the metastable state where it is located.
We introduce Rémy the Rat to illustrate this idea. Rémy walks in a land filled with holes, and we would like to be able to map those holes and know their depth (that is, we want to know all possible shapes of a protein and associated energies). Now, imagine that Rémy's land is in a tank, and we can only see it from a bird's-eye view. That makes it very difficult to see the holes or make any height measurements.
Our solution is to attach a GPS tracker to Rémy's back -see Figure 2 . As Rémy walks around, we can track his position on the x-axis. Then, we simply say that if his position does not vary much for a given time, that means that he fell in a hole. Assuming that Rémy is a strong swimmer, to set him free, we pour water at his location, until we see that he is able to move freely once again. By keeping track of the amount of water we have poured, we can know how deep the hole was. After a while, Rémy will be able to move across his entire land: we have explored all the conformations of our molecule. This is the idea behind techniques such as metadynamics.
Such algorithms make use of collective variables (CVs) that are one-dimensional coordinates assumed to describe the system in its current state. These CVs enable the "guiding" of the simulation as shown in the procedure featured in Figure 3 . By adding a bias, we can push a system out of its "prison" through the addition of an extra force. Figure 3 : Schematic representation of enhanced sampling strategies based on CVs. All of these figures represent the free energy of the system (solid blue line) as a function of one CV. At first (Fig. 3a) , the system (dark blue bullet) is trapped in a local minimum. As a high-energy barrier separates this minimum from the global minimum, the simulation is only able to sample the region around the local minimum. Therefore, the bias (red line) is only added in that regionsee Fig. 3b . As the reference walker spends more time trapped in the local minimum, the bias increases until it becomes large enough for the system to reach the global minimum (Fig. 3c ), in which a smaller bias starts to build up. Finally, the bias is larger than the free energy barrier, and the simulation is able to sample easily the entire energy landscape. The free energy can be recovered by inverting the bias.
Typically, CVs can be physical coordinates such as the angle between certain bonds in molecules. In that case, they can be chosen using intuition. Unfortunately, it is not always that simple, especially for very large systems. Several methods have been developed to automatically detect such coordinates. In particular, Trstanova, Leimkuhler, and Lelièvre [4] proposed a method based on a dimensionality reduction algorithm called DMaps. We explore the use of this technique in the next section.
This subsection focuses on the DMaps algorithm, a nonlinear dimensionality reduction technique, and its application to MD results. Trstanova, Leimkuhler, and Lelièvre [4] have shown that this method can be used to identify when the system has reached a metastable state, as well as CVs in that state. We start by discussing DMaps, and then apply them to MD simulations.
Our objective is to find a nonlinear mapping into a k-dimensional space, with k < N , while preserving the structure of the dataset. The original DMaps algorithm, introduced in Ref. [7] , is described in Algorithm 1.
The hyperparameters γ, α, t should be selected to generate a low-dimensional embedding that preserves the main features of the data set. More details are discussed in the Appendix. Note that the dimensionality of the data can be reduced with a different technique prior to this algorithm, such as Random Projections (RPs) [8] .
Algorithm 1 Diffusion map algorithm.
1. Choose an isotropic diffusion kernel, such as the RBF kernel
with γ ∈ R + * an hyperparameter, and define the m × m diffusion matrix L such that L i,j = k (x i , x j ). The diffusion matrix is positive semi-definite: it has non-negative, real eigenvalues.
3. Define the diagonal matrix
M defines the transition matrix of a Markov process. Taking larger and larger powers of this matrix, M t with t ∈ N * , reveals the geometric structure of the studied data set at larger and larger scales. The probability to transition from one state to another in t steps is given by M t . This corresponds to a diffusion process. 4. Compute the k largest eigenvalues λ i , i = 1, ...k, and corresponding eigenvectors ψ i , i = 1, ...k, and build the embedding
The data points can now be represented using their Diffusion Coordinates (DCs) λ i ψ i , i = 1, ...k. The eigenvector corresponding to the largest eigenvalue, λ 1 = 1, is always a constant vector, ψ 1 = 1. Therefore, it does not contribute to the spectrum of the diffusion matrix. Excluding i = 1, we call dominant the coordinates λ i ψ i with a large enough associated eigenvalue.
In the Appendix, we explore the use of DMaps on the swiss roll data set [9] in Section A and we discuss the choice of hyperparameters for the algorithm in Section B. We detail now how DMaps can be used on data produced by MD simulations to enhance sampling.
The authors of [4] proposed an algorithm to enhance the sampling of the configuration space of a given molecule using DMaps locally. The interest in using DMaps to MD trajectories is two-fold.
Firstly, by computing the spectrum of the diffusion matrix, it is possible to detect metastable states as a collection of states for which the eigenvalues are almost stationary. Thus, a change in the spectrum enables us to detect a conformational change.
Secondly, using Pearson's correlation coefficients (A.2) between the DCs and the physical coordinates of the problem, it is possible to identify (physical) CVs. Those correspond to the slowest modes of the metastable state. This provides important information to enable the system to escape the metastable state, enhancing the sampling. Note that using CVs is more interesting than using diffusion coordinates, as they correspond to physical quantities (coordinates, angles, etc.). Therefore, they are defined on all the configuration space, while diffusion coordinates are only defined locally.
Algorithm 2 outlines such a procedure. In this method, DMaps are used in steps 1 and 4 -computing the spectrum of the diffusion matrix to detect the entrance and exit of a metastable state -and in step 2 -computing the diffusion coordinates to identify the CVs. Figure 4 illustrates the steps of the method.
The use of such a procedure relies on applying the DMaps algorithm every T steps. As we see in the next section 3.2, this is far from optimal. Hence, we explore alternatives.
In this section, we explore the limitations of the application of DMaps alone to MD problems, and offer the use of NEWMA as an addition to the strategy for enhanced sampling introduced before.
1. Run the MD, computing the spectrum of the diffusion matrix every T ∈ N * steps, until it is almost stationary.
This means that the system has reached a metastable state. 2. Identify the CVs as the physical coordinates which are the most correlated to the diffusion coordinates. 3. Using the learnt CVs, build a bias in the metastable state. 4. A change in the spectrum means that the system has left the metastable state it was exploring. Restart from step 1, keeping the bias built before. Figure 4 : Outline of the use of DMaps for MD problems, as proposed in Ref. [4] . F t denotes the time frame produced at time t, which is a vector storing the coordinates of all n atoms.
Previously, we have highlighted how DMaps can be used to identify metastable states. Indeed, computing the spectrum of the diffusion matrix, we can identify a collection of states with almost-stationary eigenvalues as a metastable state, while sharp changes characterize an exit of this state. However, this method has some limitations.
The first one is that it forces us to treat several time frames as batches of T points on which to apply the DMaps algorithm. Too small batches are rather unpractical, as the eigenvalues may then vary too much, while too large batches are more demanding numerically.
In addition to that, this means that batches of T time frames have to be stored, which can lead to a significant memory footprint for as the number of atoms n grows, since the frames are vectors of dimension n.
Note that the DMaps algorithm requires to calculate pair-wise distances between the T frames, re-normalizing and extracting the eigenvalues from the diffusion matrix. The computational cost of these operations is quite significant.
Furthermore, as discussed in Paragraph B, the hyperparameters of the DMaps procedure can be somewhat tricky to find, and come with no guarantees to be valid from one MD trajectory to the next.
Finally, to determine if the eigenvalues are almost stationary, one needs to quantify the way they are changing. This involves defining a threshold, which may again not be universal.
In the rest of this article, we explore how the use of NEWMA, an online change-point detection algorithm, can be used in combination with the Algorithm 2 to enhance sampling in MD.
Online change-point detection aims at detecting and flagging sharp changes in a stream of data points. The challenge is to identify such transitions as soon as they occur and limit the number of false alarms. Online methods do not require to store raw data points, hence having a lower memory footprint as well as being valuable when the data is sensitive. While the classical Exponentially-Weighted Moving Average (EWMA) estimation meets those criteria, it relies on prior knowledge of the data.
Algorithm 3 NEWMA, as proposed in [5] , applied to a MD problem.
Let F t ∈ R 3n be a vector containing the coordinates of n atoms at time t, Ψ : R 3n → R k a random embedding, with k ∈ N * , 0 < λ < Λ < 1 two forgetting factors, τ ∈ R + * a threshold and z 0 = z 0 ∈ R k two initial values. For t ∈ N *
2. If z t − z t ≥ τ , flag t as a change-point. 3 . Increment t = t + 1 and restart from step 1. Figure 5 : Strategy to enhance sampling in MD, using the NEWMA algorithm to detect conformational changes.
The idea behind NEWMA is to compute a detection statistic as the difference between two EWMA statistics. This quantity is then compared to an adaptive threshold. If this difference is above said threshold, the algorithm flags that point as a change-point (Algorithm 3). This method has the advantage of requiring no prior knowledge about the change-points or the trajectory studied, and can be computed online. Furthermore, the hyperparameters of the algorithms are selected by a heuristic computed only on the window size -that is, the number of recent samples that are to be compared with older ones. More details about the algorithm as well as the heuristics for its hyperparameters search can be found in Ref. [5] .
The detection statistics are calculated using RPs as the embedding Ψ. They can be computed on CPU using methods such as Random Fourier Features (NEWMA RFF on CPU) [10] or FastFood (NEWMA FF on CPU) [11] . Recently, an Optical Processing Unit (OPU) has been developed at LightOn [12] , computing random features through light interactions with matter, at a constant computational cost and no memory expense. We use it to compute the detection statistics (NEWMA RP on OPU).
We now explore the possibility to combine DMaps with the work of Ref. [5] , which provides a low-memory-footprint method to detect change-points with an adaptive threshold scheme.
Our idea is to use such a procedure to identify conformational changes, replacing the steps 1 and 4 of Algorithm 2. This allows us to apply the DMaps algorithm only in steps 2, to identify the CVs through the diffusion coordinates, and use them to enhance the sampling. Figure 5 summarizes this method. In the next subsection, we show numerical results and discuss the performances required.
To go back to our analogy with Rémy the Rat, saying that Rémy is stuck because he hasn't moved that much lately presents some issues:
• What does "moving that much" mean? In practice, that means defining a threshold. Yet, we do not want our mapping to be dependent on a user-defined quantity.
• This method implies that we are monitoring Rémy's position at all times, which means a lot of resources: a human watching, a satellite constellation, etc. Correspondingly, sampling methods and DMaps in MD require lots of computational resources. Not only trajectories have to be computed, but then they need to be analyzed online to determine if the molecule is stuck in a conformation or not.
The use of an accelerometer circumvents those issues: accelerometers do not use satellites as GPS trackers do and are much simpler and cheaper. Using one, we can detect if Rémy is suddenly falling, and we know that this means he is falling into a hole. We can save some time and some energy. We do not have to track Rémy at all times, only to put an alarm when the accelerometer says that Rémy fell. This is essentially what using NEWMA does for our MD simulations.
NEWMA makes it possible to use the DMaps algorithm only once a conformational change has been detected, instead of using it every T batch of time frames. Once a change-point has been identified and only then, T points are stored to be used in DMaps and learn CVs. Therefore, this strategy has a much lower computational and memory cost than the one proposed in Algorithm 2. In addition, it also solves our issues of being model dependent.
In summary, in the new MD calculation pipeline shown in Figure 5 , NEWMA-based detection can be efficiently computed at every timestep while the coarser-grained, low-resolution DMaps algorithm can be used to obtain the coordinate representation in the manifold dataset when it is needed. This approach leads the way to faster global sampling studies, such as metadynamics. We present our numerical experiments in the next section.
In this section, we focus on our numerical results, testing NEWMA as a method to detect conformational changes in MD, and compare it to DMaps. We also compare the different methods to compute RPs discussed in Section 3.2. All of our experiments were run on the LightOn Cloud [12] , using an Intel Xeon Gold 6128 3.40GHz CPU and a LightOn Aurora OPU. The code is available at https://github.com/lightonai/newma-md.
On March 11, 2020, the World Health Organization (WHO) has declared the ongoing coronavirus disease COVID-19 a pandemic. This infection is caused by the virus Severe Acute Respiratory Syndrome Coronavirus 2 (SARS-CoV-2). To face this challenge, "the greatest since World War Two" according to Angela Merkel, a significant portion of the scientific community has been devoted to the research on the virus. In particular, simulations of the SARS-CoV-2 virus have been conducted to determine the efficiency of certain drugs such as Lopinavir [13] . This simulation includes 30 000 time frames for n = 4 776 atoms, that we use to showcase the efficiency of NEWMA. However, the MD simulations published by Cespugli, Durmaz, Steinkellner, and Gruber [13] of the virus SARS-CoV-2 do not include any ground truth. That is, we do not know when exactly conformational changes are happening. We compare in Figure 6 the transitions detected using the NEWMA algorithm to the transitions detected using changes in the spectrum of the diffusion operators (DMaps). The detection statistics of NEWMA being extremely noisy for our datasets, for a point to be flagged as a change of conformation, the detection statistics has to be larger than the threshold for the next 20 points.
The conformational changes detected by NEWMA match the ones obtained through changes of the DMaps spectrum. This is very promising: as pointed out before, this method does not require any prior knowledge to detect the changes. By using the change points detected by NEWMA, we can reduce the number of times that we have to compute the spectrum of the diffusion operator by a factor 4 (see Figure 6 ). This is substantial gain, as the spectrum of the diffusion operator requires the computation of pairwise distances between all atoms in the simulation and also requires the diagonalisation of that matrix. As trajectories typically consider a much larger number of time frames, this effect is amplified.
Since March 27th, D.E. Shaw Research (DESRES) has been releasing MD trajectories related to SARS-CoV-2 using the supercomputer Anton 2 [14] . Moreover, videos visualizing the simulated behaviors are also available, which gives us a comparison point for NEWMA. We focus on two 10 − µs-simulations of the trimeric SARS-CoV-2 spike glycoprotein (DESRES-ANTON-10897136 and -10897850). The first trajectory -(a) -was initiated in the closed state (PDB entry 6VXX), and remained stable. The second trajectory -(b) -was initiated in a partially opened state (PDB entry 6VYB) and showed a part of the protein detaching a bit and then detaching even more.
The singular aspect of these computations is their sheer size: the glycoprotein counts no less than n = 46 851 atoms, which amounts to 140 553 features as each atom has three coordinates. With such scales, memory does become a problem if we consider using the algorithm NEWMA FF on CPU to compute RPs. This is not the case if optical random features (NEWMA RP on OPU) are used. Figure 7 shows the results obtained with NEWMA RP on OPU for trajectory (a) and (b, including images showing the changes observed in the videos. We start by discussing trajectory (a) -initiated in the closed state. While it is mostly stable, some ever-so-slight variations in the structure can be observed in its video visualisation -in the upper-right and bottom-right parts of the glycoprotein. The change observed by NEWMA RP on OPU matches the one observed in the video -see the representations included in Figure 7a .
Next, we discuss trajectory (b) -initiated in a partially opened state. As mentioned before, this glycoprotein shows two major changes in its structure. First, the upper-right blob separates itself from the main structure. Then, it detaches further -see the representations included in Figure 7b . The observations of NEWMA RP on OPU are in agreement with those conformational changes. Figure 8 : Pyramid sketch used to deal with high-dimensional data. The timeframe F t , containing the three-dimensional coordinates of the atoms of the system, is divided to form three smaller vectors. Each of those vectors are projected using RPs into a lower-dimensional space, and the outputs are merged together. Finally, a second RP is used to project the data into a k-dimensional space.
Larger Scales While 140 553 features may seem like a very large number, current computations in HPC for MD regularly goes far beyond that. In these regimes, it becomes extremely prohibitive to detect conformational changes on either a CPU or a GPU. DESRES also released all-inclusive versions of trajectories (a) and (b), that include water and ion atoms, in addition to the glycoprotein. All in all, this computation features more than 715 439 atoms resulting in more than 2 146 317 features. Note that while this may seem like a very large number, MD simulations sometimes include a couple of millions of atoms, or more.
Analysing such data on a CPU or a GPU would take too long and would require a very large amount of memory footprint. However, NEWMA RPs implemented on the OPU can be used to study the conformational changes of these all-inclusive versions. Note that a pyramidal sketch of the data is used to bypass the limit in the input size of the OPU -see Figure 8 for additional information. Figure 9 shows the results obtained for the first microseconds of the all-inclusive version of (b): they match the behavior observed on the glycoprotein-atoms-only trajectory (b). The experiments above show that the results obtained by applying NEWMA to MD simulations match those observed through the DMaps algorithm as well as changes observed in video visualisations.
We compare here the performances of NEWMA using the three methods presented in Section 3.2 to compute RPs: NEWMA RFF on CPU, NEWMA FF on CPU, and NEWMA RP on OPU. In addition to the SARS-CoV-2 trajectories presented above [13, 14] , we benchmarked NEWMA using supplementary MD simulations of molecular systems of various sizes provided by DESRES [15] . We analyse 10 000 times steps of all those trajectories. Figure 10 shows the results of these investigations, comparing the computation times of the different implementations of NEWMA as a function of the number of atoms of the molecular system studied. By design, NEWMA RFF on CPU is slower than NEWMA FF on CPU. However, it is interesting to note that NEWMA RP on OPU is always faster than both CPU-using methods. While the difference is not significant for a number of atoms under O 10 3 , it increases as it grows larger. In fact, for trajectories (a) and (b), computation times were ten times faster on an OPU than on a CPU.
More importantly, it still took less than a minute to perform those analyses on an OPU. By comparison, Anton 2, the supercomputers used to produce trajectory (a) and (b), can simulate around 80 µs a day for systems of these sizes [16] . This translates to approximately 3 hours to produce one of such trajectories, which can be analyzed using NEWMA in about 40 s.
Using optical random features particularly shines as the computation time is almost independent of the number of atoms. Indeed, by design, the NEWMA RP on OPU provides a scalable method to analyse conformational changes in MD simulations. While the all-inclusive version of trajectory (b) was not included in Figure 10 , as we did not run the CPU-based NEWMA methods, it only took about two minutes to analyse it. This is a couple of orders of magnitude faster than the time it would take most people to download the 62 GB of this trajectory.
We presented and implemented the use of NEWMA, a scalable, model-free change-point detection method, to identify conformational changes. In addition, we also proposed a strategy combining NEWMA and DMaps to learn CVs and enhance sampling in MD.
We showed that using NEWMA is a very effective way to detect transitions in MD for large molecular systems. This way, the DMaps algorithm -which requires to compute the diffusion matrix and extracting its spectrum -need only to be applied once a change is detected by NEWMA, as a mean to learn CVs. This makes the combination of these two methods a powerful strategy to enhance sampling in MD. They provide a clever and efficient way to analyse MD trajectories online, enabling more resources to be allocated to the computation of said trajectories.
While CPU-based algorithms reach their limits with the number of features of these MD simulations, we showed that using a LightOn OPU bypasses this issue. Optical random features make the use of NEWMA virtually independent on the number of atoms in the trajectory, both in terms of memory and computational costs. In addition, as the size of the data grows, the OPU can be used to perform a pyramidal sketch. While the example presented above was made of two layers of RPs, the same idea could easily be extended, adding more layers for higher-dimensional data. This allows the seamless of use NEWMA on high dimensional data. This could be especially promising for systems such as lipid bilayers, which include billions of atoms.
In addition, NEWMA is an online detection method, that can detect conformational changes just as they occur in the simulated trajectory, without the need to store the entire trajectory. In the context of MD simulations, using optical RPs with the OPU allows the full HPC infrastructure to solely focus on the actual computation of trajectories.
We believe that NEWMA RP on OPU could be of great help in many domains relying on MD, such as drug discovery.
Figure A.1: The Swiss roll data set represented in the original three-dimensional space (Fig. A.1a) and in the twodimensional space embedding given by the two dominant DCs (Fig. A.1b) . The color map corresponds to the value of the second DC.
We apply the diffusion map algorithm, using the following parameters:
• k = 3, since the data set is originally in three dimensions. Note that this comes down to representing the data points in a two-dimensional space as the first eigenvalue and eigenvector pair is discarded.
• α = 1/2, which makes the DMaps operator coincide with the Fokker-Planck diffusion operator.
• γ = 7 and t = 1, which have been chosen through trial and error.
We discard the first pair of eigenvalue and eigenvector, and represent the points in a two-dimensional space parametrized by the other two DCs. The results are shown in Fig. A. 1b. From these results, it appears that the data points can be easily embedded in a two-dimensional space: points that are close together on the roll are indeed close together in the embedded space.
It is possible to compute the Pearson's correlation coefficients between the second and third DCs and the physical coordinates of the problem: x, y, z, φ and ξ. Pearson's correlation coefficients give us more information about the structure of the data by showing which of the original coordinates matter most in the geometrical description of the data set. They are defined as
where X and Y are two random one-dimensional variables of respective standard deviations σ X and σ Y , and cov is the covariance. Such a coefficient ranges from −1 to 1: a value of 1 implies than X and Y are linearly related, with X increasing as Y increases, while a value of −1 means than X decreases as Y increases. A value of 0 indicates that there is no linear relation between X and Y .
In the case of the Swiss roll data set, we find that the DC 2 is most correlated to φ, with DC 2 decreasing as φ increases. The third DC is most correlated to z, with DC 3 decreasing as z increases. This is what we expect from the way the data points were generated, and what can be observed in Fig. A.1 .
The DMaps algorithm (Algorithm 1) depends on four hyperparameters: the width of the kernel γ, the normalization parameter α, the time scale t, and the number of DCs k. In this work, we set α = 1/2 so that the Markov chain described by the diffusion matrix M approximates the Fokker-Planck diffusion process. We also set t = 1 as we found the value of t did not have much impact on the results observed.
It is tricky to find an appropriate value for the width of the kernel that unravels the geometrical structure of a given data set. Indeed, defining a cost function is impossible as we do not have a target to compare to. The inverse of the median of the pairwise distances between the points of the data set provides a good candidate for γ. This ensures that, for at least half of our data points, the RBF kernel is larger than a certain value. We use this method, known as the median trick [17] , through this report.
As for the number of relevant diffusion coordinates, our goal is to find the lowest value for the dimension of the diffusion space k retaining the relevant features of our data set. Thus, we define a cost function with a regularization term which penalises model with a larger value of k. For the sake of simplicity, in this section, we set t = 1 and remove the dependence on this parameter from our equations.
The diffusion distance between two vector points x i , x j at time t is defined so that it is the Euclidean distance in the diffusion embedding
We define the error for the value k as
that is, the difference between the diffusion distance computed using only the first k components of the spectrum and the diffusion distance computed using the full spectrum of the diffusion matrix. Obviously, this function is strictly decreasing with k and cannot be used as a cost function itself, as its minimum is reached for k = m.
In order to build our cost function, we introduce the regularization term
with δ ∈ Z * . This term penalises models which use a larger value of k, including eigenvalues which are very small. The introduction of such a regularization term stems from the fact that λ i ψ i 1 is a decreasing function of i, with values getting quickly suppressed and with an inflection point which seems to corresponds to the best fit value of k.
Our cost function is then the sum of our error and regularization terms J k (β) = E k + βR k , (A. 6) where β ∈ R + * is a parameter to be determined. For the sake of simplicity, we introduce and represent such that lim k→+∞ F k (β) = lim k→+∞ R k is independent of the value of the value of β. Finding a proper value for β is crucial, as we will discuss in the next subsection. From experiments, it appears that the value β = E k=1 seems to provide good results on various data sets. 