NCDL:  A Framework for Deep Learning on non-Cartesian Lattices
Authors: Joshua John Horacsek
Usman Alim
Venue: NeurIPS 2023 poster (2023)
Keywords: Computer Vision and Pattern Recognition
TL;DR: We created a data-structure for data on alternative grid structures (check our HexagDLy as a base example). We explored this in the context of convolutional networks, and found some cases where quincux convolutions can help algorithm performance.

Abstract: The use of non-Cartesian grids is a niche but important topic in sub-fields of the numerical sciences such as simulation and scientific visualization. However, non-Cartesian approaches are virtually unexplored in machine learning. This is likely due to the difficulties in the representation of data on non-Cartesian domains and the lack of support for standard machine learning operations on non-Cartesian data. This paper proposes a new data structure called the lattice tensor which generalizes traditional tensor spatio-temporal operations to lattice tensors, enabling the use of standard machine learning algorithms on non-Cartesian data. However, data need not reside on a non-Cartesian structure, we use non-Dyadic downsampling schemes to bring Cartesian data into a non-Cartesian space for further processing.   We introduce a software library that implements the lattice tensor container (with some common machine learning operations), and   demonstrate its effectiveness. Our method provides a general framework for machine learning on non-Cartesian domains, addressing the challenges mentioned above and filling a gap in the current literature.

