論文の概要: Optimizing $k$ in $k$NN Graphs with Graph Learning Perspective
- arxiv url: http://arxiv.org/abs/2401.08245v1
- Date: Tue, 16 Jan 2024 09:59:36 GMT
- ステータス: 処理完了
- システム内更新日: 2024-01-17 14:38:25.523137
- Title: Optimizing $k$ in $k$NN Graphs with Graph Learning Perspective
- Title（参考訳）: グラフ学習の視点からの$k$ in $k$NNグラフの最適化
- Authors: Asuka Tamaru, Junya Hara, Hiroshi Higashi, Yuichi Tanaka, Antonio
Ortega
- Abstract要約: グラフ信号処理に基づいて、隣接するグラフ(k$NNGs)の$k$ in $k$-nearestの選択を最適化する手法を提案する。
本手法を用いて得られた$k$NNGsは,実データセットで実験した結果,各ノードあたりのエッジの適切な変数数を決定することができることがわかった。
- 参考スコア（独自算出の注目度）: 30.290306866355536
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper, we propose a method, based on graph signal processing, to
optimize the choice of $k$ in $k$-nearest neighbor graphs ($k$NNGs). $k$NN is
one of the most popular approaches and is widely used in machine learning and
signal processing. The parameter $k$ represents the number of neighbors that
are connected to the target node; however, its appropriate selection is still a
challenging problem. Therefore, most $k$NNGs use ad hoc selection methods for
$k$. In the proposed method, we assume that a different $k$ can be chosen for
each node. We formulate a discrete optimization problem to seek the best $k$
with a constraint on the sum of distances of the connected nodes. The optimal
$k$ values are efficiently obtained without solving a complex optimization.
Furthermore, we reveal that the proposed method is closely related to existing
graph learning methods. In experiments on real datasets, we demonstrate that
the $k$NNGs obtained with our method are sparse and can determine an
appropriate variable number of edges per node. We validate the effectiveness of
the proposed method for point cloud denoising, comparing our denoising
performance with achievable graph construction methods that can be scaled to
typical point cloud sizes (e.g., thousands of nodes).
- Abstract（参考訳）: 本稿では,グラフ信号処理に基づいて,隣接するグラフ (k$NNGs) に対して$k$ in $k$-nearest の選択を最適化する手法を提案する。
$k$NNは最も一般的なアプローチの1つで、機械学習や信号処理で広く使われている。
パラメータ$k$は、ターゲットノードに接続されている隣人の数を表すが、その適切な選択は依然として難しい問題である。
したがって、ほとんどの$k$NNGは$k$のアドホックセレクションメソッドを使用する。
提案手法では,各ノードに対して異なる$k$が選択可能であると仮定する。
離散最適化問題を定式化し、連結ノード間の距離の和に制約のある最良の$k$を求める。
最適な$k$値は、複雑な最適化を解かずに効率的に得られる。
さらに,提案手法は既存のグラフ学習手法と密接に関連していることを明らかにした。
本手法を用いて得られた$k$NNGsは,実データセットで実験した結果,各ノードあたりのエッジの適切な変数数を決定することができることがわかった。
提案手法の有効性を検証し,典型的な点群(数千個のノードなど)にスケール可能な達成可能なグラフ構築法と比較した。
関連論文リスト
- Cluster-based Graph Collaborative Filtering [55.929052969825825]
グラフ畳み込みネットワーク(GCN)は、レコメンデーションシステムのためのユーザおよびアイテム表現の学習に成功している。
既存のGCNベースのほとんどのメソッドは、高階グラフ畳み込みを実行しながら、ユーザの複数の関心事を見落としている。
クラスタベースグラフ協調フィルタリング(ClusterGCF)と呼ばれる新しいGCNベースのレコメンデーションモデルを提案する。
論文 参考訳（メタデータ） (2024-04-16T07:05:16Z) - Ensemble Quadratic Assignment Network for Graph Matching [52.20001802006391]
グラフマッチングはコンピュータビジョンやパターン認識において一般的に用いられる技法である。
最近のデータ駆動型アプローチは、グラフマッチングの精度を著しく改善した。
データ駆動手法と従来の手法の利点を組み合わせたグラフニューラルネットワーク(GNN)に基づくアプローチを提案する。
論文 参考訳（メタデータ） (2024-03-11T06:34:05Z) - Random Edge Coding: One-Shot Bits-Back Coding of Large Labeled Graphs [24.761152163389735]
ランダムエッジ符号化(Random Edge Coding)と呼ばれる大きなラベル付きグラフを圧縮するためのワンショット方式を提案する。
実験によると、ランダムエッジ符号化は実世界のネットワークデータセット上での競合圧縮性能を実現することができる。
論文 参考訳（メタデータ） (2023-05-16T12:23:18Z) - Learnable Graph Matching: A Practical Paradigm for Data Association [74.28753343714858]
これらの問題に対処するための一般的な学習可能なグラフマッチング法を提案する。
提案手法は,複数のMOTデータセット上での最先端性能を実現する。
画像マッチングでは,一般的な屋内データセットであるScanNetで最先端の手法より優れている。
論文 参考訳（メタデータ） (2023-03-27T17:39:00Z) - Bring Your Own View: Graph Neural Networks for Link Prediction with
Personalized Subgraph Selection [57.34881616131377]
異なるエッジに対して最適なサブグラフを自動,個人的,帰納的に識別するプラグイン・アンド・プレイ・フレームワークとしてパーソナライズされたサブグラフセレクタ(PS2)を導入する。
PS2は二段階最適化問題としてインスタンス化され、効率よく解ける。
GNNLPトレーニングに対する新たなアプローチとして,まずエッジの最適な部分グラフを識別し,次にサンプル部分グラフを用いて推論モデルをトレーニングすることを提案する。
論文 参考訳（メタデータ） (2022-12-23T17:30:19Z) - Learning Heuristics for the Maximum Clique Enumeration Problem Using Low
Dimensional Representations [0.0]
本稿では,最大列挙問題の傾きを低減するために,入力グラフのプルーニング処理に学習フレームワークを用いる。
本手法の性能評価において,異なる頂点表現を用いることが果たす役割について検討する。
分類過程において局所的なグラフ特徴を用いることで,特徴の除去過程と組み合わせることで,より正確な結果が得られることが観察された。
論文 参考訳（メタデータ） (2022-10-30T22:04:32Z) - Communication-Efficient Adam-Type Algorithms for Distributed Data Mining [93.50424502011626]
我々はスケッチを利用した新しい分散Adam型アルゴリズムのクラス(例:SketchedAMSGrad)を提案する。
我々の新しいアルゴリズムは、反復毎に$O(frac1sqrtnT + frac1(k/d)2 T)$の高速収束率を$O(k log(d))$の通信コストで達成する。
論文 参考訳（メタデータ） (2022-10-14T01:42:05Z) - Beyond kNN: Adaptive, Sparse Neighborhood Graphs via Optimal Transport [0.1933681537640272]
最も近い近傍グラフは、データセットの幾何学や位相を捉えるために広く使われている。
そのようなグラフを構築するための最も一般的な戦略の1つは、各点について最も近い隣人 (kNN) の固定数 k を選択することである。
2次正規化最適輸送に基づく1つのパラメータから適応的近傍グラフを構築するための簡単な手法を提案する。
論文 参考訳（メタデータ） (2022-08-01T04:24:58Z) - Large-Scale Network Embedding in Apache Spark [1.3769786711365102]
本稿では,Apache Sparkを用いた大規模グラフへのネットワーク埋め込みのための効率的かつ効率的な分散アルゴリズムを提案する。
提案手法は数時間で数十億のエッジを持つグラフを処理でき、最先端のアプローチよりも少なくとも4倍高速であることを示す。
論文 参考訳（メタデータ） (2021-06-20T04:42:24Z) - Generating Target Graph Couplings for QAOA from Native Quantum Hardware
Couplings [3.2622301272834524]
本稿では,Ising型量子スピン系における限定大域制御を用いた任意の対象結合グラフの構築手法を提案する。
本手法は、量子近似最適化アルゴリズム(QAOA)をトラップされたイオン量子ハードウェア上に実装することによるものである。
Max-Cut QAOAのノイズシミュレーションにより、我々の実装は標準ゲートベースのコンパイルよりもノイズの影響を受けにくいことが示された。
論文 参考訳（メタデータ） (2020-11-16T18:43:09Z) - Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
我々は高密度サブグラフ発見のための新しい学習問題を導入する。
まず,確率の高いほぼ最適解を求めるエッジ時間アルゴリズムを提案する。
そして、理論的保証のあるよりスケーラブルなアルゴリズムを設計する。
論文 参考訳（メタデータ） (2020-06-24T11:37:33Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。