論文の概要: A Poincaré Inequality and Consistency Results for Signal Sampling on Large Graphs

• arxiv url: http://arxiv.org/abs/2311.10610v3
• Date: Wed, 09 Oct 2024 16:28:15 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-10-10 14:29:53.103124
• Title: A Poincaré Inequality and Consistency Results for Signal Sampling on Large Graphs
• Title（参考訳）: 大規模グラフ上での信号サンプリングにおけるポアンカレの不等式と一貫性結果
• Authors: Thien Le, Luana Ruiz, Stefanie Jegelka,
• Abstract要約: グラフ制限の一種であるグラフオンに対する信号サンプリング理論を導入する。 収束グラフ列上の一意なサンプリング集合は、グラフオン上の一意なサンプリング集合に収束することを示す。 そこで我々は,大規模グラフに対する関連するグラフ信号サンプリングアルゴリズムを提案し,グラフ機械学習タスクにおいて,その優れた経験的性能を示す。
• 参考スコア（独自算出の注目度）: 34.99659089854587
• License:
• Abstract: Large-scale graph machine learning is challenging as the complexity of learning models scales with the graph size. Subsampling the graph is a viable alternative, but sampling on graphs is nontrivial as graphs are non-Euclidean. Existing graph sampling techniques require not only computing the spectra of large matrices but also repeating these computations when the graph changes, e.g., grows. In this paper, we introduce a signal sampling theory for a type of graph limit -- the graphon. We prove a Poincar\'e inequality for graphon signals and show that complements of node subsets satisfying this inequality are unique sampling sets for Paley-Wiener spaces of graphon signals. Exploiting connections with spectral clustering and Gaussian elimination, we prove that such sampling sets are consistent in the sense that unique sampling sets on a convergent graph sequence converge to unique sampling sets on the graphon. We then propose a related graphon signal sampling algorithm for large graphs, and demonstrate its good empirical performance on graph machine learning tasks.
• Abstract（参考訳）: 大規模グラフ機械学習は、学習モデルの複雑さがグラフサイズとともにスケールするため、困難である。 グラフのサンプリングは実行可能な代替手段であるが、グラフがユークリッドではないため、グラフのサンプリングは自明ではない。 既存のグラフサンプリング技術では、大きな行列のスペクトルを演算するだけでなく、グラフが成長するなど、これらの計算を繰り返し行う必要がある。 本稿では,グラフ制限の一種であるグラフオンに対する信号サンプリング理論を提案する。 この不等式を満たすノード部分集合の補集合が、グラフン信号のパリー・ウィーナー空間のユニークなサンプリング集合であることを示す。 スペクトルクラスタリングとガウス除去との接続を爆発させることで、そのようなサンプリングセットは収束グラフ列上の一意なサンプリングセットがグラフオン上の一意なサンプリングセットに収束するという意味で一貫したものであることを示す。 そこで我々は,大規模グラフに対する関連するグラフ信号サンプリングアルゴリズムを提案し,グラフ機械学習タスクにおいて,その優れた経験的性能を示す。

関連論文リスト

• Graph Sampling for Scalable and Expressive Graph Neural Networks on Homophilic Graphs [7.658211994479856]
  グラフニューラルネットワーク(GNN)は多くのグラフ機械学習タスクに優れるが、大規模ネットワークへのスケーリングでは課題に直面している。 グラフ構造を保存するために特徴ホモフィリーを利用する新しいグラフサンプリングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-10-22T00:30:31Z)
• Sampling and Uniqueness Sets in Graphon Signal Processing [136.68956350251418]
  グラフとグラフの極限の理論を活用して、大きなグラフの族上のサンプリング集合の性質について検討する。 我々は、収束結果を利用して、ほぼ最適なサンプリングセットを得るアルゴリズムを提供する。
  論文  参考訳（メタデータ） (2024-01-11T22:31:48Z)
