标题： 从一个图中学习：通过小随机世界几何的归纳学习保证 显示英文标题

标题： Learning from one graph: transductive learning guarantees via the geometry of small random worlds

摘要： 自Kipf和Welling在$2017$中引入以来，图卷积网络的主要用途是归纳节点分类，在单个观测图及其特征矩阵中推断缺失标签。 尽管该网络模型被广泛使用，但归纳学习的统计基础仍然有限，因为标准推理框架通常依赖于多个独立样本，而不是单个图。 在本工作中，我们通过开发新的集中度测量工具来弥补这些差距，这些工具通过低维度度量嵌入利用大规模图的几何规律。 涌现的规律性通过随机图模型来捕捉；然而，一旦观察到，这些方法仍适用于确定性图。 我们建立了两个主要的学习结果。 第一个涉及任意确定性$k$顶点图，第二个则针对在$p \in \mathcal{O}((\log (k)/k)^{1/2})$范围内与Erdős-Rényi图$\mathbf{G}=\mathbf{G}(k,p)$共享关键几何特性的随机图。 第一个结果为第二个结果提供了基础并加以阐明。 随后，我们将这些结果扩展到图卷积网络设置中，其中出现了额外的挑战。 最后，即使只有少量标记节点$N$，我们的学习保证仍然具有信息量，并且随着$N$的增长达到最优非参数率$\mathcal{O}(N^{-1/2})$。 显示英文摘要

摘要： Since their introduction by Kipf and Welling in $2017$, a primary use of graph convolutional networks is transductive node classification, where missing labels are inferred within a single observed graph and its feature matrix. Despite the widespread use of the network model, the statistical foundations of transductive learning remain limited, as standard inference frameworks typically rely on multiple independent samples rather than a single graph. In this work, we address these gaps by developing new concentration-of-measure tools that leverage the geometric regularities of large graphs via low-dimensional metric embeddings. The emergent regularities are captured using a random graph model; however, the methods remain applicable to deterministic graphs once observed. We establish two principal learning results. The first concerns arbitrary deterministic $k$-vertex graphs, and the second addresses random graphs that share key geometric properties with an Erd\H{o}s-R\'{e}nyi graph $\mathbf{G}=\mathbf{G}(k,p)$ in the regime $p \in \mathcal{O}((\log (k)/k)^{1/2})$. The first result serves as the basis for and illuminates the second. We then extend these results to the graph convolutional network setting, where additional challenges arise. Lastly, our learning guarantees remain informative even with a few labelled nodes $N$ and achieve the optimal nonparametric rate $\mathcal{O}(N^{-1/2})$ as $N$ grows.