A low discrepancy sequence on graphs
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
GraphRNN: Generating Realistic Graphs with Deep Auto-regressive Models
Modeling and generating graphs is fundamental for studying networks in biology, engineering, and social sciences. However, modeling complex distributions over graphs and then efficiently sampling from these distributions…
Graph GenerationNeural Low-Discrepancy Sequences
Low-discrepancy points are designed to efficiently fill the space in a uniform manner. This uniformity is highly advantageous in many problems in science and engineering, including in numerical integration, computer visi…
Abstract AlgebraMotion PlanningGromov-Wasserstein Factorization Models for Graph Clustering
We propose a new nonlinear factorization model for graphs that are with topological structures, and optionally, node attributes. This model is based on a pseudometric called Gromov-Wasserstein (GW) discrepancy, which com…
ClusteringGraph ClusteringRolling Shutter CorrectionEvoluNet: Advancing Dynamic Non-IID Transfer Learning on Graphs
Non-IID transfer learning on graphs is crucial in many high-stakes domains. The majority of existing works assume stationary distribution for both source and target domains. However, real-world graphs are intrinsically d…
Transfer LearningAugmenting Knowledge Transfer across Graphs
Given a resource-rich source graph and a resource-scarce target graph, how can we effectively transfer knowledge across graphs and ensure a good generalization performance? In many high-impact domains (e.g., brain networ…
Domain AdaptationTransfer Learning