Beyond kNN: Adaptive, Sparse Neighborhood Graphs via Optimal Transport

• URL: http://arxiv.org/abs/2208.00604v1
• Date: Mon, 1 Aug 2022 04:24:58 GMT
• Title: Beyond kNN: Adaptive, Sparse Neighborhood Graphs via Optimal Transport
• Authors: Tetsuya Matsumoto, Stephen Zhang, Geoffrey Schiebinger
• Abstract summary: Nearest neighbour graphs are widely used to capture the geometry or topology of a dataset. One of the most common strategies to construct such a graph is based on selecting a fixed number k of nearest neighbours (kNN) for each point. We propose a simple approach to construct an adaptive neighbourhood graph from a single parameter, based on quadratically regularised optimal transport.
• Score: 0.1933681537640272
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Nearest neighbour graphs are widely used to capture the geometry or topology of a dataset. One of the most common strategies to construct such a graph is based on selecting a fixed number k of nearest neighbours (kNN) for each point. However, the kNN heuristic may become inappropriate when sampling density or noise level varies across datasets. Strategies that try to get around this typically introduce additional parameters that need to be tuned. We propose a simple approach to construct an adaptive neighbourhood graph from a single parameter, based on quadratically regularised optimal transport. Our numerical experiments show that graphs constructed in this manner perform favourably in unsupervised and semi-supervised learning applications.

Related papers

• Scalable Graph Compressed Convolutions [68.85227170390864]
  We propose a differentiable method that applies permutations to calibrate input graphs for Euclidean convolution. Based on the graph calibration, we propose the Compressed Convolution Network (CoCN) for hierarchical graph representation learning.
  arXiv  Detail & Related papers  (2024-07-26T03:14:13Z)
• Spectral Greedy Coresets for Graph Neural Networks [61.24300262316091]
  The ubiquity of large-scale graphs in node-classification tasks hinders the real-world applications of Graph Neural Networks (GNNs) This paper studies graph coresets for GNNs and avoids the interdependence issue by selecting ego-graphs based on their spectral embeddings. Our spectral greedy graph coreset (SGGC) scales to graphs with millions of nodes, obviates the need for model pre-training, and applies to low-homophily graphs.
  arXiv  Detail & Related papers  (2024-05-27T17:52:12Z)
• GRAPES: Learning to Sample Graphs for Scalable Graph Neural Networks [2.4175455407547015]
  Graph neural networks learn to represent nodes by aggregating information from their neighbors. Several existing methods address this by sampling a small subset of nodes, scaling GNNs to much larger graphs. We introduce GRAPES, an adaptive sampling method that learns to identify the set of nodes crucial for training a GNN.
  arXiv  Detail & Related papers  (2023-10-05T09:08:47Z)
• Learning Adaptive Neighborhoods for Graph Neural Networks [45.94778766867247]
  Graph convolutional networks (GCNs) enable end-to-end learning on graph structured data. We propose a novel end-to-end differentiable graph generator which builds graph topologies. Our module can be readily integrated into existing pipelines involving graph convolution operations.
  arXiv  Detail & Related papers  (2023-07-18T08:37:25Z)
• 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)
• Graph Signal Sampling for Inductive One-Bit Matrix Completion: a Closed-form Solution [112.3443939502313]
  We propose a unified graph signal sampling framework which enjoys the benefits of graph signal analysis and processing. The key idea is to transform each user's ratings on the items to a function (signal) on the vertices of an item-item graph. For the online setting, we develop a Bayesian extension, i.e., BGS-IMC which considers continuous random Gaussian noise in the graph Fourier domain.
  arXiv  Detail & Related papers  (2023-02-08T08:17:43Z)
• Optimal Propagation for Graph Neural Networks [51.08426265813481]
  We propose a bi-level optimization approach for learning the optimal graph structure. We also explore a low-rank approximation model for further reducing the time complexity.
  arXiv  Detail & Related papers  (2022-05-06T03:37:00Z)
• Exploiting Neighbor Effect: Conv-Agnostic GNNs Framework for Graphs with Heterophily [58.76759997223951]
  We propose a new metric based on von Neumann entropy to re-examine the heterophily problem of GNNs. We also propose a Conv-Agnostic GNN framework (CAGNNs) to enhance the performance of most GNNs on heterophily datasets.
  arXiv  Detail & Related papers  (2022-03-19T14:26:43Z)
• Optimal Transport Graph Neural Networks [31.191844909335963]
  Current graph neural network (GNN) architectures naively average or sum node embeddings into an aggregated graph representation. We introduce OT-GNN, a model that computes graph embeddings using parametric prototypes.
  arXiv  Detail & Related papers  (2020-06-08T14:57:39Z)
• Block-Approximated Exponential Random Graphs [77.4792558024487]
  An important challenge in the field of exponential random graphs (ERGs) is the fitting of non-trivial ERGs on large graphs. We propose an approximative framework to such non-trivial ERGs that result in dyadic independence (i.e., edge independent) distributions. Our methods are scalable to sparse graphs consisting of millions of nodes.
  arXiv  Detail & Related papers  (2020-02-14T11:42:16Z)
• Neighborhood and Graph Constructions using Non-Negative Kernel Regression [42.16401154367232]
  We present an alternative view of neighborhood selection, where we show that neighborhood construction is equivalent to a sparse signal approximation problem. We also propose an algorithm, non-negative kernel regression(NNK), for obtaining neighborhoods that lead to better sparse representation.
  arXiv  Detail & Related papers  (2019-10-21T13:58:14Z)

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.