我们研究光谱图卷积神经网络(GCNN),其中过滤器被定义为通过功能计算的图形移位算子(GSO)的连续函数。光谱GCNN不是针对一个特定图的量身定制的,可以在不同的图之间传输。因此,研究GCNN的可传递性很重要:网络在代表相同现象的不同图上具有大致相同影响的能力。如果测试集中的图与训练集中的图形相同,则可传递性可确保在某些图上进行训练的GCNN概括。在本文中,我们考虑了基于Graphon分析的可转让性模型。图形是图形的极限对象,在图形范式中,如果两者都近似相同的图形,则两个图表示相同的现象。我们的主要贡献可以总结如下:1)我们证明,在近似于同一图形的图的图下,任何具有连续过滤器的固定GCNN都是可以转移的,2)我们证明了近似于未结合的图形换档运算符的图形,该图是在本文中定义的,和3)我们获得了非反应近似结果,证明了GCNN的线性稳定性。这扩展了当前的最新结果,这些结果显示了在近似界图子的图下显示多项式过滤器的渐近可传递性。
translated by 谷歌翻译
图形神经网络(GNNS)是由图形卷积和叉指非线性组成的层组成的深度卷积架构。由于其不变性和稳定性属性,GNN在网络数据的学习陈述中被证明是成功的。但是,训练它们需要矩阵计算,这对于大图可能是昂贵的。为了解决这个限制,我们研究了GNN横跨图形转移的能力。我们考虑图形,这是加权和随机图形的图形限制和生成模型,以定义图形卷积和GNNS - Graphon卷曲和Graphon神经网络(WNNS)的限制对象 - 我们用作图形卷曲的生成模型和GNNS。我们表明,这些石墨源区和WNN可以通过图形滤波器和来自加权和随机图中的它们采样的GNN来近似。使用这些结果,我们将导出误差界限,用于跨越此类图形传输图形过滤器和GNN。这些界限表明,可转换性随着图尺寸的增加而增加,并且揭示了在GNN中的可转换性和光谱分辨率之间的折衷,其被点亮的非线性缓解。这些发现经验在电影推荐和分散机器人控制中的数值实验中进行了经验验证。
translated by 谷歌翻译
消息传递神经网络(MPNN)自从引入卷积神经网络以泛滥到图形结构的数据以来,人们的受欢迎程度急剧上升,现在被认为是解决各种以图形为中心的最先进的工具问题。我们研究图形分类和回归中MPNN的概括误差。我们假设不同类别的图是从不同的随机图模型中采样的。我们表明,当在从这种分布中采样的数据集上训练MPNN时,概括差距会增加MPNN的复杂性,并且不仅相对于训练样本的数量,而且还会减少节点的平均数量在图中。这表明,只要图形很大,具有高复杂性的MPNN如何从图形的小数据集中概括。概括结合是从均匀收敛结果得出的,该结果表明,应用于图的任何MPNN近似于该图离散的几何模型上应用的MPNN。
translated by 谷歌翻译
In this paper we propose a pooling approach for convolutional information processing on graphs relying on the theory of graphons and limits of dense graph sequences. We present three methods that exploit the induced graphon representation of graphs and graph signals on partitions of [0, 1]2 in the graphon space. As a result we derive low dimensional representations of the convolutional operators, while a dimensionality reduction of the signals is achieved by simple local interpolation of functions in L2([0, 1]). We prove that those low dimensional representations constitute a convergent sequence of graphs and graph signals, respectively. The methods proposed and the theoretical guarantees that we provide show that the reduced graphs and signals inherit spectral-structural properties of the original quantities. We evaluate our approach with a set of numerical experiments performed on graph neural networks (GNNs) that rely on graphon pooling. We observe that graphon pooling performs significantly better than other approaches proposed in the literature when dimensionality reduction ratios between layers are large. We also observe that when graphon pooling is used we have, in general, less overfitting and lower computational cost.
translated by 谷歌翻译
图形神经网络(GNNS)使用图形卷积来利用网络不向导并从网络数据中学习有意义的特征表示。但是,在大规模图中,卷积以高计算成本产生,导致可伸缩性限制。在本文中,我们考虑了学习图形神经网络(WNN)的问题 - GNN的极限对象 - 通过训练从Graphon采样的图形上,我们考虑了学习GragraN神经网络(WNN)的问题。在平滑性条件下,我们表明:(i)GNN和WNN上的学习步骤之间的预期距离随图形的尺寸渐近地降低,并且(ii)在一系列生长图上训练时,梯度下降遵循WNN的学习方向。受这些结果的启发,我们提出了一种新型算法,以学习大规模图的GNN,从中等数量的节点开始,在训练过程中依次增加了图的大小。该算法是在分散的控制问题上进一步基准的,在该问题下,它以降低的计算成本保留了与大规模对应物相当的性能。
translated by 谷歌翻译
散射变换是一种基于多层的小波的深度学习架构,其充当卷积神经网络的模型。最近,几种作品引入了非欧几里德设置的散射变换的概括,例如图形。我们的工作通过基于非常一般的非对称小波来引入图形的窗口和非窗口几何散射变换来构建这些结构。我们表明,这些不对称的图形散射变换具有许多与其对称对应的相同的理论保证。结果,所提出的结构统一并扩展了许多现有图散射架构的已知理论结果。在这样做时,这项工作有助于通过引入具有可提供稳定性和不变性保证的大型网络,帮助弥合几何散射和其他图形神经网络之间的差距。这些结果为未来的图形结构数据奠定了基础,对具有学习过滤器的图形结构数据,并且还可以证明具有理想的理论特性。
translated by 谷歌翻译
散射变换是一种基于小波的多层转换,最初是作为卷积神经网络(CNN)的模型引入的,它在我们对这些网络稳定性和不变性属性的理解中发挥了基础作用。随后,人们普遍兴趣将CNN的成功扩展到具有非欧盟结构的数据集,例如图形和歧管,从而导致了几何深度学习的新兴领域。为了提高我们对这个新领域中使用的体系结构的理解,几篇论文提出了对非欧几里得数据结构(如无方向的图形和紧凑的Riemannian歧管)的散射转换的概括。在本文中,我们介绍了一个通用的统一模型,用于测量空间上的几何散射。我们提出的框架包括以前的几何散射作品作为特殊情况,但也适用于更通用的设置,例如有向图,签名图和带边界的歧管。我们提出了一个新标准,该标准可以识别哪些有用表示应该不变的组,并表明该标准足以确保散射变换具有理想的稳定性和不变性属性。此外,我们考虑从随机采样未知歧管获得的有限度量空间。我们提出了两种构造数据驱动图的方法,在该图上相关的图形散射转换近似于基础歧管上的散射变换。此外,我们使用基于扩散图的方法来证明这些近似值之一的收敛速率的定量估计值,因为样品点的数量趋向于无穷大。最后,我们在球形图像,有向图和高维单细胞数据上展示了方法的实用性。
translated by 谷歌翻译
We introduce an architecture for processing signals supported on hypergraphs via graph neural networks (GNNs), which we call a Hyper-graph Expansion Neural Network (HENN), and provide the first bounds on the stability and transferability error of a hypergraph signal processing model. To do so, we provide a framework for bounding the stability and transferability error of GNNs across arbitrary graphs via spectral similarity. By bounding the difference between two graph shift operators (GSOs) in the positive semi-definite sense via their eigenvalue spectrum, we show that this error depends only on the properties of the GNN and the magnitude of spectral similarity of the GSOs. Moreover, we show that existing transferability results that assume the graphs are small perturbations of one another, or that the graphs are random and drawn from the same distribution or sampled from the same graphon can be recovered using our approach. Thus, both GNNs and our HENNs (trained using normalized Laplacians as graph shift operators) will be increasingly stable and transferable as the graphs become larger. Experimental results illustrate the importance of considering multiple graph representations in HENN, and show its superior performance when transferability is desired.
translated by 谷歌翻译
在本文中,我们为基于非交换代数的代数神经网络(ALGNN)提供稳定性结果。 ALGNN是堆叠的分层结构,每个层都与代数信号模型(ASM)相关联,由代数,矢量空间和同态性。信号被建模为矢量空间的元素,过滤器是代数中的元素,而同态则可以实现过滤器作为混凝土操作员。我们研究了代数过滤器在非交换代数对同态扰动中的稳定性,并提供了保证稳定性的条件。我们表明,轮班运算符和偏移和扰动之间的换向性不会影响稳定体系结构的属性。这提供了一个问题,即转移不变性是否是保证稳定性的卷积体系结构的必要属性。此外,我们表明,尽管非交换代数中过滤器的频率响应在交换代数中与过滤器相对于过滤器表现出很大的差异,但它们的稳定过滤器的衍生物具有相似的行为。
translated by 谷歌翻译
神经网络的经典发展主要集中在有限维欧基德空间或有限组之间的学习映射。我们提出了神经网络的概括,以学习映射无限尺寸函数空间之间的运算符。我们通过一类线性积分运算符和非线性激活函数的组成制定运营商的近似,使得组合的操作员可以近似复杂的非线性运算符。我们证明了我们建筑的普遍近似定理。此外,我们介绍了四类运算符参数化:基于图形的运算符,低秩运算符,基于多极图形的运算符和傅里叶运算符,并描述了每个用于用每个计算的高效算法。所提出的神经运营商是决议不变的:它们在底层函数空间的不同离散化之间共享相同的网络参数,并且可以用于零击超分辨率。在数值上,与现有的基于机器学习的方法,达西流程和Navier-Stokes方程相比,所提出的模型显示出卓越的性能,而与传统的PDE求解器相比,与现有的基于机器学习的方法有关的基于机器学习的方法。
translated by 谷歌翻译
High-dimensional data arises in numerous applications, and the rapidly developing field of geometric deep learning seeks to develop neural network architectures to analyze such data in non-Euclidean domains, such as graphs and manifolds. Recent work by Z. Wang, L. Ruiz, and A. Ribeiro has introduced a method for constructing manifold neural networks using the spectral decomposition of the Laplace Beltrami operator. Moreover, in this work, the authors provide a numerical scheme for implementing such neural networks when the manifold is unknown and one only has access to finitely many sample points. The authors show that this scheme, which relies upon building a data-driven graph, converges to the continuum limit as the number of sample points tends to infinity. Here, we build upon this result by establishing a rate of convergence that depends on the intrinsic dimension of the manifold but is independent of the ambient dimension. We also discuss how the rate of convergence depends on the depth of the network and the number of filters used in each layer.
translated by 谷歌翻译
我们为特殊神经网络架构,称为运营商复发性神经网络的理论分析,用于近似非线性函数,其输入是线性运算符。这些功能通常在解决方案算法中出现用于逆边值问题的问题。传统的神经网络将输入数据视为向量,因此它们没有有效地捕获与对应于这种逆问题中的数据的线性运算符相关联的乘法结构。因此,我们介绍一个类似标准的神经网络架构的新系列,但是输入数据在向量上乘法作用。由较小的算子出现在边界控制中的紧凑型操作员和波动方程的反边值问题分析,我们在网络中的选择权重矩阵中促进结构和稀疏性。在描述此架构后,我们研究其表示属性以及其近似属性。我们还表明,可以引入明确的正则化,其可以从所述逆问题的数学分析导出,并导致概括属性上的某些保证。我们观察到重量矩阵的稀疏性改善了概括估计。最后,我们讨论如何将运营商复发网络视为深度学习模拟,以确定诸如用于从边界测量的声波方程中重建所未知的WAVESTED的边界控制的算法算法。
translated by 谷歌翻译
Koopman运算符是无限维的运算符,可全球线性化非线性动态系统,使其光谱信息可用于理解动态。然而,Koopman运算符可以具有连续的光谱和无限维度的子空间,使得它们的光谱信息提供相当大的挑战。本文介绍了具有严格融合的数据驱动算法,用于从轨迹数据计算Koopman运算符的频谱信息。我们引入了残余动态模式分解(ResDMD),它提供了第一种用于计算普通Koopman运算符的Spectra和PseudtoStra的第一种方案,无需光谱污染。使用解析器操作员和RESDMD,我们还计算与测量保存动态系统相关的光谱度量的平滑近似。我们证明了我们的算法的显式收敛定理,即使计算连续频谱和离散频谱的密度,也可以实现高阶收敛即使是混沌系统。我们展示了在帐篷地图,高斯迭代地图,非线性摆,双摆,洛伦茨系统和11美元延长洛伦兹系统的算法。最后,我们为具有高维状态空间的动态系统提供了我们的算法的核化变体。这使我们能够计算与具有20,046维状态空间的蛋白质分子的动态相关的光谱度量,并计算出湍流流过空气的误差界限的非线性Koopman模式,其具有雷诺数为$> 10 ^ 5 $。一个295,122维的状态空间。
translated by 谷歌翻译
Although theoretical properties such as expressive power and over-smoothing of graph neural networks (GNN) have been extensively studied recently, its convergence property is a relatively new direction. In this paper, we investigate the convergence of one powerful GNN, Invariant Graph Network (IGN) over graphs sampled from graphons. We first prove the stability of linear layers for general $k$-IGN (of order $k$) based on a novel interpretation of linear equivariant layers. Building upon this result, we prove the convergence of $k$-IGN under the model of \citet{ruiz2020graphon}, where we access the edge weight but the convergence error is measured for graphon inputs. Under the more natural (and more challenging) setting of \citet{keriven2020convergence} where one can only access 0-1 adjacency matrix sampled according to edge probability, we first show a negative result that the convergence of any IGN is not possible. We then obtain the convergence of a subset of IGNs, denoted as IGN-small, after the edge probability estimation. We show that IGN-small still contains function class rich enough that can approximate spectral GNNs arbitrarily well. Lastly, we perform experiments on various graphon models to verify our statements.
translated by 谷歌翻译
本文通过引入几何深度学习(GDL)框架来构建通用馈电型型模型与可区分的流形几何形状兼容的通用馈电型模型,从而解决了对非欧国人数据进行处理的需求。我们表明,我们的GDL模型可以在受控最大直径的紧凑型组上均匀地近似任何连续目标函数。我们在近似GDL模型的深度上获得了最大直径和上限的曲率依赖性下限。相反,我们发现任何两个非分类紧凑型歧管之间始终都有连续的函数,任何“局部定义”的GDL模型都不能均匀地近似。我们的最后一个主要结果确定了数据依赖性条件,确保实施我们近似的GDL模型破坏了“维度的诅咒”。我们发现,任何“现实世界”(即有限)数据集始终满足我们的状况,相反,如果目标函数平滑,则任何数据集都满足我们的要求。作为应用,我们确认了以下GDL模型的通用近似功能:Ganea等。 (2018)的双波利馈电网络,实施Krishnan等人的体系结构。 (2015年)的深卡尔曼 - 滤波器和深度玛克斯分类器。我们构建了:Meyer等人的SPD-Matrix回归剂的通用扩展/变体。 (2011)和Fletcher(2003)的Procrustean回归剂。在欧几里得的环境中,我们的结果暗示了Kidger和Lyons(2020)的近似定理和Yarotsky和Zhevnerchuk(2019)无估计近似率的数据依赖性版本的定量版本。
translated by 谷歌翻译
We consider the problem of estimating a multivariate function $f_0$ of bounded variation (BV), from noisy observations $y_i = f_0(x_i) + z_i$ made at random design points $x_i \in \mathbb{R}^d$, $i=1,\ldots,n$. We study an estimator that forms the Voronoi diagram of the design points, and then solves an optimization problem that regularizes according to a certain discrete notion of total variation (TV): the sum of weighted absolute differences of parameters $\theta_i,\theta_j$ (which estimate the function values $f_0(x_i),f_0(x_j)$) at all neighboring cells $i,j$ in the Voronoi diagram. This is seen to be equivalent to a variational optimization problem that regularizes according to the usual continuum (measure-theoretic) notion of TV, once we restrict the domain to functions that are piecewise constant over the Voronoi diagram. The regression estimator under consideration hence performs (shrunken) local averaging over adaptively formed unions of Voronoi cells, and we refer to it as the Voronoigram, following the ideas in Koenker (2005), and drawing inspiration from Tukey's regressogram (Tukey, 1961). Our contributions in this paper span both the conceptual and theoretical frontiers: we discuss some of the unique properties of the Voronoigram in comparison to TV-regularized estimators that use other graph-based discretizations; we derive the asymptotic limit of the Voronoi TV functional; and we prove that the Voronoigram is minimax rate optimal (up to log factors) for estimating BV functions that are essentially bounded.
translated by 谷歌翻译
Network data are ubiquitous in modern machine learning, with tasks of interest including node classification, node clustering and link prediction. A frequent approach begins by learning an Euclidean embedding of the network, to which algorithms developed for vector-valued data are applied. For large networks, embeddings are learned using stochastic gradient methods where the sub-sampling scheme can be freely chosen. Despite the strong empirical performance of such methods, they are not well understood theoretically. Our work encapsulates representation methods using a subsampling approach, such as node2vec, into a single unifying framework. We prove, under the assumption that the graph is exchangeable, that the distribution of the learned embedding vectors asymptotically decouples. Moreover, we characterize the asymptotic distribution and provided rates of convergence, in terms of the latent parameters, which includes the choice of loss function and the embedding dimension. This provides a theoretical foundation to understand what the embedding vectors represent and how well these methods perform on downstream tasks. Notably, we observe that typically used loss functions may lead to shortcomings, such as a lack of Fisher consistency.
translated by 谷歌翻译
本文研究了基于Laplacian Eigenmaps(Le)的基于Laplacian EIGENMAPS(PCR-LE)的主要成分回归的统计性质,这是基于Laplacian Eigenmaps(Le)的非参数回归的方法。 PCR-LE通过投影观察到的响应的向量$ {\ bf y} =(y_1,\ ldots,y_n)$ to to changbood图表拉普拉斯的某些特征向量跨越的子空间。我们表明PCR-Le通过SoboLev空格实现了随机设计回归的最小收敛速率。在设计密度$ P $的足够平滑条件下,PCR-le达到估计的最佳速率(其中已知平方$ l ^ 2 $ norm的最佳速率为$ n ^ { - 2s /(2s + d) )} $)和健美的测试($ n ^ { - 4s /(4s + d)$)。我们还表明PCR-LE是\ EMPH {歧管Adaptive}:即,我们考虑在小型内在维度$ M $的歧管上支持设计的情况,并为PCR-LE提供更快的界限Minimax估计($ n ^ { - 2s /(2s + m)$)和测试($ n ^ { - 4s /(4s + m)$)收敛率。有趣的是,这些利率几乎总是比图形拉普拉斯特征向量的已知收敛率更快;换句话说,对于这个问题的回归估计的特征似乎更容易,统计上讲,而不是估计特征本身。我们通过经验证据支持这些理论结果。
translated by 谷歌翻译
我们通过严格的数学论点建设性地展示了GNN在紧凑型$ d $维欧几里得网格上的近似频带限制功能中的架构优于NN的架构。我们表明,前者只需要$ \ MATHCAL {m} $采样函数值就可以实现$ o_ {d}的均匀近似错误(2^{ - \ \ m athcal {m} {m}^{1/d/d/d}}}}} $从某种意义上说,这个错误率是最佳的,NNS可能会取得更糟的情况。
translated by 谷歌翻译
Lipschitz Learning是一种基于图的半监督学习方法,其中一个人通过在加权图上求解Infinity Laplace方程来扩展标签到未标记的数据集的标签。在这项工作中,随着顶点的数量生长到无穷大,我们证明了图形无穷大行道方程的解决方案的统一收敛速率。它们的连续内容是绝对最小化LipsChitz扩展,即关于从图形顶点采样图形顶点的域的测地度量。我们在图表权重的非常一般的假设下工作,标记顶点的集合和连续域。我们的主要贡献是,即使对于非常稀疏的图形,我们也获得了定量的收敛速率,因为它们通常出现在半监督学习等应用中。特别是,我们的框架允许绘制到连接半径的图形带宽。为了证明,我们首先显示图表距离函数的定量收敛性声明,在连续体中的测量距离功能。使用“与距离函数的比较”原理,我们可以将这些收敛语句传递给无限谐波函数,绝对最小化Lipschitz扩展。
translated by 谷歌翻译