LSH-SMILE: Locality Sensitive Hashing Accelerated Simulation and Learning
Year: 2022

Abstract:
The advancement of deep neural networks over the last decade has enabled progress in scientific knowledge discovery in the form of learning Partial Differential Equations (PDEs) directly from experiment data. Nevertheless, forward simulation and backward learning of large-scale dynamic systems requires handling billions mutually interacting elements, the scale of which overwhelms current computing architectures. We propose Locality Sensitive Hashing Accelerated Simulation and Learning (LSH-SMILE), a unified framework to scale up both forward simulation and backward learning of physics systems. LSH-SMILE takes advantages of (i) the locality of PDE updates, (ii) similar temporal dynamics shared by multiple elements. LSH-SMILE hashes elements with similar dynamics into a single hash bucket and handles their updates at once. This allows LSH-SMILE to scale with respect to the number of non-empty hash buckets, a drastic improvement over conventional approaches. Theoretically, we prove a novel bound on the errors introduced by LSH-SMILE. Experimentally, we demonstrate that LSH-SMILE simulates physics systems at comparable quality with exact approaches, but with way less time and space complexity. Such savings also translate to better learning performance due to LSH-SMILE’s ability to propagate gradients over a long duration.

text: The advancement of deep neural networks over the last decade has enabled progress in scientific knowledge discovery in the form of learning Partial Differential Equations (PDEs) directly from experiment data. Nevertheless, forward simulation and backward learning of large-scale dynamic systems requires handling billions mutually interacting elements, the scale of which overwhelms current computing architectures. We propose Locality Sensitive Hashing Accelerated Simulation and Learning (LSH-SMILE), a unified framework to scale up both forward simulation and backward learning of physics systems. LSH-SMILE takes advantages of (i) the locality of PDE updates, (ii) similar temporal dynamics shared by multiple elements. LSH-SMILE hashes elements with similar dynamics into a single hash bucket and handles their updates at once. This allows LSH-SMILE to scale with respect to the number of non-empty hash buckets, a drastic improvement over conventional approaches. Theoretically, we prove a novel bound on the errors introduced by LSH-SMILE. Experimentally, we demonstrate that LSH-SMILE simulates physics systems at comparable quality with exact approaches, but with way less time and space complexity. Such savings also translate to better learning performance due to LSH-SMILE’s ability to propagate gradients over a long duration.

