論文の概要: Empirical Error Estimates for Graph Sparsification

• arxiv url: http://arxiv.org/abs/2503.08031v1
• Date: Tue, 11 Mar 2025 04:28:57 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-03-12 15:44:48.211565
• Title: Empirical Error Estimates for Graph Sparsification
• Title（参考訳）: グラフスカラー化における経験的誤差推定
• Authors: Siyao Wang, Miles E. Lopes,
• Abstract要約: グラフスペーシフィケーション(Graph Sparsification)は、グラフベースの学習アルゴリズムを高速化する技術である。 スパシフィケーションエラーはランダムで未知であるため、ユーザは下流の計算の信頼性について不確実性に直面する必要がある。 経験的誤差推定を計算し,これらの問題に対処することを提案する。
• 参考スコア（独自算出の注目度）: 3.6095388702618414
• License:
• Abstract: Graph sparsification is a well-established technique for accelerating graph-based learning algorithms, which uses edge sampling to approximate dense graphs with sparse ones. Because the sparsification error is random and unknown, users must contend with uncertainty about the reliability of downstream computations. Although it is possible for users to obtain conceptual guidance from theoretical error bounds in the literature, such results are typically impractical at a numerical level. Taking an alternative approach, we propose to address these issues from a data-driven perspective by computing empirical error estimates. The proposed error estimates are highly versatile, and we demonstrate this in four use cases: Laplacian matrix approximation, graph cut queries, graph-structured regression, and spectral clustering. Moreover, we provide two theoretical guarantees for the error estimates, and explain why the cost of computing them is manageable in comparison to the overall cost of a typical graph sparsification workflow.
• Abstract（参考訳）: グラフスペーシフィケーション(Graph Sparsification)は、エッジサンプリングを用いて疎グラフを近似するグラフベースの学習アルゴリズムを高速化するための、確立されたテクニックである。 スパシフィケーションエラーはランダムで未知であるため、ユーザは下流の計算の信頼性について不確実性に直面する必要がある。 文献の理論的誤り境界から概念的ガイダンスを得ることは可能であるが、そのような結果は典型的には数値レベルでは非現実的である。 代替手法として、経験的誤差推定を計算し、データ駆動の観点からこれらの問題に対処することを提案する。 提案手法は,ラプラシアン行列近似,グラフカットクエリ,グラフ構造回帰,スペクトルクラスタリングの4つのユースケースで提案する。 さらに, 誤差推定の理論的保証を2つ提供し, 典型的なグラフスペーシフィケーションワークフローの全体的なコストと比較して, 計算コストが管理可能である理由を説明する。

関連論文リスト

• Robust Graph-Based Semi-Supervised Learning via $p$-Conductances [49.0776396776252]
  本研究では,データラベルが不足している,あるいは破損しているような状況下でのグラフに対する半教師付き学習の課題について検討する。 我々は、$p$-laplace と Poisson の学習方法を一般化した $p$-conductance learning という手法を提案する。 コンピュータビジョンと引用データセットの実証実験結果から,本手法が低ラベルレート, 劣化ラベル, 部分ラベルレジームにおける最先端の精度を実現することを示す。
  論文  参考訳（メタデータ） (2025-02-13T01:11:25Z)
• Stochastic Variance-Reduced Iterative Hard Thresholding in Graph Sparsity Optimization [0.626226809683956]
  グラデーションに基づくグラフ空間幅最適化法として,グラフRG-IHTとグラフSG-IHTの2つの手法を提案する。 我々は,手法が勾配に基づく枠組みを楽しむことを示す理論解析の一般性を示す。
  論文  参考訳（メタデータ） (2024-07-24T03:26:26Z)
• Learning Latent Graph Structures and their Uncertainty [63.95971478893842]
  グラフニューラルネットワーク(GNN)は、モデル精度を高めるために帰納バイアスとしてリレーショナル情報を使用する。 課題関連関係が不明なため,下流予測タスクを解きながら学習するためのグラフ構造学習手法が提案されている。
  論文  参考訳（メタデータ） (2024-05-30T10:49:22Z)
• Network Topology Inference with Sparsity and Laplacian Constraints [18.447094648361453]
  我々はラプラシアの制約付きガウス図形モデルを用いてネットワークトポロジに取り組む。 この問題を解決するために,効率的なプロジェクションアルゴリズムが開発された。
  論文  参考訳（メタデータ） (2023-09-02T15:06:30Z)
• Efficient Graph Laplacian Estimation by Proximal Newton [12.05527862797306]
  グラフ学習問題は、精度行列の最大極大推定(MLE)として定式化することができる。 いくつかのアルゴリズム的特徴を利用した効率的な解法を得るための2次手法を開発した。
  論文  参考訳（メタデータ） (2023-02-13T15:13:22Z)
• Optimal Propagation for Graph Neural Networks [51.08426265813481]
  最適グラフ構造を学習するための二段階最適化手法を提案する。 また、時間的複雑さをさらに軽減するために、低ランク近似モデルについても検討する。
  論文  参考訳（メタデータ） (2022-05-06T03:37:00Z)
• Bayesian Graph Contrastive Learning [55.36652660268726]
  本稿では,ランダムな拡張がエンコーダにつながることを示すグラフコントラスト学習手法の新たな視点を提案する。 提案手法は,各ノードを決定論的ベクトルに埋め込む既存の手法とは対照的に,各ノードを潜在空間の分布で表現する。 いくつかのベンチマークデータセットにおける既存の最先端手法と比較して,性能が大幅に向上したことを示す。
  論文  参考訳（メタデータ） (2021-12-15T01:45:32Z)
• Learning Sparse Graph with Minimax Concave Penalty under Gaussian Markov Random Fields [51.07460861448716]
  本稿では,データから学ぶための凸解析フレームワークを提案する。 三角凸分解はその上部に対応する変換によって保証されることを示す。
  論文  参考訳（メタデータ） (2021-09-17T17:46:12Z)
• Multilayer Clustered Graph Learning [66.94201299553336]
  我々は、観測された層を代表グラフに適切に集約するために、データ忠実度用語として対照的な損失を用いる。 実験により,本手法がクラスタクラスタw.r.tに繋がることが示された。 クラスタリング問題を解くためのクラスタリングアルゴリズムを学習する。
  論文  参考訳（メタデータ） (2020-10-29T09:58:02Z)
• Does the $\ell_1$-norm Learn a Sparse Graph under Laplacian Constrained Graphical Models? [13.572602792770288]
  ラプラシアン制約ガウス図形モデルの下でグラフを学習する問題を考察する。 我々は、大きな正規化パラメータが驚くほど完全なグラフ、すなわちエッジで接続されたすべてのエッジにつながることを示した。
  論文  参考訳（メタデータ） (2020-06-26T12:06:10Z)

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

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