• Generalized Graphon Process: Convergence of Graph Frequencies in Stretched Cut Distance [30.279435887366578]
  スパースグラフ列は、従来のカット距離の定義の下で自明なグラフオンに収束する。 我々は、スパースグラフ列の収束を記述するために、一般化グラフと拡張カット距離の概念を利用する。 その結果,スパースグラフ間の移動学習の可能性が示唆された。
  論文  参考訳（メタデータ） (2023-09-11T06:34:46Z)
• Graph Laplacian Learning with Exponential Family Noise [8.594140167290098]
  指数関数的家族雑音によるグラフ信号から学習するための多目的グラフ推論フレームワークを提案する。 本フレームワークは,連続的なスムーズなグラフ信号から様々なデータタイプまで,従来の手法を一般化する。
  論文  参考訳（メタデータ） (2023-06-14T02:09:52Z)
• Graphon Pooling for Reducing Dimensionality of Signals and Convolutional Operators on Graphs [131.53471236405628]
  グラフ空間における[0, 1]2の分割上のグラフとグラフ信号の誘導的グラフ表現を利用する3つの方法を提案する。 これらの低次元表現がグラフとグラフ信号の収束列を構成することを証明している。 我々は,層間次元減少比が大きい場合,グラノンプーリングは文献で提案した他の手法よりも有意に優れていることを観察した。
  論文  参考訳（メタデータ） (2022-12-15T22:11:34Z)
• Efficient Signed Graph Sampling via Balancing & Gershgorin Disc Perfect Alignment [51.74913666829224]
  強い反相関を持つデータセットに対して、適切なグラフは正および負のエッジ重みの両方を含むことを示す。 本稿では,平衡符号グラフの概念に着目した線形時間符号グラフサンプリング手法を提案する。 実験結果から, 署名付きグラフサンプリング手法は, 各種データセットにおいて, 既存の高速サンプリング方式よりも優れた性能を示した。
  論文  参考訳（メタデータ） (2022-08-18T09:19:01Z)
• G-Mixup: Graph Data Augmentation for Graph Classification [55.63157775049443]
  Mixupは、2つのランダムサンプル間の特徴とラベルを補間することにより、ニューラルネットワークの一般化とロバスト性を改善する上で優位性を示している。 グラフ分類のためのグラフを増補するために$mathcalG$-Mixupを提案し、グラフの異なるクラスのジェネレータ(すなわちグラフ)を補間する。 実験により、$mathcalG$-MixupはGNNの一般化とロバスト性を大幅に改善することが示された。
  論文  参考訳（メタデータ） (2022-02-15T04:09:44Z)
• Learning Graphon Autoencoders for Generative Graph Modeling [91.32624399902755]
  Graphonは任意のサイズでグラフを生成する非パラメトリックモデルであり、グラフから簡単に誘導できる。 解析可能でスケーラブルなグラフ生成モデルを構築するために,textitgraphon autoencoder という新しいフレームワークを提案する。 線形グルーポン分解モデルはデコーダとして機能し、潜在表現を活用して誘導されたグルーポンを再構成する。
  論文  参考訳（メタデータ） (2021-05-29T08:11:40Z)
• Graph Pooling with Node Proximity for Hierarchical Representation Learning [80.62181998314547]
  本稿では,ノード近接を利用したグラフプーリング手法を提案し,そのマルチホップトポロジを用いたグラフデータの階層的表現学習を改善する。 その結果,提案したグラフプーリング戦略は,公開グラフ分類ベンチマークデータセットの集合において,最先端のパフォーマンスを達成できることが示唆された。
  論文  参考訳（メタデータ） (2020-06-19T13:09:44Z)
• The Power of Graph Convolutional Networks to Distinguish Random Graph Models: Short Version [27.544219236164764]
  グラフ畳み込みネットワーク(GCN)はグラフ表現学習において広く使われている手法である。 サンプルグラフの埋め込みに基づいて異なるランダムグラフモデルを区別するGCNのパワーについて検討する。
  論文  参考訳（メタデータ） (2020-02-13T17:58:42Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。