heading: 1 Introduction
text: Learning-driven scientific discovery has enjoyed rapid progress thanks to the advancement of deep neural networks over the last decade. Since Partial Differential Equations (PDEs) are widely used to model physics systems, a fruitful line of research has been developed focusing on learning PDEs from experimental data, including Finzi et al. [2020], Greydanus et al. [2019], Matsubara et al. [2020].
Nevertheless, successful applications of machine learning for scientific discovery still face multiple challenges, many of which are computational. Both the forward simulation and backward learning of large-scale dynamic systems requires handling billions mutually interacting elements, the scale of which overwhelms current computing architectures. Forward simulation involves simulating the trajectory of a PDE system from a given starting state. Recent work of Greydanus et al. [2019] demonstrates such process can be represented using a neural network similar to ResNet. Backward learning is to discover (the parameters of) the physics model automatically from experimental data, which also attracts recent attention in Niu et al. [2020] and Xue et al. [2021]. Backward learning can be achieved by embedding a neural network modeling the forward simulation into the overall architecture and minimizing a loss function which penalizes the difference between the simulated result and the observed data via back-propagation. In both forward simulation and backward learning, billions of mutually interacting elements resulted from applying the finite difference or finite element
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
approaches have to be handled efficiently. Current brute-force approaches which treat each element as one matrix element do not scale to meet the computational need.
To tackle the computational bottleneck, we propose Locality Sensitive Hashing Accelerated Simulation and Learning (LSH-SMILE), a unified framework to scale up both forward simulation and backward learning of physics systems represented in a set of PDEs. The method is based on three key observations. The first is that only a small fraction of elements change while the majority of elements remain the same in one step forward simulation. The second is that the one-step update of one element depends on the values of a small set of neighboring elements. The third is that many elements share similar temporal dynamics. The three observations are shared among the simulations of a wide variety of physics phenomena, especially in the so-called interface problems that have applications in fluid dynamics, heat transfer, cracking formation, etc. Motivated by these observations, LSH-SMILE harnesses Locality Sensitive Hashing (LSH) to boost the computational throughput. By representing each element as a vector of its value and its neighbor elements’ value, we hash elements into hash buckets via LSH, where elements with similar self and neighboring element values are grouped into the same bucket. Then the forward simulation and backward learning are carried out for all the elements hashed into the same bucket at once. In this way, the time and space complexities of LSH-SMILE are reduced to be propotional to the number of non-empty hash buckets, a drastic improvement compared to the number of distinct elements in the brute-force algorithm. We also prove a novel bound on the quality of the approximation of LSH-SMILE and provide an interface to control the error rate. LSH-SMILE explores a novel way of using LSH in learning and simulation. Compared to traditional LSH usage case in the nearest neighbor search where the hash table stays the same, LSH-SMILE needs to maintain a hash table that changes dynamically over time. New theoretical and experimental ideas can be sparkled via exploring this new usage of LSH.
Experimentally, LSH-SMILE is able to simulate and learn physics systems represented in PDEs at a comparable quality with the exact methods while saving drastically in computation. We focus our attention on systems in nano-physics, where we simulate and learn the grain growth in materials (Fan and Chen [1997]) and model the spatial temporal dynamics of void shaped defects, namely nanovoids, in materials under high temperature and irradiation (Millett et al. [2011]). The proposed LSH-SMILE reduces the overall simulation time compared to an exact Torch implementation by 70% in the grain growth simulation, and by 95% in the nanovoid simulation. In terms of precision, LSH-SMILE matches the ground truth results to the scale of 10−5 in both the nanovoid and the grain growth simulations after 100 simulation steps. Such savings directly translate to better learning performance. In our experiment which uses LSH-SMILE to learn the physics parameters governing a grain growth process, LSH-SMILE-based learning approach can successfully identify the correct model parameters while brute-force baseline approaches cannot, The success is due to a longer forward simulation (30 time steps) embedded in the backward learning process enabled by the computational savings of LSH-SMILE. Baseline approaches can only embed 10 forward simulation steps with similar computational budget. One related approach is the Fast Multi-pole Method (Rokhlin [1985]) used in astrophysics. FMM is used to calculate long-ranged forces in the n-body problem, by grouping elements which are close in distance into a single source. However, LSH-SMILE groups elements based on their similarity in future updates. We believe this is a key difference. Overall, the computational innovation of LSH-SMILE opens the door for faster and better scientific discoveries.

