Generalizing the Convolution Operator
to extend CNNs to Irregular Domains

Jean-Charles Vialatte1,2 , Vincent Gripon2 , Grégoire Mercier2

arXiv:1606.01166v4 [cs.LG] 25 Oct 2017

1

Cityzen Data
Guipavas, Brittany, France

2

Telecom Bretagne
Brest, Brittany, France

1

2

jean-charles.vialatte@cityzendata.com
{jc.vialatte, vincent.gripon, gregoire.mercier}@telecom-bretagne.eu

Abstract
Convolutional Neural Networks (CNNs) have become the state-of-the-art in supervised learning vision tasks. Their convolutional filters are of paramount importance
for they allow to learn patterns while disregarding their locations in input images.
When facing highly irregular domains, generalized convolutional operators based
on an underlying graph structure have been proposed. However, these operators do
not exactly match standard ones on grid graphs, and introduce unwanted additional
invariance (e.g. with regards to rotations). We propose a novel approach to generalize CNNs to irregular domains using weight sharing and graph-based operators.
Using experiments, we show that these models resemble CNNs on regular domains
and offer better performance than multilayer perceptrons on distorded ones.

1

Introduction

CNNs[1] are state-of-the-art for performing supervised learning on data defined on lattices [2].
Contrary to classical multilayer perceptrons (MLPs) [3], CNNs take advantage of the underlying
structure of the inputs. When facing data defined on irregular domains, CNNs cannot always be
directly applied even if the data may present an exploitable underlying structure.
An example of such data are spatio-temporal time series generated by a set of Internet of Things
devices. They typically consist of datapoints irregularly spaced out on a Euclidean space. As a result,
a graph G can be defined where the vertices are the devices and the edges connect neighbouring ones.
Other examples include signals on graphs including brain imaging, transport networks, bag of words
graphs. . . In all these examples, a signal can generally be seen as a vector in Rd where d is the order
of the graph. As such, each vertex is associated with a coordinate, and the edges weights represent
some association between the corresponding vertices.
Disregarding the graph G, MLPs can be applied on these datasets. We are interested in defining
convolutional operators that are able to exploit G as well as a possible embedding Euclidean space.
Our motivation is to imitate the gain of performance allowed by CNNs over MLPs on irregular
domains.
In graph signal processing, extended convolutional operators using spectral graph theory [4] have
been proposed [5]. These operators have been applied to deep learning [6] and obtain performance
similar to CNNs on regular domains, despite the fact they differ from classical convolutions. However,
for slightly distorted domains, the obtained operators become non-localized, thus failing taking
account of the underlying structure.
1

We propose another approach that generalizes convolutional operators by taking into account G.
Namely, we make sure that the proposed solution has properties inherent to convolutions: linearity,
locality and kernel weight sharing. We then apply it directly to the graph structure. We use it as a
substitution of a convolutional layer in a CNN and stress our resulting technique on comparative
benchmarks, showing a significant improvement compared with a MLP. The obtained operator
happens to exactly be the classical convolutional one when applied on regular domains.
The outline of the paper is as follows. In Section 2, we discuss related work. In Section 3 we introduce
our proposed operator. In Section 4 we explain how to apply it to CNN-like structures. Section 5
contains the experiments. Section 6 is a conclusion.

2

Related Works