NCDL: A Framework for Deep Learning on non-Cartesian Lattices
Joshua Horaesek
Usman R. Alim Department of Computer Science
Department of Computer Science
University of Calgary
University of Calgary Calgary, Alberta ualimoucalgary.c ca.
Calgary, Alberta
j. hwwacsekkncdl..c.
Abstract
The use of hon-Cartesian grids is a niche but important topic in sub-fields of the numerical sciences, such as simulation and scientific visualization. However, non- Cartesian approaches are virtually unexplored in machine learning. This is likely due to the difficulties the representation of data on non-Cartesian domains and the lack of support for standard machine learning operations
non-Cartesian data. This paper proposes new data structure called the lattice tensor which generalizes traditional tensor spatio-temporal operations to lattice tensors, enabling the use standard machine learning algorithms on Cartesian data. We introduce software library that implements this new data structure and demonstrate its effectiveness on various problems. Our method provides general framework for machine learning non- Con-Cartesian domains, addressing the challenges mentioned above and filling a gap in the current literature.
Introduction
Machine learning heavily relies tensors represent muuti-diimensionll data. However, tensors inherently Cartesian, and representing data solely on Cartesian grids can be restrictive. Certain data may be more naturally suited to alternative grid structures. For example, raw image data from most imaging sensors is not Cartesian; a Bayer filter represents blue and red data with Cartesian structure, but green data has quincunx (checkerboard) structure. There is also abundant literature showing that hexagonal grids are superior to Cartesian grids when representing isotropically land-limited natural Representing data in these domains using traditional Cartesian tensors can be inefficient and lead to inaccuracies depending on the distribution the data belongs to. For the distribution of natural images, which have relatively isotropic behaviour in the Fourier domain, it is well known that using alternative grids yields better image representations (38).
images [ 34 32 38
Another reason use exotic grids is that alternative structures can have significantly different approximation capabilities. Again, turning to the hexagonal lattice as an example, which well known the optimal sampling lattice in 2D [4), if one samples 2D signal with number of samples, a hexagonal sampling reduces the memory consumption by approximately 14% (32]. This follows signal periodizes that function
from a simple argument in the Fourier domain; sampling in the Fourier domain. If one's sampling pattern is hexagonal (the optimal circle packing pattern) then less information is lost when the signal is hexagonally periodized. This effect compounds as dimensionality increases; for example the body-centered-ccubie (BCC) lattice is 30% more efficient than the Cartesian lattice (for isotropically band mimited functions [
However, though these grid structures show promise in other areas numerical sciences, they are relatively unexplored in the context of machine learning. There is no user-friendly, general, and
'The face-centere--cubic (FCC) lattice is also attractive, it minimizes aliasing.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

(a)
(b)
(c)
Figure 1: Three lattices used as examples throughout this paper; a) is the Cartesian lattice, b) the quincunx lattice and c) is the hexagonal lattice. The cells of each lattice have been shaded according to their distance to the origin. We ignore the cell structure the lattice, and treat a lattice structure simple point structure. The quincunx and hexagonal lattices are formed by interleaving two Cartesian grids; this is shown with the white and black filled dots.
efficient way to represent data non-Cartesian grids within the context of machine learning (or in general). To address this gap, we introduce new data-structure called a lattice tensor that we represent data any Con-Cartesian lattice structure. This structure changes the inherent representation of the data, as such requires many common operations to be rewritten terms of lattice tensors. For the most part, this straightforward. For example, element-wise operations trivial to extend. Convolution is more involved, but we still may leverage existing fast implementations. We generalize many of the traditional tensor spatio-temporal operations lattice tensors, enabling the use of these operations on non-Cartesian domains.
Ultimately, we present software library called Non-Cartesian Deep Learning (NCDL) which is an open source, concrete implementation of the lattice tensor container and the associated spatio- temporal operations defined over lattice tensors. NCDL library is implemented on top of Py PyTorch BI], and is designed to be relatively easily integrated into existing PyTorch code bases.
This work is the first general data processing library for non-Cartesian data (with the added benefit of being differentiable). In short, our contributions are as follows:
1. We introduce the concept of a lattice tensor, data-structure for the representation of data on non Ca-tetstaii lattice structures.
2. We generalize the traditional lattice tensors.
operations such as convolution and pooling to
3. We provide an open source software library that implements our methodology.
4. We show a small set of cases in which the non-Cartesian ideology produces performance benefit in the broader context of machine learning.
The remainder of the paper is organized as follows. In Section we review related work on non- Cartesian grids both in and out of the context of machine learning. In Section we formalize the key operations and concepts that we use in NCDL. Section 4 we validate the performance of implementation for convolution against specialized implementation for hexagonal lattices, and explore non- Cartesian auto-encoding networks. Finally, in Section 5 we conclude and discuss future work. Our implementation available at https::///// //w::://www.../// ncdl. ai
2 Related Work
Convolution is fundamental operation in most machine vision pipelines, and can be traced back to the early 1980s [12] Convolutional networks gained popularity owing the fact that convolutions exploit the locality of data while avoiding the curse of dimensionality (in parameter count). The recent surge of success in convolutional neural networks (CNNs) large part hardware advances in the early 2010s. General purpose GPU compute power facilitated new benchmark performance in image classification (25 D. Since then, various forms of CNNs have been proposed with various design differences: early efforts, like VGG and ResNet, focused on building deeper convolutional

---

networks [14 29 while trying to avoid the vanishing gradient problem: while others attempted to
create more computationallyyauueeeee efficient networks [8
33
36 37]. Other works have focused
on changing the mechanics of the convolution layer 44
35
18 However, none of these have pushed
into the realm of con-Cartesian data.
There has been limited work on the use of non-Cartesian grids in machine learning. The space efficiency of the hexagonal lattice has been attractive, so has garnered a small amount of attention. Neuroleex was the first to explore hexagonal convolutions in a modern CNN setting; their domain The game of Hex is restricted to a parallelpiped shaped region; to support
the game of Hex hexagonal convolution, the authors simply transform the problem domain and restrict convolutions to the hexagonal network by zeroing out filter elements. HexaConv explores hexagonal convolution in the context of image classification, and shows a surprising improvement over traditional Cartesian convolution [5]. They resample square Cartesian images on to the hexagonal lattice in an axial coordinate system (i.e. the same parallelpiped as [43, but zero padded). A similar work proposed a nearly identical structure on the isocsahedron-
spherical hexagonal grid. These works all suffer from the same problem: wasted space in their representation. There are currently only two works that do not waste space in this manner. The first is HexCNN [47), which stores data in a column format effectively linearizing the hexagonal domain column by column; convolutions then operate on this domain. The second and most similar to our work is HexagDLy. which splits the convolution into multiple convolutions over different shifts of the input domain (3.. Our work is more general than all of these works; our primary contribution is the lattice tensor, a simple, waste-free container for data arbitrary lattices. Figure 2 shows alternative representations from other frameworks, where they waste memory, and how NCDL addresses this.
This generalization forces us to think more broadly about operations on lattice tensors. Take down sampling for example; traditionally, down sampling is uniform in each dimension (usually dyadic, i.e. factor of 2 in each dimension). However, this is limitation only imposed by the restriction to Cartesian grids. There are other possible decimation strategies when discarding samples on the Cartesian lattice, one may discard samples from a checkerboard (i.e. quincunx) pattern, thereby producing another quincunx lattice. This type of downsampling is present in non-dyadic downsampling muuli-channel wavelet filterbanks (24), but has not been explored in the context of machine learning. In fact, higher dimensions exhibit more interesting cascading structures between grids (1). This cascading structure is something we explicitly support in NCDL.
The benefit of non-C non-Cartesian grids extends to higher dimensions. The optimal packing lattice in 3D is the body-centered cubic (BCC) lattice, and this is relatively well studied in the context of scientific visualization 32 4 However, most research has focused on finding high performing interpolants in these spaces 9 22 21 7 IO 6), on extending numerical techniques to exploit the inherent benefit of these approximation spaces. In this sense, we also contribute in this area, by providing an interface implement these ideas (one is not required to use the diffcrentiablity provided by NCDL).
Another related subfield of machine learning graph learning 42]. Examples of graph learning problems include document classification, where documents are the set of nodes V. and are related to other nodes/documents through the edge set F; this set may represent academic citiations, for example (28). Since non-Cartesian lattices change the inherent structure of the underlying repre- sentation of the grid, it natural to draw connections between non- Con-Cartesian methods and graph However, upon closer inspection, these connections break down in practice. Since the relationship between nodes in a graph is not necessarily constant, defining simple discrete relationship between them (i.e. discrete finite filter) is not easily achievable. Compounding this problem, the explicit spatial relationship between points is ambiguous, and depends on how a graph is embedded in space (which is not often provided as a parameter). As such, one typically turns to spectral methods or their approximations to compute the convolution of a "filter" with a graph g 23 To this end, graph convolution is not necessarily compatible with the ideology presented by traditional convolutional methods; while compelling, it is difficult to compare deep non-Cartesian methods with graph learning approaches. While the geometry of non-Cartesian structures is different than that of the traditional tensor, it is still regular structure; and as such, we seek to leverage pre-existing optimized implementations for operations on these domains.
based approaches to operations such convolution and pooling 13 26 27
3

---

Logical Domain
Memory Layout
Logicial Domain
Memory Layout
Logical Domain
Memory Layout
Axial Representation
(b) Offset Representation
Coset Representation
Three possible underlying representations for the memory of an image stored on rect- angular bounded region the hexagonal lattice. The "Logical Domain" the domain over which operation operates, the shaded cells the cells in which data is stored, and the white cells empty (i.e. wasted space). The axial representation (a) treats the hexagonal domain as transformed Cartesian domain, and requires large amount of wasted space [3). The offset representation (b) is more compact, but requires additional logic for the different rows the image and may also waste space. Our coset representation decomposes the input lattice into number of Cartesian lattices, is more compact than the offset representation in general, and works with arbitrary lattices.
Figure 2:
Computing on Non-Cartesian Grids
In general, processing data on any non-Cartesian grid is simple, but technically cumbersome. While most algorithms are easy to state on non-Cartesian discretization, the non-separable nature of these lattices makes it difficult to design efficient structures for storage and computation. We avoid this by simply igmoring the non- Cartesian structure; treating all processing as operations over separate Carte- sian components. A similar approach is taken in some recent works in the non-Cartesian world [17] [6]. Figure showws shows an example of this decomposition. The ideas in this paper are general, and we state them s-dimensional theory. However, in practice, implement this in 2D and 3D in NCDL.
Lattices We define a lattice subset of the s-dimensional integers Zt. Explicitly, we de- note this with full rank and define a lattice as a set Practically speaking, we are interested in bounded subset of these integers. In the rest of this paper assume this set is bounded within a rectangular region R of s-dimensional Euclidean space; denote this bounded as LR. When L = then all the discussion reduces to the Cartesian lattice, and classical machine learning approaches trivially apply.
1,000 0,00, +1
4,000 dy!
integer matrix L,
LZ C z..
(0.0)
Y.
(0.0)
(a)
(b)
Figure 3: Two lattice tensors on the quincunx lat-
The definition of lattice usually invokes tions of combinatorial problems and theory. While we do require some lattice algorithms to facilitate our implementation, we instead mainly use lattices data straa-struc To each lattice site within R, we assign a real (floating point) value; also explicitly include batch and channel index to facilitate common operations deep learning. We combine these ideas in the notation
tice. Each contains two tensors and two shifts (the first shift is always the trivial 0 shift). In general, other lattices there may be more cosets and shifts. These two lattice tensors are compatible, that is, they share the same overall geometry, but are shifted.
ab.o.Ca [i, k, n] E R, Vn E CR, 0 < < 5 k.
(I)
When the channel and batch indices clear from context, will write this aca [ł, k, n), or ali, k n] when all parameters are apparent from context.
The Coset Decomposition The key observation that facilitates the mechanics of this paper is that any (integer) lattice structure can be written as collection Cartesian lattices. That is, there exists an integer C', an integer diagonal matrix D x and integer shifts v,, 0 < i < C' such that
C-1
CR
U i=0
v. D(Zt)* nR.
(2)

---

This is the Cartesian coser decomposition. There are many possible coset decompositions; in general D need be diagonal matrix, however, this condition forces the cosets be Cartesian. This particular representation allows us to store data lattice multiple shifted traditional tensors (a.k.a. multi-dimensional arrays). To ensure that our algorithms maintain a consistent coset representation, we place restriction on V, and R: we restrict all v, E D[-1, 1, 1].. This puts lower bound on the boundaries of the region R, and helps avoid "coset creep" (in earlier iterations of this work, we noticed that coset vectors tend to uncontrollably walk around space if not somehow restricted).
Lattice Tensor The lattice tensor is the simple, yet fundamental backbone of this work. A lattice tensor is a collection of tensors and integer vector shifts. We define this formally, as well as a small number of additional properties in the following:
Definition 3.1 (Lattice Tensor). A lattice tensor consits of the bounded region R. the collection of
vectors v E D(-1, -,,1," 1]", and the associated values on the lattice ab.c.Cn [t. k. n]. When obvious from context, we will simply write v;. We order the V; lexically, according to their values v mod D (i.e. the vector in their equivalence class in D(0, 1]a). We denote the individual cosets of this lattice tensor as äا [1, k. m), where j < C is the coset index, and E (Z+)*.
The ordering of a lattice tensor's coset vectors small, but important part of the definition of lattice tensor; it ensures that between two arbitrary rectangular regions P and S the set v? + DØ* is always equivalent to v + Dž When working with the coset representation it is important to know which coset lattice points belong to; this is formalized as follows:
Definition 3.2 (Coset Index). Given some n E CR. the coset index z(n) is the integer such that Ve(n) + DZ
Proposition 3.1 (k--index). Given i, with < i,j C, for any n E CR. m E Ls with (n) = and ((m) j. it must be that both ((n m) and ((n + m) are constant. We define ky (1, = c(n + m).
The intuition for the x-index is simple, if we subtract or add lattice points on two cosets, the x-index tells us the resulting coset index of the operation. Figure shows an example of these concepts.
Tensor Operations on Lattice Tensors For the most part, tensor arithmetic on lattice tensors is relatively straightforward. If two lattice tensors share the same and R. then arithmeteic can be performed directly on the underlying coset tensors. However, there may be cases in which we should be able to add two lattice tensors, but the differing coset vectors break the correspondence between two lattice tensors' coset. Figure3]show: a simple case where this happens.
Definition 3.3 (Compatibility). We say two lattice tensors Tb,c, and yV.e.6% are compatible if and only if 6 = 6', c = e, = L' and 3 kR.S E 2 such that Lx = {n + kR.S : n L's).
In practice, finding this correspondence is straightforward, we shift the set of coset vectors so that their centroid is the origin, then we check if all shifted coset vectors have a corresponding match. This allows us to define element-wise binary operations as operations over the underlying Cartesian tensors.
Definition 3.4 (Binary Elementwise Operations). Given a binary operation O defined over the elements of RR two compatible lattice tensors Tb,c, and Cb,c,Cs. we define
(Db,e,Cr Lo. Ji. n| == 2b. [i. j. Mo.c..s + kR,s).
(3)
Note that this always outputs a new lattice tensor on LR-
A Note About Reflection It is common to flip tensor about an axis, either for data augmentation or for another common operation, like padding. However, an astute reader may notice that not all lattices have reflective symmetry.
Definition 3.5. A lattice L has reflective symmetry about the plane defined by ea if and only if Vn E it is true that ee n e where ea is the tt unit cardinal vector.
If a lattice tensor has reflective symmetry about an axis, materializing a reflected tensor is straightfor- ward: flip the underlying tensor and correct the coset shift vectors.
5

---

Lattice Tensor Padding Padding is a simple but fundamental operation in many data processing schemes. On the Cartesian lattice we simply extend the region of interest, then introduce the appropriate new elements. Padding a lattice tensor on LR. is slightly more involved. Fix an axis d, and assume we wish to pad on the right by unit of In this case, we extend the support of by the smallest amount on the right so as to introduce new lattice sites to the lattice tensor, we then pad the appropriate underlying tensors on the right to fill this new space. To pad on the left by a unit of I, we again extend the support of R by the smallest amount on the left so as introduce new lattice sites to the lattice tensor, any underlying tensors are padded to the left, and their corresponding coset vectors become v, Cd- If this moves coset vector outside of the valid range D(-1, 1]", then all vectors are uniformly shifted back within this range. We leave the details to our implementation, provided as supplementary material.
Convolution The convolution operation naturally generalizes as an operation over lattices, we note this in the following definition.
Definition 3.6. For lattice tensor acx. and filter fcr where the region P is strictly positive, define convolution as
(ab,c.Ex * feh In,
Σ Σ
ain.j. P...ip+ssffi....
(4)
3=0 sEsupo(s)
whose output lattice tensor is in Ls where LR = Ls a Lp (here, T is the Minkowski-sum of two point-sets).
When C is the Cartesian lattice, then this reduces to the classical case. This definition excludes fused operations such downsampling (strided convolutions) and any form of padding. We do this inten- tionally, as including these operations is quite complex, and supporting such fused operation would require large additional implementation effort. Even as such, creating dedicated implementation of this generalized convolution operation is a large challenge on its own [2]. Instead, we leverage pre-existing implementations on Cartesian lattices. We use the following proposition to achieve this. Proposition 3.2. For a lattice tensor ace and filter fcr where the region P is strictly positive, the result of the convolution Ls == (0b,e,Lx *fo,k.Co) can be written in terms of its output cosets as C-1
ō dee (i.1) [. + 5(i,))
(5)
where * is the traditional Cartesian convolution operator, and ((2,j) = D-' (v (v+4(1))) v v
is a constant by which we shift the appropriate coset of ac
A practical note about this operation is in order. We are typically limited to rectangular support for supp(f)) in all popular implementations of Cartesian convolution. To address this, we simply take the "ZeroOut" approch 47 and zero out any inappropriate elements in the square filters' support.
Pooling The pooling operator also naturally extends to lattice tensors, we note this in the following definition.
Definition 3.7. For lattice tensor aLx and filter geometry Cp where the region P is strictly positive, lattice pooling is defined as
Cb., m. n] max max(all, m. +
(6)
SELP
whose output lattice tensor is in Ls where LR L.s @ Lp.
We again, re-write this terms of processing over Cartesian lattices in order to leverage existing frameworks for evaluation
Proposition 3.3. For a lattice tensor dsR and stencil geometry Lp where the region P is strictly positive, the result of the lattice pooling operation ob.e, [1, m. n max {a[t, m. n + s]} can be written terms of its output cosets as
0. m, n|
max U$J<C'
max SED- (Et v,)nz
(ār)(t)) [n+st 8 (i.,)))
where the maximum operation running over the set D 0-1 (Cp v,) 1 is the traditional max pool operator, restricted to the jth coset of the stencil.

---

Downsampling Downsampling (i.e. discarding data then reducing resolution) is another basic operation that we generalize. The most general case for downsampling is systematically remove samples in such way that the lattice property is preserved. We take the standard path to define down/up sampling about an integer matrix with < det E Z. We obtaín the sub-sampled lattice by restricting to the new set Q == SC. Loosely, for the new lattice Q we obtain the coset decomposition, then subsample the input lattice tensor according to the new decomposition. This yields new lattice tensor.
Upsampling Upsampling introduces new datapoints (initialized zero) higher resolution lattice. We denote this with a matrix L & g*xe, This employs the same mechanics as downsampling, but rather than removing points, we introduce new points according to the lattice in question. The mechanics of this are similar to downsampling, and we leave the details to the supplementary implementation.
3.1 Derivative Computation
Since gradient computation is an important feature that must be supported by any deep learning framework, it is crucial to discuss gradient computation from the perspective of lattice tensors. For given loss function h, and the lattice tensor the gradient 0h/Ou is simply the lattice tensor consisting of the gradients of the individual cosets, that is, 0h/0ā. Computing the gradient of any element- wise operation is straightforward; we simply operate independently on the coset tensors. However, for the remainder of the operations discussed far, require more We start with convolution.
Proposition 3.4. For lattice tensor acæ and filter fiP where the region strictly positive, with convolution defined as
i,n, p] == (ab.e,.z * (e.k..))) [n, P.
(8)
whose output lattice tensor is in Ls where LR Ls Lp, the derivatives of the loss with respect to the filter and input lattice tensor given by
Oh.
(o* Je,k, [n,i,k),
(9)
aa n, i, k)
Oh
Σ
Öh Oo(n, i, p.
a j. k]
(10)
j
pECc
where 7 mirrors the filter and swaps the channels, i.e. Jli,j.k] k) = fli,ú, -k].
Note that common to state the filter gradient as a convolution. We avoid introducing new notation to describe this fact and simply note this here.
Proposition 3.5. For lattice tensor alz and filter geometry Lp where the region P is strictly positive, lattice pooling
Ob [n, i,
max s}}
(11)
selr
whose output lattice tensor is in Ls. has the gradients given
Oh
Ōh
Σ
M|n,i, P.P.
(12)
Dain, i, k]
iofn, k
PELp
where
Mn.ipp.q = [1 if maxxecrra/ln. i, + s|} = afn,
(13)
otherwise.
The proofs of these facts are direct consequences of the chain rule, and can be found in the Appendix.
Derivatives of Padding, Downsampling and Upsampling The loss gradient of the downsampling operation is upsampling (taking care to respect the original dimensions of the original lattice tensor) and vice versa. The gradient of the padding operation simply truncates the padded gradient tensor, discarding any gradient signal outside of the original geometry of the tensor from the forward pass. For the most part, we leverage the automatic differentiablity of PyTorch to compute derivatives of these operations 31 However, more streamlined implementations using the forms above may save memory in future iterations of this work, since less temporary tensors must be saved during the forward pass.
7

---

Exploring non-Cartesian Networks
In this section, delineate the experiments conducted to evaluate NCDL. First, compare NCDL with the closest existing hexagonal convolution library [34]. Subsequently, we explore the use of non-dyadic down/up sampling within bottlenecked architectures. To the best of our knowledge, this operation has not been explored in machine learning. All experiments are conducted on an AMD Ryzen 9 3900X (3.8GHz) with 128GB of DDR4 RAM operating at 3200 MHz, accompanied by an NVIDIA RTX 3090 with 24GB of RAM.
4.1 Hexagonal Convolution
While NCDL focuses primarily on integer lattices, the hexagonal lattice exhibits the same coset structure as the quincunx lattice. This permits the storage of a hexagonal image on quincunx lattice convolution can be implemented via the selection of a suitable filter on the quíneux lattice. We assess the efficacy of this method in comparison to HexagDLy 34 which, among all other related works, is conceptually most similar to our approach.
Evaluation Figure 4 illustrates the performance trend as the grid size increases. Here, all grids are "equivalent" to the Cartesian grid. That is, we choose our hexagonal domain/lattice tensors to con-
Convolution Size v.s. Execution Time
Conv20
HlexegByy
NCDL
sume roughly the same amount of memory as the Cartesian grid. For example, if our Cartesian grid is 256 x 256, then each coset of our lattice tensor has dimension of 182 x 182. We fixed input and output channels at 32 and 64 respectively (simulating an early stage in convolutional pipeline). We limit our experiment to the case where the convolution ker- nel is a hexagonal I-ring/l hoing/l-neighborhood filter. We set the stride to 1, as NCDL does not support fused strides with convolution. It is important to note that employ the same filter sizes as HexagDLy, but our convolutions occur over the separate cosets of the lattice, which smaller than the grids over which HexagDLy operates.
Size
112
2018
Mean Time (ms)
Figure 4: Average run time in milliseconds (ms) as grid size increases, averaged over 100 runs, bench-marked on GPU. Variance is neg- ligible.
There are a few things to note about this experiment. For smaller grid sizes, NCDL exhibited slower performance compared to HexagDLy. This is likely due to the inherent overhead of managing the coset structure and the overhead of GPU kernel queueing. However, beyond a threshold, NCDL vastly outperforms HexagDLy. This is likely due to the fact that HexagDLy operates over larger grids (even though it employs strided convolutions). This effectively increases the computational load, particularly in processing larger inputs. While the strides in HexagDLy's implementation help in reducing the spatial dimensions of the output, the fundamental operation over larger grids does demand additional computational resources. Interestingly, only in one scenario (2048) did non-Cartesian implementation outperform the Cartesian 1-ring filter. This finding is particularly significant, considering that the Cartesian convolution employs larger filter size and is thus expected to involve more computation.
4.2 Non-dyadic Downsampling and the Quincunx Lattice
It is somewhat expected that convolution on hexagonal images yields superior results in aspects such as speed accuracy. Nonetheless, non-Cartesian lattices may enhance performance without necessitating a change in approximation space through other means. In this second set of experiments, we investigate the application of non-dyadic downsampling. That is, as data flows through the network, it starts as tensor on a Cartesian lattice; subsequent layers perform convolution, then a downsample operation according to the following sub-sampling matrix = [-1 1; 1). This generates a lattice tensor on the Quincunx lattice. A subsequent convolution (followed by a downsample operation) results in a lattice tensor on the Cartesian lattice. Different levels of convolution alternate between these two grids (analogous to 19),, offering more gradual reduction in resolution.

---

Traditional Cartesian Tensor
Quincunx Lattice Tensor
Aaba
N004
Cartesian Filter Geometry
512
Cartesian Network
Quincunx Filter Geometry
1024
1034
1aas
1024
912
206
26
46
Quincunx Network
4
Figure 5: The network structures we propose. The auto-encoder experiments we conduct omit the skip connections between the layers. To maintain parity with the quincunx design, additional skip connections were added to the Cartesian case. Both networks share the same amounts of parameters.
Training
Validation Loss
0.255
Curlizzan 0.13
Qumcumn
CAE
QCAE
1:288
0.68304
L.2
0.01955
0.01399
0.150
PSNR
SSIM
06113
0.6066
0.100
0.03
Sumbor of Borations
Number Iaraaiono
Figure 6: Error plots for training and validation. The QCAE marginally outperforms in training, and outperforms with wider margin in the validation. The table on the right shows the final model performance with respect to various error metrics; superior performance is noted in bold-font.
Quincunx Auto-encoder In this experiment, we establish a rudimentary autoencoder structure that progressively downsamples to latent space before upsampling back to the image space. We first establish a baseline experiment, incorporating by downsample (we maintain two convolutions to preserve parameter parity with the quincuux case). The Quincunx Convolutional Auto-Encoder (QCAE) lattice encompasses one convolution, downsample onto the Quincunx lattice, one convolution, and downsample onto the Cartesian lattice. Figure 5 shows the exact structures we design.
Cartesian convolutions with 3 filters, followed
We train our models using the CelebA dataset [30 Employing a straightforward LI loss, we measure validation L1. L2, PSNR, SSIM 41 and LPIPs metrics [46.. The network is trained with the Adam optimizer, default parameters, and a batch size of 8. We train for 300,000 iterations, as convergence was observed at this point, and take an average of 5 runs. This represents a total of approximately 160 hours of training time for all experiments.
Salient Object Detection with a Quincunx U-Net In this experiment, we extend the rudimentary auto-encoder from the previous experiment by simply adding skip connections. Figure 5 shows the exact structures design, and the dotted lines show the additional skip connections that

---

Trining
Validation
2.35
Cartesinn
0:35
Cartellan
0.30
0.28
U--ie
QCH--Nee
0.24
0.07583
0:08268
0.20
0:24
0,04969
0.05107
0.15
RCP.
0.19366
0.18706
0.58
20320
42000
00020
02000
100003 100020
20000
43000
G0320
60000
100000
120000
Namber Hteratioma
Fterations
Figure 7: Error plots for training and validation. The QCU-Net marginally fits to the data in the training set worse than the strictly Cartesian U-Net. However, the QCU-Net outperforms in generalization for this task. The table on the right shows the validation error at the end of training. Better performance is noted in bold-font.
introduce for this example. We train our models on the DUTS salient object detection dataset 40). and employ a straightforward binary cross-entropy (BCE) loss; we measure validation BCE, L1, L2 and SSIM. The network trained with the Adam optimizer, with default parameters, and a batch size of 8. We train for 120,000 iterations, as convergence observed in the validation data at this point.
Discussion In experiments, introducing quincunx downsampling shows noteable difference across our tasks. For the autoencoder experiment, we note a small improvement performance for no additional cost in parameters (Figure o): replacing traditional Cartesian convolution with downsample operation followed by a Quincunx convolution should also be more computationally efficient, since certain convolutions occur smaller grids. However, due to implementation overhead, we note that this is currently not truc. The U-Net experiment is interesting in that it does not show distinetly better performance in training, but validation performance improves for the BCE metric (Figure 7). It is somewhat surprising that other metrics do not reflect the improved validation entropy: however minimizng BCE does not strictly imply that other pixel-wise metrics will improve, due to the way in which BCE weights pixelwise classification errors.
There are a few potential reasons for the improved quantitative performance of these networks. The downsampling scheme more gradual QCAE. This likely leads to more gradual reduction of information passes through the bottleneck of the network. Important information is less likely to be "missed" by this more gradual reduction. The second, more simple explanation may be that the aliasing introduced by the quincunx downsampling operation is much less strong, thereby providing stronger signal as data pass through lower resolution layers of the network; aliasing is a well-known enemy of neural networks 455
Future Work and Conclusions
This work has presented a general approach to enable the use of non-Cartesian lattices in machine learning. Doing so has opened new avenue of research by introducing a new twist on a fundamental concept in machine learning. There are many possible avenues for future work: we plan on exploring this in the context of models at scale, for example in generative approaches like GANs diffusion models [5] 20 Additionally, modern components, such as the attention mechanism [39], must be generalized to this new structure. There is also still a good amount of performance left on the table. Decomposing convolution across the different cosets separates the convolution operation into disjoint operations that could, for example, take place on completely separate hardware. These separate operations could be scheduled across different memory chips, for example, to avoid bank conflicts or other complications that arise in GPU memory controllers.
Acknowledgements
We would like to thank Richard Zhang and Derek Nowrouzezahrai for their involvement in earlier less successful iterations of this work and for pushing to finish this work.
10

---

References
[1] Md Zahangir Alom, Tarek M Taha, Christopher Yakopeic, Stefan Westberg, Paheding Sidike, Mst Shamima Nasrin, Brian C Van Esesn, Abdul A S Awwal, and Vijayan K Asari. The history began from alexnet: A comprehensive survey on deep learning approaches. arXiv preprint arXiv: 2018.
[2] Sharan Chetlur, Cliff Woolley, Philippe Vandermersch, Jonathan Cohen, John Tran, Bryan Catanzaro, and Evan Shelhamer. cudnn: Efficient primitives for deep learning. arXiv preprint arXiv:1410.0759, 2014.
[3] Cohen and J-M Schlenker. Compactly supported bidimensional wavelet bases with hexagonal symmetry. Constructive approximation, 9(2-3):209-233 1993.
[4] John Horton Conway and Neil James Alexander Sloane. Sphere packings, lattices and groups. volume 290. Springer Science & Business Media, 2013.
[5] Florinel-Alin Croitoru, Vlad Hondru, Radu Tudor lonescu, and Mubarak Shah. Diffusion models in vision: A survey. IEEE Transactions on Puttern Analysis and Machine Intelligence, 2023.
[6] Balazs Csebfalvi. Cosine-weighted b-spline interpolation: A fast and high-quality reconstruction scheme for the body-centered cubic lattice. IEEE transactions on visualization and computer graphics, 1955:1455-1466, 2013.
[7] Balázs Csébfalvi and Gergely Ráez. Retailoring box splines to lattices for highly isotropic volume representations. Computer Graphics Forum, 35(3):411-425 2016.
[8] Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. Advances in neural information processing systems, 29, 2016.
[9] A. Entezari, D. Van De Ville. and T. Moller. Practical box splines for reconstruction the body centered cubic lattice. Visualization and Computer Graphics, IEEE Transactions on, 1422):3133228, March 2008
[10] Alireza Entezari, Ramsay Dyer, and Torsten Möller. Linear and eubic box splines for the body centered cubic lattice. In Proceedings of the conference on Visualization '04, pages 11-18. IEEE Computer Society, 2004.
[11] Alireza Entezari and Torsten Möller. Extensions of the Zwart-Powell box spline for volumetric data reconstruction on the cartesian lattice. IEEE Transactions on Visualization and Computer Graphics, 12(5), 2006.
[12] Kunihiko Fukushima. Neocognitron: A self-organizing neural network model for a mechanism of pattern recognition unaffected by shift in position. Biological cybernetics, 36(4):193-205 1980.
[13] Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. International conference on machine learning. pages 1272. PMLR, 2017.
[14] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and paltern recognition, pages 770-778, 2016.
[15] Emiel Hoogeboom, Jorn WT Peters, Taco Cohen, and Max Welling. Hexaconv. arXiv preprint 1rXiv:1803.02/008 2018.
[16] Joshua Horacsek and Usman Alim. A closed form of box splines via green's function decomposition. Journal of Approximation Theory, 233:37-57, 2018
[17] Joshua Horaesek and Usman Alim. Fastspline: Automatic generation of interpolants for lattice samplings. ACM Trans. Math. Softw., 49(2), jun 2023.

---

[18] Andrew G Howard, Menglong Zhu, Bo Chen, Dmitry Kalenichenko, Weijun Wang, Tobias Weyand, Marco Andreetto, and Hartwig Adam. Mobilenets: Efficient convolutional neural networks for mobile vision applications. arXiv preprint arXiv:170.0486., 2017.
[19] Jiro Inoue and A James Stewart. Multiresolution sphere packing tree: hierarchical multireso- lution 3d data structure. Proceedings of the 2008 ACM symposium on Solid and physical modeling, pages 367-373, 2008.
[20] Minguk Kang, Jun-Yan Zhu, Richard Zhang, Jaesik Park, Eli Shechtman, Sylvain Paris, and Taesung Park. Scaling up gans for text-to-image synthesis. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, pages 00124-10134, 2023.
[21] Minho Kim. GPU isosurface raycasting of FCC datasets. Graphical Models, 75(2):90 101, 2013.
[22] Minho Kim. Quartic box-spline reconstruction on the BCC lattice. IEEE transactions on visualization and computer graphics, 1922)319-330, 2013.
[23] Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv: 2016.
[24] Jelena Kovacevic and Martin Vetterli. Nonseparable multidimensional perfect reconstruction filter banks and wavelet bases for r/sup n. IEEE Transactions on Information Theory, 38(2):333-
555, 1992.
[25] Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convolutional neural networks, In F. Pereira, C.J. Burges, L. Bottou, and K.Q. Weinberger, editors, Advances in Neural Information Processing Systems, volume 25. Curran Associates, Inc., 2012.
[26] Zongyi Li, Daniel Zhengyu Huang, Burigede Liu, and Anima Anandkumar. Fourier neural oper- ator with learned deformations for pdes on general geometries. arXiv preprint 220.::2207.002009 2022.
[27] Levi Lingsch, Mike Michelis, Sirani M Perera, Robert K Katzschmann, and Siddartha Mishra. Vandermonde neural operators. arXiv preprint arXiv:2305. 2023.
[28] Jiaying Liu, Jing Ren, Wenqing Zheng, Lianhua Chi, Ivan Lee, and Feng Xia. Web of scholars: A scholar knowledge graph. In Proceedings of the 43rd International ACM SIGIR Conference on Research and Development in Information Retrieval, pages 2153-2156, 2020.
[29] Shuying Liu and Weihong Deng. Very deep convolutional neural network based image clas- sification using small training sample size. In 2015 3rd IAPR Asian conference pullern recognition (ACPR), pages 730-734. IEEE, 2015.
[30] Ziwei Liu, Ping Luo, Xiaogang Wang, and Xiaoou Tang. Large-scale celebfaces attributes (celeba) dataset. Retrieved August, 15(2018):11, 2018.
[31] 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 Vito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high-perffommncce deep learning library. In Advances in Neural Information Processing Systems 32, pages 8024-8035. Curran Associates, Inc., 2019.
[32] Daniel P Petersen and David Middleton. Sampling and reconstruction of wave-mumber-limite functions n-dimensional euclidean spaces. Information and control, 5(4):279-323, 1962.
[33] Mark Sandler, Andrew Howard, Menglong Zhu, Andrey Zhmoginov, and -hing Chen. Mobilenetv2: Inverted residuals and linear bottlenecks. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 4510-4520 2018
[34] Constantin Steppa and Tim L. Holch. Hexagdly processing hexagonally sampled data with cnns in pytorch. SoftwareX, 9:193 - 198, 2019.
12

---

[35] Christian Szegedy, Wei Liu, Yangging Jia, Pierre Sermanet, Scott Reed, Dragomir Anguelov, Dumitru Erhan, Vincent Vanhoucke, and Andrew Rabinovich. Going deeper with convolutions. In Proceedings of the IEFE conference computer vision and pattern recognition, pages 1-9,
2015.
[36] Mingxing Tan and Quoc Le. Efficientnet: Rethinking model scaling for convolutional neural networks. In International conference machine learning, pages 6105-61 6114. PMLR, 2019.
[37] Mingxing Tan and Quoc Le. Efficientnetv2: Smaller models and faster training. In International conference on machine learning, pages 10096-10106. PMLR, 2021.
[38] Dimitri Van De Ville, Thierry Blu, Michael Unser, Wilffied Philips, Ignace Lemahieu, and Rik Van de Walle. Hex-splines: A novel spline family for hexagonal lattices. IEEE Transactions on Image Processing, 13(6):758-777 -728, 2004.
[39] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, tukasz Kaiser, and Illia Polosukhin. Attention all you need. Advances neural information processing systems, 30, 2017.
[40] Lijun Wang, Huchuan Lu, Yifan Wang. Mengyang Feng, Dong Wang, Baocai Yin, and Xiang Ruan. Learning to detect salient objects with image-level supervision. In CVPR, 2017.
[41] Zhou Wang, Alan C Bovik, Hamid R Sheikh, and Eero Simoncelli. Image quality assessment: from error visibility structural similarity. IEEE transactions on image processing, (4)::600 612, 2004.
[42] Feng Xia, Ke Sun, Shuo Yu, Abdul Aziz, Liangtian Wan, Shirui Pan, and Huan Liu. Graph learning: A survey. IEEE Transactions on Artificial Intelligence, 2(2):109- 127, 2021.
[43] Kenny Young, Gautham Vasan, and Ryan Hayward. Neurohex: A deep q-learning hex agent. In Computer Games: 5th Workshop Computer Games, CGW 2016, and 5th Workshop General Intelligence in SlayePlaaying Agents, GIGA 2016, Held in Conjunction with the 25th International Conference Artificial Intelligence, IJCAI 2016, New York, USA, July 9-10, 2016, Revised Selected Papers. pages 3-18. Springer, 2017.
[44] Jiahui Yu, Zhe Lin, Jimei Yang, Xiaohui Shen, Xin Lu, and Thomas S Huang. Free-form image inpainting with gated convolution. In Proceedings of the IEEE/CVF international conference on computer vision, pages 1471-4480, 2019.
[45] Richard Zhang. Making convolutional networks shift-invariant again. In International confer- ence on machine learning, pages 7324-7334 7334. PMLR, 2019.
[46] Richard Zhang, Phillip Isola, Alexei A Efros, Eli Shechtman, and Oliver Wang. The unreason- able effectiveness of deep features as perceptual metric. In CVPR, 2018.
[47] Yunxiang Zhao, Qiuhong Ke, Flip Korn, Jianzhong Qi, and Rui Zhang. Hexenn: a framework for native hexagonal convolutional neural networks. In 2020 IEEE International Conference on Data Mining (ICDM), pages 1424-1429, IEEE, 2020.
13


Reviews:
[{"review_id": "jCd2a5gL6H", "reviewer": "Reviewer_aoAr", "summary": "he authors claim that the concept of tensors, a fundamental cornerstone in machine learning, assumes data are organized on Cartesian grids. They further suggest that alternative non-Cartesian representations may be more beneficial in certain situations. One case is when the data is inherently non-Cartesian — for example, the raw R/G/B image data from most imaging sensors are follows a quincunx (checkerboard) structure in the green channel. Another case is when non-Cartesian grids show superior performance in certain aspects — for example, the hexagonal lattice is known as the optimal sampling lattice in 2D.\nThe authors hereby propose a framework and a software library that introduces standard machine learning operations on non-Cartesian data. The new data structure is called lattice tensor and the software library is called Non-Cartesian Deep Learning (NCDL).\n", "questions": "1. Continuing on Weakness #1, it will be very helpful if the authors can construct a table which outlines several typical use cases, with the following information: (1) domain (vision/language/graph/etc), (2) dataset name and description of data format, (3) machine learning task (classification/segmentation/reconstruction/retrieval/etc), (4) preferable non-Cartesian representation, (5) short explanation on why it’s better than Cartesian. Do you think it is a reasonable idea, or is there a better way to demonstrate the applications and impact?\n\n2. Open-ended question: will it be better to embed the proposed method in hardware?\n", "limitations": "While it has been covered in previous sections, the main limitations are:\n-Unclear potential application and impact.\n-Insufficient of experiments and comparisons.", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. In the introduction section, the authors provided sufficient context on why non-Cartesian grid structures may be superior to Cartesian counterparts under certain circumstances.\n2. We shall appreciate the effort in designing the memory-efficient coset representation for operations on the hexagonal lattice (shown in Figure 2).\n", "weaknesses": "While custom tensor definitions and operations for non-Cartesian data representation are theoretically pleasing, the authors have not shown clearly the potential applications and impact. It is not obvious which datasets and/or standard machine learning tasks will directly benefit from the non-Cartesian representation. A table detailing some typical use cases will be utterly helpful. \nThe experiments/comparisons performed are not convincing enough. The two main results shown in the submission are (1) runtime of convolution operation at different grid sizes, and (2) loss curves of a Cartesian vs. Quincunx auto-encoder on CelebA (celebrity faces) dataset. \n\nIn the first experiment, while the authors compare the runtime against the standard Cartesian Conv2D and another non-Cartesian baseline (HexagDLy), they have only investigated the convolution operation but skipped the other operations such as pooling, downsampling, upsampling, gradient computation, and back-propagation. Further, no comment has been made on numerical correctness or precision.\nIn the second experiment, the authors aim to show superior performance of Quincunx auto-encoder for image reconstruction. It is a bit weak as the experiment is only performed on one task over one dataset. It may be helpful to include a few more datasets — they don’t even need to be big one, e.g., STL-10, SVHN, LSUN will be sufficient. Besides, the only metrics shown are L1 and SSIM on the validation set. I would recommend including other metrics such as L2, PSNR, FID, and perceptual distance.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "###  \"It will be very helpful if the authors can construct a table which outlines several typical use cases, with the following information: (1) domain (vision/language/graph/etc), (2) dataset name and description of data format, (3) machine learning task (classification/segmentation/reconstruction/retrieval/etc), (4) preferable non-Cartesian representation, (5) short explanation on why it’s better than Cartesian. Do you think it is a reasonable idea, or is there a better way to demonstrate the applications and impact?\"\n\nThis is a good suggestion, but difficult to execute because some of these points venture into research territory. I can briefly comment on how NCDL can affect each of these aspects.\n\n * **domain**) The applicable domains here are any vision problem or any problem involving volumetric data. One key observation that bares repeating is that your data do not need to reside on a Cartesian grid to use these approaches. The non-dyadic downsampling operation takes data from one lattice configuration and places it in another (for example, Cartesian to Quincunx). Depending on the source and target lattice, this operation discards much less data compared to a standard stride=2 convolution. This would be a relatively large list of problems.\n\n *  **datasets and data formats**) My assumption is that you would want to see how a non-Cartesian approach would be more appropriate with a given dataset? There are cases where data may be structured inappropriately for a specific grid. For example, if the data in question is pixel art, and we attempt to represent that pixel art in a hexagonal domain, this will clearly be beaten by a Cartesian approach. However, there may be some other network architecture that both 1) includes non cartesian convolution, and 2) outperforms a purely Cartesian approach. Again, this is something we are actively investigating as future research.\n\n* **non-Cartesian representation**. The lattice tensor is always our preferred representation. There is no compelling reason to use a different data-structure that can support arbitrary lattices as the lattice tensor does. Even if we limit ourselves to strictly hexagonal lattices, then there is no data-structure that has the flexibility needed for appropriately padding data before convolution (or pooling, or any other operation that consumes part of the data's spatial extent)\n\n * **reason for using a non-Cartesian approach**. In the context approximation theory there are good arguments as to why non-Cartesian approaches should be superior to Cartesian approaches. In the context of machine learning, I'm not sure if these arguments hold, this needs to be assessed on a problem-by-problem basis.  NCDL introduces a new primitive that adds another degree of freedom to network architecture design, how that degree of freedom will affect results is not 100% clear. To us, this is a very attractive avenue for future work.\n\nWe can add a table detailing some of what you want. This is completely doable and reasonable, however it will be based on speculation, and likely belongs in the future work section. \n\n### \"Will it be better to embed the proposed method in hardware?\"\nWe are confident that there would be a benefit to specialized hardware, yes. How to do this is a subject of future research. For example, there are necessarily parallel computations that can be exploited (for convolution, there are completely independent convolutions happening for one given operation). Without giving too much away, I can say that splitting grids onto physically separate memory chips could allow for more efficient use of the bandwidth of those chips. This is something we are actively thinking about. \n  \n### \"Insufficient of experiments and comparisons.\"\nWe will expand our set of test metrics, and add another application/dataset to compare with.\n  \n### \"Unclear potential application and impact.\"\nWe do not agree with this point. This work adds a set of new primitives that are applicable to many problems that use convolution. However, we do agree that more evaluation would help drive this point home."}, {"review_id": "B26W0EGE68", "reviewer": "Reviewer_uhBv", "summary": "This paper introduces a high-quality software extension for PyTorch that enables seamless computations with non-Cartesian lattices for 1D, 2D and 3D images. The key observation made by the authors of this work is that **non-Cartesian lattices can be decomposed as \"sums\" of Cartesian lattices**: up to some clever refactoring (which makes up the core numerical code of the proposed software package), efficient computations on non-Cartesian lattices can directly leverage the standard (and highly optimized) PyTorch/cuDNN implementations of e.g. convolutional layers. \n\nThis implies that **the proposed software package is both efficient and easy to maintain in the long run**. ", "questions": " ", "limitations": " ", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "- The authors tackle an interesting and **very original topic**. Non-Cartesian lattices are indeed fundamental to low-level image processing but essentially absent from the machine learning literature.\n\n- The paper is **extremely well written**, with clear figures, attention paid to details and a satisfying evaluation. I haven't tried to run the code provided in the supplementary materials (too many papers to review at once!), but this is **clearly a high-quality software package** with a clean structure, a full test suite and extensive documentation.\n\n- This package targets successfully one specific and interesting operation in image processing, providing a **useful extension to our common toolbox via a neat and clever software package**. This is more than what most papers (never mind submissions) can provide and, in my opinion, clearly warrants publication at NeurIPS.\n", "weaknesses": "Reviewers can always ask for more (outstanding deep learning experiments, better run times, support for all types of attention layers and niche hardware architectures, etc.)... But realistically, I am very happy with the paper as submitted.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you, I believe no comments are necessary from me, here."}, {"review_id": "kgYu4YlePy", "reviewer": "Reviewer_Pd5c", "summary": "This works introduces a framework as well as software for computing convolutions on non-Cartesian lattices. The method is compared to existing software for hexagonal lattices as well as on image data.", "questions": "The motivation for images on hexagonal grids are is a bit unclear to me. I always think of images as living on Cartesian grids, so it is somewhat strange to consider them on hexagonal grids instead. Why is this useful? Furthermore, where do you see most of the applications for this? Would be great to include possible large scale applications that lead a vision for future work.", "limitations": "The authors have adequately addressed limitations and potential negative societal impact. ", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The method is put in a strong theoretical framework that also explores the very important up and down sampling operations on non-uniform grids. The authors also make available open-source software that is more general and whose performance seems much better than anything available. ", "weaknesses": "In the context of scientific machine learning, there have been similar ideas explored on how to make architectures which work on arbitrary grids, for example, https://arxiv.org/abs/2207.05209, https://arxiv.org/abs/2305.19663, and I am sure there are others. Furthermore, graph neural networks can also perform convolutions or arbitrary grids, for example, https://arxiv.org/abs/1704.01212, among many, many others. It would be good to mention some of these and even include some comparisons.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review : ). With respect to the missing references, see the main rebuttal. \n\nThis work does indeed require you to bend the notion that images are composed of square pixels. Given an isotropically band-limited image/function (which is really most natural images) it is possible represent that image with ~14% less samples on a hexagonal grid compared to a Cartesian grid [1]. This is perhaps surprising from the perspective of computer science, but when you look to nature, it is less surprising. Many structures that appear in nature are hexagonal; the photo-receptor cells in your retina are arranged in a nearly hexagonal pattern. There's a relatively large body of work on this, it is worth taking a look at both [1] and [2] if you are interested (also, some of the references in our background section expand on this higher dimensions). \n\nIt's also worth noting that NCDL is not limited to the Hexagonal grid. We support any regular (integer) lattice structure. This is notable because it allows us to start with data on a Cartesian lattice, then move to another lattice (quincunx, for example, see the experiment at the end of the current submission). This provides a much smoother transition to lower resolution representations."}, {"review_id": "waBwmWIyKF", "reviewer": "Reviewer_Y55j", "summary": "This paper generalizes common machine learning operations from Cartesian lattices to other regular lattices, such as the hexagonal lattice. The authors argue that the Cartesian lattice is a sub-optimal representation for important natural signals, and that operating on their non-Cartesian structure natively leads to more efficient implementations and better results.\n\nThe authors further promise to release a software library for non-Cartesian deep learning, and include an experimental section with implementation details and efficiency arguments, as well as experimental results on various computer vision tasks.", "questions": "The area of non-Cartesian deep learning could reasonably be considered a sub-field of geometric deep learning, which also includes deep learning on graphs, and models that leverage group symmetry. The authors should consider comparing lattice neural network approaches with GNNs (similar to experiments using sub-pixel graphs), as the graph models should be able to handle the non-Cartesian grid (albeit differently and with less inductive bias).", "limitations": "Some aspects are lacking, as explained above:\n- Derivatives and numerical stability\n- Comparison with other non-Cartesian models such as GNNs and group equivariant neural networks", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "The contribution is very novel in the sense that the field of deep learning on lattices is under-explored. The author's work is likely to have a big impact on this area of machine learning, as providing a complete optimized library with non-Cartesian version of common lattice operations with speed-up future research significantly.", "weaknesses": "The paper is short, with the authors being allowed one more page of content. They could improve the discussion by expanding, for example, on the computation of the derivatives.\n\nAre the backward passes of all operations naturally handled by PyTorch or did it require manual implementations? What about numerical stability?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review : ). Please, see the global rebuttal, it should address most your comments. \n\nI believe the only issue left unaddressed is the question about numerical stability. This is a good catch, and something we didn't touch on in the paper. Since we leverage PyTorch for (almost all) of our operations, we inherit all the properties of PyTorch's underlying implementations. Lattice tensor convolution, for example, is the sum of a small number number of cartesian convolutions. If we assume PyTorch's implementation of convolution is stable, then we can reasonably assume that the resulting lattice convolution is stable. This is not a completely formal argument, but could be formalized better if appropriate for the final submission. "}]

Author rebuttal:
First of all, I’d like to thank the reviewers for their time and detailed reviews. We will first address comments common to multiple reviewers.
 
###  Derivatives 
Multiple reviewers pointed out some variation of concern towards the derivative computation. To clarify this, all of the computation for derivatives are handled by PyTorch. In earlier iterations of this work, some derivative computation was explicit, however we opted to rely on PyTorch for derivative computation; writing a new layer with a custom backwards pass (especially for something like the LatticeConvolution layer), is non-trivial (we noticed no significant performance difference when doing this for some test cases).  

There would, however, be a benefit in terms of memory consumption, as fewer auxiliary tensors need to be kept for the backwards pass. We will expand the discussion around derivative computation, then provide the additional theory for these computations (at least) in the supplementary material. 
 
### Graph convolution and other missed references: 
We missed this connection. We will provide, at the very least, a discussion on graph convolutions and how they fit in with our work. We will cite the relevant information in the following works 
* https://arxiv.org/abs/2207.05209 
* https://arxiv.org/abs/2305.19663 
* https://arxiv.org/abs/1704.01212 
 
### References: 
 [1] The processing of hexagonally sampled two-dimensional signals, Proceedings of the IEEE 67 (6) (1979) 930–949. doi:10.1109/PROC.1979.11356.

 [2] Middleton, Lee, and Jayanthi Sivaswamy. Hexagonal image processing: A practical approach. Springer Science & Business Media, 2005.



Meta-review: The authors propose a framework and a software library that introduces standard machine learning operations (i.e. convolutions) for non-Cartesian data. The majority of reviewers were very positive about this work. While there was some concern about potential applications, this work adds a set of new primitives that could be applied to many problems with non-Cartesian grid structures.
Decision: Accept (poster)