論文の概要: Taxonomy of reduction matrices for Graph Coarsening

• arxiv url: http://arxiv.org/abs/2506.11743v1
• Date: Fri, 13 Jun 2025 12:55:03 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-16 17:50:49.793884
• Title: Taxonomy of reduction matrices for Graph Coarsening
• Title（参考訳）: グラフ粗化のための還元行列の分類法
• Authors: Antonin Joly, Nicolas Keriven, Aline Roumy,
• Abstract要約: グラフ粗化は、グラフのサイズを小さくし、メモリフットプリントを軽量化することを目的としている。 ほとんどの粗いフレームワークは、リダクションとリフトマトリクスの間に固定的な関係を課している。 固定昇降行列で表される固定粗化の場合、還元行列を変更するだけでRSAをさらに小さくすることができることを示す。
• 参考スコア（独自算出の注目度）: 14.662574002430794
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Graph coarsening aims to diminish the size of a graph to lighten its memory footprint, and has numerous applications in graph signal processing and machine learning. It is usually defined using a reduction matrix and a lifting matrix, which, respectively, allows to project a graph signal from the original graph to the coarsened one and back. This results in a loss of information measured by the so-called Restricted Spectral Approximation (RSA). Most coarsening frameworks impose a fixed relationship between the reduction and lifting matrices, generally as pseudo-inverses of each other, and seek to define a coarsening that minimizes the RSA. In this paper, we remark that the roles of these two matrices are not entirely symmetric: indeed, putting constraints on the lifting matrix alone ensures the existence of important objects such as the coarsened graph's adjacency matrix or Laplacian. In light of this, in this paper, we introduce a more general notion of reduction matrix, that is not necessarily the pseudo-inverse of the lifting matrix. We establish a taxonomy of ``admissible'' families of reduction matrices, discuss the different properties that they must satisfy and whether they admit a closed-form description or not. We show that, for a fixed coarsening represented by a fixed lifting matrix, the RSA can be further reduced simply by modifying the reduction matrix. We explore different examples, including some based on a constrained optimization process of the RSA. Since this criterion has also been linked to the performance of Graph Neural Networks, we also illustrate the impact of this choices on different node classification tasks on coarsened graphs.
• Abstract（参考訳）: グラフ粗化は、グラフのサイズを小さくしてメモリフットプリントを軽量化することを目的としており、グラフ信号処理や機械学習に多くの応用がある。 通常、リダクション行列とリフト行列を使って定義され、それぞれ元のグラフから粗いグラフへグラフ信号を投影することができる。 これにより、いわゆるRestricted Spectral Approximation (RSA)によって測定される情報の損失が発生する。 ほとんどの粗いフレームワークは、還元行列と持ち上げ行列の間に固定的な関係を課し、一般的には互いに擬似逆数として、RSAを最小化する粗い関係を定義しようとする。 実際に、持ち上げ行列のみに制約を課すことで、粗いグラフの隣接行列やラプラシアンのような重要な対象の存在が保証される。 これを踏まえて、我々はより一般的な還元行列の概念を導入し、これは必ずしも持ち上げ行列の擬逆ではない。 我々は、還元行列の「許容可能な」ファミリーの分類を確立し、それらが満たさなければならない異なる特性と、それらが閉形式の記述を許容するか否かを議論する。 固定昇降行列で表される固定粗化の場合、還元行列を変更するだけでRSAをさらに小さくすることができることを示す。 我々は、RSAの制約付き最適化プロセスに基づくものを含む、異なる例を探索する。 この基準はグラフニューラルネットワークの性能にも関係しているため、この選択が粗いグラフに対する異なるノード分類タスクに与える影響についても説明する。

関連論文リスト

• Cramer-Rao Bounds for Laplacian Matrix Estimation [56.1214184671173]
  クラマー・ラオ境界(CRB)の閉形式行列式をラプラシア行列推定に特化して導出した。 電力系統における(i)トポロジー同定,(ii)拡散モデルにおけるグラフフィルタ同定,(iii)ラプラシアン制約下でのガウスマルコフ確率場における精度行列推定の3つの代表的応用について示す。
  論文  参考訳（メタデータ） (2025-04-06T18:28:31Z)
• Beyond symmetrization: effective adjacency matrices and renormalization for (un)singed directed graphs [0.0]
  変形ラプラシア作用素の定義から生じる効果的な隣接行列の概念を定義する。 これらの効果的な行列は、ジェネリックグラフを符号のない無向グラフの族にマッピングすることを可能にする。 ホッジ・ヘルムホルツ分解がこの複雑さをナビゲートするのにどのように役立つかを示す。
  論文  参考訳（メタデータ） (2024-06-03T16:48:25Z)
• Learning Graphical Factor Models with Riemannian Optimization [70.13748170371889]
  本稿では,低ランク構造制約下でのグラフ学習のためのフレキシブルなアルゴリズムフレームワークを提案する。 この問題は楕円分布のペナルティ化された最大推定値として表される。 楕円モデルによく適合する正定行列と定ランクの正半定行列のジオメトリを利用する。
  論文  参考訳（メタデータ） (2022-10-21T13:19:45Z)
• A Unified Framework for Optimization-Based Graph Coarsening [5.720402020129441]
  大きなグラフが与えられたとき、グラフ粗化は、もともと与えられたグラフの特性を保ちながら、より小さく抽出可能なグラフを学習することを目的としている。 提案するフレームワークは,グラフ学習と次元減少の一体化にある。 学習された粗大化グラフは、元のグラフと類似した$epsin(0,1)$であることが確立されている。
  論文  参考訳（メタデータ） (2022-10-02T06:31:42Z)
• 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)
• Non-PSD Matrix Sketching with Applications to Regression and Optimization [56.730993511802865]
  非PSDおよび2乗根行列の次元削減法を提案する。 複数のダウンストリームタスクにこれらのテクニックをどのように使用できるかを示す。
  論文  参考訳（メタデータ） (2021-06-16T04:07:48Z)
• Matrix Decomposition on Graphs: A Functional View [36.85782408336389]
  本稿では,グラフ上の行列分解問題の関数的考察を提案する。 我々のフレームワークは、還元基底を用いて積空間上の関数を表現することは、低階行列近似を回復するのに十分である、というキーアイデアに基づいている。
  論文  参考訳（メタデータ） (2021-02-05T15:28:11Z)

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

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