論文の概要: Beyond kNN: Adaptive, Sparse Neighborhood Graphs via Optimal Transport
- arxiv url: http://arxiv.org/abs/2208.00604v1
- Date: Mon, 1 Aug 2022 04:24:58 GMT
- ステータス: 処理完了
- システム内更新日: 2022-08-02 13:05:05.737114
- Title: Beyond kNN: Adaptive, Sparse Neighborhood Graphs via Optimal Transport
- Title（参考訳）: beyond knn: 最適輸送による適応的、スパースな近傍グラフ
- Authors: Tetsuya Matsumoto, Stephen Zhang, Geoffrey Schiebinger
- Abstract要約: 最も近い近傍グラフは、データセットの幾何学や位相を捉えるために広く使われている。
そのようなグラフを構築するための最も一般的な戦略の1つは、各点について最も近い隣人 (kNN) の固定数 k を選択することである。
2次正規化最適輸送に基づく1つのパラメータから適応的近傍グラフを構築するための簡単な手法を提案する。
- 参考スコア（独自算出の注目度）: 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.
- Abstract（参考訳）: 近辺のグラフはデータセットの幾何やトポロジをキャプチャするために広く使われている。
そのようなグラフを構成する最も一般的な戦略の1つは、各点に対して固定数 k の近傍 (knn) を選択することである。
しかし、サンプリング密度やノイズレベルがデータセットによって異なる場合、kNNヒューリスティックは不適切になる可能性がある。
これを回避しようとする戦略は、通常、チューニングが必要な追加のパラメータをもたらす。
2次正規化最適輸送に基づく1つのパラメータから適応的近傍グラフを構築するための簡単な手法を提案する。
この方法で構築されたグラフは,教師なしおよび半教師なし学習アプリケーションにおいて好適に機能することを示す。
関連論文リスト
- Scalable Graph Compressed Convolutions [68.85227170390864]
ユークリッド畳み込みのための入力グラフのキャリブレーションに置換を適用する微分可能手法を提案する。
グラフキャリブレーションに基づいて,階層型グラフ表現学習のための圧縮畳み込みネットワーク(CoCN)を提案する。
論文 参考訳（メタデータ） (2024-07-26T03:14:13Z) - Spectral Greedy Coresets for Graph Neural Networks [61.24300262316091]
ノード分類タスクにおける大規模グラフの利用は、グラフニューラルネットワーク(GNN)の現実的な応用を妨げる
本稿では,GNNのグラフコアセットについて検討し,スペクトル埋め込みに基づくエゴグラフの選択により相互依存の問題を回避する。
我々のスペクトルグレディグラフコアセット(SGGC)は、数百万のノードを持つグラフにスケールし、モデル事前学習の必要性を排除し、低ホモフィリーグラフに適用する。
論文 参考訳（メタデータ） (2024-05-27T17:52:12Z) - GRAPES: Learning to Sample Graphs for Scalable Graph Neural Networks [2.4175455407547015]
グラフニューラルネットワークは、隣人からの情報を集約することでノードを表現することを学ぶ。
いくつかの既存手法では、ノードの小さなサブセットをサンプリングし、GNNをもっと大きなグラフにスケールすることで、この問題に対処している。
本稿では,GNNのトレーニングに不可欠なノードの集合を識別する適応サンプリング手法であるGRAPESを紹介する。
論文 参考訳（メタデータ） (2023-10-05T09:08:47Z) - Learning Adaptive Neighborhoods for Graph Neural Networks [45.94778766867247]
グラフ畳み込みネットワーク(GCN)は、グラフ構造化データのエンドツーエンド学習を可能にする。
本稿では,グラフトポロジを構築する新しいエンドツーエンドの微分可能なグラフ生成器を提案する。
私たちのモジュールは、グラフ畳み込み操作を含む既存のパイプラインに簡単に統合できます。
論文 参考訳（メタデータ） (2023-07-18T08:37:25Z) - Optimality of Message-Passing Architectures for Sparse Graphs [13.96547777184641]
スパース設定における特徴デコレーショングラフ上のノード分類問題、すなわちノードの期待次数がノード数で$O(1)$である場合について検討する。
局所ベイズ最適性(英語版)と呼ばれるノード分類タスクに対するベイズ最適性(英語版)の概念を導入する。
最適なメッセージパッシングアーキテクチャは,低グラフ信号のレギュレーションにおける標準と高グラフ信号のレギュレーションにおける典型とを補間することを示す。
論文 参考訳（メタデータ） (2023-05-17T17:31:20Z) - Graph Signal Sampling for Inductive One-Bit Matrix Completion: a
Closed-form Solution [112.3443939502313]
グラフ信号解析と処理の利点を享受する統合グラフ信号サンプリングフレームワークを提案する。
キーとなる考え方は、各ユーザのアイテムのレーティングをアイテムイットグラフの頂点上の関数(信号)に変換することである。
オンライン設定では、グラフフーリエ領域における連続ランダムガウス雑音を考慮したベイズ拡張(BGS-IMC)を開発する。
論文 参考訳（メタデータ） (2023-02-08T08:17:43Z) - Optimal Propagation for Graph Neural Networks [51.08426265813481]
最適グラフ構造を学習するための二段階最適化手法を提案する。
また、時間的複雑さをさらに軽減するために、低ランク近似モデルについても検討する。
論文 参考訳（メタデータ） (2022-05-06T03:37:00Z) - Exploiting Neighbor Effect: Conv-Agnostic GNNs Framework for Graphs with
Heterophily [58.76759997223951]
我々はフォン・ノイマンエントロピーに基づく新しい計量を提案し、GNNのヘテロフィリー問題を再検討する。
また、異種データセット上でのほとんどのGNNの性能を高めるために、Conv-Agnostic GNNフレームワーク(CAGNN)を提案する。
論文 参考訳（メタデータ） (2022-03-19T14:26:43Z) - Optimal Transport Graph Neural Networks [31.191844909335963]
現在のグラフニューラルネットワーク(GNN)アーキテクチャは、集約グラフ表現に平均または総和ノードを埋め込む。
本稿では,パラメトリックプロトタイプを用いたグラフ埋め込み計算モデルOT-GNNを紹介する。
論文 参考訳（メタデータ） (2020-06-08T14:57:39Z) - Block-Approximated Exponential Random Graphs [77.4792558024487]
指数乱グラフ(ERG)の分野における重要な課題は、大きなグラフ上の非自明なERGの適合である。
本稿では,非自明なERGに対する近似フレームワークを提案する。
我々の手法は、数百万のノードからなるスパースグラフにスケーラブルである。
論文 参考訳（メタデータ） (2020-02-14T11:42:16Z) - Neighborhood and Graph Constructions using Non-Negative Kernel
Regression [42.16401154367232]
そこで我々は, 近傍構造がスパース信号近似問題と等価であることを示す。
また,非負のカーネル回帰(NNK)アルゴリズムを提案する。
論文 参考訳（メタデータ） (2019-10-21T13:58:14Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。