heading: 2 Preliminaries
text: Energy-based systems represented in Partial Differential Equations (PDEs). The dynamics of many physics systems can be described with first or second-order Partial Differential Equations (PDEs) modeling the system energy. Given the state ~u(~p, t) = (u1(~p, t), . . . , um(~p, t))T , where ~p = (x1, . . . , xd) T denotes the spatial coordinates and t denotes time, such PDEs are in the form:
∂~u(~p, t)
∂t = D(~u) +G(~u)∇F (~u) + I(~u)∇2H(~u). (1)
Here, F and H are functions that map Rm to R. ∇ = ( ∂∂x1 , . . . , ∂ ∂xd )T represents the gradient operator, ∇2 = ∇ · ∇ is the Laplace operator. D is a function that maps Rm to Rm. G(~u) is an m-by-d matrix and I(~u) is a m-by-1 vector.
Many notable physics systems can be represented using PDEs in Equation 1. The widely used AllenCahn and Cahn-Hilliard Equations in phase field modeling are good examples. The Cahn–Hilliard
equation and Allen-Cahn equation are used to describes the physics process of field variables in nano-scale materials. The values of the field variables represent the micro-structure composition at different spatial coordinates. The Cahn–Hilliard equation has the general form:
∂u ∂t = ∇ ·
( M∇ 1
N
δF
δu
) . (2)
The Allen-Cahn equation has the general form:
∂v ∂t = −L δF δv . (3)
Here u and v are the field variables of interest and they are assumed to be continuous and changing rapidly across the inter-facial regions. t is time. M , N , L are physics parameters that are related to the changing process. F is the energy function which is different in different applications. More details are left in the supplementary materials.
Discretization with finite difference. Finite difference methods allow us to simulate and learn PDEs using the forward and backward propagation of a neural network. It has attracted recent attentions in recent works, e.g., Wang et al. [2020], Dong and Simos [2017], Forsythe and Wasows [1963] and Shojaei et al. [2019]. More specifically, let {xi,1, xi,2, . . . , xi,R} be a finite discretization of the domain of xi, where each xi,k is called a discretization point. {t1, t2, . . . , tS} is the discretization of the time. Let ~i = (i1, i2, . . . , id). We use ~u(~i, j) as a shorthand for ~u evaluated at position ~i = (x1,i1 , . . . , xd,id)
T and time tj , i.e., ~u(~i, j) = ~u(x1,i1 , . . . , xd,id , tj). Each discretized position ~i is also called an element. The left-hand side of Equation 1 can be discretized using the finite difference: ∂~u(
~i,j) ∂t ≈ ~u(~i,j+1)−~u(~i,j) tj+1−tj . Similarly, notice ∇F (~u) = ( ∂F (~u) ∂x1 , . . . , ∂F (~u)∂xd ) T , where
∂F (~u) ∂xl = ∑m k=1 ∂F (~u) ∂uk ∂uk ∂xl . We need ∂uk( ~i,j) ∂xl to compute ∇F and ∂uk(~i,j)∂xl can be approximated by uk( ~i+1l,j)−uk(~i,j) xl,il+1−xl,il . Here,~i + 1l means to move the l-th coordinate of~i, namely il, to the next discretization point il+1. Repeating this type of calculations for the second-order derivatives∇2H(~u), the PDE in Equation 1 can be approximated in the following general form:
~u(~i, j + 1) = ~u(~i, j) + δtQ({~u(~i′, j),~i′ ∈ N(~i)}). (4)
Here, we intentionally use function Q to abstract out the actual form, because its derivation is pure arithmetic and is only marginally related to the main purpose of this paper. One important fact to notice: Q depends on a small set of ~u(~i′, j)’s, in which~i′ is a neighboring element of~i. We use N(~i) to represent the set of neighbors of~i. In the two applications we consider in this paper, N(~i) is actually small and only consists of the first and second order neighbors. Two elements are first or second order neighbors if and only if they differ in one dimension within two discretization points, or they differ in two dimensions, each dimension within one discretization point.
Forward simulation. By discretizing PDEs with finite difference approach (Equation 4), we can simulate future states of a physics system from an initial state by updating the left-hand side with values from the right-hand side of Equation 4 repeatedly. Interestingly, such a process can be
implemented as a multi-layer convolutional neural network (see, e.g., Xue et al. [2021]). See Figure 1 for a demonstration of the forward simulation process. Here we use the grain growth as an example.
Backward Learning. Backward learning allows us to learn the parameters of the PDE that governs the dynamics of a physics system from experiment data. It is developed with a series of work, e.g. Wen et al. [2021], Dupont et al. [2019], Xue et al. [2021] and Rubanova et al. [2019]. During backward learning, physics rules are expressed in the form of Equation 4 initialized with random parameters. The dataset consists of the observed pairs of states: ~u(~p, t) and ~u(~p, t + T ), where ~u(~p, t) is the state of physics system at time t and ~u(~p, t+ T ) is the state at time t+ T . Here T is a constant set manually. Starting with ~u(~p, t), a repeated evaluation of Equation 4 of T times will yield the simulated state ~u′(~p, t + T ). A loss function is defined to penalize the difference between the simulated state ~u′(~p, t+ T ) and observed state ~u(~p, t+ T ). In our experiment, we use the L2 loss function. Back-propagation (Rumelhart et al. [1986], Robbins and Monro [1951]) is then applied to minimize the difference. Upon convergence, correct physics parameters are learned which yield the same temporal dynamics as the observed data.
Locality Sensitive Hashing (LSH). For a domain S with distance measure D, a LSH family is: Definition 1. H = {h : S → U} is called a (r1, r2, p, q)-sensitive LSH function family for D if for any two points x, y ∈ S, one function h chosen uniformly at random fromH satisfies:
• if D(x, y) ≤ r1, then Ph∈H[h(x)=h(y)] ≥ p, • if D(x, y) ≥ r2, then Ph∈H[h(x)=h(y)] ≤ q.
In this paper, Euclidean distance is used as the distance measure D. In this case, a function in the LSH hash function family has the following form ha,b(v) = ⌊ a·v+b r ⌋ , where a is a d-dimensional vector with entries chosen independently at random from a standard Gaussian distribution and b is a real number chosen uniformly from the range [0, r]. r is a hyper-parameter denoting the size of the hash bucket. We refer the reader to Datar et al. [2004] for the selection of r and the resulting performance (i.e., the values of r1, r2, p, q).

