Geometric deep learning: going beyond Euclidean data（几何深度学习：超越欧几里得数据）
摘要：
许多科学领域研究具有非欧几里德空间的底层结构的数据。一些例子包括计算社会科学中的社会网络、通信中的传感器网络、脑成像中的功能网络、遗传学中的调节网络以及计算机图形学中的网状表面。在许多应用中，此类几何数据庞大而复杂（在社交网络中，规模达数十亿），是机器学习技术的自然目标。特别是，我们希望使用深度神经网络，它最近被证明是解决计算机视觉、自然语言处理和音频分析等广泛问题的强大工具。然而，这些工具在具有潜在欧几里德或网格状结构的数据上，以及在将这些结构的不变性构建到用于对其建模的网络中的情况下，最为成功。
几何深度学习是试图将（结构化）深度神经模型推广到非欧几里德域（如图和流形）的新兴技术的总称。本文的目的是概述几何深度学习问题的不同示例，并提出该新兴领域中可用的解决方案、关键难点、应用和未来的研究方向。
1 介绍
“深度学习”是指通过分层或多层的方式从简单的概念中构建复杂的概念来学习这些概念。人工神经网络是这种深层多层结构的普遍实现。在过去几年中，现代基于GPU的计算机不断增长的计算能力和大型训练数据集的可用性，使我们能够成功地训练具有多层次和多*度的神经网络[1]。这导致了从语音识别[2]、[3]和机器翻译[4]到图像分析和计算机视觉[5]、[6]、[7]、[8]、[9]、[10]、[11]等一系列任务的质的突破（读者可以参考[12]、[13]了解更多成功应用深度学习的例子）。如今，深度学习已经成熟成为一项广泛应用于商业应用的技术，包括苹果iPhone中的Siri语音识别、谷歌文本翻译和基于MobileEye Vision的自动驾驶汽车技术。
深层神经网络成功的一个关键原因是它们能够通过局部统计利用数据的统计特性，如平稳性和合成性，这些特性存在于自然图像、视频和语音中[14]，[15]。这些统计特性与物理学[16]有关，并在卷积神经网络（CNN）[17]、[18]、[19]的特定类别中正式化。在图像分析应用中，人们可以将图像视为欧几里得空间（平面）上的函数，在网格上采样。在该设置中，平稳性归因于平移不变性，局部性归因于局部连通性，而合成性源自网格的多分辨率结构。卷积结构[20]利用了这些特性，它由交替卷积和下采样（池）层构成。卷积的使用具有双重效果。首先，它允许提取跨图像域共享的局部特征，并大大减少了网络中关于通用深层架构的参数数量（因此也减少了过度拟合的风险），而不会牺牲网络的表达能力。其次，卷积结构本身对数据施加了一些先验知识，这些知识似乎特别适合自然图像[21]、[18]、[17]、[19]。
虽然深度学习模型在处理语音、图像或视频等信号时特别成功，其中存在潜在的欧几里德结构，但最近，人们越来越有兴趣尝试将学习应用于非欧几里德几何数据。这类数据出现在许多应用中。例如，在社交网络中，用户的特征可以建模为社交图顶点上的信号[22]。传感器网络是分布式互连传感器的图形模型，其读数被建模为顶点上的时间相关信号。在遗传学中，基因表达数据被建模为调控网络上定义的信号[23]。在神经科学中，图形模型用于表示大脑的解剖结构和功能结构。在计算机图形学和视觉中，三维对象被建模为黎曼流形（曲面），并赋予诸如颜色纹理等属性。
这些数据的非欧几里德性质意味着不存在诸如全局参数化、公共坐标系、向量空间结构或平移不变性等熟悉的属性。因此，在欧几里德情况下被视为理所当然的卷积等基本运算在非欧几里德域上甚至没有得到很好的定义。本文的目的是展示将成功的深度学习方法（如卷积神经网络）的关键要素转换为非欧几里德数据的不同方法。
2 几何学习问题
广义地说，我们可以区分两类几何学习问题。在第一类问题中，目标是描述数据的结构。第二类问题涉及分析在给定非欧几里德域上定义的函数。这两个类是相关的，因为理解域上定义的函数的属性会传递有关域的某些信息，反之亦然，域的结构会对域上的函数施加某些属性。
域结构：作为第一类问题的一个示例，假设给定一组数据点，这些数据点具有嵌入高维欧几里德空间的一些底层低维结构。恢复低维结构通常被称为流形学习或非线性降维，是无监督学习的一个实例。许多非线性降维方法包括两个步骤：首先，它们从构造数据点（通常是稀疏连通图）的局部相关性表示开始。其次，数据点被嵌入到低维空间中，试图保留原始亲和力的某些标准。例如，光谱嵌入倾向于将具有许多连接的点映射到附近的位置，MDS类型的方法试图保留全局信息，如图形测地距离。流形学习的示例包括不同风格的多维标度（MDS）[26]、局部线性嵌入（LLE）[27]、随机邻居嵌入（t-SNE）[28]、谱嵌入，如拉普拉斯特征映射[29]和扩散映射[30]，以及深度模型[31]。最新的方法[32]、[33]、[34]试图将成功的单词嵌入模型[35]应用于图形。不嵌入顶点，可以通过将图结构分解为称为motif[36]或graphles[37]的小子图来处理图结构。
在某些情况下，数据在开始时以流形或图的形式呈现，并且不需要构建上述亲和结构的第一步。例如，在计算机图形学和视觉应用中，可以通过构造局部几何描述符来分析以网格表示的三维形状。G类曲率性质[38]，[39]。在计算社会学等网络分析应用中，代表人与人之间社会关系的社会图的拓扑结构具有重要的见解，例如，允许对顶点进行分类和检测社区[40]。在自然语言处理中，语料库中的单词可以用共现图表示，如果两个单词经常出现在彼此附近，则两个单词是相连的[41]。
域上的数据：我们的第二类问题涉及分析在给定非欧几里德域上定义的函数。我们可以将这些问题进一步细分为两个子类：域固定的问题和多个域给定的问题。例如，假设给定了社交网络用户的地理坐标，表示为社交图顶点上的时间相关信号。在基于位置的社交网络中，一个重要的应用是根据用户过去的行为预测用户的位置，以及他或她的朋友的位置[42]。在这个问题中，假设域（社会图）是固定的；在本杂志[43]中已经回顾过的图形信号处理方法可以应用于该设置，特别是为了定义类似于光谱域中卷积的操作。这反过来又允许将CNN模型推广到图[44]，[45]。
在计算机图形学和视觉应用中，寻找形状之间的相似性和对应性是第二类问题的例子：每个形状都被建模为一个流形，一个形状必须处理多个这样的域。在此设置中，使用局部制图[46]、[47]、[48]在空间域中对卷积进行泛化似乎更合适。
简史：本综述的主要重点是第二类问题，即非欧几里德结构域上的学习函数，特别是试图将流行的CNN推广到此类设置。Scarselli等人[49]首次尝试将神经网络推广到我们已知的图形，他提出了一种结合递归神经网络和随机游走模型的方案。这种方法几乎没有被注意到，在[50]，[51]中以现代形式重新出现，这是因为最近人们对深度学习重新产生了兴趣。图上CNN的第一个公式是由Bruna等人[52]提出的，他使用了谱域中卷积的定义。他们的论文虽然在概念上很重要，但在计算上却有很大的缺陷，无法成为真正有用的方法。这些缺陷随后在Henaff等人[44]和Defferrard等人[45]的后续工作中得到了解决。在后一篇论文中，图形CNN允许实现一些最先进的结果。
在计算机视觉和图形学界的一项并行工作中，Masci等人[47]利用基于局部固有面片的卷积运算的空间定义，展示了网格表面上的第一个CNN模型。在其他应用中，这些模型在发现可变形3D形状之间的对应关系方面表现出了最先进的性能。后续工作提出了点云[53]、[48]和一般图[54]上内在斑块的不同构造。
在过去的一年里，人们对图形或流形的深入学习产生了浓厚的兴趣，因此，人们试图将这些方法应用于从生物化学[55]到推荐系统[56]的一系列问题中。由于这些应用来自不同的领域，通常不会相互影响，因此该领域的出版物往往使用不同的术语和符号，这使得新手很难掌握基础和当前最先进的方法。我们相信，我们的论文来得正是时候，试图系统化并为该领域带来一些秩序。
论文结构：在第三节中，我们首先概述了传统的欧几里德深度学习，总结了关于数据的重要假设，以及它们是如何在卷积网络体系结构中实现的。
在第四节中，我们将讨论非欧几里德世界，然后定义微分几何和图论中的基本概念。这些主题在信号处理界还不太为人所知，据我们所知，还没有一个介绍人级别的参考文献以一种通用的方式处理这些如此不同的结构。我们的目标之一是尽可能借助传统信号处理的直觉，提供这些模型的可访问概述。
在第五至第八节中，我们概述了主要的几何深度学习范式，强调了欧几里得和非欧几里得学习方法之间的相似性和差异。这些方法之间的关键区别在于在图和流形上形成卷积式运算的方式。一种方法是利用卷积定理的类比，在谱域中定义卷积。另一种方法是将卷积视为空间域中的模板匹配。然而，这样的区别远不是明确的：正如我们将看到的那样，一些方法虽然从光谱域中提取其公式，但本质上归结为在空间域中应用滤波器。还可以借助空间频率分析技术，如小波或加窗傅里叶变换，将这两种方法结合起来。
在第九节中，我们展示了从网络分析、粒子物理、推荐系统、计算机视觉和图形领域中选择的问题的示例。在第十节中，我们总结并概述了几何深度学习目前面临的主要挑战和未来的潜在研究方向。为了使论文更具可读性，我们使用插入说明重要概念。最后，读者被邀请访问一个专门的网站geometricdeeplearning.com 获取更多资料、数据和代码示例。
3 欧几里得域的深度学习
几何先验：考虑一个紧凑的 d 维欧几里德域 Ω = [0,1]d ⊂ Rd，在该域上定义了平方可积函数 f ∈ L2(Ω)（例如，在图像分析应用中，图像可以被认为是单位平方Ω = [0,1]2)。我们考虑一个通用的监督学习设置，其中在训练集上观察到一个未知函数 y : L2(Ω) → Y
在监督分类设置中，目标空间Y可以被认为是离散的，其中| Y |是类的数量。在多目标识别设置中，我们可以用表示后验概率p（Y | x）的K维单纯形代替Y。在回归任务中，我们可以考虑y= rm。
在绝大多数计算机视觉和语音分析任务中，对未知函数y有几个重要的先验假设。正如我们将在下面看到的，卷积神经网络结构有效地利用了这些假设。
平稳性：
设 x 是作用于函数 f ∈ L2(Ω) 的平移算子。我们的第一个假设是函数 y 在平移方面是不变的或等变的，这取决于任务。在前一种情况下，对于任何 f ∈ L2(Ω) 和 v ∈ Ω，我们有 y(Tvf) = y(f)。在对象分类任务中通常就是这种情况。在后者中，我们有 y(Tvf) = Tvy(f)，当模型的输出是一个平移可以作用的空间时（例如，在对象定位、语义分割或运动估计的问题中），它是明确定义的）。我们对不变性的定义不应与信号处理中翻译不变系统的传统概念相混淆，后者对应于我们语言中的翻译等变（因为每当输入翻译时，输出就会翻译）。
局部变形和尺度分离：类似地，变形Lτ，其中τ：Ω → Ω 是一个光滑的向量场，作用于L2(Ω) 当 Lτf（x）=f（x− τ（x））。变形可以模拟局部平移、视角变化、旋转和频率变换[18]。
计算机视觉中研究的大多数任务不仅是平移不变/等变的，而且在局部变形方面也是稳定的 [57]、[18]。在平移不变的任务中，我们有
对于所有 f, τ。这里，||∇τ|| 测量给定变形场的平滑度。换句话说，如果输入图像轻微变形，则要预测的数量不会发生太大变化。在翻译等变的任务中，我们有
这个属性比前一个强得多，因为局部变形空间具有高维度，与 d 维平移组相反。
从（3）可以看出，我们可以通过对解调的局部滤波器响应进行下采样而不损失逼近能力，以较低的空间分辨率提取足够的统计数据。这样做的一个重要后果是，可以将远程依赖分解为多尺度局部交互项，从而导致空间分辨率逐渐降低的分层模型。为了说明这个原则，表示为
两个图像像素在相互偏移v处的联合分布。在存在长期依赖的情况下，这种联合分布对于任何v都是不可分离的。然而，之前的变形稳定性表明Y（x1，x2；v）≈ Y（x1，x2；v（1+€）表示小的€。换句话说，尽管自然图像中确实存在长距离相关性，并且对对象识别至关重要，但它们可以在不同的尺度上被捕获和下采样。这种局部变形稳定性原理已在计算机视觉领域的CNN以外的模型中得到利用，例如，可变形部件模型[58]。
实际上，欧几里德域Ω 使用具有n个点的规则网格进行离散；平移和变形操作符仍然定义良好，因此上述属性在离散设置中保持不变。
卷积神经网络：在卷积神经网络中，对局部平移的平稳性和稳定性都得到了充分利用（见插入部分1）。CNN由几个形式为g=CΓ（f）的卷积层组成，作用于P维输入f（x）=（f1（x），…，fp（x））通过应用滤波器组Γ=（γl，l’），l=1,…,q、 l’=1,…,p和点态非线性ξ，
产生q维输出g（x）=（g1（x）,…,gq（x））通常被称为特征映射。在这里
表示标准卷积。根据局部变形先验，滤波器Γ具有紧凑的空间支撑。
此外，可使用下采样或池化层g＝P（f），定义为
其中N（x）⊂ Ω 是围绕x的邻域，P是置换不变函数，如Lp范数（在后一种情况下，选择P=1,2或∞ 结果为平均、能量或最大池）。
卷积网络由几个卷积层和可选的池层组成，获得一个通用的层次表示
其中 Θ = {Γ(1), . . . ,Γ(K)} 是网络参数（所有滤波器系数）的超向量。如果该模型包含多个层，则据说该模型是深的，尽管这个概念相当模糊，人们可以找到少至几层和多至数百层的 CNN 示例 [11]。输出特征享有平移不变性/协方差，这取决于空间分辨率是通过池化逐渐丢失还是保持固定。此外，如果将卷积张量指定为复小波分解算子并使用复模作为逐点非线性，则可以证明可以获得对局部变形的稳定性 [17]。尽管这种稳定性并未针对通用的紧凑支持的卷积张量得到严格证明，但它支持了 CNN 架构在各种计算机视觉应用中取得的成功经验 [1]。
在监督学习任务中，可以通过最小化训练集 {fi, yi}i∈i 上的任务特定成本 L 来获得 CNN 参数，
例如，L(x, y) = kx − yk。如果模型足够复杂并且训练集具有足够的代表性，那么当将学习到的模型应用于以前看不见的数据时，人们期望 U(f) ≈ y(f)。尽管 (10) 是一个非凸优化问题，但随机优化方法提供了出色的经验性能。了解优化问题 (10) 的结构并为其解决方案寻找有效的策略是深度学习的一个活跃研究领域 [62]、[63]、[64]、[65]、[66]。
CNN 解释其在众多任务中取得成功的一个关键优势是，CNN 所基于的几何先验导致了避免维度灾难的学习复杂性。由于平稳性和局部变形先验，每一层的线性算子具有恒定数量的参数，与输入大小 n（图像中的像素数）无关。此外，由于多尺度分层属性，层数以 O(logn) 的速度增长，导致 O(logn) 参数的总学习复杂度。
4 流行和图的几何形状
我们的主要目标是将 CNN 类型的结构推广到非欧几里德域。在本文中，通过非欧几里德域，我们指的是两种原型结构：流形和图。虽然出现在非常不同的数学领域（分别是微分几何和图论），但在我们的上下文中，这些结构具有几个共同的特征，我们将在整个评论中尝试强调这些特征。
[IN1] 卷积神经网络：CNN 是目前在各种任务中最成功的深度学习架构之一，尤其是在计算机视觉方面。计算机视觉应用中使用的典型 CNN（见图 1）由多个卷积层 (6) 组成，将输入图像通过一组滤波器 Γ 后跟逐点非线性 ξ（通常，半整流器 ξ(z) = max (0, z) 被使用，尽管从业者已经尝试了多种选择 [13]）。该模型还可以包括一个偏置项，这相当于向输入添加一个常数坐标。由 K 个卷积层组成的网络组合在一起 U(f) = (CΓ(K) . . ◦ CΓ(2) ◦ CΓ(1))(f) 产生与 w.r.t.平移和近似协变到局部变形。需要协方差的典型计算机视觉应用是语义图像分割 [8] 或运动估计 [59]。
在需要不变性的应用中，例如图像分类 [7]，卷积层通常与池化层 (8) 交错，逐渐降低通过网络的图像的分辨率。或者，可以将卷积和下采样集成到单个线性算子（带步幅的卷积）中。最近，一些作者还试验了使用插值核 [60] 来增加空间分辨率的卷积层。通过模仿所谓的算法[61]，也称为扩张卷积，可以有效地学习这些内核。
[FIGS1] 计算机视觉应用中使用的典型卷积神经网络架构（图复制自 [1]）
流形：粗略地说，流形是局部欧几里得的空间。最简单的例子之一是模拟我们星球的球面：围绕一个点，它似乎是平面的，这让几代人相信地球是平坦的。正式地说，一个（可微的）d 维流形 X 是一个拓扑空间，其中每个点 x 都有一个邻域，该邻域在拓扑上等价（同胚）到一个 d 维欧几里得空间，称为切线空间，用 TxX 表示（见图 1 ， 顶部）。所有点处的切空间的集合（更正式地说，它们的不相交联合）被称为切丛并用 TX 表示。在每个切线空间上，我们定义一个内积 <·,·>TxX：TxX × TxX → R，另外假设它平滑地依赖于位置 x。这种内积在微分几何中被称为黎曼度量，允许对角度、距离和体积进行局部测量。带有度量的流形称为黎曼流形。
需要注意的是，黎曼流形的定义是完全抽象的，不需要在任何空间中进行几何实现。然而，黎曼流形可以通过使用欧几里德空间的结构来推导黎曼度量来实现为欧几里德空间的子集（在这种情况下，它被称为嵌入到该空间中）。著名的纳什嵌入定理保证了任何足够平滑的黎曼流形都可以在足够高维的欧几里得空间中实现[67]。嵌入不一定是唯一的；黎曼度量的两种不同实现称为等距。
嵌入到 R3 中的二维流形（表面）在计算机图形学和视觉中用于描述 3D 对象的边界表面，通俗地称为“3D 形状”。这个术语有点误导，因为这里的“3D”指的是嵌入空间的维数，而不是流形的维数。考虑到这种由无限薄材料制成的形状，不会拉伸或撕裂它的非弹性变形是等距的。等距不影响流形的度量结构，因此，保留可以用黎曼度量（称为内在度量）表示的任何量。相反，与欧几里德空间中流形的具体实现相关的属性称为外在的。
作为这种差异的直观说明，想象一下生活在二维表面上的昆虫（图 1，底部）。另一方面，人类观察者在 3D 空间中看到一个表面——这是一种外在的观点。
图 1. 顶部：二维流形（表面）上的切线空间和切线向量。底部：等距变形示例
流形上的微积分：下一步是考虑定义在流形上的函数。我们对两种类型的函数特别感兴趣： 标量场是流形上的平滑实函数 f : X → R。切向量场 F : X → TX 是将切向量 F(x) ∈ TxX 附加到每个点 x 的映射。正如我们将在下面看到的，切线向量场用于形式化流形上无穷小位移的概念。我们定义流形上标量场和向量场的希尔伯特空间，分别用 L2(X) 和 L2(TX) 表示，具有以下内积：
dx 在这里表示由黎曼度量引起的 d 维体积元素。
在微积分中，导数的概念描述了函数的值如何随着其参数的无穷小变化而变化。区分经典微积分与微分几何的一大区别是流形上缺乏向量空间结构，这使我们无法天真地使用 f(x+dx) 等表达式。将这些概念推广到流形所需的概念飞跃是需要在切线空间中局部工作。
为此，我们将 f 的微分定义为一个操作符 df : TX → R 作用于切向量场。在每个点 x，微分可以定义为线性泛函（1 型） df(x) = <∇f(x), · >TxX 作用于切向量 F(x) ∈ TxX，它模拟了围绕 x 的小位移.通过将形式应用于切向量，df(x)F(x) = <∇f(x), F(x)>TxX，可以得到作为该位移结果的函数值的变化，并且可以认为作为经典方向导数概念的扩展。
上面定义中的算子 ∇f : L2(X) → L2(TX) 称为固有梯度，类似于定义函数在某一点上最陡峭变化方向的梯度的经典概念，其中唯一的区别是方向现在是切线向量。类似地，内在散度是一个算子 div ：L2(TX) → L2(X) 作用于切向量场并且（形式上）伴随梯度算子 [71]，
在物理上，切线矢量场可以被认为是流形上的物质流。散度测量场在某一点的净流量，允许区分场的“源”和“汇”。最后，拉普拉斯算子（或微分几何术语中的拉普拉斯-贝尔特拉米算子）∆ : L2(X) → L2(X) 是一个算子
作用于标量场。使用关系式（17），很容易看出拉普拉斯算子是自伴的（对称的），
方程 (19) 中的 lhs 在物理学中被称为狄利克雷能量，用于测量流形上标量场的平滑度（参见插页 IN3）。拉普拉斯算子可以解释为一个函数在一个点周围的无穷小球面上的平均值与该点本身的函数值之间的差值。它是数学物理中最重要的算子之一，用于描述热扩散（见插入 IN4）、量子力学和波传播等多种现象。正如我们将在下面看到的，拉普拉斯算子在非欧几里得域的信号处理和学习中起着核心作用，因为它的特征函数概括了经典的傅立叶基，允许对流形和图进行谱分析。
重要的是要注意上述所有定义都是无坐标系的。通过定义切线空间中的基，可以将切线向量表示为 d 维向量，将黎曼度量表示为 d × d 对称正定矩阵。
图和离散微分算子：我们感兴趣的另一种结构是图，它是网络、交互和不同对象之间相似性的流行模型。为简单起见，我们将考虑加权无向图，正式定义为一对 (V,E)，其中 V = {1, . . . , n} 是 n 个顶点的集合，E ⊆ V × V 是边的集合，其中无向图意味着 (i, j) ∈ E iff (j, i) ∈ E。此外，我们关联 a每个顶点 i ∈ V 的权重 ai> 0，每个边 (i, j) ∈ E 的权重 wij≥ 0。
[FIGS2] 二维流形的两种常用离散化：图和三角网格
[IN2] 离散流形上的拉普拉斯算子：在计算机图形和视觉应用中，二维流形通常用于对 3D 形状进行建模。有几种常见的方法可以离散化这种流形。首先，假设在 n 个点对流形进行采样。它们的嵌入坐标 x1, . . . ,xn 称为点云。其次，在这些点上构建一个图，作为它的顶点。图的边代表流形的局部连通性，告诉两个点是否属于一个邻域，例如高斯边权重
流形的几何形状（例如，随着采样密度的增加，图拉普拉斯算子通常不会收敛到流形的连续拉普拉斯算子 [68]）。几何一致的离散化可以通过面 F ∈ V × V × V 的附加结构实现，其中 (i, j, k) ∈ F 意味着 (i, j),(i, k),(k, j) ∈ E . 面的集合将底层连续流形表示为由粘合在一起的小三角形组成的多面体表面。三元组 (V,E,F) 称为三角形网格。要成为流形（流形网格）的正确离散化，每条边必须恰好由两个三角形面共享；如果流形有边界，则任何边界边都必须恰好属于一个三角形。
在三角形网格上，黎曼度量最简单的离散化是通过为每条边指定长度 Lij> 0 来给出的，该长度必须另外满足每个三角形面中的三角不等式。网格拉普拉斯算子由公式 (25) 给出，其中
其中
是Heron公式给出的三角形ijk的面积，而
是三角形ijk的半周长。顶点权重可以解释为局部区域元素（在图2中以红色显示）。请注意，权重（12-13）仅用离散量度表示，因此是固有的。当在某些技术条件下对网格进行无限细化时，可以证明这种构造收敛于底层歧管的连续拉普拉斯算子[69]。
网格的嵌入（相当于指定顶点坐标 X1, . . , Xn）诱导离散度量Lij= ||Xi− Xj||2，由此（12）成为计算机图形学中普遍使用的余切权重 [70]。
图的顶点和边上的实函数 f : V → R 和 F : E → R 分别是微分几何中连续标量和切向量场的离散类比。 4我们可以定义希尔伯特空间 L2(V) 和通过指定各自的内积，这些函数的 L2(E)，
设 f ∈ L2(V) 和 F ∈ L2(E) 分别是图的顶点和边上的函数。我们可以定义作用于这些函数的微分算子，类似于流形上的微分算子 [72]。图梯度是一个算子 ∇ : L2(V) → L2(E) 将顶点上定义的函数映射到边上定义的函数，
自动满足 (∇f)ij= −(∇f)ji。图散度是一个算子 div : L2(E) → L2(V) 做相反的，
很容易验证这两个算子是伴随 w.r.t.内积 (20)–(21)，
图拉普拉斯算子是一个算子 ∆ : L2(V) → L2(V) 定义为 ∆ = -div∇。结合定义（22）-（23），可以用熟悉的形式表达
请注意，公式 (25) 将拉普拉斯算子的直观几何解释捕获为点周围函数的局部平均值与该点本身的函数值之间的差异。
由 W = (wij) 表示 n × n 边权重矩阵（假设 wij= 0 如果 (i, j) ∉ E），由 A = diag(a1, . . , an) 表示对角矩阵顶点权重，并通过 D = diag(∑j:j≠iWij) 度矩阵，将图拉普拉斯应用到函数 f ∈ L2(V) 表示为列向量 f = (f1, . . . , fn) > 可以写成矩阵向量形式为
(26)中A=I的选择称为非归一化图拉普拉斯算子；另一个流行的选择是 A = D 产生随机游走拉普拉斯算子 [73]。
离散流形：正如我们提到的，在许多实际情况下，人们会得到来自流形而不是流形本身的点的采样。在计算机图形应用中，从点云重建流形的正确离散化本身就是一个难题，称为网格划分（参见插入 IN2）。在流形学习问题中，流形通常近似为捕获局部亲和结构的图。我们警告读者，在通用数据科学的上下文中使用的术语“流形”在几何上并不严格，并且可能比我们事先定义的经典平滑流形具有更少的结构。例如，一组在实践中“看起来局部欧几里得”的点可能具有自相交、无限曲率、不同维度（取决于人们观看的尺度和位置）、密度的极端变化以及具有混杂结构的“噪声”。
非欧域的傅里叶分析：拉普拉斯算子是一个自伴随正半定算子，在紧凑域上允许具有一组离散正交特征函数 φ0, φ1, 的特征分解。 . . （满足 <φi，φj>L2(X)= δij）和非负实数特征值 0 = λ0≤ λ1≤ …（简称拉普拉斯谱），
特征函数是狄利克雷能量意义上最平滑的函数（参见插入 IN3），可以解释为标准傅立叶基的推广（实际上，由一维欧几里得拉普拉斯算子的特征函数给出， 到非欧几里得域。重要的是要强调，由于拉普拉斯算子本身的内在构造，拉普拉斯本征基是内在的。
X 上的平方可积函数 f 可以分解为傅立叶级数为
其中基函数上的投影产生一组离散的傅立叶系数 (^fi) 概括了经典信号处理中的分析（正向变换）阶段，用这些系数对基函数求和是合成（逆变换）阶段。
经典欧几里得信号处理的核心是傅里叶变换对角化卷积算子的属性，通俗地称为卷积定理。此属性允许将谱域中两个函数的卷积 f*g 表示为它们的傅立叶变换的元素乘积，
不幸的是，在非欧几里得情况下，我们甚至无法定义流形或图上的操作 x − x’，因此卷积（7）的概念不能直接扩展到这种情况。将卷积推广到非欧几里得域的一种可能性是使用卷积定理作为定义，
这种构造与经典卷积的主要区别之一是缺乏平移不变性。在信号处理方面，它可以解释为一个位置相关的滤波器。虽然通过频域中固定数量的系数进行参数化，但滤波器的空间表示在不同点可能会发生巨大变化（参见图 4）。
上面的讨论也适用于图形而不是流形，其中只需将方程 (32) 和 (34) 中的内积替换为离散的 (20)。 i 上的所有和都将变为有限，因为图拉普拉斯算子 ∆ 有 n 个特征向量。在矩阵向量表示法中，广义卷积 f * g 可以表示为 Gf = Φdiag(ˆ g)ΦTf，其中 ˆ g = (ˆ g1, . . , ˆ gn) 是滤波器的频谱表示，而 Φ = (φ1, . . , φn)表示拉普拉斯特征向量 (30)。缺乏平移不变性导致矩阵 G 中缺少循环（托普利兹）结构，这是欧几里德设置的特征。此外，很容易看出卷积运算与拉普拉斯算子交换，G∆f = ∆Gf。
唯一性和稳定性：最后，重要的是要注意拉普拉斯本征函数不是唯一定义的。首先，它们被定义为符号，即 ∆(±φ) = λ(±φ)。因此，即使是等距域也可能具有不同的拉普拉斯本征函数。此外，如果拉普拉斯特征值具有多重性，那么相关的特征函数可以定义为跨越相应特征子空间的正交基（或者换句话说，特征函数被定义为特征子空间中的正交变换）。域的小扰动会导致拉普拉斯特征向量发生非常大的变化，尤其是那些与高频相关的特征向量。同时，热核 (36) 和扩散距离 (38) 的定义不受这些歧义的影响——例如，符号歧义随着特征函数的平方而消失。热核似乎也对域扰动具有鲁棒性。
[IN3] 拉普拉斯本征函数的物理解释：给定域 X 上的函数 f，狄利克雷能量
衡量它的平滑程度（（27）中的最后一个恒等式来自（19））。我们正在寻找 X 的正交基，包含 k 个最平滑的可能函数（图 3），通过解决优化问题
在离散设置中，当域在 n 个点采样时，问题（28）可以改写为
其中 Φk= (φ0, . . . .φk−1)。 (29) 的解由满足 Δ 的前 k 个特征向量给出
其中 Λk= diag(λ0, . . . , λk−1) 是对应特征值的对角矩阵。由于拉普拉斯算子的正半定性，特征值 0 = λ0≤ λ1≤…λk−1 是非负的，可以解释为“频率”，其中 φ0= const 和相应的特征值 λ0= 0 扮演 DC 的角色。
拉普拉斯本征分解可以通过两种方式进行。首先，方程 (30) 可以改写为广义特征问题 (D − W)Φk = AΦkΛk，得到 A 正交特征向量，ΦTkAΦk= I。或者，引入变量 Ψk= A1/2Φk 的变化，我们可以得到一个标准的特征分解问题 A−1/2(D − W)A−1/2Ψk= ΨkΛk，正交特征向量 Ψ> kΨk= I。 当使用 A = D 时，矩阵 Δ = A−1/2(D − W )A−1/2 被称为归一化对称拉普拉斯算子
[FIGS3]前四个拉普拉斯本征函数的例子φ0，…， φ3在欧几里得域(1D线，左上)和非欧几里得域(人体形状建模为2D流形，右上;明尼苏达道路图，底部)。在欧几里得的情况下，结果是由频率递增的正弦信号组成的标准傅里叶基。在所有情况下，零本征值对应的本征函数φ0为常数(’ DC ')。
5 谱方法
现在我们终于达到了我们的主要目标，即在非欧几里得域上构建一个CNN架构的泛化。我们首先假设我们工作的领域是固定的，在本节的其余部分，我们将使用固定图上的信号分类问题作为原型应用。
我们已经知道卷积是与拉普拉斯算子交换的线性算子。因此，给定一个加权图，推广卷积结构的第一个途径是首先限制我们对与图拉普拉斯交换的线性算子的兴趣。这个性质，反过来，意味着对图的权值的谱进行操作，权值由图的拉普拉斯特征向量给出。
[IN4]非欧几里得域的热扩散:光谱分析的一个重要应用，历史上，约瑟夫·傅里叶发展它的主要动机是偏微分方程(PDEs)的解。特别地，我们对非欧几里得域上的热传播感兴趣。这一过程由热扩散方程控制，在最简单的均质和各向同性扩散中，热扩散方程的形式为
如果域有边界，就有附加的边界条件。f(x, t)表示t时刻x点的温度。公式(35)编码了牛顿冷却定律，根据该定律，物体的温度变化率与物体自身和周围的温度之差成正比。比例系数c称为热扩散系数常数;这里，为了简单起见，我们假设它等于1。将热算符Ht= e−t∆应用于初始条件，得到(35)的解，在谱域可表示为
ht (x, x’)被称为热核函数，表示初始条件为f0(x) = δx’(x)的热方程的解，或者，用信号处理术语来说，一个“脉冲响应”。在物理术语中，ht(x, x’)描述了在时间t内从一个点x流向另一个点x’的热量。
在欧几里得的情况下，热核是平移不变的，ht(x, x’) = ht(x−x’)，允许将(36)中的积分解释为f(x, t) = (f0*ht)(x)的卷积。在光谱域，与热核的卷积相当于低通滤波，频率响应为e - tλ。扩散时间t值越大，有效截止频率越低，解在空间中越平滑(对应的直觉是扩散时间越长，初始热分布越平滑)。
位于x和x’点的两个热核之间的“串音”允许测量一个固有距离
称为扩散距离[30]。注意，将（37）和（38）分别解释为空间域和频域规范||·||L2（X）和||·||L2，它们的等价性是帕塞瓦尔恒等式的结果。与测量流形或图形上最短路径长度的测地距离不同，扩散距离具有在不同路径上求平均值的效果。因此，它对域的扰动更为鲁棒，例如，图中边的引入或移除，或流形上的“切”。
[FIGS4]非欧几里德域上的热核示例（流形，顶部；图形，底部）。观察将热核移动到不同位置如何改变其形状，这表明缺乏平移不变性。
光谱CNN（SCNN）[52]：与经典欧几里德CNN的卷积层（6）类似，Bruna等人[52]将光谱卷积层定义为
其中，n×p和n×q矩阵F=（f1，…，fp）和G=（g1，…，gq）分别表示图顶点上的p维和q维输入和输出信号（我们使用n=| V |表示图中的顶点数），Γl，l’是谱乘子的k×k对角矩阵，表示频域中的滤波器，ξ是应用于顶点函数值的非线性。仅使用（39）中的前k个特征向量设置截止频率，该频率取决于图形的内在规律性和样本大小。通常，k<<n、 因为只有描述图的光滑结构的第一个拉普拉斯特征向量在实践中是有用的。
如果图具有潜在的群不变性，那么这样的构造可以发现它。特别是，可以从光谱域重新定义标准CNN（参见第5页的插入）。然而，在许多情况下，图形没有组结构，或者组结构不与拉普拉斯变换，因此我们不能将每个过滤器视为通过V传递模板并记录模板与该位置的相关性。
我们应该强调，谱构造的一个基本限制是它对单个域的限制。原因是频谱滤波器系数 (39) 是基相关的。这意味着如果我们学习一个过滤器 w.r.t.一个域上的Φk基础，然后尝试将其应用于具有另一个基 Ψk 的另一个域，结果可能会大不相同（见图 2 并插入 IN6）。借助联合对角化过程[74]、[75]，可以跨不同域构建兼容的正交基。但是，这样的构造需要了解域之间的某些对应关系。例如，在社交网络分析等应用中，处理社交图的两个时间实例，其中添加了新的顶点和边，这样的对应关系可以很容易地计算出来，因此是一个合理的假设。相反，在计算机图形应用程序中，找到形状之间的对应关系本身就是一个非常困难的问题，因此假设域之间已知的对应关系是一个相当不合理的假设。
图 2. 一个玩具示例，说明了跨非欧几里得域推广频谱滤波的难度。左：定义在流形上的函数（函数值用颜色表示）；中：在频域中应用边缘检测滤波器的结果；右图：应用于相同函数但应用于不同（近等距）域的相同过滤器会产生完全不同的结果。这种行为的原因是傅里叶基是域相关的，并且在一个域上学习的滤波器系数不能以直接的方式应用于另一个域。
假设保留了拉普拉斯算子的 k = O(n) 个特征向量，卷积层 (39) 需要 pqk = O(n) 个参数来训练。接下来我们将看到如何将图的全局和局部规则结合起来以产生具有恒定参数数量的层（即，每层可学习参数的数量不依赖于输入的大小），即经典欧几里得 CNN 中的情况。
池化的非欧类比是图粗化，其中仅保留图顶点的一部分 α < 1。图拉普拉斯算子在两种不同分辨率下的特征向量通过以下多重网格属性相关：令 Φ,˜Φ 分别表示原始图和粗化图的拉普拉斯特征向量的 n × n 和 αn × αn 矩阵。然后，
其中 P 是一个 αn × n 二元矩阵，其第 i 行编码原始图上粗略图的第 i 个顶点的位置。因此，通过仅保留频谱的低频分量，可以使用频谱构造来推广跨步卷积。此属性还允许我们（通过插值）将空间构造中更深层的局部滤波器解释为低频。然而，由于在（39）中非线性应用于空间域，实际上必须重新计算每个分辨率下的图拉普拉斯特征向量，并在每个池化步骤后直接应用它们。
谱构造 (39) 为图拉普拉斯算子的每个特征向量分配一个*度。在大多数图中，单个高频特征向量变得非常不稳定。然而，与欧几里德域中的小波构造类似，通过对每个倍频程中的高频特征向量进行适当分组，可以恢复有意义且稳定的信息。正如我们接下来将看到的，这个原则也带来了更好的学习复杂性。
具有平滑谱乘法器的谱 CNN [52]、[44]：为了降低过拟合的风险，调整学习复杂度以减少模型的*参数数量很重要。在欧几里德域上，这是通过学习具有小空间支持的卷积核来实现的，这使模型能够学习与输入大小无关的许多参数。为了在频谱域中实现类似的学习复杂度，因此有必要将频谱乘法器的类别限制为对应于局部滤波器的那些。
为此，我们必须在频域中表达滤波器的空间定位。在欧几里得情况下，频域中的平滑度对应于空间衰减，因为
凭借帕塞瓦尔同一性。这表明，为了学习一个不仅可以在不同位置共享特征，而且还可以在原始域中很好地定位的层，我们可以学习平滑的频谱乘数。光滑性可以通过只学习频率乘子的下采样集和使用插值核来获得其余的，如三次样条。
然而，平滑的概念还需要谱域中的一些几何形状。在欧几里德设置中，这样的几何自然产生于频率的概念；例如，在平面上，两个傅立叶原子eiωtx和eiω’tx之间的相似度可以通过距离||ω − ω’||来量化，其中x表示二维平面坐标，ω表示二维频率向量。在图上，这种关系可以通过对两个特征向量 φi 和 φj 之间的相似性进行编码的权重 ˜ wij 的对偶图来定义。
一个特别简单的选择是选择一个一维排列，通过根据特征值对特征向量进行排序而获得。在这种情况下，谱乘数被参数化为
[IN5] 使用相关内核重新发现标准 CNN：在从数据构建图的情况下，图的边权重 (11) 的一个直接选择是数据的协方差。让 F 表示输入数据分布，
是数据协方差矩阵。如果每个点具有相同的方差 σii= σ2，则拉普拉斯算子上的对角算子简单地缩放 F 的主成分。
在自然图像中，由于它们的分布近似平稳，协方差矩阵具有循环结构 σij≈ σi−j，因此被标准离散余弦变换 (DCT) 基础对角化。因此，F 的主成分大致对应于按频率排序的 DCT 基向量。此外，自然图像表现出功率谱 E|f(ω)|2∼ |ω|−2，因为附近的像素比远处的像素更相关 [14]。结果协方差的主成分本质上是从低频到高频排序的，这与傅里叶基的标准群结构是一致的。当应用于表示为具有由协方差定义的权重的图的自然图像时，光谱 CNN 构造恢复了标准 CNN，无需任何先验知识 [76]。实际上，(39) 中的线性算子 ΦΓl,l’ΦT 是傅立叶基中的前一个参数对角线，因此平移不变，因此是经典卷积。此外，第六节解释了如何通过删除拉普拉斯算子的最后一部分频谱来获得空间子采样，从而导致池化，并最终成为标准 CNN。
[图5a] 使用欧几里得 RBF 内核在 16 × 16 图像块中二维嵌入像素。通过使用协方差 σij 作为两个特征之间的欧几里德距离，RBF 内核的构造如 (11) 中所述。使用结果图拉普拉斯算子的前两个特征向量将像素嵌入到 2D 空间中。左图和右图的颜色分别代表像素的横坐标和纵坐标。从相关测量中粗略地恢复像素的空间排列。
其中 B = (bij) = (βj(λi)) 是 k × q 固定插值核（例如，βj(λ) 可以是三次样条），α 是 q 插值系数的向量。为了获得具有恒定空间支持的滤波器（即，与输入大小 n 无关），应该在谱域中选择一个采样步长 γ ∼ n，这导致常数 nγ−1= O(1) 系数αl,l’ 每个过滤器。因此，通过将光谱层与图粗化相结合，该模型对于大小为 n 的输入具有 O(logn) 的总可训练参数，从而恢复与欧几里德网格上的 CNN 相同的学习复杂度。
即使对滤波器进行了这样的参数化，频谱 CNN (39) 也需要执行前向和后向传递的高计算复杂性，因为它们需要一个昂贵的矩阵乘法步骤 Φk 和 Φ> k。虽然在欧几里德域上，可以使用 FFT 类型算法在 O(nlogn) 运算中有效地进行这种乘法，但对于一般图，此类算法不存在并且复杂度为 O(n2)。接下来我们将看到如何通过避免拉普拉斯特征向量的显式计算来减轻这种成本。
6 无频谱方法
拉普拉斯算子的多项式充当特征值上的多项式。因此，与方程 (43) 中的频谱乘法器在频域中显式操作不同，可以通过多项式展开来表示滤波器：
对应于
这里α是多项式系数的r维向量，gα(Λ) = diag(gα(λ1), . . , gα(λn))，得到滤波器矩阵Γl,l’ = gαl,l’(Λ ) 其条目在特征值方面具有明确的形式。
这种表示的一个重要特性是它会自动生成局部过滤器，原因如下。由于拉普拉斯算子是本地算子（在 1 跳邻域上工作），因此其 j 次幂的作用仅限于 j 跳。由于滤波器是拉普拉斯算子幂的线性组合，因此整体（45）的行为就像一个扩散算子，仅限于每个顶点周围的 r 跳。
Graph CNN (GCNN)又名ChebNet [45]: Defferrard等人使用了由递归关系生成的Chebyshev多项式
因此，过滤器可以通过r−1阶的展开来唯一地参数化
其中~∆= 2λ−1 n∆−I和~ Λ = 2λ−1 nΛ−I表示拉普拉斯映射其特征值从区间[0，λn]到[−1,1]的缩放(必要的，因为切比雪夫多项式在[−1,1]中形成标准正交基)。
2˜∆¯f(j−1)−¯f(j−2) 与¯f(0)= f 和 ¯f(1)=˜∆f。因此，该过程的计算复杂度为 O(rn) 次操作，并且不需要显式计算拉普拉斯特征向量。
图卷积网络 (GCN) [77]：Kipf 和 Welling 通过进一步假设 r = 2 和 λn≈ 2 简化了这种结构，从而得到了以下形式的滤波器
进一步约束 α = α0= -α1，得到由单个参数表示的滤波器，
由于I + D−1/2WD−1/2的特征值现在在[0,2]范围内，重复应用这样的滤波器会导致数值不稳定。这可以通过重整来补救
其中~W = W + I，属于~D = diag(∑j≠i~wij)。
请注意，尽管我们从谱域开始构建 ChebNet 和 GCN，但它们归结为在空间域中应用作用于图的 r- 或 1 跳邻域的简单滤波器。我们认为这些结构是更通用的图神经网络 (GNN) 框架的示例：
图神经网络 (GNN) [78]：图神经网络概括了通过图权重直接在图上应用过滤操作的概念。与欧几里德 CNN 将通用滤波器学习为局部、定向带通和低通滤波器的线性组合类似，图神经网络在每一层学习图低通和高通运算符的通用线性组合。这些分别由 f → Wf 和 f → ∆f 给出，因此由度矩阵 D 和扩散矩阵 W 生成。 给定图顶点上的 p 维输入信号，由 n×p 矩阵表示F，GNN 考虑通用非线性函数 ηθ：Rp×Rp→ Rq，由应用于图的所有节点的可训练参数 θ 参数化，
特别是，选择 η(a,b) = b−a 可以恢复拉普拉斯算子 Δf，但更一般的非线性选择 η 会产生可训练的、特定于任务的扩散算子。与 CNN 架构类似，可以堆叠生成的 GNN 层 g = Cθ(f) 并将它们与图池操作符交错。 Chebyshev 多项式 Tr(Δ) 可以通过 (51) 的 r 层获得，从而原则上可以将 ChebNet 和 GCN 视为 GNN 框架的特定实例。
从历史上看，GNN 的一个版本是图上深度学习的第一个公式，在 [49]、[78] 中提出。这些工作在图上某些扩散过程（或随机游走）的参数化稳态上进行了优化。这可以解释为等式（51），但使用大量层，其中每个 Cθ 是相同的，因为通过 Cθ 的前向近似于稳态。最近的工作 [55]、[50]、[51]、[79]、[80] 放宽了接近稳态或重复应用相同 Cθ 的要求。
因为每一层的通信都是局部于一个顶点邻域，人们可能会担心需要很多层才能将信息从图的一个部分获取到另一部分，需要多跳（实际上，这是使用[78] 中的稳态）。但是，对于许多应用程序来说，信息没有必要完全遍历图。此外，请注意，网络每一层的图不必相同。因此，我们可以用自己喜欢的输入图的多尺度粗化替换原始邻域结构，并对其进行操作以获得与上述卷积网络相同的信息流（或者更像是“局部连接网络”[81]） .通过将每个输出连接到一个特殊的输出节点，这也允许为整个图生成单个输出（用于“平移不变”任务），而不是一个 pervertex 输出。或者，可以允许 η 不仅在每个节点使用 Wf 和 ∆f，而且在多个扩散尺度 s > 1 上使用 Wsf，（如 [45] 中所示），使 GNN 能够学习诸如幂方法之类的算法，以及更直接地访问图的光谱属性。
GNN 模型可以进一步推广以复制图上的其他算子。例如，逐点非线性 η 可以取决于顶点类型，从而允许极其丰富的架构 [55]、[50]、[51]、[79]、[80]。
7 基于图表的方法
我们现在将考虑非欧几里得学习问题的第二个子类，其中给定了多个域。读者在本节中应该记住的一个典型应用是找到形状之间的对应关系，建模为流形（见插入 IN7）。正如我们所见，在频域中定义卷积有一个固有的缺点，即无法跨不同域调整模型。因此，我们需要在空间域中采用一种替代的卷积泛化方法，该方法不受此缺点的影响。
此外，请注意，在多个域的设置中，没有立即定义有意义的空间池化操作的方法，因为不同域上的点数可能会有所不同，并且它们的顺序是任意的。然而，可以通过将所有本地信息聚合到单个向量中来汇集网络产生的逐点特征。这种池化的一种可能性是计算逐点特征的统计数据，例如均值或协方差 [47]。请注意，在这样的池化之后，所有空间信息都将丢失。
在欧几里德域上，由于平移不变性，卷积可以被认为是在域的每个点传递一个模板，并记录模板与该点函数的相关性。考虑到图像过滤，这相当于提取一个（通常为正方形）像素块，将其与模板逐元素相乘并总结结果，然后以滑动窗口的方式移动到下一个位置。移位不变性意味着在每个位置提取补丁的操作总是相同的。
将同一范式应用于非欧几里德域的主要问题之一是缺乏平移不变性，这意味着提取局部“面片”的“面片算子”将是位置相关的。此外，图形或流形力缺乏有意义的全局参数化，无法在局部固有坐标系中表示面片。这种映射可以通过定义一组加权函数v1（x，·），vJ（x，·）定位在x附近的位置（参见图3中的示例）。提取面片相当于通过这些权重平均每个点的函数f，
提供卷积内在等价物的空间定义
其中 g 表示应用于在每个点提取的补丁上的模板系数。总的来说，(52)-(53) 充当了 f 的一种非线性滤波，补丁算子 D 通过定义权重函数 v1, . . , vJ来指定。这样的过滤器通过构造进行局部化，并且参数的数量等于权重函数的数量 J = O(1)。非欧几里得 CNN 的几个框架基本上相当于这些权重的不同选择。上一节中描述的无频谱方法（ChebNet 和 GCN）也可以从局部加权函数的角度考虑，因为很容易看出公式（53）和（47）之间的类比。
Geodesic CNN [47]：由于流形自然带有与每个点相关联的低维切线空间，因此在切线空间中的局部坐标系统中工作是很自然的。特别是，在二维流形上，可以创建一个围绕 x 的极坐标系，其中径向坐标由某个固有距离 ρ(x0) = d(x, x0) 给出，并获得角坐标 θ(x)通过从一个点以等间距的角度发射光线。这种情况下的加权函数可以作为高斯的乘积获得
其中 i = 1, . . . , J 和 j = 1, . . . , J0 分别表示径向和角度仓的索引。由此产生的 JJ’ 权重是极坐标中宽度为 σρ×σθ 的区间（图 3，右）。
各向异性 CNN [48]：我们已经看到了非欧几里得热方程 (35)，其热核 ht(x,·) 在点 x 周围产生局部的 blob 状权重（见图 4）。改变扩散时间 t 控制内核的传播。然而，这种内核是各向同性的，这意味着热量在所有方向上的流动速度都一样快。流形上更一般的各向异性扩散方程
涉及热导率张量 A(x)（在二维流形的情况下，一个 2×2 矩阵应用于每个点切平面中的固有梯度），允许对位置和方向相关的热流进行建模 [82] . [53] 中提出的热导率张量的一个特殊选择是
其中 2 × 2 矩阵 Rθ(x) 执行 θ w.r.t. 的旋转。一些参考（例如最大曲率）方向和 α > 0 是控制各向异性程度的参数（α = 1 对应于经典的各向同性情况）。这种各向异性扩散方程的热核由谱展开式给出
其中 φαθ0(x), φαθ1(x), . . .是特征函数和 λαθ0, λαθ1, . . .各向异性拉普拉斯算子的相应特征值
各向异性拉普拉斯算子的离散化是对网格上的余切公式 (14) 或点云上的图拉普拉斯算子 (11) 的修改 [48]。
各向异性热核 hαθt(x,·) 看起来像拉长的旋转斑点（见图 3，中心），其中参数 α、θ 和 t 分别控制伸长率、方向和尺度。在构造补丁算子 (52) 时使用这样的内核作为加权函数 v，可以获得类似于测地线补丁的图表（粗略地说，θ 扮演角坐标的角色，而 t 扮演径向坐标的角色）。
混合模型网络（MoNet）[54]：最后，作为最通用的补丁构建，Monti 等人。 [54] 建议在每个点定义一个围绕 x 的 d 维伪坐标 u(x, x0) 的局部系统。在这些坐标上，一组参数核 v1(u), . . . , vJ(u)) 被应用，产生（52）中的权重函数。 Monti 等人没有像以前的结构那样使用固定内核。使用高斯核
其参数（d×d 协方差矩阵 Σ1, . . , ΣJ 和 d×1 平均向量 μ1, . . , μJ）被学习。不仅学习滤波器而且学习（53）中的补丁算子提供了额外的*度到 MoNet 架构，这使其成为目前多个应用程序中最先进的方法。也很容易看出这种方法概括了以前的模型，例如经典的欧几里得 CNN 以及测地线和各向异性 CNN 可以作为其特定实例获得 [54]。 MoNet 也可以应用于一般图，使用一些局部图特征作为伪坐标，如顶点度、测地距离等。
图 3. 顶部：用于在黑色标记的点处构造补丁算子的内在权重函数示例（不同颜色代表不同的权重函数）。扩散距离（左）允许根据相邻点与参考点的距离映射相邻点，从而定义局部固有坐标的一维系统。不同尺度和方向的各向异性热核（中）和测地极权重（右）是二维坐标系。底部：局部极坐标 (ρ, θ) 坐标系中权重函数的表示（红色曲线代表 0.5 水平集）。
8 组合空间/光谱方法
构造非欧几里得域的卷积类操作的第三种选择是在空间频率域中联合进行。
加窗傅里叶变换：经典傅里叶分析的显着缺点之一是缺乏空间定位。凭借不确定性原理（傅里叶变换的基本特性之一），空间定位以频率定位为代价，反之亦然。在经典信号处理中，这个问题是通过在窗口 g(x) 中定位频率分析来解决的，导致窗口傅立叶变换（WFT，在信号处理中也称为短时傅立叶变换或频谱图）的定义，
WFT 是两个变量的函数：窗口 x 的空间位置和调制频率 ω。窗口函数 g 的选择允许控制空间和频率定位之间的权衡（更宽的窗口导致更好的频率分辨率）。请注意，WFT 可以解释为具有平移和调制窗口 gx,ω 的函数 f 的内积 (60)，称为 WFT 原子。
将这种构造推广到非欧几里得域需要定义翻译和调制算子 [83]。虽然调制只是与拉普拉斯本征函数相乘，但由于缺乏平移不变性，平移没有明确定义。可以再次求助于类似卷积操作的频谱定义 (34)，将平移定义为具有 delta 函数的卷积，
平移和调制的原子可以表示为
其中，窗口在谱域中由其傅立叶系数 ˆ gi 指定；非欧域上的 WFT 因此采用形式
由于其定义中涉及的所有数量的内在性质，WFT 也是内在的。
小波：将时间频率表示中的频率概念替换为尺度的概念导致小波分解。小波已在一般图域中得到广泛研究 [84]。他们的目标是定义稳定的线性分解，原子在空间和频率上都很好地定位，可以有效地近似具有孤立奇点的信号。与欧几里得设置类似，小波族可以根据其谱约束或空间约束来构建。
这些家族中最简单的是 Haar 小波。在[85]和[86]中研究了图上的几个自下而上的小波构造。在 [87] 中，作者开发了一种无监督方法，通过优化稀疏重建目标来学习图上的小波分解。在 [88] 中，Haar 小波分解的集合被用于定义一般域上的深小波散射变换，获得了出色的数值性能。学习相当于在每个尺度上找到节点的最佳配对，这可以在多项式时间内有效地解决。
局部光谱 CNN (LSCNN) [89]：Boscaini 等人。使用 WFT 作为在流形和点云上构建补丁算子 (52) 的一种方式，并用于内在卷积结构 (53)。 WFT 允许以 Dj(x)f = (Sf)(x, j) 的形式表达谱域中某个点周围的函数。将可学习过滤器应用于此类“补丁”（在这种情况下可以解释为频谱乘数），可以提取有意义的特征，这些特征似乎也可以泛化到不同领域。另一个额外的*度是窗口的定义，这也可以学习[89]。
9 应用
网络分析：许多网络分析工作中使用的经典示例之一是引文网络。引文网络是一个图，其中顶点代表论文，如果论文 i 引用论文 j，则存在有向边 (i, j)。通常，可以使用表示论文内容的顶点特征（例如，论文中频繁术语的直方图）。一个典型的分类应用是将每篇论文归于一个领域。传统方法按顶点工作，分别对每个顶点的特征向量进行分类。最近，研究表明使用来自相邻顶点的信息可以显着改善分类，例如在图 [45]、[77] 上使用 CNN。插入 IN6 展示了光谱和空间图 CNN 模型在引文网络上的应用示例。
网络分析中的另一个基本问题是排名和社区检测。这些可以通过解决图上适当定义的算子上的特征值问题来估计：例如，Fiedler 向量（与拉普拉斯算子的最小非平凡特征值相关联的特征向量）携带关于具有最小切割的图分区的信息 [73 ]，流行的 PageRank 算法使用修改后的拉普拉斯算子的主特征向量来近似页面排名。在某些情况下，人们可能希望开发此类算法的数据驱动版本，以适应模型不匹配，并可能为对角化方法提供更快的替代方案。通过展开幂迭代，可以获得一种图神经网络架构，其参数可以通过标记示例的反向传播来学习，类似于学习稀疏编码范式 [91]。我们目前正在通过构建多尺度版本的图神经网络来探索这种联系。
[IN6] 引文网络分析应用：CORA 引文网络[90] 是一个包含 2708 个代表论文的顶点和 5429 个代表引文的边的图。每篇论文都由一个 1433 维的词袋特征向量描述，属于七类。为简单起见，网络被视为无向图。应用具有根据 (50) 参数化的两个光谱卷积层的光谱 CNN，[77] 的作者获得了 81.6% 的分类准确率（与之前的最佳结果 75.7% 相比）。在 [54] 中，这个结果得到了进一步的改善，使用 MoNet 架构达到了 81.7% 的准确率。
[FIGS6a] 使用 MoNet 对 CORA 数据集中的研究论文进行分类。显示的是引文图，其中每个节点是一篇论文，一条边代表一个引文。顶点填充和轮廓颜色分别代表预测和真实标签；理想情况下，两种颜色应该重合。 （图转载自[54]）。
推荐系统：推荐 Netflix 上的电影、Facebook 上的朋友或 Amazon 上的产品是最近在广泛应用中无处不在的推荐系统的几个例子。在数学上，推荐方法可以被视为矩阵完成问题[92]，其中列和行分别代表用户和项目，矩阵值表示确定用户是否喜欢项目的分数。给定矩阵的一小部分已知元素，目标是填充其余部分。一个著名的例子是 2009 年提供的 Netflix 挑战赛 [93]，该挑战赛的算法奖金为 100 万美元，该算法可以根据之前的评分最好地预测用户对电影的评分。 Netflix 矩阵的大小为 480K 电影 × 18K 用户（8.5B 元素），只有 0.011% 的已知条目。
最近的几项工作提出将几何结构合并到矩阵完成问题 [94]、[95]、[96]、[97] 中，分别以列图和行图的形式表示用户和项目的相似性（见图 4）。这样的几何矩阵完成设置很有意义，例如矩阵值平滑的概念，并被证明有利于推荐系统的性能。
在最近的一项工作中，Monti 等人。 [56]提出通过结合多图CNN（MGCNN）和循环神经网络（RNN）的可学习模型来解决几何矩阵完成问题。多图卷积可以被认为是标准二维图像卷积的泛化，其中行和列的域现在不同（在我们的例子中，用户和项目图）。通过 MGCNN 从分数矩阵中提取的特征然后传递给 RNN，它产生一系列分数值的增量更新。总体而言，该模型可以被视为分数的可学习扩散，与传统方法相比的主要优势是独立于矩阵大小的固定数量的变量。 MGCNN 在几个经典的矩阵补全挑战中取得了最先进的结果，并且在更概念化的层面上，它可能是几何深度学习在经典信号处理问题上的一个非常有趣的实际应用。
图 4. 以著名的 Netflix 电影推荐问题为例的几何矩阵完成。列图和行图分别表示用户和项目之间的关系。
计算机视觉和图形：计算机视觉社区最近对处理 3D 几何数据表现出越来越大的兴趣，这主要是由于 Microsoft Kinect 或 Intel RealSense 等经济实惠的距离传感技术的出现。许多成功处理图像的机器学习技术都在 3D 几何数据上“按原样”进行了尝试，为此目的，标准框架以某种“可消化”的方式表示，例如作为范围图像 [98]、[99] 或光栅化体积 [100]、[101]。这种方法的主要缺点是它们将几何数据视为欧几里得结构。首先，对于复杂的 3D 对象，深度图像或体素等欧几里德表示可能会丢失对象的重要部分或其精细细节，甚至破坏其拓扑结构。其次，欧几里德表示不是内在的，并且在改变姿势或使对象变形时会发生变化。实现形状变形的不变性，这是许多视觉应用中的常见要求，由于描述非刚性变形涉及大量*度，因此需要非常复杂的模型和庞大的训练集（图 5，左）。
图 5. 应用于被视为欧几里得对象的 3D 形状（方格表面）的经典 CNN（左）与应用在表面上的几何 CNN（右）之间的差异图示。在后一种情况下，卷积滤波器（可视化为彩色窗口）在构造上是变形不变的。
另一方面，在计算机图形领域，本质上处理几何形状是一种标准做法。在该领域，3D 形状通常建模为黎曼流形，并离散化为网格。许多研究（参见，例如 [102]、[103]、[104]、[105]、[106]）一直致力于设计局部和全局特征，例如用于在具有保证的等距不变性的可变形形状之间建立相似性或对应关系。
此外，计算机视觉和图形中的不同应用可能需要完全不同的特征：例如，为了在一组人体形状之间建立基于特征的对应关系，人们需要相应的解剖部位（鼻子、嘴巴等）的描述符。在整个集合中尽可能相似。换句话说，这样的描述符应该对集合可变性保持不变。相反，对于形状分类，人们想要强调特定主题特征的描述符，例如，区分两种不同的鼻子形状（见图 6）。先验地决定应该使用哪些结构以及应该忽略哪些结构通常是困难的，有时甚至是不可能的。此外，几何噪声（如 3D 扫描伪影）的公理化建模被证明是极其困难的。
图 6. 左：用于形状对应的特征在理想情况下应该在整个形状类中表现出不变性（例如，这里显示的“膝盖特征”不应该取决于特定的人）。正确：相反，用于形状检索的特征应该特定于类内的形状，以便区分不同的人。相似的特征用相同的颜色标记。为每个应用程序手工制作正确的功能是一项非常具有挑战性的任务。
通过使用内在的深度神经网络，等距变形的不变性自动构建到模型中，从而大大减少了描述不变性类所需的*度数。粗略地说，内在深度模型将尝试学习偏离等距模型的“残余”变形。几何深度学习可以应用于 3D 形状分析中的几个问题，可以分为两类。首先，诸如局部描述符学习 [47]、[53] 或对应学习 [48]（参见插入 IN7 中的示例）等问题，其中网络的输出是逐点的。网络的输入是一些逐点特征，例如颜色纹理或简单的几何特征，例如法线。使用具有多个内在卷积层的 CNN 架构，可以生成捕获每个点周围上下文的非局部特征。第二种类型的问题，例如形状识别，需要网络生成一个全局形状描述符，使用例如协方差池[47]。
粒子物理和化学：许多实验科学领域都对研究定义在低维相空间上的离散粒子系统感兴趣。例如，分子的化学性质由其原子的相对位置决定，粒子加速器中事件的分类取决于所有参与碰撞的粒子的位置、动量和自旋。
N 粒子系统的行为最终源自薛定谔方程的解，但其精确解涉及对指数大小的线性系统进行对角化。在这种情况下，一个重要的问题是，是否可以用一个易于处理的模型来近似动力学，该模型通过构造结合了薛定谔方程假设的几何稳定性，同时具有足够的灵活性来适应数据驱动的场景并捕获复杂的交互.
一个 Nl 粒子系统的实例 l 可以表示为
其中(αj,l)模型粒子的自旋等特定信息，(xj,l)是粒子在给定相空间中的位置。这样的系统可以被重定义为一个信号，这个信号定义在一个图上，这个图的顶点为|Vl| = Nl，边权为Wl= (φ(αi,l， αj,l, xi,l, xj,l)，通过一个相似核捕获适当的先验来表示。图神经网络目前被应用于大型强子对撞机(LHC)等高能物理实验的事件分类、能量回归和异常检测，以及冰立方天文台的中微子检测。近年来，基于图神经网络的模型被应用于n体系统的动力学预测[111]，[112]显示出良好的预测性能。
分子设计：材料和药物设计中的一个关键问题是从其结构预测新分子的物理、化学或生物学特性（例如毒性溶解度）。最先进的方法依赖于手工制作的分子描述符，例如圆形指纹 [113]、[114]、[115]。哈佛大学最近的一项工作 [55] 提出将分子建模为图（其中顶点代表原子，边代表化学键）并使用图卷积神经网络来学习所需的分子特性。他们的方法明显优于手工制作的功能。这项工作为分子设计开辟了一条新途径，可能会彻底改变该领域。
医学成像：在非欧几里德域上自然收集信号的应用领域以及我们审查的方法可能非常有用的应用领域是脑成像。神经科学的最新趋势是将功能性 MRI 迹线与预先计算的连接性相关联，而不是从迹线本身推断出来 [116]。在这种情况下，挑战在于处理和分析通过复杂拓扑收集的一系列信号，这会导致微妙的依赖关系。在帝国理工学院 [117] 最近的一项工作中，图 CNN 被用于检测与自闭症相关的大脑功能网络的中断。
10 未解决的问题和未来方向
最近在各种社区和应用领域中出现的几何深度学习方法（我们试图在本文中对其进行概述）使我们能够宣布，也许有些谨慎，我们可能正在见证一个新领域的诞生。我们预计接下来的几年会带来令人兴奋的新方法和结果，并通过对当前关键困难和未来研究的潜在方向的一些观察来总结我们的评论。
许多处理几何数据的学科都采用一些经验模型或“手工制作”的特征。这是几何处理和计算机图形学中的典型情况，其中使用公理构造的特征来分析 3D 形状，或计算社会学，通常首先提出假设，然后在数据上对其进行测试 [22]。然而，这些模型假设有一些先验知识（例如等距形状变形模型），并且通常无法正确捕获数据的全部复杂性和丰富性。在计算机视觉中，从“手工制作”的特征转向以特定任务的方式从数据中学习的通用模型带来了性能上的突破，并导致社区中支持深度学习方法的压倒性趋势。由于缺乏足够的方法，在处理几何数据的领域还没有发生这种转变，但有迹象表明即将发生范式转变。
[IN7] 3D 形状对应应用：寻找可变形形状之间的内在对应是一个经典的难题，它是广泛的视觉和图形应用的基础，包括纹理映射、动画、编辑和场景理解 [107]。从机器学习的角度来看，对应可以被认为是一个分类问题，其中查询形状上的每个点都分配给参考形状上的一个点（作为“标签空间”）[108]。可以学习与应用于查询形状 X 的每个点 x 处的某个输入特征向量 f(x) 的深度内在网络的对应关系，产生输出 UΘ(f(x))(y)，它被解释为x 映射到 y 的条件概率 p(y|x)。使用一组训练点及其真值对应 {xi, yi}i∈I，执行监督学习以最小化多项式回归损失
w.r.t.网络参数 Θ。损失惩罚了预测对应与真实情况的偏差。我们注意到，虽然产生了令人印象深刻的结果，但这种方法本质上是学习逐点对应，然后必须对其进行后处理以满足某些属性，例如平滑度或双射性。对应是结构化输出的一个例子，其中网络在一个点的输出取决于其他点的输出（在最简单的设置中，对应应该是平滑的，即附近点的输出应该是相似的）。 Litany 等人。 [109] 通过将层计算功能对应 [106] 集成到深度神经网络中，提出了形状对应的内在结构化预测。
[FIGS7a] 学习形状对应：一个内在深度网络 UΘ 被逐点应用于在每个点定义的一些输入特征。网络在查询形状 X 的每个点 x 的输出是参考形状 Y 的概率分布，可以认为是软对应。
[FIGS7b] 使用内在深度架构（具有三个卷积层的 MoNet [54]）在人体形状之间建立内在对应关系。在这个例子中，捕捉局部法向量方向的 SHOT 描述符 [110] 被用作输入特征。通过从最左边的参考形状转移纹理来可视化对应关系。有关其他示例，请参阅 [54]。
泛化：将深度学习模型泛化到几何数据不仅需要找到基本构建块（例如卷积和池化层）的非欧几里德对应物，还需要跨不同域的泛化。泛化能力是许多应用程序的关键要求，包括计算机图形学，其中模型是在非欧几里得域（3D 形状）的训练集上学习的，然后应用于以前看不见的域。卷积的谱公式允许在图上设计 CNN，但是在一个图上以这种方式学习的模型不能直接应用于另一个图，因为卷积的谱表示是域相关的。频谱方法泛化问题的一种可能补救措施是 [118] 中提出的最新架构，在频谱域中应用了空间变换器网络 [119] 的思想。这种方法让人想起通过联合拉普拉斯对角化[75]构建兼容正交基，这可以解释为在 k 维空间中对齐两个拉普拉斯特征基。
另一方面，空间方法允许跨不同领域的泛化，但在图上构建低维局部空间坐标变得相当具有挑战性。特别是在一般图上构建各向异性扩散是一个有趣的研究方向。
无谱方法还允许跨图的泛化，至少在它们的功能形式方面。然而，如果在没有非线性或学习参数 θ 的情况下使用多层方程 (51)，模拟高功率扩散，模型可能在不同类型的图上表现不同。目前正在研究了解这些方法在什么情况下以及在多大程度上可以跨图泛化。
时变域：本综述中讨论的几何深度学习问题的一个有趣扩展是处理在动态变化结构上定义的信号。在这种情况下，我们不能假设一个固定的域，必须跟踪这些变化如何影响信号。这对于解决社交或金融网络中的异常活动检测等应用程序可能很有用。在计算机图形和视觉领域，潜在的应用程序处理动态形状（例如由距离传感器捕获的 3D 视频）。
有向图：处理有向图也是一个具有挑战性的话题，因为此类图通常具有非对称拉普拉斯矩阵，这些矩阵不具有正交特征分解，允许轻松解释谱域构造。引用网络是有向图，通常被视为无向图（包括在我们的 IN7 示例中），考虑两篇论文之间的引用而不区分哪篇论文引用了哪篇。这显然可能会丢失重要信息。
综合问题：我们在本次审查中的主要重点主要是非欧几里德域的分析问题。同样重要的是数据合成问题。最近有几次尝试尝试学习允许合成新图像 [120] 和语音波形 [121] 的生成模型。将此类方法扩展到几何设置似乎是一个有希望的方向，尽管关键困难是需要从一些内在表示重建几何结构（例如，在 3D 欧几里得空间中嵌入 2D 流形建模可变形形状）[122] .
计算：最后的考虑是计算问题。所有现有的深度学习软件框架主要针对欧几里得数据进行了优化。深度学习架构计算效率高的主要原因之一（也是促成其复兴的因素之一）是假设在一维或二维网格上有规则的结构化数据，从而可以利用现代 GPU 硬件。另一方面，几何数据在大多数情况下没有网格结构，需要不同的方法来实现高效计算。似乎为大规模图形处理开发的计算范式是更适合此类应用程序的框架。
参考文献
[1] Y . LeCun, Y . Bengio, and G. Hinton, “Deep learning,” Nature, vol.
521, no. 7553, pp. 436–444, 2015.
[2] T. Mikolov, A. Deoras, D. Povey, L. Burget, and J.ˇCernock` y, “Strate-
gies for training large scale neural network language models,” in Proc.
ASRU, 2011, pp. 196–201.
[3] G. Hinton, L. Deng, D. Y u, G. E. Dahl, A. Mohamed, N. Jaitly,
A. Senior, V . V anhoucke, P . Nguyen, and T. N. Sainath, “Deep neural
networks for acoustic modeling in speech recognition: The shared
views of four research groups,” IEEE Sig. Proc. Magazine, vol. 29,
no. 6, pp. 82–97, 2012.
[4] I. Sutskever, O. Vinyals, and Q. V . Le, “Sequence to sequence learning
with neural networks,” in Proc. NIPS, 2014.
[5] Y . LeCun, K. Kavukcuoglu, and C. Farabet, “Convolutional networks
and applications in vision,” in Proc. ISCAS, 2010.
[6] D. Cires ¸an, U. Meier, J. Masci, and J. Schmidhuber, “A committee of
neural networks for traffic sign classification,” in Proc. IJCNN, 2011.
[7] A. Krizhevsky, I. Sutskever, and G. Hinton, “Imagenet classification
with deep convolutional neural networks,” in Proc. NIPS, 2012.
[8] C. Farabet, C. Couprie, L. Najman, and Y . LeCun, “Learning hierar-
chical features for scene labeling,” Trans. PAMI, vol. 35, no. 8, pp.
1915–1929, 2013.
[9] Y . Taigman, M. Yang, M. Ranzato, and L. Wolf, “Deepface: Closing the
gap to human-level performance in face verification,” in Proc. CVPR,
2014.
[10] K. Simonyan and A. Zisserman, “V ery deep convolutional networks
for large-scale image recognition,” arXiv:1409.1556, 2014.
[11] K. He, X. Zhang, S. Ren, and J. Sun, “Deep residual learning for image
recognition,” arXiv:1512.03385, 2015.
[12] L. Deng and D. Y u, “Deep learning: methods and applications,”
F oundations and Trends in Signal Processing, vol. 7, no. 3–4, pp. 197–
387, 2014.
[13] I. Goodfellow, Y . Bengio, and A. Courville, Deep Learning. MIT
Press, 2016, in preparation.
[14] E. P . Simoncelli and B. A. Olshausen, “Natural image statistics and
neural representation,” Annual Review of Neuroscience, vol. 24, no. 1,
pp. 1193–1216, 2001.
[15] D. J. Field, “What the statistics of natural images tell us about visual
coding,” in Proc. SPIE, 1989.
[16] P . Mehta and D. J. Schwab, “An exact mapping between the variational
renormalization group and deep learning,” arXiv:1410.3831, 2014.
[17] S. Mallat, “Group invariant scattering,” Communications on Pure and
Applied Mathematics, vol. 65, no. 10, pp. 1331–1398, 2012.
[18] J. Bruna and S. Mallat, “Invariant scattering convolution networks,”
Trans. PAMI, vol. 35, no. 8, pp. 1872–1886, 2013.
[19] M. Tygert, J. Bruna, S. Chintala, Y . LeCun, S. Piantino, and A. Szlam,
“A mathematical motivation for complex-valued convolutional net-
works,” Neural Computation, 2016.
[20] Y . LeCun, B. Boser, J. S. Denker, D. Henderson, R. E. Howard,
W. Hubbard, and L. D. Jackel, “Backpropagation applied to handwritten
ZIP code recognition,” Neural Computation, vol. 1, no. 4, pp. 541–551,
1989.
[21] I. J. Goodfellow, D. Warde-Farley, M. Mirza, A. Courville, and
Y . Bengio, “Maxout networks,” arXiv:1302.4389, 2013.
[22] D. Lazer et al., “Life in the network: the coming age of computational
social science,” Science, vol. 323, no. 5915, p. 721, 2009.
[23] E. H. Davidson et al., “A genomic regulatory network for develop-
ment,” Science, vol. 295, no. 5560, pp. 1669–1678, 2002.
[24] M. B. Wakin, D. L. Donoho, H. Choi, and R. G. Baraniuk, “The
multiscale structure of non-differentiable image manifolds,” in Proc.
SPIE, 2005.
[25] N. V erma, S. Kpotufe, and S. Dasgupta, “Which spatial partition trees
are adaptive to intrinsic dimension?” in Proc. Uncertainty in Artificial
Intelligence, 2009.
[26] J. B. Tenenbaum, V . De Silva, and J. C. Langford, “A global geometric
framework for nonlinear dimensionality reduction,” Science, vol. 290,
no. 5500, pp. 2319–2323, 2000.
[27] S. T. Roweis and L. K. Saul, “Nonlinear dimensionality reduction by
locally linear embedding,” Science, vol. 290, no. 5500, pp. 2323–2326,
2000.
[28] L. Maaten and G. Hinton, “Visualizing data using t-SNE,” JMLR,
vol. 9, pp. 2579–2605, 2008.
[29] M. Belkin and P . Niyogi, “Laplacian eigenmaps for dimensionality
reduction and data representation,” Neural Computation, vol. 15, no. 6,
pp. 1373–1396, 2003.
[30] R. R. Coifman and S. Lafon, “Diffusion maps,” App. and Comp.
Harmonic Analysis, vol. 21, no. 1, pp. 5–30, 2006.
[31] R. Hadsell, S. Chopra, and Y . LeCun, “Dimensionality reduction by
learning an invariant mapping,” in Proc. CVPR, 2006.
[32] B. Perozzi, R. Al-Rfou, and S. Skiena, “DeepWalk: Online learning of
social representations,” in Proc. KDD, 2014.
[33] J. Tang, M. Qu, M. Wang, M. Zhang, J. Yan, and Q. Mei, “LINE:
Large-scale information network embedding,” in Proc. WWW, 2015.
[34] S. Cao, W. Lu, and Q. Xu, “GraRep: Learning graph representations
with global structural information,” in Proc. IKM, 2015.
[35] T. Mikolov, K. Chen, G. Corrado, and J. Dean, “Efficient estimation
of word representations in vector space,” arXiv:1301.3781, 2013.
[36] R. Milo, S. Shen-Orr, S. Itzkovitz, N. Kashtan, D. Chklovskii, and
U. Alon, “Network motifs: simple building blocks of complex net-
works,” Science, vol. 298, no. 5594, pp. 824–827, 2002.
[37] N. Prˇ zulj, “Biological network comparison using graphlet degree
distribution,” Bioinformatics, vol. 23, no. 2, pp. 177–183, 2007.
[38] J. Sun, M. Ovsjanikov, and L. J. Guibas, “A concise and provably
informative multi-scale signature based on heat diffusion,” Computer
Graphics F orum, vol. 28, no. 5, pp. 1383–1392, 2009.
[39] R. Litman and A. M. Bronstein, “Learning spectral descriptors for
deformable shape correspondence,” Trans. PAMI, vol. 36, no. 1, pp.
171–180, 2014.
[40] S. Fortunato, “Community detection in graphs,” Physics Reports, vol.
486, no. 3, pp. 75–174, 2010.
[41] T. Mikolov and J. Dean, “Distributed representations of words and
phrases and their compositionality,” Proc. NIPS, 2013.
[42] E. Cho, S. A. Myers, and J. Leskovec, “Friendship and mobility: user
movement in location-based social networks,” in Proc. KDD, 2011.
[43] D. I. Shuman, S. K. Narang, P . Frossard, A. Ortega, and P . V an-
dergheynst, “The emerging field of signal processing on graphs: Ex-
tending high-dimensional data analysis to networks and other irregular
domains,” IEEE Sig. Proc. Magazine, vol. 30, no. 3, pp. 83–98, 2013.
[44] M. Henaff, J. Bruna, and Y . LeCun, “Deep convolutional networks on
graph-structured data,” arXiv:1506.05163, 2015.
[45] M. Defferrard, X. Bresson, and P . V andergheynst, “Convolutional
neural networks on graphs with fast localized spectral filtering,” in
Proc. NIPS, 2016.
[46] J. Atwood and D. Towsley, “Diffusion-convolutional neural networks,”
arXiv:1511.02136v2, 2016.
[47] J. Masci, D. Boscaini, M. M. Bronstein, and P . V andergheynst,
“Geodesic convolutional neural networks on Riemannian manifolds,”
in Proc. 3DRR, 2015.
[48] D. Boscaini, J. Masci, E. Rodolà, and M. M. Bronstein, “Learning
shape correspondence with anisotropic convolutional neural networks,”
in Proc. NIPS, 2016.
[49] M. Gori, G. Monfardini, and F. Scarselli, “A new model for learning
in graph domains,” in Proc. IJCNN, 2005.
[50] Y . Li, D. Tarlow, M. Brockschmidt, and R. Zemel, “Gated graph
sequence neural networks,” arXiv:1511.05493, 2015.
[51] S. Sukhbaatar, A. Szlam, and R. Fergus, “Learning multiagent com-
munication with backpropagation,” arXiv:1605.07736, 2016.
[52] J. Bruna, W. Zaremba, A. Szlam, and Y . LeCun, “Spectral networks
and locally connected networks on graphs,” Proc. ICLR, 2013.
[53] D. Boscaini, J. Masci, E. Rodolà, M. M. Bronstein, and D. Cremers,
“Anisotropic diffusion descriptors,” in Computer Graphics F orum,
vol. 35, no. 2, 2016, pp. 431–441.
[54] F. Monti, D. Boscaini, J. Masci, E. Rodolà, J. Svoboda, and M. M.
Bronstein, “Geometric deep learning on graphs and manifolds using
mixture model CNNs,” in Proc. CVPR, 2017.
[55] D. K. Duvenaud, D. Maclaurin, J. Iparraguirre, R. Bombarell, T. Hirzel,
A. Aspuru-Guzik, and R. P . Adams, “Convolutional networks on graphs
for learning molecular fingerprints,” in Proc. NIPS, 2015.
[56] F. Monti, X. Bresson, and M. M. Bronstein, “Geometric matrix com-
pletion with recurrent multi-graph neural networks,” arXiv:1704.06803,
2017.
[57] S. Mallat, “Understanding deep convolutional networks,” Phil. Trans.
R. Soc. A, vol. 374, no. 2065, 2016.
[58] P . F. Felzenszwalb, R. B. Girshick, D. McAllester, and D. Ramanan,
“Object detection with discriminatively trained part-based models,”
Trans. PAMI, vol. 32, no. 9, pp. 1627–1645, 2010.
[59] A. Dosovitskiy, P . Fischery, E. Ilg, C. Hazirbas, V . Golkov, P . van der
Smagt, D. Cremers, T. Brox et al., “Flownet: Learning optical flow
with convolutional networks,” in Proc. ICCV, 2015.
[60] J. T. Springenberg, A. Dosovitskiy, T. Brox, and M. Riedmiller,
“Striving for simplicity: The all convolutional net,” arXiv:1412.6806,
2014.
[61] S. Mallat, A wavelet tour of signal processing. Academic Press, 1999.
[62] A. Choromanska, M. Henaff, M. Mathieu, G. B. Arous, and Y . LeCun,
“The loss surfaces of multilayer networks,” in Proc. AISTATS, 2015.
[63] I. Safran and O. Shamir, “On the quality of the initial basin in
overspecified neural networks,” arXiv:1511.04210, 2015.
[64] K. Kawaguchi, “Deep learning without poor local minima,” in Proc.
NIPS, 2016.
[65] T. Chen, I. Goodfellow, and J. Shlens, “Net2net: Accelerating learning
via knowledge transfer,” arXiv:1511.05641, 2015.
[66] C. D. Freeman and J. Bruna, “Topology and geometry of half-rectified
network optimization,” ICLR, 2017.
[67] J. Nash, “The imbedding problem for Riemannian manifolds,” Annals
of Mathematics, vol. 63, no. 1, pp. 20–63, 1956.
[68] M. Wardetzky, S. Mathur, F. Kälberer, and E. Grinspun, “Discrete
laplace operators: no free lunch,” in Proc. SGP, 2007.
[69] M. Wardetzky, “Convergence of the cotangent formula: An overview,”
in Discrete Differential Geometry, 2008, pp. 275–286.
[70] U. Pinkall and K. Polthier, “Computing discrete minimal surfaces and
their conjugates,” Experimental Mathematics, vol. 2, no. 1, pp. 15–36,
1993.
[71] S. Rosenberg, The Laplacian on a Riemannian manifold: an introduc-
tion to analysis on manifolds. Cambridge University Press, 1997.
[72] L.-H. Lim, “Hodge Laplacians on graphs,” arXiv:1507.05379, 2015.
[73] U. V on Luxburg, “A tutorial on spectral clustering,” Statistics and
Computing, vol. 17, no. 4, pp. 395–416, 2007.
[74] A. Kovnatsky, M. M. Bronstein, A. M. Bronstein, K. Glashoff, and
R. Kimmel, “Coupled quasi-harmonic bases,” in Computer Graphics
F orum, vol. 32, no. 2, 2013, pp. 439–448.
[75] D. Eynard, A. Kovnatsky, M. M. Bronstein, K. Glashoff, and A. M.
Bronstein, “Multimodal manifold analysis by simultaneous diagonal-
ization of Laplacians,” Trans. PAMI, vol. 37, no. 12, pp. 2505–2517,
2015.
[76] N. L. Roux, Y . Bengio, P . Lamblin, M. Joliveau, and B. Kégl, “Learning
the 2-d topology of images,” in Proc. NIPS, 2008.
[77] T. N. Kipf and M. Welling, “Semi-supervised classification with graph
convolutional networks,” arXiv:1609.02907, 2016.
[78] F. Scarselli, M. Gori, A. C. Tsoi, M. Hagenbuchner, and G. Monfardini,
“The graph neural network model,” IEEE Trans. Neural Networks,
vol. 20, no. 1, pp. 61–80, 2009.
[79] M. B. Chang, T. Ullman, A. Torralba, and J. B. Tenenbaum, “A
compositional object-based approach to learning physical dynamics,”
2016.
[80] P . Battaglia, R. Pascanu, M. Lai, D. Jimenez Rezende, and
K. Kavukcuoglu, “Interaction networks for learning about objects,
relations and physics,” in Proc. NIPS, 2016.
[81] A. Coates and A. Y . Ng, “Selecting receptive fields in deep networks,”
in Proc. NIPS, 2011.
[82] M. Andreux, E. Rodolà, M. Aubry, and D. Cremers, “Anisotropic
Laplace-Beltrami operators for shape analysis,” in Proc. NORDIA,
2014.
[83] D. I. Shuman, B. Ricaud, and P . V andergheynst, “V ertex-frequency
analysis on graphs,” App. and Comp. Harmonic Analysis, vol. 40, no. 2,
pp. 260–291, 2016.
[84] R. R. Coifman and M. Maggioni, “Diffusion wavelets,” App. and Comp.
Harmonic Analysis, vol. 21, no. 1, pp. 53–94, 2006.
[85] A. D. Szlam, M. Maggioni, R. R. Coifman, and J. C. BremerJr,
“Diffusion-driven multiscale analysis on manifolds and graphs: top-
down and bottom-up constructions,” in Optics & Photonics 2005.
International Society for Optics and Photonics, 2005, pp. 59 141D–
59 141D.
[86] M. Gavish, B. Nadler, and R. R. Coifman, “Multiscale wavelets on
trees, graphs and high dimensional data: Theory and applications to
semi supervised learning,” in Proc. ICML, 2010.
[87] R. Rustamov and L. J. Guibas, “Wavelets on graphs via deep learning,”
in Proc. NIPS, 2013.
[88] X. Cheng, X. Chen, and S. Mallat, “Deep Haar scattering networks,”
Information and Inference, vol. 5, pp. 105–133, 2016.
[89] D. Boscaini, J. Masci, S. Melzi, M. M. Bronstein, U. Castellani, and
P . V andergheynst, “Learning class-specific descriptors for deformable
shapes using localized spectral convolutional networks,” in Computer
Graphics F orum, vol. 34, no. 5, 2015, pp. 13–23.
[90] P . Sen, G. Namata, M. Bilgic, L. Getoor, B. Galligher, and T. Eliassi-
Rad, “Collective classification in network data,” AI Magazine, vol. 29,
no. 3, p. 93, 2008.
[91] K. Gregor and Y . LeCun, “Learning fast approximations of sparse
coding,” in Proc. ICML, 2010.
[92] E. Candès and B. Recht, “Exact matrix completion via convex opti-
mization,” Commu. ACM, vol. 55, no. 6, pp. 111–119, 2012.
[93] Y . Koren, R. Bell, and C. V olinsky, “Matrix factorization techniques
for recommender systems,” Computer, vol. 42, no. 8, pp. 30–37, 2009.
[94] H. Ma, D. Zhou, C. Liu, M. Lyu, and I. King, “Recommender systems
with social regularization,” in Proc. Web Search and Data Mining,
2011.
[95] V . Kalofolias, X. Bresson, M. Bronstein, and P . V andergheynst, “Matrix
completion on graphs,” arXiv:1408.1717, 2014.
[96] N. Rao, H.-F. Y u, P . K. Ravikumar, and I. S. Dhillon, “Collaborative
filtering with graph information: Consistency and scalable methods,”
in Proc. NIPS, 2015.
[97] D. Kuang, Z. Shi, S. Osher, and A. Bertozzi, “A harmonic extension
approach for collaborative ranking,” arXiv:1602.05127, 2016.
[98] H. Su, S. Maji, E. Kalogerakis, and E. Learned-Miller, “Multi-view
convolutional neural networks for 3D shape recognition,” in Proc.
ICCV, 2015.
[99] L. Wei, Q. Huang, D. Ceylan, E. V ouga, and H. Li, “Dense human
body correspondences using convolutional networks,” in Proc. CVPR,
2016.
[100] Z. Wu, S. Song, A. Khosla, F. Y u, L. Zhang, X. Tang, and J. Xiao,
“3D shapenets: A deep representation for volumetric shapes,” in Proc.
CVPR, 2015.
[101] C. R. Qi, H. Su, M. Nießner, A. Dai, M. Yan, and L. J. Guibas,
“V olumetric and multi-view CNNs for object classification on 3D data,”
in Proc. CVPR, 2016.
[102] A. M. Bronstein, M. M. Bronstein, and R. Kimmel, “Generalized
multidimensional scaling: a framework for isometry-invariant partial
surface matching,” PNAS, vol. 103, no. 5, pp. 1168–1172, 2006.
[103] M. M. Bronstein and I. Kokkinos, “Scale-invariant heat kernel signa-
tures for non-rigid shape recognition,” in Proc. CVPR, 2010.
[104] V . Kim, Y . Lipman, and T. Funkhouser, “Blended intrinsic maps,” ACM
Trans. Graphics, vol. 30, no. 4, p. 79, 2011.
[105] A. M. Bronstein, M. M. Bronstein, L. J. Guibas, and M. Ovsjanikov,
“ShapeGoogle: Geometric words and expressions for invariant shape
retrieval,” ACM Trans. Graphics, vol. 30, no. 1, p. 1, 2011.
[106] M. Ovsjanikov, M. Ben-Chen, J. Solomon, A. Butscher, and L. J.
Guibas, “Functional maps: a flexible representation of maps between
shapes,” ACM Trans. Graphics, vol. 31, no. 4, p. 30, 2012.
[107] S. Biasotti, A. Cerri, A. M. Bronstein, and M. M. Bronstein, “Recent
trends, applications, and perspectives in 3D shape similarity assess-
ment,” in Computer Graphics F orum, 2015.
[108] E. Rodolà, S. Rota Bulo, T. Windheuser, M. V estner, and D. Cremers,
“Dense non-rigid shape correspondence using random forests,” in Proc.
CVPR, 2014.
[109] O. Litany, E. Rodolà, A. M. Bronstein, and M. M. Bronstein, “Deep
functional maps: Structured prediction for dense shape correspon-
dence,” arXiv:1704.08686, 2017.
[110] F. Tombari, S. Salti, and L. Di Stefano, “Unique signatures of his-
tograms for local surface description,” in Proc. ECCV, 2010.
[111] P . Battaglia, R. Pascanu, M. Lai, D. J. Rezende et al., “Interaction
networks for learning about objects, relations and physics,” in Proc.
NIPS, 2016.
[112] M. B. Chang, T. Ullman, A. Torralba, and J. B. Tenenbaum, “A
compositional object-based approach to learning physical dynamics,”
arXiv:1612.00341, 2016.
[113] H. L. Morgan, “The generation of a unique machine description for
chemical structure,” J. Chemical Documentation, vol. 5, no. 2, pp. 107–
113, 1965.
[114] R. C. Glem, A. Bender, C. H. Arnby, L. Carlsson, S. Boyer, and
J. Smith, “The generation of a unique machine description for chemical
structure,” Investigational Drugs, vol. 9, no. 3, pp. 199–204, 2006.
[115] D. Rogers and M. Hahn, “Extended-connectivity fingerprints,” J. Chem-
ical Information and Modeling, vol. 50, no. 5, pp. 742–754, 2010.
[116] M. G. Preti, T. A. Bolton, and D. V an De Ville, “The dynamic
functional connectome: State-of-the-art and perspectives,” NeuroImage,
2016.
[117] S. I. Ktena, S. Parisot, E. Ferrante, M. Rajchl, M. Lee, B. Glocker, and
D. Rueckert, “Distance metric learning using graph convolutional net-
works: Application to functional brain networks,” arXiv:1703.02161,
2017.
[118] L. Yi, H. Su, X. Guo, and L. J. Guibas, “SyncSpecCNN: Synchronized
spectral CNN for 3D shape segmentation,” in Proc. CVPR, 2017.
[119] M. Jaderberg, K. Simonyan, A. Zisserman, and K. Kavukcuoglu,
“Spatial transformer networks,” in Proc. NIPS, 2015.
[120] A. Dosovitskiy, J. Springenberg, M. Tatarchenko, and T. Brox, “Learn-
ing to generate chairs, tables and cars with convolutional networks,”
in Proc. CVPR, 2015.
[121] S. Dieleman, H. Zen, K. Simonyan, O. Vinyals, A. Graves, N. Kalch-
brenner, A. Senior, and K. Kavukcuoglu, “Wavenet: A generative model
for raw audio,” arXiv:1609.03499, 2016.
[122] D. Boscaini, D. Eynard, D. Kourounis, and M. M. Bronstein, “Shape-
from-operator: Recovering shapes from intrinsic operators,” in Com-
puter Graphics F orum, vol. 34, no. 2, 2015, pp. 265–274.