Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userLearning Graphons via Structured Gromov-Wasserstein Barycenters
86
0
0.0
(
0
)
Added by
Hongteng Xu
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We propose a novel and principled method to learn a nonparametric graph model called graphon, which is defined in an infinite-dimensional space and represents arbitrary-size graphs. Based on the weak regularity lemma from the theory of graphons, we leverage a step function to approximate a graphon. We show that the cut distance of graphons can be relaxed to the Gromov-Wasserstein distance of their step functions. Accordingly, given a set of graphs generated by an underlying graphon, we learn the corresponding step function as the Gromov-Wasserstein barycenter of the given graphs. Furthermore, we develop several enhancements and extensions of the basic algorithm, $e.g.$, the smoothed Gromov-Wasserstein barycenter for guaranteeing the continuity of the learned graphons and the mixed Gromov-Wasserstein barycenters for learning multiple structured graphons. The proposed approach overcomes drawbacks of prior state-of-the-art methods, and outperforms them on both synthetic and real-world data. The code is available at https://github.com/HongtengXu/SGWB-Graphon.
rate research
Read More
Graph matching finds the correspondence of nodes across two graphs and is a basic task in graph-based machine learning. Numerous existing methods match every node in one graph to one node in the other graph whereas two graphs usually overlap partially in many realworld{} applications. In this paper, a partial Gromov-Wasserstein learning framework is proposed for partially matching two graphs, which fuses the partial Gromov-Wasserstein distance and the partial Wasserstein distance as the objective and updates the partial transport map and the node embedding in an alternating fashion. The proposed framework transports a fraction of the probability mass and matches node pairs with high relative similarities across the two graphs. Incorporating an embedding learning method, heterogeneous graphs can also be matched. Numerical experiments on both synthetic and realworld{} graphs demonstrate that our framework can improve the F1 score by at least $20%$ and often much more.
In this thesis, we consider the Wasserstein barycenter problem of discrete probability measures from computational and statistical sides in two scenarios: (I) the measures are given and we need to compute their Wasserstein barycenter, and (ii) the measures are generated from a probability distribution and we need to calculate the population barycenter of the distribution defined by the notion of Frechet mean. The statistical focus is estimating the sample size of measures necessary to calculate an approximation for Frechet mean (barycenter) of a probability distribution with a given precision. For empirical risk minimization approaches, the question of the regularization is also studied together with proposing a new regularization which contributes to the better complexity bounds in comparison with quadratic regularization. The computational focus is developing algorithms for calculating Wasserstein barycenters: both primal and dual algorithms which can be executed in a decentralized manner. The motivation for dual approaches is closed-forms for the dual formulation of entropy-regularized Wasserstein distances and their derivatives, whereas the primal formulation has closed-form expression only in some cases, e.g., for Gaussian measures. Moreover, the dual oracle returning the gradient of the dual representation for entropy-regularized Wasserstein distance can be computed for a cheaper price in comparison with the primal oracle returning the gradient of the entropy-regularized Wasserstein distance. The number of dual oracle calls, in this case, will also be less, i.e., the square root of the number of primal oracle calls. This explains the successful application of the first-order dual approaches for the Wasserstein barycenter problem.
Image interpolation, or image morphing, refers to a visual transition between two (or more) input images. For such a transition to look visually appealing, its desirable properties are (i) to be smooth; (ii) to apply the minimal required change in the image; and (iii) to seem real, avoiding unnatural artifacts in each image in the transition. To obtain a smooth and straightforward transition, one may adopt the well-known Wasserstein Barycenter Problem (WBP). While this approach guarantees minimal changes under the Wasserstein metric, the resulting images might seem unnatural. In this work, we propose a novel approach for image morphing that possesses all three desired properties. To this end, we define a constrained variant of the WBP that enforces the intermediate images to satisfy an image prior. We describe an algorithm that solves this problem and demonstrate it using the sparse prior and generative adversarial networks.
Interpreting molecular dynamics simulations usually involves automated classification of local atomic environments to identify regions of interest. Existing approaches are generally limited to a small number of reference structures and only include limited information about the local chemical composition. This work proposes to use a variant of the Gromov-Wasserstein (GW) distance to quantify the difference between a local atomic environment and a set of arbitrary reference environments in a way that is sensitive to atomic displacements, missing atoms, and differences in chemical composition. This involves describing a local atomic environment as a finite metric measure space, which has the additional advantages of not requiring the local environment to be centered on an atom and of not making any assumptions about the material class. Numerical examples illustrate the efficacy and versatility of the algorithm.
In this work we introduce the concept of Bures-Wasserstein barycenter $Q_*$, that is essentially a Frechet mean of some distribution $mathbb{P}$ supported on a subspace of positive semi-definite Hermitian operators $mathbb{H}_{+}(d)$. We allow a barycenter to be restricted to some affine subspace of $mathbb{H}_{+}(d)$ and provide conditions ensuring its existence and uniqueness. We also investigate convergence and concentration properties of an empirical counterpart of $Q_*$ in both Frobenius norm and Bures-Wasserstein distance, and explain, how obtained results are connected to optimal transportation theory and can be applied to statistical inference in quantum mechanics.
suggested questions
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