heading: 3 Intuition
text: The intuitions behind the development of LSH-SMILE is inspired by the following three observations. Notice that these observations apply to a wide range of physics systems beyond the applications considered in this paper. Hence, we believe our method can be applied in a broad context.
Concentrated updates. Our first observation is that most element updates are concentrated in small area. For example, consider our application of grain growth (Fan and Chen [1997]). As shown in Figure 2 (first and second rows), the updates are concentrated in rather small boundary area (shown in yellow in the first row). There are no updates inside the grains (shown in green, purple, blue of the first row). From our calculation, the boundary area where significant updates reside makes up under 1% of the entire image. Notice this phenomenon is prevalent in many physics systems, especially among the so-called interface problems. Such concentrated updates makes it wasteful to spread computation resources over the entire area. An algorithm focused on area of real updates can potentially save a lot of computation.
Spatial local dependency. Out second observation is that updating one element only depends on the values of the element itself and its small set of neighboring elements. Notice this property is a direct consequence of applying the finite difference method on PDEs. See, e.g., applying finite difference on Equation 1 results in Equation 4, in which the updates depend on a small set of elements in N(~i). As a consequence, this observation applies to a wide range of PDE systems. A more intuitive illustration is shown in Figure 3 for the nanovoid evolution application we consider. Here the update of one element (shown in the red box) depends on its first and second-order neighbors (shown in blue boxes).
Elements share similar dynamics. Our third observation is that many elements share similar temporal dynamics. Notice that this is a direct consequence of the spatial local dependency. Because the temporal update of one element depends on its own value and those of its neighbors, the temporal update of two elements will be the same if their own value and their neighbors’ values meet. For example in Figure 2, the temporal dynamics of elements inside each grain are basically the same.

