LSH-SMILE: Locality Sensitive Hashing Accelerated Simulation and Learning
Authors: Chonghao Sima
Yexiang Xue
Venue: NeurIPS 2021 Poster (2021)
Keywords: Partial Differential Equation
Locality Sensitive Hashing
Learning-driven Scientific Discovery
Learning Physics Systems
Acceleration

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 require handling billions of 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 advantage 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.

LSH-SMILE: Locality Sensitive Hashing Accelerated Simulation and Learning
Chonghao Sima Department of Computer Science Purdue University West Lafayette, IN, USA, 47907 s simacQpurdue. edu
Yexiang Xue Department of Computer Science
Purdue University West Lafayette, IN, USA, 47907 yexiangOpurdue edu
Abstract
The advancement of deep neural networks the last decade has enabled progress in scientific knowledge discovery the form of learning Partial Differential Equa- tions (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), unified framework to scale up both forward simulation and backward learning of physics systems. LSH-SMIL 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 single hash bucket and handles their updates at once. This allows LSS-SMIL.F to scale with respect the number of non-empty hash buckets, 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 's ability to propagate gradients over a long duration.
Introduction
Learning-drive -oiming-drrven scientific discovery has enjoyed rapid progress thanks to the advancement of deep neural networks the last decade. Since Partial Differential Equations (PDEs) are widely used to model physics systems, fruitful line of research has been developed focusing on learning PDEs from
experimental data, including Finzi al. 20200 Greydanus al. 2219)] Matsubara et al. (2020)
Nevertheless, successful applications 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 PDE system from a given starting state. Recent work of Greydanus et al. (019) demonstrates such process can be represented using 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 NNu al. (2020) and Xue al. (2021). Backward learning can be achieved by embedding 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 (NcurIPS 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-SMILLF), unified framework to scale up both forward simula- tion 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 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 (L.SH) to boost the computational throughput. By representing each element as 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-SMILL 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 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, LIIL 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 (197]) and model the spatial temporal dynamics of void shaped defects, namely nanovoids, in materials under high temperature and irradiation (Millett et al.. (201I)) 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 MEE-SSLLE--aase learning approach can successfully identify the correct
grain growth process, brute-force baseline approaches cannot, The success is due to a longer model parameters while forward simulation (30 time steps) embedded in the backward learning process enabled by the computational savings of LSILSM 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-SMIL opens the door for faster and better scientific discoveries.
2 Preliminaries
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 alβ t) (w1 t)..... Umm (p,, t))², where (Z1....,2) xz)) denotes the spatial coordinates and t denotes time, such PDEs are in the form:
Dū(ptt) t) Øt
D(T) G(T)V + ((T)
Here, F and H are functions that map R. to R. V (azn a yt represents the gradient operator, V = V. V is the Laplace operator. D is a function that maps Rm to Rm. G(t) is an m-by-d matrix and [(ū) is m-by-1 vector.
Many notable physics systems can be represented using PDEs in Equation | The widely used Allen- Cahn and
Equations in phase field modeling are good examples. The Sahn-Hilliard

---

[0, 0.3, 0.7] [0, 0
[0. [0, 0,
[0, 0, 1] [0, 1,
Forward [0, 0, 1] Simulation
Forward [0, 0, 1] Simulation
[0, 0, 1]
[0.8, 0.2, 0]
[0.92, 0.08, o]
[1. 0,
[0.46, O, 0.54 [1, 0,
[1, 0, 0] 0,
[1, O. 0 [1, 0, 0]
Figure 1: toy example showing the forward simulation of grain growth. Here, the state ल(Ø, t) is represented using a triple (u, t), (2, !), Ug (p, ()). 7 vary over location p and time according to specific form of Equation u1 (ug, Ug) if inside the first (second, third) grain and 0 outside. Values between 0 and for u(1, U2 can be found at the boundary.
equation and Allen-Cahn equation are used to describes the physics thysics 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:
du
(MV OF N du
δ1 = V.
(2)
The Allen-Cahn equation has the general form:
du
5F
L
(3)
Ōt
8v
Here and 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, are physics parameters that are related to the changing process. F is the energy function which 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. [2200] Dong and Simos [017)] Forsythe and Wasows 19633
and Shooaei et al. [2019]. More specifically, let [-i,1, 24.2, R..R be a finite discretization domain of Iyz where each T is called discretization point. (4,
(2,,2.... ......,.ss } is the discretization of the time. Let 7 (i1, i2,,..................... ia). We use T({,j) a shorthand for iī evaluated position T= (x1,i)...., x= Fdd..)) and time (,, i.e., d((,j) ((...)............. Tdiia 4)). Fach discretized position i is also called an element. The left-hand side of Equation can be discretized using the finite difference: (r((7,)) a(G.+11) Similarly, notice VF(TT) =( 1
ar dez yT. where
dt
dz:
(F( 2
(F Bus Bue
We need dug(E,)) compute V and (.g can be approximated Ozg
Oe,
di.." -z (2,) Here, 7+ 1, means to move the I-th coordinate of namely it, to the next
0z:
by 21 -2.4
discretization point 4- Repeating this type of calculations for the second-order derivatives V (17).
the PDE in Equation 1 can be approximated in the following general form:
प(. - 1) ((..j) + 8,Q(1 .7, 7 (())..
(4)
Here, we intentionally use function Q 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 in which 7 is neighboring element of 7. We use (() to represent the set of neighbors of ū. In the two applications consider in this paper, (i) is actually small and only consists the first and second order neighbors. Two elements are first or second order neighbors if and only if they differ in dimension within two discretization points, they differ in two dimensions, each dimension within one discretization point.
notice: Q depends a small set of (T( j)''s "(("))""
Forward simulation. By discretizing PDEs with finite difference approach (Equation we can simulate future states of physies system from an initial state by updating the left-hand side with values from the right-hand side of Equation repeatedly. Interestingly, such process can be

---

t=0s
t=2.55
t=5s
t=7.5s t=10s t=12.5s
Phase
Field
Picture
Difference
between
two frames
HashBuck-
ets distribution
Figure 2: Intuitions that motivates LSH-SMILF.. The updates of grain growth (difference between two consecutive frames, shown in the second row) only happens at the grain boundaries (show in red dots). Also, notice from the first and the second rows, elements with similar values of themselves and their neighbors share the same temporal dynamics. Hence the third row, they can be hashed into the same hash bucket using LSH. The colors represent the hash buckets of the elements.
implemented as multi-laye layer convolutional neural network (see, e.g.. Xue et al. [002]). See Figure T for a demonstration of the forward simulation process. Here we use the grain growth as an example.
.ug...ue
Backward Learning. Backward learning allows to learn the parameters of the PDE that governs developed with a series of work, e.g. Ween et al. [202]] Dupont et al. [209)) Xue et al. [2021] and Rubanova al. [2019). During backward learning, physics rules are ex expressed in the form of Equation
dynamics of a physies system from experiment data.
4 initialized with random parameters. The dataset consists of the observed pairs of states: ū(p, t) and ūp t T),, where ((p, t) is the state physics system at time t and u(p t + +") I the state at time + T.. Here T is constant set manually. Starting with u((,,) t), repeated evaluation of Equation 4f Tf times will yield the simulated state u' (p. T). .. A loss function is defined penalize the difference between the simulated state x (f, function. Back-propagation (Rumelhart et al. [1986). Robbins and Monro [195]] is then applied to minimize the difference. Upon convergence, correct physics parameters are learned which yield the same temporal dynamics the observed data.
7') and observed state ū(p, + +T). our experiment, we use the L2 loss
Locality Sensitive Hashing (LSH), For a domain S with distance measure D. a LSH family is:
Definition 1. H (h S U} is called (ri, 12, P. g)-sensitive LSH function family for D if for any two points x. y E S, one function chosen uniformly at random from H satisfies:
if D(x. < rı. then Phex (hex(((z)=h(p)
IV IAM 4.
P.
(f. 2 r2, then Then[h(z)=h(g))
In this paper, Fuclidean distance is used the distance measure D.. In this case, function in the LSH hash function family has the following form hv,((v) a-v+bb where is a a d-dimensional vector with entries chosen independently at random from standard Gaussian distribution and is real number chosen uniformly from the range r0. is hyper- hyper-parameter denoting the size of the hash bucket. We refer the reader to Datar et al. (0044 for the selection of and the resulting performance (i.e., the values of ri, F2, P. ②)
3 Intuition
The intuitions behind the development of LSH-SMILE is inspired by the following three observations. Notice that these observations apply to wide range physics systems beyond the applications considered in this paper. Hence, we believe our method can be applied in a broad context.

---

Base
Cu
100nm
nanovoid this Update of pixel only depends Copperlayer
on its neighbor pixels(blue)
Figure 3: The spatial local dependency of the updates also motivates LSH-SMMLL The left picture (from Bremmert et al. [2019] shows nanovoid, enlarged in the middle. The update of one element of the nanovoid (shown in the red box) only depends on the values of itself and its neighboring elements (shown in the blue boxes in the right). This local dependency implies elements with similar values of themselves and their neighbors will share similar dynamics.
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 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 wasteful to spread computation resources over the entire area. An algorithm focused on area of real updates can potentially save a 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 direct consequence of applying the finite difference method on PDEs. See, e.g., applying finite difference on Equation results in Equation 4 in which the updates depend on small set of elements in ((). As a consequence, this observation applies to a wide range 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 blue boxes).
Elements share similar dynamics. Our third observation is that many elements share similar temporal dynamics. Notice that this is 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.
4 The LSH-SMILE Algorithm
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 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 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 cxample, the third row of Figure colors clements 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-SMIL- algorithm for forward simulation, then will discuss LSH-SMILE for backward learning. The pseudo code of
for forward simulation is in Figure 4
Notation. We first introduce the notation used in LSH-SMILE in Figure time 7 the initial state. r, K, I, are L.SH parameters. To a threshold. simulation steps.
B, is the hash table
N is the number of
5

---

1
Fune Forward N, r, K, L):
Func MergeBuckets((, K, L):
2
Bo <
I,K,K,, L); B, t- OneStep((BB-as 1, K, L.);
B' 9
3
for I,.... do
for B E B do
for I E [l...., L. do
5 end
if there exists B' E B', such that B.LSH,
return BN;
L.S then
7 end
B' + B' {B'}; B+ + Merge(B,
8
Fune (rreStep(B..11 K, L):
9
ActiveL t- 0;
end
10
for Bi, E B, do
end
11
Bi,i-Vold &- Br,;.U;
10
B' + B' (B]:
12
BL. f-
11
end
Eval(Br,isn) N eighhor (i, B:));
for B B' do for E [1....,,]] L do B.LSH, +- LSHI(B.v, Neighbor BBrg (Brrep,
14
Update LS LSHH if [B, Botd- > then ActiveL t ActiveL B end end
13
15
16
15
end end
18
Be+1 + B₁; 19
17
return B':
for E ActiveL do
18
end
21
Remove a from the original bucket that contains in B,+1;
19
F Func EncodelnitState(] K, L):
20
B. = 0:
22
Ba+ +
for E I do
Brcktt Bi+1 + BB+1 (Ba):
K, L)L);
22
Ba +-
23
L);
24
end
23
Bo - Bo {Ba};
BI+1 +- MurgeeBuuketss(ppoo
24
end
26
return B.41;
return
end
26 end
Figure 4: The forward simulation algorithm of N steps using locality sensitive hashing. The main function is Forward, which calls children functions OneStep, MergeBuckets, and EncodeInitState.
Data structure. B, is the hash table at time each entry of which is hash bucket. In one hash bucket B E B,, there representative value B a representative element rep, list of its elements' coordinates P and list of neighbor elements' coordinates Br,;.N. Here we use mion-ffnnddeeete data structure (Ben-ammet -een-amram and Yoffe (201T) to organize B,,.P. which ensures that we can perform the union of the elements of two hash buckets and deleting one element from a hash bucket nearly constant time. The idea of building such a hash bucket that, using LSH, every element T[[; j) that shares almost the same values for itself and for its neighbors (() shall be hashed into the same bucket with high probability. We intentionally give all elements in one bucket single value, namely U, We use P. P to track all the elements in the bucket and B to track all the elements that neighbor elements in B,, but are not in Bt. P. According Equation 4 the elements in one hash bucket have similar updates. Hence, we can update the value B for all elements in this bucket following Equation 4 in 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 itcrates all elements in the input data and construct a hash table where each hash bucket only contain element. Then 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 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 E The update carried out using function Eval(.). After the update, updates its LSH hash code and sees if the update is bigger than threshold If so, all elements in the bucket needs to be re-hashed. We do so by updating their I.SH code. Notice this an operation that 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 B,, We put these elements into ActiveL for later processing. After iterating all hash buckets, LSH--MILE 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 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 To is set small, its own value change will trigger the exceeding of rn 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 MergeBucker operation, since buckets with colliding LSH codes are merged.
AND of OR LSH. We introduce multi-probe LSH techniques from Lv al. [007]] 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 hig constructed in the form [v. = a. where asd
and bt. are sampled in the way described in Section 2 Construct g: (p) (p), ................................ h (p)]. select L different functions 91..... -t. For one element p. hash p into all L buckets, denoted by 91.....9h IL- p and q "collides" they collide under any of the : 9 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.
The ActiveL L 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 namely, replacing u(i j) with vt,,, j + 1), when used in back-propagation.
5 Analysis
Algorithm running time analysis. Let n be the size of input 7, b be the largest number of buckets in any B,,g g be the size of largest neighbor list for one bucket during simulation. The merging of two buckets Merge(B, BB B') has to merge the element list B.P and B as well as updating the neighbor's list. Merging element list is conducted using the finn-findddelete data structure and is handled in near constant time. The bottleneck is to update the neighbor list, which scales Ogg log g) using sorted list merge. For MurgeBuckets, at most bl. Merge operations can happen and hence the complexity is ObbKT, + bL.g log g). In function E nillState()) line 21 to 24 iterates every element in I, line 25 calls M Merge In function OneStep()), line 10 to 18 iterates on B, the time complexity is O(bK L). Line 20 to 24 iterates on ActiveL, which has size smaller than bg. Line 25 calls MurgeBuckets. Hence the time complexity of OneStep is O(bKL + bLg log g). In function Forward(-), :). line 2 calls Encode IncoodIInit.taie Stittt ), line 3 to 5 calls Sneppte(-)) for N steps. The time complexity of Forward(.) is OLbNKL- + bN Lg log g n).. In comparison, a brute-force method has time complexity O(nN). Our LSH-SMILE will be faster than the frute-force method when bKL + bLg logg << n.
thus this function have time complexity O(n + bKL + bLg log g).
Error bound introduced by LSH-SMILE.. When quantifying the approximation quality of LSH- SMILE, we assume all the elements during simulation are naturally clustered. Naturally clustered means that there exists > 1 and r > 0, for any two elements and y. either they belong to the same
7

---

t=Cs
t=4.55
t=95
t=13.5s
t=18s
t=22.5s
t=27s
LSH-SMILE Simulation Init cond 1
Ground truth
Simulation Init cond 1
LSH-SMILE Simulation cond
Ground truth Simulation Init cond 2
Figure 5: LSH-SMILE simulation results (the first and the third rows) closely match the ground truth (the second and the fourth rows). First two rows are initialized with condition 1. Last two rows are initialized with condition
cluster and hence their distance || - yl1 S r, or they belong to different clusters and || yll 2 er. Here and 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 different grains or the boundaries are different (hence having large pairwise distances). Under the natural clustering assumption, we can build LSH function which guarantees with high probabilities that elements inside each cluster are hashed to the same bucket while elements of different clusters hashed to different buckets, reflected in the following theorem:
Theorem 1. For 0 < c 0.5, let C = log, (1 c), then 0 < C < 1. Suppose each hi is sampled sensitive LSH function family. Pick K = max(1, [logp/g C1}, L = (1-p(
from a (r, Build L LSH functions in the way described in "AND of OR LSH", we have
For all elements v, y.y satisfying || yll S r, i.e., they belong the same cluster, we have
Pr(æ collide with y) 2 -
For all elements x, y satisfying || - vll 2 or, i.e., they belong to different clusters, we have
Pr(x collide with y) <
We will show the proof the supplementary materials. A consequence of this theorem is to bound the approximation errors introduced in one-step LSH-SMILE simulation. Because of theorem [ 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 in replacement of the updates of all the elements in the bucket. Let us assume one step update based on Equation magnifies this difference by M. In other words, for two elements whose distance bounded by the value distance these two elements after one step update from Equation 4 becomes Mr. As result, if we choose the parameters of the LSH functions according theorem [ know after call of OneStep(.). the errors will be bounded by Mr with high probability (a union bound argument is needed). In experiment introduced by LSH-SMILE by setting to be small. We will show the forward simulation result in experiment to support this idea.
found the magnitude of M is around 10. We can hence control the error
Experiments
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 model the grain growth (Fan and Chen (197]) and the other is to model nanovoids evolution MMillett
in materials. One is to

---

t=Os
t=2s
t=4s
t=6s
t=8s
t=10s
t=12s
LSH-SMILE Simulation Inil cond
Ground truth Simulation Init cond
LSH-SMILE Simulation Init cond 2
Ground truth Simulation Init cond
Figure 6: LSH-SMILE simulation results of nanovoids closely match the ground truth. The first two rows are initialized with condition The last two rows are initialized with condition
2=
t=4s
t=6s
t=8s
t=10s
t=12s
t=14s
Ground truth Simulation Init cond 1
LSH-SMILE learned Simulation Init cond 1
Baseline learned Simulation cond 1
FUVYYRY
Figure 7: LSH-SMILE is able learn the dynamics of grain growth, while the brute-force baseline cannot. The first row is the ground truth data. The second row shows the simulated dynamics of the physics model learned by LSH-SMILE, which matches the ground-truth well. The third row brute-force approach to learn, resulting in physics model with incorrect dynamics.
al. (011]) In each experiment, two forward simulation algorithms applied. One is the brute force method coded up using the Torch framework (Paszke et al. [2019) under Modified BSD license). The other LSH-SMILE simulation. The physies 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]). this application, the i-th grain is represented using a phase field variable (p, t). M changes over time and evaluates to when p inside the i-th grain and 0 outside the grain. The value of π) on the grain boundary is between 0 and 1. After discretizing the PDEs governing 7 dynamics using finite difference, the update rule for each grain is expressed in the following equation. More details can found in the supplementary materials.
N
Th ( = (7. L,dt
AAn((p,t) + BT²((,)) + (F, Σ ((( - (3 (2.
(

---

Algorithms
Runtime (hr)
Memory Usage(mb)
GG-Sim LSH-SMILE
3,86
870
GG-Sim Baseline
16.84
1135
NN-Sim LSH-SMILE
2.13
2735
NN-Sim Baseline
53.13
3294
GG-Sim Learn LSH-SMILE
4.5
889
GG-Sim Learn Baseline
17.29
1212
Table 1: Running times of different approaches. LSH-SMILE needs less time and space compared to baseline methods.
Using the finite difference approach, V2 is expressed using a convolutional layer with the fixed 3x3 kernel [0 1 0, 1 -4 1, 0 1 0j. We set dl to 0.05 in this simulation. The image size is 128 by 128. For LSH parameter, r and ro are set to be 0.01, K is 3 and 10. The simulation results is in Figure 3 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). D. The system is described using three phase () represents the fraction of void defects in unit volume of the material located at 1. while c2(p, 1) represents the fraction of interstitial concentration p. n)(7,, 1) is the indicator function that evaluates to 1 if pì is inside void cluster, and O outside. The update function for field variable Cp is:
field variables, c. t). c 1) and n(p², l). On (1,
c. (,, (o, d2M (((1) (f + +j(1) (f. K. V.c.)
Oc,,
Oc.
In this equation, Cu. and 1 mean co f), cs(F t) and n(57, t) when (₁, are omitted. The actual definition of f and the PDE equations for e, and 17 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 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-SMMLL 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 L, 555.0, A=B=1.0, all Ky 1. After 10 epochs of training. LSH-SMILE learned all L, 1 1.6504, A=1.98483, B=2.01454 454, all K& 5=449939,,,, close to the ground-truth. At the same time, baseline method Iearned L=9.046,, 1.11.44111 B= B=8.8226, x=0.8431, 1, 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 Iearned parameters lcad to similar dynamics as the groundtruth, while the baseline model Iearned 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 1700x 10x30 = 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 [ Here GG stands for grain growth and N N 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.
7 Conclusion
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 theoreti- cally and experimentally that LSH-SMIL_F simulates and learns physics models in precise fashion and with reduced time and space complexity.
10

---

Acknowledgements
This research was supported by NSF grants IIS- 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-0766 from the office of the assistant secretary of defense for health affairs.
References
Amir Ben-amram and Simon Yoffe. A simple and efficient ciiion-indddelete algorithm. Theoretical Computer Science, 412(():487-45) 492, 2011. ISSN 0304-3975. doi: https//doi..rr//10 101.0.1116610 1016///..tsss.. 2010.11.000
Stefanie Bremmert, Laurence Gregoriades, Kay Wurdinger, Thomas Vágó, Tobias Bernhard, Frank Bruning, and Roger Massey, Developments in electroless copper processes to improve performance in amsap mobile applications. 2019.
Mayur Datar, Nicole Immorlica, Piotr Indyk, and Vahab S. Mirrokni. Locality-sensitiig hashing scheme based on p-stable distributions. In Proceedings of the Twentieth Anmual Symposium on
Computational Geometry, SCG '04, page 253-262, New York, NY. USA. 2004. Association
for Computing Machinery. ISBN 138857. doi: 10.1145/997817.997777
URL https
//doi. org
997857
Ming Dong and Theodore E. Simos. A new high algebraic order efficient finite difference method for the solution of the schrödinger equation. Filomat, 31:4999-5011 2017.
Emilien Dupont, Arnaud Doucet, and Yee Whye Teh. Augmented neural odes. H. Wallach, H. Larochelle. A. Beygelzimer, F. d'Alché-Bon Bucc E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
Danan Fan and Longqing Chen. Computer simulation of grain growth using a continuum field model. Acta Materialia, 45:611 1-622, 1997.
Mare Finzi, Ke Alexander Wang, and Andrew Gordon Wilson. Simplifying hamiltonian and la- grangian neural networks via explicit constraints. Advances in Neural Information Processing Systems, 33, 2020.
George F. Forsythe and Wolfgang R. Wasows. Finite-difference methods for partial differential equa- tions. Canadian Mathematical Bulletin, 6(1):177-33, 1963. doi: 10. 11011775000008-5500026600000
Samuel Greydanus, Misko Dzamba, and Jason Yosinski. Hamiltonian neural networks. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and Garnett, editors, Advances in Neural Information Processing Systems, volume 32, Curran Associates, Inc., 2019.
Qin Lv, William Josephson, Zhe Wang, Moses Charikar, and Kai Li. Multi Ish: Efficient indexing for high-dimensional similarity search. Proceedings of the 33rd International Con- ference on Very Large Data Bases, VLDB '07, page 950-961, VLDB Endowment, 2007. ISBN 9781595936493.
Takashi Matsubara, Ai Ishikawa, and Takaharu Yaguchi. Deep energy-based modeling of discrete- time physics. In Advances in Neural Information Processing Systems 33, 2020.
Paul C Millett, Anter El-Azab, Srujan Rokkam, Michael Tonks, and Dieter Wolf. Phase-field simulation of irradiated metals: Part i: Void kinetics. Computational Materials Science, 50(3): 949-959, 201
T. Niu, M. Nasim, R. Annadanam, C. Fan, Jin Li, Zhongxia Shang, Y. Xue, Anter El-Azab, H. Wang, and Zhang. Resent studies on void shrinkage metallic materials subjected in situ heavy ion irradiations. JOM, 72, 09 2020. doi: 11110077111837--00-0455555

---

Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang. Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high-performance deep learning library. In H. Wallach, H. Larochelle, A. Beygelziee, F. d'Alché-Bue E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems 32, pages 8024-8035.
Curran Associates, Inc., 2019.
Herbert Robbins and Sutton Monro. A Stochastic Approximation Method. The Annals of Mathemati- cal Statistics, 22(3):400 - 407, 1951. doi: 10.121 10. 1/114///mm//111/// 177729586.
Rokhlin. Rapid solution of integral equations of classical potential theory. Journal of Computational 1ttp///ooorrr/1.1000000001--1110
Physics, 60(2):1872277, 1985. ISSN 0021-9991. 90002-6.
doi:
Yulia Rubanova, Ricky T. Q. Chen, and David K Duvenaud. Latent ordinary differential equations for iregularly-sampled time series. Wallach, H. Larochelle, A. Beygelzimer, F. d' d'Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32.
Curran Associates, Inc., 2019.
David E. Rumelhart, Geoffrey E. Hinton, and Ronald J. Williams. Learning Representations by Back-proggg Errors. Nature, 323(6088):533-555 536, 1986. doi: 10.1038/323533a0.
Arman Shojaei, Ugo Galvanetto, Timon Rabezuk, Ali Jenabi, and Mirco Zaccariotto. A generalized finite difference method based on the peridynamic differential operator for the solution of problems in bounded and unbounded domains. Computer Methods in Applied Mechanics and Engineering, 146, 2019. ISSN 0045-7825. doi:
Yuanyuan Wang, Yan Gu, and Jianlin Liu. A domain-deccomposition generalized finite difference method for stress analysis in three- dime-dimmnsional composite materials. Applied Mathematics Letters, 104: 104:106226, 2020. ISSN 1893-9659, doi: https://bb.org/11.1106jj...
106226.
Gege Wen, Zongyi Li, Kamyar Azizzadenesheli, Anima Anandkumar, and Sally M. Benson. U-fno an enhanced fourier neural operator based-deep learning model for multiphase flow, 2021.
Yexiang Xue, Md Nasim, Maosen Zhang, Cuncai Fan, Xinghang Zhang, and Anter El-Azab. Physics knowledge discovery via neural differential equation embedding. In Yuxiao Dong, Nicolas Kourtellis, Barbara Hammer, and Jose A. Lozano, editors, Machine Learning and Knowledge Discovery in Databases. Applied Data Science Track, pages 1 Cham, 2021. Springer International Publishing, ISBN 978-3-030-86517-7
12

---

Checklist
The checklist follows the references. Please read the checklist guidelines carefully for information on how to answer these questions. For each question, change the default [TODO] to [Yes], [No], , or [N/A]. You are strongly encouraged include justification your answer, either by referencing the appropriate section of your paper or providing a brief inline description. For example:
Did you include the license to the code and datasets? [Yes] See Section XXX.
Did you include the license the code and datasets? [No] The code and the data are proprictary.
Did you include the license to the code and datasets? [N/A]
Please do not modify the questions and only the provided macros for your answers. Note that the Checklist section does not count towards the page limit. In your paper, please delete this instructions block and only keep the Checklist section heading above along with the questions/answers below.
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes] see section and
(b) Did you describe the limitations of your work? [Yes] see section S
(c) Did you discuss any potential negative societal impacts of your work? [No]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] see section 5
(b) Did you include complete proof's of all theoretical results? [No] they will be uploaded in supplementary material
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as a URL)? [Yes] they will be provided in the supplementary material
(b) Did you specify all the training details (e.g.. data splits, hyperparameters, how they were chosen)? [Yes] they will be provided in the supplementary material
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [Yes] they will be provided in the supplementary material
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [Yes]
4. If you using cxisting assets (e.g., code, data, models) or curating/releasing assets...
(a) If your work uses existing assets, did you cite the creators? [Yes] We use Torch as our baselien implementation
(b) Did you mention the license of the assets? [Yes]
(c) Did you include any new assets either in the supplemental material or as a URL? [No]
(d) Did you discuss whether and how consent was obtained from people whose data you're 're using/curating? [N/A] We use our own synthetic data
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [No]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "kJ9fx-56Qek", "reviewer": "Reviewer_gTTS", "summary": "The paper proposes a method (LSH-SMILE) that applies LSH to speed up PDE forward simulation and backward learning.\nObserving 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. \nThe 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.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n- The paper is well-written and easy to understand. Section 3 provides valuable intuition, and I enjoyed reading it.\n- The method works for both forward simulation and backward learning, by leveraging the nature of differential equations (instead of relying on auto-differentiation, which can be memory-costly).\n- The method can significantly speed up the PDE simulation and learning.\n\nWeaknesses:\n1. Limitation of application: it's not clear to me how widely the proposed method can be apply, as there's no discussion of its limitations. It seems to work for two narrow physics problem. However, I'm not sure which conditions will allow it to work well. This is the most significant weakness.\n2. It seems that the algorithm is hard to parallelize, compared to the brute-force simulation. Thus the brute-force computation may able to better use GPUs to speed it, while LSH-SMILE would be bound to CPUs?\n\nQuestions:\n1. The observation that close-by elements are very similar, is quite reminiscent of fast multi-pole method. I wonder if there's a connection here.\n2. In Figure 3, Func OneStep, line 15, the ActiveL set is updated when the change is larger than r. However, what if the change per iteration is smaller than r but over time it can add up to be larger than r. Would the ActiveL set be updated then?\n\n============== Post-rebuttal\n\nThank you for the response to my questions. That has helped me understand the method better. \n\nThe clarification on the setting where the method is expected to work is valuable. Given that the goal of the paper is to accelerated simulation and learning on physical systems in general, I think the case could be made much stronger if the applications are more diverse.\n\nI've increased my rating.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "J8xcxHFKc2q", "reviewer": "Reviewer_nWzM", "summary": "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). \n\nThe motivation for this approach comes from three critical observations - \n1) 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.\n2) one step updates for a element is dependent on the neighborhood (neighborhood can be thought of a context in NLP).\n3) most points share similar temporal dynamics\n\nIn learned PDE, the practical simulation happens by discretizing finite-difference approach and obtaining learnable vectors.\n\nStarting 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.\n\nThe backward process is similar with an additional gradient computation step that I presume is also done a bucket basis.\n\nI’m not entirely sure abt the input structure and the hash function used (I may have missed some details).\n\nBut essentially, LSH-SMILE does the standard updates process on a chunk by chunk basis instead of on all elements.\n\n\n\n\n", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths\n\n1. Neat idea\n2. Impressive gains in time and memory with negligible difference with ground truth simulations.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations:\n\n1. LSH theory is a direct import from prior literature (understandable though). The primary novelty is integrating it with the PDE solver's forward and backward passes. \n\n2. There maybe PDE applications where the three critical observations might not hold.\n\n3. Noticeable typos like\n\nline 183 : perform update ---> perform an update\nline 189 : every elements --> every element \nline 257 : by we directly coding --> because we directly coded\nline 258 : rules is --> rules are", "review_text": "", "extra_scores": {"ethical_concerns": "No evident ethical concerns", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "IOm2E3DBkXA", "reviewer": "Reviewer_z9La", "summary": "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.  ", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is novel that applies Locality Sensitive Hashing (LSH) to physics systems for faster runtime. As a tradeoff, LSH introduces errors to the physic systems since LSH is an approximate approach. But the paper demonstrates that the errors are acceptable since the simulation quality of the physics system can match the quality of using conventional exact match approach, as shown in Figure 4 and Figure 5. Runtime-wise, the proposed method LSH-SMILE can outperform conventional approach by more than 10 times, as shown in Table 1.  \n\nAlthough the paper has merits in integrating computer science approaches with physics systems, it contains a lot of undefined physical terms that affect the understanding of the paper for general computer science audiences (like myself). The undefined physical terms impact reproducibility of the experiments as well. In particular, I suggest the authors improve the draft as follows:\n\n(1)\tProvide definitions for technical terms before using them, in plain language that general audiences can understand. For example, “forward simulation” and “backward learning” are introduced early in the Abstract, but they are not standard terms in computer science. Although computer science researchers often use “forward propagation” and “backward propagation” in neural networks, it is not sure whether the authors refer to the same things. There are a lot of undefined technical terms in the paper, such as “Partial Differential Equations”, “elements”, and “temporal dynamics” in the Abstract. \n\n(2)\tProvide toy examples for long definitions. The paper gives a definition for Partial Differential Equation (PDE) in Section 2 Preliminaries. The definition is as long as half a page, but the paper does not give any toy examples. It is unclear what a PDE looks like. \n\n(3)\tSpecify the inputs and outputs of the LSH algorithm. The input format of an LSH algorithm should be a query vector and a set of item vectors. The output format should be the most similar item vectors to the query vector. When applying LSH to physics systems, it is natural that one has to formulate physics systems into query vector and item vectors. However, the paper does not illustrate how the formulation looks like. It will be good if the authors can add the details to the paper for better clarity.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "There is no sign of negative impact. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "ECntxxRrep5", "reviewer": "Reviewer_z4Ec", "summary": "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.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strength:\n1. Novel formulation that transforms PDEs into the nearest neighbor problem\n2. Efficient combination of LSH and PDEs.\n3. Error bounds for the errors", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Suggestions:\n\nLSH is a great approach for scaling up large scale machine learning models. Is is possible to demonstrate more experiments on larger scale? ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "12"}, "extra_text": {}}]

Author rebuttal:

Meta-review: All the reviewers concurred that this paper is above bar for publication. Rebuttal reaffirmed that sentiment. Reviewers like the idea of using LSH for speeding up simulations.  In particular,  applying LSH algorithm to a completely new domain, i.e. physic systems. The results look promising and since the paper belongs to interdisciplinary research, reviewers agree that even though the paper is less advanced in algorithmic techniques, it will be a educative read for a broader community of people. 

Please take in account comments from the reviewers to improve the paper.   
Decision: Accept (Poster)