Scalable Optimal Transport in High Dimensions for Graph Distances, Embedding Alignment, and More

• URL: http://arxiv.org/abs/2107.06876v1
• Date: Wed, 14 Jul 2021 17:40:08 GMT
• Title: Scalable Optimal Transport in High Dimensions for Graph Distances, Embedding Alignment, and More
• Authors: Johannes Klicpera, Marten Lienen, Stephan G\"unnemann
• Abstract summary: We propose two effective log-linear time approximations of the cost matrix for optimal transport. These approximations enable general log-linear time algorithms for entropy-regularized OT that perform well even for the complex, high-dimensional spaces. For graph distance regression we propose the graph transport network (GTN), which combines graph neural networks (GNNs) with enhanced Sinkhorn.
• Score: 7.484063729015126
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The current best practice for computing optimal transport (OT) is via entropy regularization and Sinkhorn iterations. This algorithm runs in quadratic time as it requires the full pairwise cost matrix, which is prohibitively expensive for large sets of objects. In this work we propose two effective log-linear time approximations of the cost matrix: First, a sparse approximation based on locality-sensitive hashing (LSH) and, second, a Nystr\"om approximation with LSH-based sparse corrections, which we call locally corrected Nystr\"om (LCN). These approximations enable general log-linear time algorithms for entropy-regularized OT that perform well even for the complex, high-dimensional spaces common in deep learning. We analyse these approximations theoretically and evaluate them experimentally both directly and end-to-end as a component for real-world applications. Using our approximations for unsupervised word embedding alignment enables us to speed up a state-of-the-art method by a factor of 3 while also improving the accuracy by 3.1 percentage points without any additional model changes. For graph distance regression we propose the graph transport network (GTN), which combines graph neural networks (GNNs) with enhanced Sinkhorn. GTN outcompetes previous models by 48% and still scales log-linearly in the number of nodes.

Related papers

• Sparse Decomposition of Graph Neural Networks [20.768412002413843]
  We propose an approach to reduce the number of nodes that are included during aggregation. We achieve this through a sparse decomposition, learning to approximate node representations using a weighted sum of linearly transformed features. We demonstrate via extensive experiments that our method outperforms other baselines designed for inference speedup.
  arXiv  Detail & Related papers  (2024-10-25T17:52:16Z)
• CiliaGraph: Enabling Expression-enhanced Hyper-Dimensional Computation in Ultra-Lightweight and One-Shot Graph Classification on Edge [1.8726646412385333]
  CiliaGraph is an enhanced expressive yet ultra-lightweight HDC model for graph classification. CiliaGraph reduces memory usage and accelerates training speed by an average of 292 times.
  arXiv  Detail & Related papers  (2024-05-29T12:22:59Z)
• Exact Gauss-Newton Optimization for Training Deep Neural Networks [0.0]
  We present EGN, a second-order optimization algorithm that combines the generalized Gauss-Newton (GN) Hessian approximation with low-rank linear algebra to compute the descent direction. We show how improvements such as line search, adaptive regularization, and momentum can be seamlessly added to EGN to further accelerate the algorithm.
  arXiv  Detail & Related papers  (2024-05-23T10:21:05Z)
• Efficient Heterogeneous Graph Learning via Random Projection [58.4138636866903]
  Heterogeneous Graph Neural Networks (HGNNs) are powerful tools for deep learning on heterogeneous graphs. Recent pre-computation-based HGNNs use one-time message passing to transform a heterogeneous graph into regular-shaped tensors. We propose a hybrid pre-computation-based HGNN, named Random Projection Heterogeneous Graph Neural Network (RpHGNN)
  arXiv  Detail & Related papers  (2023-10-23T01:25:44Z)
• Neural Gradient Learning and Optimization for Oriented Point Normal Estimation [53.611206368815125]
  We propose a deep learning approach to learn gradient vectors with consistent orientation from 3D point clouds for normal estimation. We learn an angular distance field based on local plane geometry to refine the coarse gradient vectors. Our method efficiently conducts global gradient approximation while achieving better accuracy and ability generalization of local feature description.
  arXiv  Detail & Related papers  (2023-09-17T08:35:11Z)
• Geometry-Informed Neural Operator for Large-Scale 3D PDEs [76.06115572844882]
  We propose the geometry-informed neural operator (GINO) to learn the solution operator of large-scale partial differential equations. We successfully trained GINO to predict the pressure on car surfaces using only five hundred data points.
  arXiv  Detail & Related papers  (2023-09-01T16:59:21Z)
• Optimality of Message-Passing Architectures for Sparse Graphs [13.96547777184641]
  We study the node classification problem on feature-decorated graphs in the sparse setting, i.e., when the expected degree of a node is $O(1)$ in the number of nodes. We introduce a notion of Bayes optimality for node classification tasks, called local Bayes optimality. We show that the optimal message-passing architecture interpolates between a standard in the regime of low graph signal and a typical in the regime of high graph signal.
  arXiv  Detail & Related papers  (2023-05-17T17:31:20Z)
• Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
  Efficient computation of the optimal transport distance between two distributions serves as an algorithm that empowers various applications. This paper develops a scalable first-order optimization-based method that computes optimal transport to within $varepsilon$ additive accuracy.
  arXiv  Detail & Related papers  (2023-01-30T15:46:39Z)
• Unfolding Projection-free SDP Relaxation of Binary Graph Classifier via GDPA Linearization [59.87663954467815]
  Algorithm unfolding creates an interpretable and parsimonious neural network architecture by implementing each iteration of a model-based algorithm as a neural layer. In this paper, leveraging a recent linear algebraic theorem called Gershgorin disc perfect alignment (GDPA), we unroll a projection-free algorithm for semi-definite programming relaxation (SDR) of a binary graph. Experimental results show that our unrolled network outperformed pure model-based graph classifiers, and achieved comparable performance to pure data-driven networks but using far fewer parameters.
  arXiv  Detail & Related papers  (2021-09-10T07:01:15Z)
• Improving predictions of Bayesian neural nets via local linearization [79.21517734364093]
  We argue that the Gauss-Newton approximation should be understood as a local linearization of the underlying Bayesian neural network (BNN) Because we use this linearized model for posterior inference, we should also predict using this modified model instead of the original one. We refer to this modified predictive as "GLM predictive" and show that it effectively resolves common underfitting problems of the Laplace approximation.
  arXiv  Detail & Related papers  (2020-08-19T12:35:55Z)
• A Study of Performance of Optimal Transport [16.847501106437534]
  We show that network simplex and augmenting path based algorithms can consistently outperform numerical matrix-scaling based methods. We present a new algorithm that improves upon the classical Kuhn-Munkres algorithm.
  arXiv  Detail & Related papers  (2020-05-03T20:37:05Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.