heading: 4 The LSH-SMILE Algorithm
text: Our proposed LSH-SMILE algorithm harnesses locality sensitive hashing to accelerate both the forward simulation and the backward learning of physics systems represented in PDEs. We first hash every element into a hash table based on LSH computed from the values of the element and its neighbors. Because of previous observations, the elements hashed into the same bucket share similar dynamics. The key idea behind LSH-SMILE is to handle all the elements in each hash bucket at once, hence reducing the complexity from proportional to the number of elements to proportional to the number of non-empty hash buckets, a drastic improvement. For example, the third row of Figure 2 colors elements of different hash buckets with different colors. We can see that elements inside each grain are hashed into a single hash bucket (shown in red, blue and pink), while elements on the boundary are hashed into many different hash buckets. In this way, only three operations suffice to handle the updates of all elements inside the three grains. In this section, we will first describe LSH-SMILE algorithm for forward simulation, then will discuss LSH-SMILE for backward learning. The pseudo code of LSH-SMILE for forward simulation is in Figure 4.
Notation. We first introduce the notation used in LSH-SMILE in Figure 4. Bt is the hash table at time t. I is the initial state. r,K,L are LSH parameters. r0 is a threshold. N is the number of simulation steps.
Data structure. Bt is the hash table at time t, each entry of which is a hash bucket. In one hash bucket Bt,i ∈ Bt, there is a representative value Bt,i.v, a representative element Bt,i.rep, a list of its elements’ coordinates Bt,i.P and a list of neighbor elements’ coordinates Bt,i.N . Here we use union-find-delete data structure (Ben-amram and Yoffe [2011]) to organize Bt,i.P , which ensures that we can perform the union of the elements of two hash buckets and deleting one element from a hash bucket in nearly constant time. The idea of building such a hash bucket is that, using LSH, every element ~u(~i, j) that shares almost the same values for itself and for its neighbors N(~i) shall be hashed into the same bucket with high probability. We intentionally give all elements in one bucket a single value, namely Bt,i.v. We use Bt,i.P to track all the elements in the bucket and Bt,i.N to track all the elements that neighbor elements in Bt,i.P but are not in Bt,i.P . According to Equation 4, the elements in one hash bucket have similar updates. Hence, we can update the value Bt,i.v for all elements in this bucket following Equation 4 in one step, thus saving computation time.
Encode initial state. The first step of LSH-SMILE is to encode the input data into the data structure described above. At the beginning, since we do not have any prior information of the input data, we use a brute-force method which iterates all elements in the input data and construct a hash table where each hash bucket only contain one element. Then we perform MergeBucket which merges those buckets whose elements share colliding LSH codes.
Forward and OneStep functions. The main function for the forward simulation is Forward, which calls OneStep N times to simulate forward simulation of N time steps. Each OneStep simulates one step. In OneStep, first it iterates every hash bucket to perform an one-step update given in Equation 4. The update is carried out using function Eval(·). After the update, it updates its LSH hash code and sees if the update is bigger than a threshold r0. If so, all elements in the bucket needs to be re-hashed. We do so by updating their LSH code. Notice this is an operation that is carried out at once for all elements in the bucket. Also notice that the value updates of the elements in the bucket may affect
the LSH codes of neighboring elements, namely those in Bt,i.N . We put these elements into ActiveL for later processing. After iterating all hash buckets, LSH-SMILE handles ActiveL, rehashing the elements inside one by one to make sure that they are in their correct buckets. Finally, it merges all the buckets with colliding LSH hash codes.
Invariants. LSH-SMILE strives to maintain the following invariants: (i) every element is in one and only one hash bucket. (ii) The LSH code computed for every element residing in a bucket collides with the LSH code of the representative element of the bucket. (iii) The LSH code of different hash buckets do not collide. (i) is guaranteed because we only move elements between buckets. (ii) is ensured because the change of the LSH code of one element can only happen if either the value of the element changes or the values of its neighboring elements change. When r0 is set small, its own value change will trigger the exceeding of r0 threshold and hence the element is rehashed. The values change of its neighbors will put the element in ActiveL and hence is rehashed. (iii) is guaranteed because of the MergeBuckets operation, since buckets with colliding LSH codes are merged.
AND of OR LSH. We introduce multi-probe LSH techniques from Lv et al. [2007] to guarantee high probabilities that two elements within the distance of r will be hashed into the same hash bucket. Consider a series of LSH functions hi,j constructed in the form hi,j(v) = ⌊ ai,j ·v+bi,j
r
⌋ where ai,j
and bi,j are sampled in the way described in Section 2. Construct gi(p) = [hi,1(p), . . . , hi,K(p)], select L different functions g1, . . . , gL. For one element p, hash p into all L buckets, denoted by g1, . . . , gL. p and q “collides” if they collide under any of the g1, . . . , gL values. We refer to the next section on how to choose K,L, r and the corresponding guarantees we can have.
Merge Buckets. During simulation, the values of the representative element and neighbors may change, leading to several hash buckets colliding on the LSH codes. To avoid duplicative computation, we use MergeBuckets to merge those buckets with colliding LSH codes.
ActiveL. TheActiveL is a list of elements whose neighbors’ values are updated which can potentially lead to their own LSH updates. We maintain this list during simulation and process these elements one by one in the end of OneStep.
Backward learning. The described forward simulation process can be embedded in the backward learning which learns the parameters of the PDEs from experimental data. The high-level idea is to harness stochastic gradient descend to adjust the PDE parameters so as to minimize the difference between the simulated results of T steps and the experiment data after T steps. Notice in the forward simulation, we do not retain the hash table for every time stamp. Otherwise there is a large overhead copying hash buckets between hash tables. However, elements values in previous time stamps are needed for back propagation. In this case, we slightly modify Equation 4, namely, replacing ~u(~i′, j) with ~u(~i′, j + 1), when used in back-propagation.

