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.

本文提出了一种灵活的图节点特征分布描述方法，即特征函数，并引入了计算 FEATHER 算法。该算法定义了特征函数的概率权重，以表示随机游走的转移概率。实验显示，该算法可用于节点级别机器学习和图分类算法的特征提取，并且在数据上的鲁棒性良好。本文还定义了基于特征函数的参数化模型，并在真实数据集上展示了该算法优越性能。

图上的特征函数：从统计特征到参数模型

Characteristic Functions on Graphs: Birds of a Feather, from Statistical  Descriptors to Parametric Models

Optimal transportation distances are valuable for comparing and analyzing
probability distributions, but larger-scale computational techniques for the
theoretically favorable quadratic case are limited to smooth domains or
regularized approximations. Motivated by fluid flow-based transportation on
$\mathbb{R}^n$, however, this paper introduces an alternative definition of
optimal transportation between distributions over graph vertices. This new
distance still satisfies the triangle inequality but has better scaling and a
connection to continuous theories of transportation. It is constructed by
adapting a Riemannian structure over probability distributions to the graph
case, providing transportation distances as shortest-paths in probability
space. After defining and analyzing theoretical properties of our new distance,
we provide a time discretization as well as experiments verifying its
effectiveness.

该论文提出了一种基于图顶点的概率分布最优传输方法，它不仅满足三角不等式，而且具有更好的可扩展性和与连续传输理论的联系，同时提供了一个适用于该方法的时间离散化方法并验证了其有效性。

连续图传输距离

Continuous-Flow Graph Transportation Distances

A new class of distances for graph vertices is proposed. This class contains
parametric families of distances which reduce to the shortest-path, weighted
shortest-path, and the resistance distances at the limiting values of the
family parameters. The main property of the class is that all distances it
comprises are graph-geodetic: $d(i,j)+d(j,k)=d(i,k)$ if and only if every path
from $i$ to $k$ passes through $j$. The construction of the class is based on
the matrix forest theorem and the transition inequality.

本文提出了一类包含参数族的距离，该类距离在族参数的极限值处降至最短路径、有权最短路径和电阻距离。该类距离的主要性质是所有距离都是图地理距离：如果且仅当从 $i$ 到 $k$ 的每一条路径都通过 $j$，则 $d (i,j)+d (j,k)=d (i,k)$。该类的构造基于矩阵森林定理和转移不等式。