Signal Processing - July 2017 - 20

[24] and [25]). Many methods for nonlinear dimensionality
setting, a generalization of convolution in the spatial domain
reduction consist of two steps: first, they start with conusing local charting [46]-[48] appears to be more appropriate.
structing a representation of local affinity of the data points
(typically, a sparsely connected graph). Second, the data
Brief history
points are embedded into a low-dimensional space, trying to
The main focus of this review is on this second class of probpreserve some criterion of the original affinity. For example,
lems, namely, learning functions on non-Euclidean structured
spectral embeddings tend to map points with many connecdomains, and, in particular, attempts to generalize the popular
tions between them to nearby locations, and multidimensionCNNs to such settings. The first attempts to generalize neural
al scaling (MDS)-type methods try to
networks to graphs we are aware of are due
preserve global information, such as graph
to Gori et al. [49], who proposed a scheme
Today, deep learning has
geodesic distances. Examples of manifold
matured into a technology combining recurrent neural networks (RNNs)
learning include different flavors of MDS
and random walk models. This approach
that is widely used in
[26], locally linear embedding [27], stowent almost unnoticed, reemerging in a
commercial applications.
chastic neighbor embedding [28], spectral
modern form in [50] and [51] due to the
embeddings, such as Laplacian eigenmaps
renewed recent interest in deep learning.
[29] and diffusion maps [30], and deep models [31]. Instead
The first formulation of CNNs on graphs is due to Bruna et al.
of embedding the vertices, the graph structure can be pro[52], who used the definition of convolutions in the spectral
cessed by decomposing it into small subgraphs called motifs
domain. Their article, while being of conceptual importance,
[36] or graphlets [37]. Finally, most recent approaches [32]-
came with significant computational drawbacks that fell short
[34] tried to apply the successful word-embedding model
of a truly useful method. These drawbacks were subsequently
[35] to graphs.
addressed in the follow-up works of Henaff et al. [44] and
In some cases, the data are presented as a manifold or
Defferrard et al. [45]. In the latter article, graph CNNs (GCNNs)
graph at the outset, and the first step of constructing the affinallowed achieving some state-of-the-art results.
ity structure described previously is unnecessary. For instance,
In a parallel effort in the computer vision and graphics
in computer graphics and vision applications, one can analyze
community, Masci et al. [47] showed the first CNN model on
3-D shapes represented as meshes by constructing local geomeshed surfaces, resorting to a spatial definition of the convometric descriptors capturing, e.g., curvature-like properties
lution operation based on local intrinsic patches. Among other
[38], [39]. In social network analysis applications the topologiapplications, such models were shown to achieve state-of-thecal structure of the social graph representing the social relaart performance in finding correspondence between deformable
tions between people carries important insights allowing, e.g.,
3-D shapes. Follow-up works proposed different construction of
to classify the vertices and detect communities [40]. In naturalintrinsic patches on point clouds [48], [53] and general graphs [54].
language processing, words in a corpus can be represented by
The interest in deep learning on graphs or manifolds has
the co-occurrence graph, where two words are connected if
exploded in the past year, resulting in numerous attempts to
they often appear near each other [41].
apply these methods to a broad spectrum of problems ranging
from biochemistry [55] to recommender systems [56]. Because
Data on a domain
such applications originate in different fields that usually do
Our second class of problems deals with analyzing functions
not cross-fertilize, publications in this domain tend to use difdefined on a given non-Euclidean domain. We can further
ferent terminology and notation, making it difficult for a newbreak down such problems into two subclasses: problems
comer to grasp the foundations and current state-of-the-art
where the domain is fixed and those where multiple domains
methods. We believe that our article comes at the right time,
are given. For example, assume that we are given the geoattempting to systemize and bring some order into the field.
graphic coordinates of the users of a social network, represented as a time-dependent signal on the vertices of the social
Signal processing, differential geometry,
graph. An important application in location-based social netand graph theory
works is to predict the position of the user given his or her
Geometric deep-learning frameworks dealt with in this paper are
past behavior as well as that of his or her friends [42]. In this
based on notions in differential geometry and graph theory.
problem, the domain (social graph) is assumed to be fixed;
Unfortunately, these topics are insufficiently known in the signal
methods of signal processing on graphs, which have previousprocessing community, and to our knowledge, there is no introly been reviewed in IEEE Signal Processing Magazine [43],
ductory-level reference treating these so different structures in a
can be applied to this setting, in particular, to define an
common way. One of our goals is to provide an accessible overoperation similar to convolution in the spectral domain. This,
view of these models, resorting as much as possible to the
in turn, allows generalizing CNN models to graphs [44], [45].
intuition of traditional signal processing.
In computer graphics and vision applications, finding similariOne of the key differences between Euclidean and nonty and correspondence between shapes are examples of the
Euclidean learning settings is the lack of traditional operasecond subclass of problems: each shape is modeled as a mantions such as convolutions. Various non-Euclidean convolutional
ifold, and one has to work with multiple such domains. In this
architectures differ in the way a convolution-like operation is
20

IEEE SIGNAL PROCESSING MAGAZINE

July 2017

Table of Contents for the Digital Edition of Signal Processing - July 2017