heading: 5 Analysis
text: Algorithm running time analysis. Let n be the size of input I , b be the largest number of buckets in any Bt, g be the size of largest neighbor list for one bucket during simulation. The merging of two buckets Merge(B,B′) has to merge the element list B.P and B′.P as well as updating the neighbor’s list. Merging element list is conducted using the union-find-delete data structure and is handled in near constant time. The bottleneck is to update the neighbor list, which scales O(g log g) using sorted list merge. For MergeBuckets, at most bL Merge operations can happen and hence the complexity is O(bKL + bLg log g). In function EncodeInitState(·), line 21 to 24 iterates every element in I , line 25 calls MergeBuckets, thus this function have time complexity O(n+ bKL+ bLg log g). In function OneStep(·), line 10 to 18 iterates on B, the time complexity is O(bKL). Line 20 to 24 iterates on ActiveL, which has size smaller than bg. Line 25 calls MergeBuckets. Hence the time complexity of OneStep is O(bKL + bLg log g). In function Forward(·), line 2 calls EncodeInitState(·), line 3 to 5 calls OneStep(·) for N steps. The time complexity of Forward(·) is O(bNKL+ bNLg log g + n). In comparison, a brute-force method has time complexity O(nN). Our LSH-SMILE will be faster than the brute-force method when bKL+ bLg log g << n.
Error bound introduced by LSH-SMILE. When quantifying the approximation quality of LSHSMILE, we assume all the elements during simulation are naturally clustered. Naturally clustered means that there exists c > 1 and r > 0, for any two elements x and y, either they belong to the same
cluster and hence their distance ||x− y|| ≤ r, or they belong to different clusters and ||x− y|| ≥ cr. Here x and y refer to the vectors containing the values of the corresponding elements and their neighbors. Naturally clustering well describes the observed data in practice. In the grain growth example, the elements inside each grain share similar values (hence having small pairwise distances), while the elements of different grains or in the boundaries are different (hence having large pairwise distances). Under the natural clustering assumption, we can build a LSH function which guarantees with high probabilities that elements inside each cluster are hashed to the same bucket while elements of different clusters are hashed to different buckets, as reflected in the following theorem: Theorem 1. For 0 < < 0.5, let C = log (1− ), then 0 < C < 1. Suppose each hi,j is sampled from a (r, cr, p, q)-sensitive LSH function family. Pick K = max{1, dlogp/q Ce}, L = 1log (1−pK) . Build L LSH functions in the way described in “AND of OR LSH”, we have
• For all elements x, y satisfying ||x− y|| ≤ r, i.e., they belong to the same cluster, we have Pr(x collide with y) ≥ 1− . • For all elements x, y satisfying ||x− y|| ≥ cr, i.e., they belong to different clusters, we have Pr(x collide with y) ≤ .
We will show the proof in the supplementary materials. A consequence of this theorem is to bound the approximation errors introduced in one-step LSH-SMILE simulation. Because of theorem 1, the pairwise distance among elements in one hash bucket is bounded by r with high probability. LSH-SMILE uses the update of one representative element (shown in Equation 4) in replacement of the updates of all the elements in the bucket. Let us assume one step update based on Equation 4 magnifies this difference by M . In other words, for two elements whose distance bounded by r, the value distance of these two elements after one step update from Equation 4 becomes Mr. As a result, if we choose the parameters of the LSH functions according to theorem 1, we know after one call of OneStep(·), the errors will be bounded by Mr with high probability (a union bound argument is needed). In experiment we found the magnitude of M is around 10. We can hence control the error introduced by LSH-SMILE by setting r to be small. We will show the forward simulation result in experiment to support this idea.

