图神经网络（十）：FASTGCN: FAST LEARNING WITH GRAPH CONVOLUTIONAL NETWORKS VIA IMPORTANCE SAMPLING

这篇论文提出了一种名为fastGCN的新模型，旨在解决传统GCN（图卷积网络）在处理大型动态图时的计算效率问题。传统GCN主要适用于Transductive任务（仅对训练数据进行预测），而实际应用中更需要Inductive模型（能够处理不断变化的新数据）。fastGCN通过将图节点解释为某种概率分布下的独立同分布样本，并利用蒙特卡洛近似对积分进行评估，将复杂的卷积操作转换为更高效的计算方式。这种方法不仅降低了模型复杂度，还引入了重要性采样以进一步优化估计结果。此外，fastGCN还通过与GraphSAGE的对比展示了其在稀疏性和计算效率方面的优势，在保持准确性的同时显著提升了性能。

该研究引入了fastGCN方法，在其核心思想中提出了一种新的处理图数据的方式：它主要基于将图中的每个节点视为独立同分布的概率分布样本，并将其损失与每个卷积层表示成顶点嵌入函数的积分形式。随后采用蒙特卡洛方法对这些积分进行估计以获得最终结果。

Introduction：
研究背景：
尽管17年提出图卷积网络（GCN）展现了不错的性能[1]，但其局限性在于在训练过程中需要全局图的信息而使其实现仅限于Transductive场景。这与现实世界中图节点动态变化的特点不符，在这种情况下开发一种归纳模型尤为迫切。然而，在这一领域仍面临一个更为严峻的问题——递归扩展邻域带来的计算成本较高。特别是在处理稠密图和幂律分布图时这一问题尤为突出，在小批量训练中也会产生大量相关数据量需处理。因此实现对大规模密集图的有效应用仍需解决好扩展性这一关键问题

作者致力于研究一种Inductive类型的模型，并探讨该模型如何能够在大规模图数据中实现显著地降低其复杂度。

其研究工作主要贡献在于：将其创新性地将图卷积算子视为一种基于概率测度框架下的嵌入函数积分变换。这种视角则为归纳学习提供了坚实的理论支撑。具体而言, 本文则将图中的顶点解释为一种特定的概率分布下的独立同分布样本, 并将其损失与每个卷积层对应的顶点嵌入函数的积分相关联。进而通过蒙特卡罗方法对这些损失进行估计, 并允许根据需要调整采样分布（例如, 在重要性采样中选择合适的策略）来降低估计方差。

作者提出的模型：
首先回顾GCN的传播规则：

从本质上讲, GCN通过融合自身特性和领域节点信息来构建其表示。具体而言, 对于任意顶点V, 其表征可通过该数学表达式得到, 其实质是对归一化后的邻接矩阵对应行的数据进行特征整合。

在研究过程中，默认假设所涉及的图形为无穷大量，并将当前关注的具体图形视为这一无穷大量中的一个局部子图形；基于此前提下，在讨论一个无穷大的整体时（即整个图形），我们可以将其表示为积分的形式。

其中P(U)代表节点的概率分布，在模型假设下认为每个节点都是独立同分布样本。
通过蒙特卡洛方法, 从每一层中抽取t_l个样本点用于数值积分计算, 从而推导出各层对应的顶点表示：

对应这个算法：

随后作者以降低估计方差为目标，并提出了一种名为重要性采样的技术；该技术规定：每个顶点均按照以下概率分布进行采样：

该过程实际上是指通过邻接矩阵计算各顶点对其他顶点的贡献度作为其重要性指标；更直观地说，则是依据各节点连接的数量来进行采样；改进后所得到的每一层顶点表示即为此：

对应算法2：

在主要方面上，这两个算法存在显著差异：第一种方法采用等比例选取tl个样本的方式；第二种方法则基于节点的重要性权重进行样本选取。

该图所反映的是以下内容：首先将整个数据集划分为多个批次，在每个批次中按照概率q(u)随机选择tl个节点进行训练操作。值得注意的是，在这一过程中最后一层并没有采用采样策略。随后将其与GraphSAGE方法进行对比分析：FastGCN在每层阶段内均固定选择一定数量的节点参与计算，而GraphSAGE则针对每个节点随机选取固定的邻居数量作为输入特征。值得注意的是这两者具有相似的特点即在采样阶段都采用了固定数量的选择策略。然而还存在一个潜在的问题即当两个相邻层次之间的采样节点缺乏关联性（即两者之间也没有任何连接边）时可能导致网络表现出较高的稀疏性这可能进而影响最终模型性能的表现效果。

如果未能理解的话 首先假设每个batch包含有589944张图片 然后从第一层中选取了2374张样本进入第二层 每一层的抽样比例都是相同的 接着从第二层中选取了949张样本进入第三层 在第三层次则不进行抽样操作；相反地 在第三层次中使用前一层的样本数量（即167）来推断整个层次的规模（即286）。这样不仅减少了计算量 还能够保持数据的代表性与准确性

Results：

本文的主要研究内容是什么？该研究是否建立在何种假设基础之上？这些假设在哪些场景下可能失效？该算法在何种条件下可能失效？其目的是针对历史上的哪些问题进行解决？

占位！！！