For graph-structured data, Bruna et al. [6] have proposed an extension of the CNN using graph signal
processing theory [5]. Their convolution is defined in the spectral domain related to the Laplacian
matrix of the graph. As such, in the case where the graph is a lattice, the construction is analogous to
the regular convolution defined in the Fourier domain. The operation is defined as spectral multipliers
obtained by smooth interpolation of a weight kernel, and they explain how it ensures the localization
property. In that paper, they also define a construction that creates a multi-resolution structure of
a graph, for allowing it to support a deep learning architecture. Henaff et al. [7] have extended
Bruna’s spectral network to large scale classification tasks and have proposed both supervised and
unsupervided methods to find an underlying graph structure when it isn’t already given.
However, when the graph is irregular, they partly lose the localization property of their convolution is
partially lost. As the spectral domain is undirected with respect to the graph domain, some sort of
rotation invariances are also introduced. Hence, the results in the graph domain aren’t ressembling to
those of a convolution. In our case, we want to define a convolution supported locally. Moreover, we
want that every input can be defined on a different underlying graph structure, so that the learnt filters
can be applied on data embedded in the same space regardless of what structure have supported the
convolution during the training.
These properties are also retained by the convolution defined in the ShapeNet paper[8], which defines
a convolution for data living on non-euclidean manifolds. I.e their construction does maintain the
locality and allow for reusing the learnt filters on other manifolds. However, it requires at least
a manifold embedding of the data and a geodesic polar coordinates system. Although being less
specific, our proposed method will be a strict generalization of CNN in the sense that CNNs are a
special case of it.
In the case where the data is sparse, Graham [9] has proposed a framework to implement a spatially
sparse CNN efficiently. If the underlying graph structure is embedded into an Euclidean space, the
convolution we propose in this paper can be seen as spatially sparse too, in the sense that the data has
only non-zero coordinates on the vertices of the graph it is defined on. In our case we want to define
a convolution for which the inputs can have values on any point of the embedding space, whereas in
the regular case inputs can only have values on vertices of an underlying grid.

3
3.1

Proposed convolution operator
Definitions

Let S be a set of points, such that each one defines a set of neighbourhoods.
An entry e of a dataset D is a column vector that can be of any size, for which each dimension
represents a value taken by e at a certain point u ∈ S. u is said to be activated by e. A point u can be
associated to at most one dimension of e. If it is the ith dimension of e, then we denote the value
taken by e at u by either eu or ei . D is said to be embedded in S.

We say that two entries e and e0 are homogeneous if they have the same size and if their dimensions
are always associated to the same points.
2

3.2

Formal description of the generalized convolution

Let’s denote by C a generalized convolution operator.We want it to observe the following conditions:
• Linearity
• Locality
• Kernel weight sharing
As C must be linear, then for any entry e, there is a matrix W e such that C(e) = W e e. Unless the
entries are all homogeneous, W e depends on e. For example, in the case of regular convolutions on
images, W is a Toeplitz matrix and doesn’t depend on e.
In order to meet the locality condition, we first want that the coordinates of C(e) have a local meaning.
To this end, we impose that C(e) lives in the same space as e, and that C(e) and e are homogeneous.
Secondly, for each u, we want C(e)u to be only function of values taken by e at points contained in a
certain neighbourhood of u. It results that rows of W e are generally sparse.
Let’s attribute to C a kernel of n weights in the form of a row vector w = (w1 , w2 , .., wn ), and let’s
define the set of allocation matrices A as the set of binary matrices that have at most one non-zero
coordinate per column. As C must share its weights across the activated points, then for each row
Wie of W e , there is an allocation matrix Aei ∈ A such that Wie = wAei . To maintain locality, the jth
column of Aei must have a non-zero coordinate if and only if the ith and jth activated points are in a
same neighbourhood.
Let’s Ae denotes the block column vector that has the matrices Aei for attributes, and let’s ⊗ denotes
the tensor product. Hence, C is defined by a weight kernel w and an allocation map e 7→ Ae that
maintains locality, such that
C(e) = (w ⊗ Ae ) . e
3.3

(1)

The underlying graph that supports the generalized convolution

As vertices, the set of activated points of an entry e defines a complete oriented graph that we call Ge .
If all the entries are homogeneous, then Ge is said to be static. In this case, we note G. Otherwise,
there can be one different graph per entry so the kernel of weights can be re-used for new entries
defined on different graphs.
Suppose we are given u 7→ Vu which maps each u ∈ S to a neighbourhood Vu . We then define GeV
as the subgraph of Ge such that it contains the edge (u0 , u) if and only if u0 ∈ Vu . Let aV : e 7→ Ae
be an allocation map such that the jth column of Aei have a non-zero coordinate if and only if (ei , ej )
is an edge of GeV .

