Beyond kNN: Adaptive, Sparse Neighborhood Graphs via Optimal Transport

2022-08-01 · Tetsuya Matsumoto, Stephen Zhang, Geoffrey Schiebinger

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.

📄 PDF Abstract BibTeX arXiv:2208.00604

Code (0)

등록된 구현이 없습니다.

Mean-Field Control on Sparse Graphs: From Local Limits to GNNs via Neighborhood Distributions

2026-01-29 · Tobias Schmidt, Kai Cui arxiv

Mean-field control (MFC) offers a scalable solution to the curse of dimensionality in multi-agent systems but traditionally hinges on the restrictive assumption of exchangeability via dense, all-to-all interactions. In t…

Reinforcement Learning

Discovering Invariant Neighborhood Patterns for Heterophilic Graphs

2024-03-15 · Ruihao Zhang, Zhengyu Chen, Teng Xiao, Yueyang Wang 외

This paper studies the problem of distribution shifts on non-homophilous graphs Mosting existing graph neural network methods rely on the homophilous assumption that nodes from the same class are more likely to be linked…

Graph Learning Graph Neural Network

Beyond Low-Pass Filters: Adaptive Feature Propagation on Graphs

2021-03-26 · Sean Li, Dongwoo Kim, Qing Wang

Graph neural networks (GNNs) have been extensively studied for prediction tasks on graphs. As pointed out by recent studies, most GNNs assume local homophily, i.e., strong similarities in local neighborhoods. This assump…

Node Classification

Robust Graph Representation Learning via Neural Sparsification

2020-01-01 · ICML 2020 1 · Cheng Zheng, Bo Zong, Wei Cheng, Dongjin Song 외

Graph representation learning serves as the core of important prediction tasks, ranging from product recommendation to fraud detection. Real-life graphs usually have complex information in the local neighborhood, where e…

Fraud Detection Graph Representation Learning Node Classification Product Recommendation+1

Learning Discrete Adaptive Receptive Fields for Graph Convolutional Networks

2021-01-01 · Xiaojun Ma, Ziyao Li, Lingjun Xu, Guojie Song 외

Different nodes in a graph neighborhood generally yield different importance. In previous work of Graph Convolutional Networks (GCNs), such differences are typically modeled with attention mechanisms. However, as we prov…