論文の概要: Graph Laplacians on Shared Nearest Neighbor graphs and graph Laplacians
on $k$-Nearest Neighbor graphs having the same limit
- arxiv url: http://arxiv.org/abs/2302.12399v1
- Date: Fri, 24 Feb 2023 02:03:40 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-27 14:50:27.136015
- Title: Graph Laplacians on Shared Nearest Neighbor graphs and graph Laplacians
on $k$-Nearest Neighbor graphs having the same limit
- Title(参考訳): 共有近傍グラフ上のグラフラプラシアンおよび同じ極限を持つ$k$Nearest Neighborグラフ上のグラフラプラシアン
- Authors: A. Martina Neuman
- Abstract要約: 共有近傍グラフ(英: Shared Nearest Neighbor graph、SNN)は、共有近傍情報を用いたグラフ構築の一種である。
グラフラプラシアンの点収束率は、高い確率で$(k/n)1/m$に対して線型であることを示す。
- 参考スコア(独自算出の注目度): 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: A Shared Nearest Neighbor (SNN) graph is a type of graph construction using
shared nearest neighbor information, which is a secondary similarity measure
based on the rankings induced by a primary $k$-nearest neighbor ($k$-NN)
measure. SNN measures have been touted as being less prone to the curse of
dimensionality than conventional distance measures, and thus methods using SNN
graphs have been widely used in applications, particularly in clustering
high-dimensional data sets and in finding outliers in subspaces of high
dimensional data. Despite this, the theoretical study of SNN graphs and graph
Laplacians remains unexplored. In this pioneering work, we make the first
contribution in this direction. We show that large scale asymptotics of an SNN
graph Laplacian reach a consistent continuum limit; this limit is the same as
that of a $k$-NN graph Laplacian. Moreover, we show that the pointwise
convergence rate of the graph Laplacian is linear with respect to $(k/n)^{1/m}$
with high probability.
- Abstract(参考訳): 共有隣人グラフ(英: Shared Nearest Neighbor graph、SNN)は、共有隣人情報を用いたグラフ構築の一種であり、一次の$k$-nearest(k$-NN)測度によって誘導されるランクに基づく二次類似度尺度である。
SNN測度は従来の距離測度よりも次元の呪いの傾向が低いと評価されており、特に高次元データセットのクラスタリングや高次元データのサブスペースにおけるアウトリーチの発見において、SNNグラフを用いた手法が広く用いられている。
それにもかかわらず、SNNグラフとグラフラプラシアンの理論的研究は未解明のままである。
この先駆的な仕事において、私たちはこの方向に最初に貢献します。
SNNグラフラプラシアンの大規模漸近が一貫した連続極限に達することを示し、この極限は$k$-NNグラフラプラシアンと同じである。
さらに、グラフラプラシアンの点収束率は、高い確率で$(k/n)^{1/m}$に対して線形であることを示した。
関連論文リスト
- Limits, approximation and size transferability for GNNs on sparse graphs
via graphops [44.02161831977037]
我々は,GNNを構成する集約演算など,グラフから導出される演算子の極限を取るという観点から考える。
我々の結果は、密でスパースなグラフ、およびグラフ極限の様々な概念に当てはまる。
論文 参考訳(メタデータ) (2023-06-07T15:04:58Z) - Self-attention Dual Embedding for Graphs with Heterophily [6.803108335002346]
多くの実世界のグラフはヘテロ親和性があり、標準のGNNを用いた分類精度ははるかに低い。
ヘテロ親和性グラフとホモ親和性グラフの両方に有効である新しいGNNを設計する。
我々は,数千から数百万のノードを含む実世界のグラフ上でアルゴリズムを評価し,最先端の結果が得られたことを示す。
論文 参考訳(メタデータ) (2023-05-28T09:38:28Z) - Training Graph Neural Networks on Growing Stochastic Graphs [114.75710379125412]
グラフニューラルネットワーク(GNN)は、ネットワーク化されたデータの意味のあるパターンを活用するために、グラフ畳み込みに依存している。
我々は,成長するグラフ列の極限オブジェクトであるグラフオンを利用して,非常に大きなグラフ上のGNNを学習することを提案する。
論文 参考訳(メタデータ) (2022-10-27T16:00:45Z) - Graph Condensation via Receptive Field Distribution Matching [61.71711656856704]
本稿では,元のグラフを表す小さなグラフの作成に焦点をあてる。
我々は、元のグラフを受容体の分布とみなし、受容体が同様の分布を持つ小さなグラフを合成することを目的としている。
論文 参考訳(メタデータ) (2022-06-28T02:10:05Z) - Deep Ensembles for Graphs with Higher-order Dependencies [13.164412455321907]
グラフニューラルネットワーク(GNN)は多くのグラフ学習タスクで最先端のパフォーマンスを継続する。
従来のグラフ表現が各ノードの近傍に不適合な傾向は,既存のGNNの一般化に悪影響を及ぼすことを示す。
本稿では,同一ノードの異なる近傍部分空間上でGNNのアンサンブルを訓練することにより,近傍のばらつきを捉える新しいディープグラフアンサンブル(DGE)を提案する。
論文 参考訳(メタデータ) (2022-05-27T14:01:08Z) - Transferability Properties of Graph Neural Networks [125.71771240180654]
グラフニューラルネットワーク(GNN)は、中規模グラフでサポートされているデータから表現を学ぶのに成功している。
適度な大きさのグラフ上でGNNを訓練し、それらを大規模グラフに転送する問題について検討する。
その結果, (i) グラフサイズに応じて転送誤差が減少し, (ii) グラフフィルタは非線型性の散乱挙動によってGNNにおいて緩和されるような転送可能性-識別可能性トレードオフを有することがわかった。
論文 参考訳(メタデータ) (2021-12-09T00:08:09Z) - Graph Neural Networks with Feature and Structure Aware Random Walk [5.431036185361236]
典型的な好適なグラフでは、エッジを指向する可能性があり、エッジをそのまま扱うか、あるいは単純に非指向にするかは、GNNモデルの性能に大きな影響を与える。
そこで我々は,グラフの方向性を適応的に学習するモデルを開発し,ノード間の長距離相関を生かした。
論文 参考訳(メタデータ) (2021-11-19T08:54:21Z) - A Unified Lottery Ticket Hypothesis for Graph Neural Networks [82.31087406264437]
本稿では,グラフ隣接行列とモデルの重み付けを同時に行う統一GNNスペーシフィケーション(UGS)フレームワークを提案する。
グラフ宝くじ(GLT)をコアサブデータセットとスパースサブネットワークのペアとして定義することにより、人気のある宝くじチケット仮説を初めてGNNsにさらに一般化します。
論文 参考訳(メタデータ) (2021-02-12T21:52:43Z) - Graphon Neural Networks and the Transferability of Graph Neural Networks [125.71771240180654]
グラフニューラルネットワーク(GNN)は、ネットワークデータから局所的な特徴を抽出するためにグラフ畳み込みに依存する。
我々は,GNNのリミットオブジェクトとしてグラフオンNNを導入し,GNNの出力とそのリミットグラフオン-NNとの差を証明した。
これにより、GNNの識別可能性と転送可能性のトレードオフが確立される。
論文 参考訳(メタデータ) (2020-06-05T16:41:08Z) - CoSimGNN: Towards Large-scale Graph Similarity Computation [5.17905821006887]
グラフニューラルネットワーク(GNN)はこのタスクにデータ駆動型ソリューションを提供する。
既存のGNNベースの手法は、それぞれ2つのグラフを埋め込んだり、グラフ全体のクロスグラフインタラクションをデプロイしたりするが、まだ競合する結果が得られない。
このフレームワークは,まず適応的なプーリング操作で大きなグラフを埋め込んで粗くし,最後に類似点を求めるために粗いグラフにきめ細かな相互作用を展開させる。
論文 参考訳(メタデータ) (2020-05-14T16:33:13Z) - Block-Approximated Exponential Random Graphs [77.4792558024487]
指数乱グラフ(ERG)の分野における重要な課題は、大きなグラフ上の非自明なERGの適合である。
本稿では,非自明なERGに対する近似フレームワークを提案する。
我々の手法は、数百万のノードからなるスパースグラフにスケーラブルである。
論文 参考訳(メタデータ) (2020-02-14T11:42:16Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。