Then the generalized convolution of e by the couple (w, aV ) is supported by the underlying graph
GeV in the sense that WVe = w ⊗ aV (e) is its adjacency matrix. Note that the underlying graph of a
regular convolution is a lattice.

Also note that the family (Vu )u∈S can be seen as local receptive fields for the generalized convolution,
and that the map aV can be seen as if it were distributing the kernel weights into each Vu .
Remarks
The generalized convolution has been defined here as an operation between a kernel weight and a
vector. If G = (E, V ) denotes a graph, then such operator ∗ with respect to a third rank tensor A
could also have been defined as a bilinear operator between two graph signals f, g ∈ RE :
f ∗ g = (f > ⊗ A) . g
>

∀v ∈ V, (f ∗ g)(v) = f Av g, with Av ∈ A

(2)
(3)

Note that the underlying graph depends on the entry. So the learnt filter w is reusable regardless of
the entry’s underlying graph structure. This is not the case for convolutions defined on fixed graphs
like in [6, 7].
3

3.4

Example of a generalized convolution shaped by a rectangular window

Let E be a two-dimensional Euclidean space and let’s suppose here that S = E.
Let’s denote by CR , a generalized convolution shaped by a rectangular window R. We suppose that
its weight kernel w is of size Nw = (2p + 1)(2q + 1) and that R is of width (2p + 1)µ and height
(2q + 1)µ, where µ is a given unit scale.
Let Gep,q be the subgraph of Ge such that it contains the edge (u0 , u) if and only if |u0x −ux | ≤ (p+ 12 )µ
and |u0y − uy | ≤ (q + 12 )µ. In other terms, Gep,q connects a vertex u to every vertex contained in R
when centered on u.
Then, we define CR as being supported by Gep,q . As such, its adjacency matrix acts as the convolution
operator. At this point, we still need to affect the kernel weights to its non-zero coordinates, via
the edges of Gep,q . This amounts for defining explicitely the map e 7→ Ae for CR . To this end, let’s
consider the grid of same size as that rectangle, which breaks it down into (2p + 1)(2q + 1) squares
of side length µ, and let’s associate a different weight to each square. Then, for each edge (u0 , u), we
affect to it the weight associated with the square within which u0 falls when the grid is centered on u.
This procedure allows for the weights to be shared across the edges. It is illustrated on figure 1.
Note that if the entries are homogeneous and the activated points are vertices of a regular grid, then
the matrix W , independant of e, is a Toepliz matrix which acts as a regular convolution operator on
the entries e. In this case, CR is just a regular convolution. For example, this is the case in section 3.5.

µ
µ

(2p + 1)µ

S=E

S=E

Figure 1: Example of a moving grid. The grid
defines the allocation of the kernel weights.

3.5

Figure 2: On regular domains, the moving grid
allocates the weights similarly to the moving window of a standard convolution.

Link with the standard convolution on image datasets

Let D be an image dataset. Entries of D are homogeneous and their dimensions represent the value
at each pixel. In this case, we can set S = E, of dimension 2, such that each pixel is located at entire
coordinates. More precisely, if the images are of width n and height m, then the pixels are located at
coordinates (i, j) ∈ {0, 1, 2, ..., n}x{0, 1, 2, ..., m}. Hence, the pixels lie on a regular grid and thus
are spaced out by a constant distance µ = 1.
Let’s consider the static underlying graph Gp,q and the generalized convolution by a rectangular
window CR , as defined in the former section. Then, applying the same weight allocation strategy will
lead to affect every weight of the kernel into the moving window R. Except on the border, one and
only one pixel will fall into each square of the moving grid at each position, as depicted in figure 2.
Indeed, R behaves exactly like a moving window of the standard convolution, except that it considers
that the images are padded with zeroes on the borders.
4