heading: 6 Experiments
text: Forward simulation. We first examine the proposed LSH-SMILE algorithm in forward simulation. We apply LSH-SMILE on two physics models for nano-structure evolution in materials. One is to model the grain growth (Fan and Chen [1997]), and the other is to model nanovoids evolution (Millett
et al. [2011]). In each experiment, two forward simulation algorithms are applied. One is the brute force method coded up using the Torch framework (Paszke et al. [2019] under Modified BSD license). The other is our LSH-SMILE simulation. The physics rules of the two applications are implemented in the Eval(·) function in the pseudo code in Figure 4. Grain growth simulation. We evaluated the forward simulation for grain growth system (Fan and Chen [1997]). In this application, the i-th grain is represented using a phase field variable ηi(~p, t). ηi changes over time and evaluates to 1 when ~p inside the i-th grain and 0 outside the grain. The value of ηi on the grain boundary is between 0 and 1. After discretizing the PDEs governing ηi’s dynamics using finite difference, the update rule for each grain is expressed in the following equation. More details can be found in the supplementary materials.
ηi(~p, t+ 1) = ηi(~p, t)− Lidt −Aηi(~p, t) +Bη3i (~p, t) + 2ηi(~p, t) N∑ i6=j η2j (~p, t)− κi∇2ηi(~p, t)  .
Using the finite difference approach, ∇2 is expressed using a convolutional layer with the fixed 3x3 kernel [0 1 0, 1 -4 1, 0 1 0]. We set dt to 0.05 in this simulation. The image size is 128 by 128. For LSH parameter, r and r0 are set to be 0.01, K is 3 and L is 10. The simulation results is in Figure 5, where LSH-SMILE simulates the physics process similarly compared to the ground truth computed by the brute-force approach. To measure the difference, we subtract the simulated result from LSH-SMILE with the ground truth. The difference is at the level of 10−5 after 180 steps.
Nanovoid simulation. We evaluated the forward simulation of nanovoid dynamics in materials under high temperature and irradiation (Millett et al. [2011]). The system is described using three phase field variables, cv(~p, t), ci(~p, t) and η(~p, t). cv(~p, t) represents the fraction of void defects in unit volume of the material located at ~p, while ci(~p, t) represents the fraction of interstitial concentration at ~p. η(~p, t) is the indicator function that evaluates to 1 if ~p is inside a void cluster, and 0 outside. The update function for field variable cv is:
cv(~p, t+ 1) = cv(~p, t) + dtMv∇2 ( h(η) ∂fs(cv, ci)
∂cv + j(η)
∂fv(cv, ci)
∂cv − κv∇2cv
) .
In this equation, cv, ci and η mean cv(~p, t), ci(~p, t) and η(~p, t) when (~p, t) are omitted. The actual definition of fs, fv and the PDE equations for ci and η are left to the supplementary materials. We start the simulation with two different starting state, shown in the first column of Figure 6. We set dt to 0.1 in this simulation. The image size is 128 by 128. For LSH parameter, r is set to be 0.0001, K is 3 and L is 10. The results is in Figure 6. It shows that LSH-SMILE simulate the physics process at comparable quality to the ground truth (difference at the level of 10−5 after 100 steps).
Grain growth learning. We examined the performance of LSH-SMILE in backward learning as well. The dataset is synthetic and contains 1700 frames of grain growth ground truth simulation results. The time and memory savings brought by LSH-SMILE allows the learning algorithm to match the predicted outcomes and the ground-truth outcomes that are T=30 steps away from the starting states, while the baseline method (embedding a brute-force forward approach) can only match the outcomes T=10 steps away, under the same computational budget. LSH-SMILE uses stochastic gradient descent, while the baseline use the Adam optimizer in our experiment. The ground truth parameter to be learned is all Li’s=5.0, A=B=1.0, all κi’s=0.1. After 10 epochs of training, LSH-SMILE learned all Li’s=11.6504, A=1.98483, B=2.01454, all κi’s=0.0834962, close to the ground-truth. At the same time, baseline method learned L=9.0462, A=1.9431, B=8.8226, κ=0.8431, far away from the ground-truth. We also simulated grain growth from the same initial condition using the parameters learned. The simulation is shown in Figure 7, verifying that LSH-SMILE learned parameters lead to similar dynamics as the groundtruth, while the baseline model learned an implausible model.
Running time and memory comparison. We examine the running time of both algorithms in simulation and learning. The forward simulation steps is 1700×10×30 = 510000 for both baseline and LSH-SMILE. For the learning task, both algorithms train for 10 epoch. Our LSH-SMILE embeds forward simulation for T = 30 steps while baseline embeds T = 10 steps. The results is shown in Table 1. Here GG stands for grain growth and NN stands for nanovoid. We can see that our LSH-SMILE method drastically reduces the running time and memory usage in the same setting compared to baseline method implemented in Torch.

