论文标题
图表上的特征功能：羽毛鸟，从统计描述到参数模型
Characteristic Functions on Graphs: Birds of a Feather, from Statistical Descriptors to Parametric Models
论文作者
论文摘要
在本文中，我们提出了图表顶点定义的特征函数的灵活概念，以描述多个尺度上顶点特征的分布。我们介绍了羽毛，这是一种计算有效算法，用于计算这些特征函数的特定变体，其中特征函数的概率权重定义为随机步行的过渡概率。我们认为，此过程提取的功能对于节点级别的机器学习任务很有用。我们讨论这些节点表示的汇总，从而导致图形的紧凑描述符，这些描述可以用作图形分类算法的特征。我们在分析上证明，羽毛描述具有相同表示形式的同构图，并表现出对数据损坏的鲁棒性。使用节点特征特征函数，我们定义了参数模型，其中学习了函数的评估点是监督分类器的参数。现实世界中的实验大型数据集表明，我们提出的算法会创建高质量的表示，有效地进行转移学习，对超参数变化表现出鲁棒性，并与输入大小线性缩放。
In this paper, we propose a flexible notion of characteristic functions defined on graph vertices to describe the distribution of vertex features at multiple scales. We introduce FEATHER, a computationally efficient algorithm to calculate a specific variant of these characteristic functions where the probability weights of the characteristic function are defined as the transition probabilities of random walks. We argue that features extracted by this procedure are useful for node level machine learning tasks. We discuss the pooling of these node representations, resulting in compact descriptors of graphs that can serve as features for graph classification algorithms. We analytically prove that FEATHER describes isomorphic graphs with the same representation and exhibits robustness to data corruption. Using the node feature characteristic functions we define parametric models where evaluation points of the functions are learned parameters of supervised classifiers. Experiments on real world large datasets show that our proposed algorithm creates high quality representations, performs transfer learning efficiently, exhibits robustness to hyperparameter changes, and scales linearly with the input size.