4
4.1

Application to CNNs
Neural network interpretation

Let Ld and Ld+1 be two layers of neurons, such that forward-propagation is defined from Ld to
Ld+1 . Let’s define such layers as a set of neurons being located in S. These layers must contain as
many neurons as points that can be activated. In other terms, S ∼
= Ld ∼
= Ld+1 . As such, we will
abusively use the term of neuron instead of point.

Ld

Ld+1

Figure 3: Generalized convolution between two layers of neurons.
The generalized convolution between these two layers can be interpreted as follow. An entry e
activates the same N neurons in each layer. Then, a convolution shape takes N positions onto Ld ,
each position being associated to one of the activated neurons of Ld+1 . At each position, connections
are drawn from the activated neurons located inside the convolution shape in destination to the
associated neuron. And a subset of weights from w are affected to these connections, according to a
weight sharing strategy defined by an allocation map. Figure 3 illustrates a convolution shaped by a
rectangular window.
The forward and backward propagation between Ld and Ld+1 are applied using the described neurons
and connections. After a generalized convolution operation, an activation function is applied on the
output neurons. Then a pooling operation is done spatially: the input layer is divided into patches of
same size, and all activated neurons included in this patch are pooled together. Unlike a standard
pooling operation, the number of activated neurons in a patch may vary.
Generalized convolution layers can be vectorized. They can have multiple input channels and multiple
feature maps. They shall naturally be placed into the same kind of deep neural network structure than
in a CNN. Thus, they are for the irregular input spaces what the standard convolution layers are for
regular input spaces.
4.2

Implementation

There are two main strategies to implement the propagations. The first one is to start from (1), derive
it and vectorize it. It implies handling semi-sparse representations to minimize memory consumption
and to use adequate semi-sparse tensor products.
Instead, we decide to use the neural network interpretation and the underlying graph structure whose
edges amount for neurons connections. By this mean, the sparse part of the computations is included
via the use of this graph. Also, computations on each edge can be parallelized.
5

4.3

Forward and back propagation formulae

Let’s first recall the propagation formulae from a neural network point of view.
Let’s denote by eu the value of a neuron of Ld located at u ∈ S, by fv for a neuron of Ld+1 , and by
gv if this neuron is activated by the activation function σ.
We denote by prev(v) the set neurons from the previous layer connected to v, and by next(u) those of
the next layer connected to u. wuv is the weight affected to the connection between neurons u and v.
b is the bias term associated to Ld+1 .
After the forward propagation, values of neurons of Ld+1 are determined by those of Ld :
X
fv =
eu wuv

(4)

u∈prev(v)

gv = σ(fv + b)

(5)

Thanks to the chain rule, we can express derivatives of a layer with those of the next layer:
δv =

∂E
∂E ∂gv
=
=
∂fv
∂gv ∂fv
X ∂E
∂E
=
∂eu
∂fv
v∈next(u)

∂E 0
σ (fv + b)
∂gv
X
∂fv
=
δv wuv
∂eu

(6)
(7)

v∈next(u)

We call edges(w) the set of edges to which the weight w is affected. If ω ∈ edges(w), fω+ denotes
the value of the destination neuron, and eω− denotes the value of the origin neuron.
The back propagation allows to express the derivative of any weight w:
∂E
=
∂w

X
ω∈edges(w)

∂E ∂fω+
=
∂fω+ ∂w

X

δ ω + eω −

(8)

ω∈edges(w)

X ∂E ∂gv
X
∂E
=
=
δv
∂b
∂gv ∂b
v
v

(9)

The sets prev(v), next(u) and edges(w) are determined by the graph structure, which in turn is
determined beforehand by a procedure like the one described in section 3.4. The particularization of
the propagation formulae with these sets is the main difference with the standard formlulae.
4.4

Vectorization

