論文の概要: 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}$に対して線形であることを示した。
関連論文リスト
- Generalization, Expressivity, and Universality of Graph Neural Networks on Attributed Graphs [33.266521866968304]
ノード属性を持つ属性グラフ上でのグラフニューラルネットワーク(GNN)の普遍性と一般化を解析する。
我々は、GNNに対する普遍近似定理と、属性グラフの任意のデータ分布上のGNNの有界一般化を証明した。
我々の研究は、属性のないグラフのみの導出理論、GNNが連続だが分離パワーのない導出コンパクトなメトリクス、GNNが連続かつ分離ポイントである導出指標を拡張・統合する。
論文 参考訳（メタデータ） (2024-11-08T10:34:24Z) - Higher-Order GNNs Meet Efficiency: Sparse Sobolev Graph Neural Networks [6.080095317098909]
グラフニューラルネットワーク(GNN)は,グラフ内のノード間の関係をモデル化する上で,非常に有望であることを示す。
これまでの研究では、主にグラフ内の高次隣人からの情報を活用しようと試みてきた。
我々は基本的な観察を行い、ラプラシア行列の正則とアダマールの力はスペクトルでも同様に振る舞う。
グラフ信号のスパースなソボレフノルムに基づく新しいグラフ畳み込み演算子を提案する。
論文 参考訳（メタデータ） (2024-11-07T09:53:11Z) - Generalization of Geometric Graph Neural Networks [84.01980526069075]
幾何グラフニューラルネットワーク(GNN)の一般化能力について検討する。
我々は,このGNNの最適経験リスクと最適統計リスクとの一般化ギャップを証明した。
最も重要な観察は、前の結果のようにグラフのサイズに制限されるのではなく、1つの大きなグラフで一般化能力を実現することができることである。
論文 参考訳（メタデータ） (2024-09-08T18:55:57Z) - Limits, approximation and size transferability for GNNs on sparse graphs
via graphops [44.02161831977037]
我々は,GNNを構成する集約演算など,グラフから導出される演算子の極限を取るという観点から考える。
我々の結果は、密でスパースなグラフ、およびグラフ極限の様々な概念に当てはまる。
論文 参考訳（メタデータ） (2023-06-07T15:04:58Z) - Training Graph Neural Networks on Growing Stochastic Graphs [114.75710379125412]
グラフニューラルネットワーク(GNN)は、ネットワーク化されたデータの意味のあるパターンを活用するために、グラフ畳み込みに依存している。
我々は,成長するグラフ列の極限オブジェクトであるグラフオンを利用して,非常に大きなグラフ上のGNNを学習することを提案する。
論文 参考訳（メタデータ） (2022-10-27T16:00:45Z) - 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 [7.143879014059894]
典型的な好適なグラフでは、エッジを指向する可能性があり、エッジをそのまま扱うか、あるいは単純に非指向にするかは、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) - Block-Approximated Exponential Random Graphs [77.4792558024487]
指数乱グラフ(ERG)の分野における重要な課題は、大きなグラフ上の非自明なERGの適合である。
本稿では,非自明なERGに対する近似フレームワークを提案する。
我々の手法は、数百万のノードからなるスパースグラフにスケーラブルである。
論文 参考訳（メタデータ） (2020-02-14T11:42:16Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。