heading: 7 Conclusion
text: We propose LSH-SMILE, a unified framework to accelerate the forward simulation and backward learning of physics models, taking advantages of locality sensitive hashing. We show both theoretically and experimentally that LSH-SMILE simulates and learns physics models in a precise fashion and with reduced time and space complexity.

heading: Acknowledgements
text: This research was supported by NSF grants IIS-1850243, CCF-1918327. We thank anonymous reviewers for their comments and suggestions. C. S. acknowledges additional financial support for an internship at SenseTime. Y. X. discloses additional support Award No. W81XWH-18-1-0769 from the office of the assistant secretary of defense for health affairs.

Review summaries:
The paper proposes a method (LSH-SMILE) that applies LSH to speed up PDE forward simulation and backward learning. Observing that most of the elements are very similar, they can be hashed into buckets and each bucket can be represented by a single value, thus reducing computational and memory cost.  The method is validated empirically on two problems, grain growth and nanovoid simulation, showing that it is much faster than standard brute-force computation while maintaining reasonable accuracy.

In learned Partial Differential Equation (PDE) solvers, the forward simulation (thereby data collection) and backward learning processes are very time consuming. This paper tries to mitigate this issue by using Locality Sensitive Hashing (LSH).   The motivation for this approach comes from three critical observations -  1) that most PDE updates in a close vicinity tend to be similar ,i.e., in a one step update, most elements change only on few steps and remain unchanged in the rest of the process. 2) one step updates for a element is dependent on the neighborhood (neighborhood can be thought of a context in NLP). 3) most points share similar temporal dynamics  In learned PDE, the practical simulation happens by discretizing finite-difference approach and obtaining learnable vectors.  Starting from an initial state and hashing to one bucket per element, LSH-Smile iteratively pools elements that have similar hash codes into the same buckets. On each hash bucket, there will be a classic PDE update (same update for all elements in a bucket). Then the hash codes of buckets are updated to  obtain the ones with significant change (>r, a threshold). Then the elements in those buckets are rehashed.  The backward process is similar with an additional gradient computation step that I presume is also done a bucket basis.  I’m not entirely sure abt the input structure and the hash function used (I may have missed some details).  But essentially, LSH-SMILE does the standard updates process on a chunk by chunk basis instead of on all elements.     

This paper proposes a novel LSH based approach for efficient forward and backward pass of Partial Differential Equations (PDEs). The proposed LSH-SMILE approach focus on local updates and use LSH to find the local neighbors. Moreover, LSH-SMILE propose a bucket merging method to avoid empty buckets.

The paper applies locality sensitive hashing to neural networks for solving Partial Differential Equations (PDEs). The paper proposes a solution called LSH-SMILE and claims several contributions: (1) LSH-SMILE achieves a drastic improvement in scalability than conventional approaches. (2) Theoretically, the paper proves a novel bound on the errors introduced by LSH-SMILE (3) Experimentally, the paper demonstrates LSH-SMILE exhibits comparable quality with exact approaches but costs less time and space.