Computations are done per batch of entries B. Hence, the graph structure used for the computations
must contain the weighted edges of all entries e ∈ B. If necessary, entries of B are made homogeneous: if a neuron u is not activated by an entry e but is activated by another entry of B, then eu is
defined and is set to zero.
The third-rank tensor counterparts of e, f , and g are thus denoted by E, F and G. Their third dimension
indexes the channels (input channels or feature maps). Their submatrix along the neuron located at
x ∈ S are denoted Ex , Fx and Gx , rows are indexing entries and columns are indexing channels. The
counterparts of w and b are W and β. The first being a third-rank tensor and the second being a vector
with one value per feature map. βe denotes the 3D tensor obtained by broadcasting β along the two
other dimensions of F. Ww denotes the submatrix of W along the kernel weight w. Its rows index the
feature maps and its columns index the input channels.
With these notations, the convolution formulae (1) rewrites:
C(E) = (W ⊗ AE )  E

(10)

⊗ and  being tensor products. ⊗ is contracted along the dimensions that index the kernel weights,
and  is contracted along the dimensions that index the points present in the entries.
6

The vectorized counterparts of the formulae from section 4.3 can be obtained in the same way:
X
(11)
Fv =
Eu W>
wuv
u∈prev(v)

e
G = σ(F + β)
 

0
∂E
∂E
e
∆=
=
◦ σ (F + β)
∂F
∂G


X
∂E
∆v Wuv
=
∂E u
v∈next(u)


X
∂E
=
∆>
ω + Eω −
∂W w
ω∈edges(w)
!
X X
∂E
=
∆v
∂β
v
j

(12)



(13)
(14)
(15)

(16)

j-th column

Where ◦ and > respectively denotes Hadamard product and transpose.

5

Experiments

In order to measure the gain of performance allowed by the generalized CNN over MLP on irregular
domains, we made a series of benchmarks on distorded versions of the MNIST dataset [10], consisting
of images of 28x28 pixels. To distort the input domain, we plunged the images into a 2-d euclidean
space by giving entire coordinates to pixels. Then, we applied a gaussian displacement on each
pixel, thus making the data irregular and unsuitable for regular convolutions. For multiple values of
standard deviation of the displacement, we trained a generalized CNN and compared it with a MLP
that has the same number of parameters. We choosed a simple yet standard architecture in order to
better see the impact of generalized layers.
The architecture used is the following: a generalized convolution layer with relu [11] and max pooling,
made of 20 feature maps, followed by a dense layer and a softmax output layer. The generalized
convolution is shaped by a rectangular window of width and height 5µ where the unit scale µ is
chosen to be equal to original distance between two pixels. The max-pooling is done with square
patches of side length 2µ. The dense layer is composed of 500 hidden units and is terminated by
relu activation as well. In order to have the same number of parameters, the compared MLP have 2
dense layers of 500 hidden units each and is followed by the same output layer. For training, we used
stochastic gradient descent [12] with Nesterov momentum [13] and a bit of L2 regularization [14].
2.2
2

MLP
G-CNN

Error

1.8
1.6
1.4
1.2
CNN

1

+
0

1

2

3

4

5

6

10−1

100

101

102

Standard deviation used for the domain distortion

Figure 4: Results for Generalized CNN and MLP
The plot drawn on figure 4 illustrates the gain of performance of a generalized convolutional layer
over a dense layer with equal number of parameters. After 15 epochs for both, it shows that the
7

generalized CNN on a distorded domain performs better than the MLP. Indeed, in the case of no
domain distortion, the score is the same than a CNN with zero-padding. The error rate goes up a bit
with distortion. But even at 200µ, the generalized CNN still performs better than the MLP.

6

Conclusion and future work

