論文の概要: Fast Graph Laplacian Estimation using Effective Resistance
- arxiv url: http://arxiv.org/abs/2609.23668v1
- Date: Sun, 20 Sep 2026 14:23:43 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-09-22 20:29:00.907322
- Title: Fast Graph Laplacian Estimation using Effective Resistance
- Title（参考訳）: 有効抵抗を用いた高速グラフラプラシアン推定
- Abstract要約: 正規化に有効な抵抗を用いたグラフラプラシアンの非定性推定器を提案する。
実験により, エッジと重み回復のトレードオフを考慮し, 適度なグラフの計算コストを大幅に削減できることが示唆された。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Inferring network topology from noisy node observations is a central problem in graph signal processing. In this paper, we consider Laplacian-constrained graph estimation for Gaussian Markov random fields, focusing on the underdetermined regime in which the number of samples is smaller than the number of graph nodes. Existing approaches often formulate the problem as a sparsity-regularized maximum-likelihood estimation problem. While effective, such methods typically require iterative optimization and are often computationally demanding, particularly under Laplacian constraints. Instead, we propose a non-iterative estimator of graph Laplacians that uses effective resistance for regularization, and evaluate the method using a simple sparsification procedure. Experiments show that with some trade-off in edge and weight recovery on the considered dataset, computational cost for moderately sized graphs can be substantially reduced.
- Abstract（参考訳）: ノイズノード観測からネットワークトポロジを推定することは、グラフ信号処理における中心的な問題である。
本稿では,ガウスマルコフ確率場に対するラプラシアン制約グラフ推定について考察する。
既存のアプローチでは、時空間規則化最大線量推定問題として問題を定式化することが多い。
有効ではあるが、そのような手法は典型的には反復最適化を必要とし、特にラプラシアの制約の下では計算的に要求されることが多い。
代わりに、正規化に有効な抵抗を用いたグラフラプラシアンの非定性推定器を提案し、簡単なスペーシフィケーション法を用いて評価する。
実験により, エッジと重み回復のトレードオフを考慮し, 適度なグラフの計算コストを大幅に削減できることが示唆された。
関連論文リスト
- Scalable Graph Coreset Selection via Greedy Sampling [48.91894218306487]
最小内部積グリーディ選択規則に基づく,単純かつ効率的なカラム選択グラフサンプリングアルゴリズムを提案する。
ブロックモデルに基づいてアルゴリズムを解析し,次数分布がノード間で均衡している場合,クラスタサイズに対する比例サンプリングを実現する。
論文 参考訳（メタデータ） (2026-07-30T02:45:31Z) - Low-Complexity and Consistent Graphon Estimation from Multiple Networks [0.0]
アルゴリズムの複雑さの低い新しいヒストグラムベースの推定器を導入し、全てのグラフのノードを協調的に整列させることにより高精度な推定を行う。
数値的な研究により,提案手法の精度は既存の推定手法よりも優れており,特にデータセットが小型かつ可変サイズのネットワークで構成されている場合の方が優れていることがわかった。
論文 参考訳（メタデータ） (2026-03-16T17:41:00Z) - Mitigating Over-Squashing in Graph Neural Networks by Spectrum-Preserving Sparsification [81.06278257153835]
本稿では,構造的ボトルネック低減とグラフ特性保存のバランスをとるグラフ再構成手法を提案する。
本手法は、疎性を維持しながら接続性を高めたグラフを生成し、元のグラフスペクトルを大半保存する。
論文 参考訳（メタデータ） (2025-06-19T08:01:00Z) - Empirical Error Estimates for Graph Sparsification [3.6095388702618414]
グラフスペーシフィケーション(Graph Sparsification)は、グラフベースの学習アルゴリズムを高速化する技術である。
スパシフィケーションエラーはランダムで未知であるため、ユーザは下流の計算の信頼性について不確実性に直面する必要がある。
経験的誤差推定を計算し,これらの問題に対処することを提案する。
論文 参考訳（メタデータ） (2025-03-11T04:28:57Z) - 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) - Nonconvex Stochastic Scaled-Gradient Descent and Generalized Eigenvector
Problems [98.34292831923335]
オンライン相関解析の問題から,emphStochastic Scaled-Gradient Descent (SSD)アルゴリズムを提案する。
我々はこれらのアイデアをオンライン相関解析に適用し、局所収束率を正規性に比例した最適な1時間スケールのアルゴリズムを初めて導いた。
論文 参考訳（メタデータ） (2021-12-29T18:46:52Z) - Scaling Up Graph Neural Networks Via Graph Coarsening [18.176326897605225]
グラフニューラルネットワーク(GNN)のスケーラビリティは、マシンラーニングにおける大きな課題のひとつだ。
本稿では,GNNのスケーラブルなトレーニングにグラフ粗大化を用いることを提案する。
既成の粗大化法を単純に適用すれば,分類精度を著しく低下させることなく,ノード数を最大10倍に削減できることを示す。
論文 参考訳（メタデータ） (2021-06-09T15:46:17Z) - Fast Graph Attention Networks Using Effective Resistance Based Graph
Sparsification [70.50751397870972]
FastGATは、スペクトルスペーシフィケーションを用いて、注目に基づくGNNを軽量にし、入力グラフの最適プルーニングを生成する手法である。
我々は,ノード分類タスクのための大規模実世界のグラフデータセット上でFastGATを実験的に評価した。
論文 参考訳（メタデータ） (2020-06-15T22:07:54Z) - Block-Approximated Exponential Random Graphs [77.4792558024487]
指数乱グラフ(ERG)の分野における重要な課題は、大きなグラフ上の非自明なERGの適合である。
本稿では,非自明なERGに対する近似フレームワークを提案する。
我々の手法は、数百万のノードからなるスパースグラフにスケーラブルである。
論文 参考訳（メタデータ） (2020-02-14T11:42:16Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。