论文标题
图上的低差异序列
A low discrepancy sequence on graphs
论文作者
论文摘要
许多应用程序，例如选举预测，环境监测，健康政策和基于图形的机器学习都需要对图表顶点定义的功能进行期望。我们描述了一种类似于复杂电势理论中所谓的LEJA点的采样方案的构造，可以证明，基于这些点，可通过这些点具有可观的期望值对期望值的近似值产生较低的差异估计。与经典的潜在理论相反，固定内核和平衡分布取决于内核，我们固定概率分布并构造一个核（代表图形结构），其平衡分布是给定概率分布的。我们的估计不取决于图的大小。
Many applications such as election forecasting, environmental monitoring, health policy, and graph based machine learning require taking expectation of functions defined on the vertices of a graph. We describe a construction of a sampling scheme analogous to the so called Leja points in complex potential theory that can be proved to give low discrepancy estimates for the approximation of the expected value by the impirical expected value based on these points. In contrast to classical potential theory where the kernel is fixed and the equilibrium distribution depends upon the kernel, we fix a probability distribution and construct a kernel (which represents the graph structure) for which the equilibrium distribution is the given probability distribution. Our estimates do not depend upon the size of the graph.
