右肺下叶gnn是什么意思 gnn是什么意思网络用语( 二 ) _经验知识

文章主要贡献本文所研究的特定任务是图论中的一些优化任务，特定限制条件是 GNN 的深度和广度，将深度和广度与理论计算机科学中的复杂度等度量联系起来，再将计算复杂度作为这些优化任务的完成下界（从 impossible 变为 possible 的最低复杂度要求），从而得到GNN的深度和广度对具体任务的影响，以及对GNN普适性的影响。具体地，关于普适性的研究有以下两个结论。
1、GNN 的图灵普适性
在足够的条件下，GNN 能以图灵机的形式对任意输入函数进行运算，且不限于网络结构。通过建立 GNN 和经典分布式计算模型 LOCAL 之间的图灵等效，来间接的研究其普适性。这里的足够条件是：
（1）有足够的层数
（2）每一层都有足够的广度
（3）节点之间可以相互独立（ids）
（4）每一层计算的函数有足够的表现力

文章插图
2、GNN 的学习能力局限性
正如前面提到的，在深度和广度都被限制的情况下，GNN是无法表现出其图灵普适性，即应用在具体任务上时，无法解决这个任务。那么如何确定能否完成任务的下界呢？还是通过 LOCAL 。任务或问题的 impossiblility result 可以在GNN和LOCAL之间以一定的形式相互转换，因此研究任务在 GNN下能否完成和在LOCAL下能否完成是等效的，进而可以在LOCAL模型下为完成任务的计算复杂度要求设置下界。具体的，文章中提到了四种类型的任务（问题定义详见原论文）：
（1）检测（detecting）图G中是否含有特定长度的环（cycle of specific length）
（2）验证（verifying）图G的给定子图是否连通（connected），是否具有环（cycle），是否为生成树（spanning tree，具备树结构，没有环），是否为二分图（bipartite，顶点 *** 可以分为两个子集，所有边的两个顶点分属于这两个子集），是否为简单路径（simple path，与图的哈密顿循环有关）
（3）计算（computing）两个顶点间的最短路径（shortest path between two vertices），图的最小割（minimum cut），以及最小生成树（the minimum spanning tree）
（4）求图的最大独立集（maximum independent），最小顶点覆盖（minimum vertex cover），或图的顶点着色问题（chromatic coloring）
以上问题都是属于图论中的传统优化问题，虽然不是现在主流研究的顶点分类，图分类问题，但二者之间有密不可分的联系。这些问题的具体计算复杂度下界为：

文章插图
总结本文首次对GNN模型提出了 impossible 问题，并通过等效计算的 *** ，以计算复杂度的形式，给出了 GNN 在部分图论任务中impossible results下界与网络宽度和广度的关系，在一定程度上说明了 GNN 的性能会受到网络本身的宽度和广度的限制。
由于原文中的数学推导过于复杂，因此这里我只介绍文章的基本思想。GNN作为目前机器学习领域的热门研究之一，已经被应用于各种各样的任务，通常在应用一个网络的同时，也要同步地去研究这个网络的内在本质，从而更好的理解，改进它，进而帮助我们在实际应用网络时更好的设置网络的参数，这篇文章就是一个很好的例子。
【参考文献】
[1] https://en. *** .org/wiki/Consensus_(computer_science)
[2] Fischer, M. J.; Lynch, N. A.; Paterson, M. S. (1985). "Impossibility of distributed consensus with one faulty process" (PDF). Journal of the ACM. 32 (2): 374–382. doi:10.1145/3149.214121.
原文链接： https://arxiv.org/abs/1907.03199