标题： 关于图的统计学习 显示英文标题

标题： On statistical learning of graphs

摘要： 我们研究由可数无限图G的复制形成的假设类的PAC和在线可学习性，其中每个复制是通过排列G的顶点得到的。 这对应于学习一个图的标记，已知其结构和标记集。 我们考虑那些仅移动有限多个顶点的排列的类。 我们的主要结果表明，所有这种有限支持复制的PAC可学习性意味着G的完整同构类型的在线可学习性，并且等价于自同构平凡性的条件。 我们还使用无限随机图的扩展性质的松弛来表征由交换两个顶点生成的复制不可学习的图。 最后，我们证明对于所有G和k>2，k-顶点排列的可学习性等价于2-顶点排列的可学习性，从而得出无限图的四类划分，我们还使用来自描述集合论和可计算性理论的工具确定了其复杂性。 显示英文摘要

摘要： We study PAC and online learnability of hypothesis classes formed by copies of a countably infinite graph G, where each copy is induced by permuting G's vertices. This corresponds to learning a graph's labeling, knowing its structure and label set. We consider classes where permutations move only finitely many vertices. Our main result shows that PAC learnability of all such finite-support copies implies online learnability of the full isomorphism type of G, and is equivalent to the condition of automorphic triviality. We also characterize graphs where copies induced by swapping two vertices are not learnable, using a relaxation of the extension property of the infinite random graph. Finally, we show that, for all G and k>2, learnability for k-vertex permutations is equivalent to that for 2-vertex permutations, yielding a four-class partition of infinite graphs, whose complexity we also determine using tools coming from both descriptive set theory and computability theory.