論文の概要: Subspace Projection Methods for Fast Spectral Embeddings of Evolving Graphs

• arxiv url: http://arxiv.org/abs/2603.19439v1
• Date: Thu, 19 Mar 2026 20:07:48 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-03-23 19:48:38.860763
• Title: Subspace Projection Methods for Fast Spectral Embeddings of Evolving Graphs
• Title（参考訳）: 進化グラフの高速スペクトル埋め込みのための部分空間投影法
• Authors: Mohammad Eini, Abdullah Karaaslanli, Vassilis Kalantzis, Panagiotis A. Traganitis,
• Abstract要約: いくつかのグラフデータマイニング、信号処理、機械学習下流タスクは、関連する隣接行列やラプラシア行列の固有ベクトルに関連する情報に依存している。 本稿では,グラフが動的に進化するにつれて,初期隣接行列やラプラシア行列の先頭固有値に付随する固有ベクトルを更新するアルゴリズムフレームワークを提案する。
• 参考スコア（独自算出の注目度）: 8.707677538886852
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Several graph data mining, signal processing, and machine learning downstream tasks rely on information related to the eigenvectors of the associated adjacency or Laplacian matrix. Classical eigendecomposition methods are powerful when the matrix remains static but cannot be applied to problems where the matrix entries are updated or the number of rows and columns increases frequently. Such scenarios occur routinely in graph analytics when the graph is changing dynamically and either edges and/or nodes are being added and removed. This paper puts forth a new algorithmic framework to update the eigenvectors associated with the leading eigenvalues of an initial adjacency or Laplacian matrix as the graph evolves dynamically. The proposed algorithm is based on Rayleigh-Ritz projections, in which the original eigenvalue problem is projected onto a restricted subspace which ideally encapsulates the invariant subspace associated with the sought eigenvectors. Following ideas from eigenvector perturbation analysis, we present a new methodology to build the projection subspace. The proposed framework features lower computational and memory complexity with respect to competitive alternatives while empirical results show strong qualitative performance, both in terms of eigenvector approximation and accuracy of downstream learning tasks of central node identification and node clustering.
• Abstract（参考訳）: いくつかのグラフデータマイニング、信号処理、機械学習下流タスクは、関連する隣接行列やラプラシア行列の固有ベクトルに関連する情報に依存している。 古典的固有分解法は、行列が静的なままでは強力であるが、行列のエントリが更新されたり、行数や列数が頻繁に増加する問題には適用できない。 このようなシナリオは、グラフが動的に変化し、エッジと/またはノードが追加および削除されているときに、グラフ分析で定期的に発生する。 本稿では,グラフが動的に進化するにつれて,初期隣接行列やラプラシア行列の先頭固有値に付随する固有ベクトルを更新するアルゴリズムフレームワークを提案する。 提案アルゴリズムはRayleigh-Ritz射影に基づいており、元の固有値問題は制限された部分空間に投影され、探索された固有ベクトルに関連する不変部分空間を理想的にカプセル化する。 固有ベクトル摂動解析の考え方に従い、射影部分空間を構築するための新しい方法論を提案する。 提案フレームワークは,計算量やメモリの複雑さの低減を特徴とし,実験結果からは固有ベクトル近似とノードクラスタリングによる下流学習タスクの精度の両面において,定性的な性能を示す。

関連論文リスト

• Towards Stable, Globally Expressive Graph Representations with Laplacian Eigenvectors [29.055130767451036]
  本稿では,ラプラシアン固有ベクトルを用いて,安定かつグローバルに表現可能なグラフ表現を生成する手法を提案する。 提案手法は, 数値的近接固有値を円滑に処理し, 摂動に対するロバスト性を向上する。
  論文  参考訳（メタデータ） (2024-10-13T06:02:25Z)
• Mode-wise Principal Subspace Pursuit and Matrix Spiked Covariance Model [13.082805815235975]
  行列データに対して行次元と列次元の両方に隠れたバリエーションを抽出するために,モードワイド・プリンシパル・サブスペース・スーツ (MOP-UP) と呼ばれる新しいフレームワークを導入する。 提案フレームワークの有効性と実用性は、シミュレーションと実データの両方の実験を通して実証される。
  論文  参考訳（メタデータ） (2023-07-02T13:59:47Z)
• Accelerated structured matrix factorization [0.0]
  行列分解は、複雑な高次元データにおいて、実際の信号は一般に低次元構造にあるという考え方を利用する。 ベイジアン縮退を先取りして,高次元行列分解のための計算に便利な手法を考案する。 行と列のエンティティ間の依存性は、要素内でフレキシブルなスパースパターンを誘導することによってモデル化される。
  論文  参考訳（メタデータ） (2022-12-13T11:35:01Z)
• Learning Graphical Factor Models with Riemannian Optimization [70.13748170371889]
  本稿では,低ランク構造制約下でのグラフ学習のためのフレキシブルなアルゴリズムフレームワークを提案する。 この問題は楕円分布のペナルティ化された最大推定値として表される。 楕円モデルによく適合する正定行列と定ランクの正半定行列のジオメトリを利用する。
  論文  参考訳（メタデータ） (2022-10-21T13:19:45Z)
• Graph Polynomial Convolution Models for Node Classification of Non-Homophilous Graphs [52.52570805621925]
  本研究では,高階グラフ畳み込みからの効率的な学習と,ノード分類のための隣接行列から直接学習する。 得られたモデルが新しいグラフと残留スケーリングパラメータをもたらすことを示す。 提案手法は,非親和性パラメータのノード分類における精度の向上を実証する。
  論文  参考訳（メタデータ） (2022-09-12T04:46:55Z)
• Semi-Supervised Subspace Clustering via Tensor Low-Rank Representation [64.49871502193477]
  本稿では,初期監視情報を同時に拡張し,識別親和性行列を構築することのできる,新しい半教師付きサブスペースクラスタリング手法を提案する。 6つの一般的なベンチマークデータセットの総合的な実験結果から,本手法が最先端手法よりも優れていることを示す。
  論文  参考訳（メタデータ） (2022-05-21T01:47:17Z)
• Analysis of Truncated Orthogonal Iteration for Sparse Eigenvector Problems [78.95866278697777]
  本研究では,多元的固有ベクトルを分散制約で同時に計算するTruncated Orthogonal Iterationの2つの変種を提案する。 次に,我々のアルゴリズムを適用して,幅広いテストデータセットに対するスパース原理成分分析問題を解く。
  論文  参考訳（メタデータ） (2021-03-24T23:11:32Z)
• Projection techniques to update the truncated SVD of evolving matrices [17.22107982549168]
  本稿では,新しい行や列の追加に伴う行列のランク-k truncated Singular Value Decomposition (SVD) の更新の問題について考察する。 提案するフレームワークは純粋に代数的であり、一般的な更新問題をターゲットにしている。 実アプリケーションから得られた行列の結果から,提案アルゴリズムの精度が向上する可能性が示唆された。
  論文  参考訳（メタデータ） (2020-10-13T13:46:08Z)
• Eigendecomposition-Free Training of Deep Networks for Linear Least-Square Problems [107.3868459697569]
  我々は、ディープネットワークのトレーニングに固有分解のないアプローチを導入する。 この手法は固有分解の明示的な微分よりもはるかに堅牢であることを示す。 我々の手法は収束特性が良く、最先端の結果が得られます。
  論文  参考訳（メタデータ） (2020-04-15T04:29:34Z)

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

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