論文の概要: Sparse Graph Learning from Sparse Data via Fiedler Number Maximization

• arxiv url: http://arxiv.org/abs/2604.26132v1
• Date: Tue, 28 Apr 2026 21:40:39 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-30 15:59:36.17703
• Title: Sparse Graph Learning from Sparse Data via Fiedler Number Maximization
• Title（参考訳）: フィッシャー数最大化によるスパースデータからのスパースグラフ学習
• Authors: Bahar Oveisgharan, Gene Cheung, Andrew Eckford,
• Abstract要約: ここでは、RNにおける信号 x の信号次元 N よりも観測数 K がかなり小さくなり、基礎となる分布が不明であるスパースデータからスパースグラフと連結グラフを学習することを目的とする。 スパースグラフ学習目的において、フィドラー数(連結性を定量化するグラフラプラシア行列の第2固有値)を頑健な正規化項として組み込む。 シミュレーション実験により、ファイドラー数はスパースグラフ推定を強固にし、従来のスパースグラフ学習アルゴリズムより優れていることが示された。
• 参考スコア（独自算出の注目度）: 16.83442282933831
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We aim to learn a sparse and connected graph from sparse data, where the number of observations K can be substantially smaller than the signal dimension N for signals x in R^N, and the underlying distribution is unknown. In this severely ill-posed setting, we incorporate Fiedler number (the second eigenvalue of the graph Laplacian matrix that quantifies connectedness) as a robust regularization term in the sparse graph learning objective. We first develop a greedy algorithm that iteratively selects one edge globally for weakening/removal to reduce the objective, leveraging eigenvalue perturbation theorems that bound the adverse effect of an edge change to the Fiedler number. Next, we design a parallel variant, based on the Cheeger's inequality, that recursively partitions an input graph into two sub-graphs using an approximate Cheeger cut to distributedly find an optimal edge. Simulation experiments show that Fiedler number maximization robustifies sparse graph estimates, outperforming previous sparse graph learning algorithms.
• Abstract（参考訳）: 本研究では,R^N における信号 x の信号次元 N よりも観測数 K がかなり小さく,基礎となる分布が不明なスパースデータから疎結合グラフを学習することを目的とする。 この酷い設定では、スパースグラフ学習目的において、フィドラー数(連結性を定量化するグラフラプラシア行列の第2固有値)を頑健な正規化項として組み込む。 まず,フェドラー数に対するエッジ変化の悪影響を束縛する固有値摂動定理を生かして,目的を弱めるために1つのエッジをグローバルに反復的に選択するグリーディアルゴリズムを開発した。 次に、Cheegerの不等式に基づいて並列な変種を設計し、Cheeger カットを用いて入力グラフを2つのサブグラフに再帰的に分割し、最適なエッジを分散的に見つける。 シミュレーション実験により、フィッシャー数最大化はスパースグラフ推定を強固にし、従来のスパースグラフ学習アルゴリズムより優れていることが示された。

関連論文リスト

• Graph Semi-Supervised Learning for Point Classification on Data Manifolds [16.311715311352597]
  データ多様体上の分類タスクのためのグラフ半教師付き学習フレームワークを提案する。 多様体仮説により、低次元 $mathcalM 部分集合 mathbbRF$ からサンプリングされた点としてデータをモデル化する。 我々は、$mathcalM$から一様サンプリングを行うと、半教師付きタスクの一般化ギャップはグラフサイズの増加とともに減少することを示す。
  論文  参考訳（メタデータ） (2025-06-13T19:52:54Z)
• Efficient Graph Matching for Correlated Stochastic Block Models [7.320365821066744]
  2つのバランスの取れたコミュニティを持つ相関ブロックモデルの学習問題について検討する。 我々の主な成果は、この設定におけるグラフマッチングのための最初の効率的なアルゴリズムである。 我々はこれを情報理論的に可能であれば、正確なグラフマッチングのための効率的なアルゴリズムに拡張する。
  論文  参考訳（メタデータ） (2024-12-03T18:36:45Z)
• Deep Manifold Graph Auto-Encoder for Attributed Graph Embedding [51.75091298017941]
  本稿では,属性付きグラフデータに対する新しいDeep Manifold (Variational) Graph Auto-Encoder (DMVGAE/DMGAE)を提案する。 提案手法は,最先端のベースラインアルゴリズムを,一般的なデータセット間でのダウンストリームタスクの差を大きく越える。
  論文  参考訳（メタデータ） (2024-01-12T17:57:07Z)
• Efficient Graph Laplacian Estimation by Proximal Newton [12.05527862797306]
  グラフ学習問題は、精度行列の最大極大推定(MLE)として定式化することができる。 いくつかのアルゴリズム的特徴を利用した効率的な解法を得るための2次手法を開発した。
  論文  参考訳（メタデータ） (2023-02-13T15:13:22Z)
• Graph Signal Sampling for Inductive One-Bit Matrix Completion: a Closed-form Solution [112.3443939502313]
  グラフ信号解析と処理の利点を享受する統合グラフ信号サンプリングフレームワークを提案する。 キーとなる考え方は、各ユーザのアイテムのレーティングをアイテムイットグラフの頂点上の関数(信号)に変換することである。 オンライン設定では、グラフフーリエ領域における連続ランダムガウス雑音を考慮したベイズ拡張(BGS-IMC)を開発する。
  論文  参考訳（メタデータ） (2023-02-08T08:17:43Z)
• Graph Condensation via Receptive Field Distribution Matching [61.71711656856704]
  本稿では,元のグラフを表す小さなグラフの作成に焦点をあてる。 我々は、元のグラフを受容体の分布とみなし、受容体が同様の分布を持つ小さなグラフを合成することを目的としている。
  論文  参考訳（メタデータ） (2022-06-28T02:10:05Z)
• Multilayer Graph Clustering with Optimized Node Embedding [70.1053472751897]
  多層グラフクラスタリングは、グラフノードをカテゴリまたはコミュニティに分割することを目指しています。 与えられた多層グラフの層をクラスタリングに親しみやすい埋め込みを提案する。 実験の結果,本手法は著しい改善をもたらすことがわかった。
  論文  参考訳（メタデータ） (2021-03-30T17:36:40Z)
• Multilayer Clustered Graph Learning [66.94201299553336]
  我々は、観測された層を代表グラフに適切に集約するために、データ忠実度用語として対照的な損失を用いる。 実験により,本手法がクラスタクラスタw.r.tに繋がることが示された。 クラスタリング問題を解くためのクラスタリングアルゴリズムを学習する。
  論文  参考訳（メタデータ） (2020-10-29T09:58:02Z)
• Block-Approximated Exponential Random Graphs [77.4792558024487]
  指数乱グラフ(ERG)の分野における重要な課題は、大きなグラフ上の非自明なERGの適合である。 本稿では,非自明なERGに対する近似フレームワークを提案する。 我々の手法は、数百万のノードからなるスパースグラフにスケーラブルである。
  論文  参考訳（メタデータ） (2020-02-14T11:42:16Z)

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

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