In this paper, we have defined a generalized convolution operator. This operator makes possible to
transport the CNN paradigm to irregular domains. It retains the proprieties of a regular convolutional
operator. Namely, it is linear, supported locally and uses the same kernel of weights for each local
operation. The generalized convolution operator can then naturally be used instead of convolutional
layers in a deep learning framework. Typically, the created model is well suited for input data that
has an underlying graph structure.
The definition of this operator is flexible enough for it allows to adapt its weight-allocation map to
any input domain, so that depending on the case, the distribution of the kernel weight can be done in
a way that is natural for this domain. However, in some cases, there is no natural way but multiple
acceptable methods to define the weight allocation. In further works, we plan to study these methods.
We also plan to apply the generalized operator on unsupervised learning tasks.
Acknowledgements
I would like to thank my academic mentors, Vincent Gripon and Grégoire Mercier who helped me
in this work, as well as my industrial mentor, Mathias Herberts who gave me insights in view of
applying the designed model to industrial datasets.
This work was partly funded by Cityzen Data, the company behind the Warp10 platform, and by
the ANRT (Agence Nationale de la Recherche et de la Technologie) through a CIFRE (Convention
Industrielle de Formation par la REcherche), and also by the European Research Council under the
European Union’s Seventh Framework Program (FP7/2007-2013) / ERC grant agreement number
290901.

References
[1] Y. LeCun, L. Bottou, Y. Bengio, and P. Haffner, “Gradient-based learning applied to document
recognition,” Proceedings of the IEEE, vol. 86, no. 11, pp. 2278–2324, 1998.
[2] A. Krizhevsky, I. Sutskever, and G. E. Hinton, “Imagenet classification with deep convolutional
neural networks,” in Advances in neural information processing systems, pp. 1097–1105, 2012.
[3] K. Hornik, M. Stinchcombe, and H. White, “Multilayer feedforward networks are universal
approximators,” Neural networks, vol. 2, no. 5, pp. 359–366, 1989.
[4] F. R. K. Chung, Spectral Graph Theory (CBMS Regional Conference Series in Mathematics,
No. 92). American Mathematical Society, 1996.
[5] D. I. Shuman, S. K. Narang, P. Frossard, A. Ortega, and P. Vandergheynst, “The emerging field
of signal processing on graphs: Extending high-dimensional data analysis to networks and other
irregular domains,” IEEE Signal Processing Magazine, vol. 30, no. EPFL-ARTICLE-189192,
pp. 83–98, 2013.
[6] J. Bruna, W. Zaremba, A. Szlam, and Y. LeCun, “Spectral networks and locally connected
networks on graphs,” arXiv preprint arXiv:1312.6203, 2013.
[7] M. Henaff, J. Bruna, and Y. LeCun, “Deep convolutional networks on graph-structured data,”
arXiv preprint arXiv:1506.05163, 2015.
[8] J. Masci, D. Boscaini, M. Bronstein, and P. Vandergheynst, “Shapenet: Convolutional neural
networks on non-euclidean manifolds,” tech. rep., 2015.
[9] B. Graham, “Spatially-sparse convolutional neural networks,” arXiv preprint arXiv:1409.6070,
2014.
[10] Y. LeCun, C. Cortes, and C. J. Burges, “The mnist database of handwritten digits,” 1998.
[11] X. Glorot, A. Bordes, and Y. Bengio, “Deep sparse rectifier neural networks,” in International
Conference on Artificial Intelligence and Statistics, pp. 315–323, 2011.
8

[12] L. Bottou, “Large-scale machine learning with stochastic gradient descent,” in Proceedings of
COMPSTAT’2010, pp. 177–186, Springer, 2010.
[13] I. Sutskever, J. Martens, G. Dahl, and G. Hinton, “On the importance of initialization and
momentum in deep learning,” in Proceedings of the 30th international conference on machine
learning (ICML-13), pp. 1139–1147, 2013.
[14] A. Y. Ng, “Feature selection, l 1 vs. l 2 regularization, and rotational invariance,” in Proceedings
of the twenty-first international conference on Machine learning, p. 78, ACM, 2004.

9

