論文の概要: Laplacian Canonization: A Minimalist Approach to Sign and Basis Invariant Spectral Embedding

• arxiv url: http://arxiv.org/abs/2310.18716v2
• Date: Wed, 10 Jan 2024 20:19:47 GMT
• ステータス: 処理完了
• システム内更新日: 2024-01-13 03:21:39.900755
• Title: Laplacian Canonization: A Minimalist Approach to Sign and Basis Invariant Spectral Embedding
• Title（参考訳）: Laplacian Canonization: Sign and Basis Invariant Spectral Embeddingに対するミニマリストアプローチ
• Authors: Jiangyan Ma, Yifei Wang, Yisen Wang
• Abstract要約: スペクトル埋め込みは強力なグラフ計算手法であり、グラフトランスフォーマーの有効性から最近多くの注目を集めている。 従来の手法は、新しい不変量を学び、高い複雑さに苦しむために、コストのかかるアプローチを開発した。 本研究では,固有ベクトルの正準方向を直接求めることにより,あいまいさを解消する最小限のアプローチを検討する。
• 参考スコア（独自算出の注目度）: 36.61907023057978
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Spectral embedding is a powerful graph embedding technique that has received a lot of attention recently due to its effectiveness on Graph Transformers. However, from a theoretical perspective, the universal expressive power of spectral embedding comes at the price of losing two important invariance properties of graphs, sign and basis invariance, which also limits its effectiveness on graph data. To remedy this issue, many previous methods developed costly approaches to learn new invariants and suffer from high computation complexity. In this work, we explore a minimal approach that resolves the ambiguity issues by directly finding canonical directions for the eigenvectors, named Laplacian Canonization (LC). As a pure pre-processing method, LC is light-weighted and can be applied to any existing GNNs. We provide a thorough investigation, from theory to algorithm, on this approach, and discover an efficient algorithm named Maximal Axis Projection (MAP) that works for both sign and basis invariance and successfully canonizes more than 90% of all eigenvectors. Experiments on real-world benchmark datasets like ZINC, MOLTOX21, and MOLPCBA show that MAP consistently outperforms existing methods while bringing minimal computation overhead. Code is available at https://github.com/PKU-ML/LaplacianCanonization.
• Abstract（参考訳）: スペクトル埋め込み(spectrum embedded)は、グラフトランスフォーマーの有効性から近年注目を集めている強力なグラフ埋め込み技術である。 しかし、理論的な観点からは、スペクトル埋め込みの普遍的な表現力は、グラフ、符号および基底不変性の2つの重要な不変性を失うことの代償となり、グラフデータに対するその有効性も制限される。 この問題を解決するために、多くの従来の手法は、新しい不変量を学び、高い計算複雑性に悩まされるコストのかかるアプローチを開発した。 本研究では、固有ベクトルの正準方向を直接見つけることにより、あいまいさを解消する最小限のアプローチ、Laplacian Canonization (LC) を提案する。 純粋な前処理法としてLCは軽量化されており、既存のGNNにも適用可能である。 理論からアルゴリズムまで、このアプローチで徹底的な調査を行い、符号と基底の不変性の両方に有効で、すべての固有ベクトルの90%以上を正準化する、maximal axis projection (map) という効率的なアルゴリズムを発見した。 ZINC、MOLTOX21、MOLPCBAといった実世界のベンチマークデータセットの実験では、MAPは計算オーバーヘッドを最小限に抑えながら、既存のメソッドを一貫して上回っている。 コードはhttps://github.com/PKU-ML/LaplacianCanonizationで入手できる。

関連論文リスト

• S-CFE: Simple Counterfactual Explanations [21.975560789792073]
  スパースデータに対する多様体対応の反実的説明を求める問題に対処する。 提案手法は,スパースかつ多様体に整列した反実的説明を効果的に生成する。
  論文  参考訳（メタデータ） (2024-10-21T07:42:43Z)
• Learning Cartesian Product Graphs with Laplacian Constraints [10.15283812819547]
  ラプラシアン制約下でのカルト積グラフの学習問題について検討する。 我々は、ペナルティ化された最大推定値に対する統計的整合性を確立する。 また、構造的欠落のある値の存在下で、効率的な共同グラフ学習と計算を行う方法を拡張した。
  論文  参考訳（メタデータ） (2024-02-12T22:48:30Z)
• Efficient Graph Laplacian Estimation by Proximal Newton [12.05527862797306]
  グラフ学習問題は、精度行列の最大極大推定(MLE)として定式化することができる。 いくつかのアルゴリズム的特徴を利用した効率的な解法を得るための2次手法を開発した。
  論文  参考訳（メタデータ） (2023-02-13T15:13:22Z)
• Graph Laplacian for Semi-Supervised Learning [8.477619837043214]
  そこで本研究では,Semi-Supervised Learning (SSL)問題に適応した新しいグラフラプラシアンを提案する。 これは密度とコントラストの両測度に基づいており、演算子に直接ラベル付きデータの符号化を可能にする。
  論文  参考訳（メタデータ） (2023-01-12T12:02:26Z)
• Softmax-free Linear Transformers [90.83157268265654]
  視覚変換器(ViT)は、視覚知覚タスクの最先端を推し進めている。 既存の手法は理論的に欠陥があるか、視覚認識に経験的に効果がないかのいずれかである。 我々はSoftmax-Free Transformers (SOFT) のファミリーを提案する。
  論文  参考訳（メタデータ） (2022-07-05T03:08:27Z)
• Learning Sparse Graph with Minimax Concave Penalty under Gaussian Markov Random Fields [51.07460861448716]
  本稿では,データから学ぶための凸解析フレームワークを提案する。 三角凸分解はその上部に対応する変換によって保証されることを示す。
  論文  参考訳（メタデータ） (2021-09-17T17:46:12Z)
• Unfolding Projection-free SDP Relaxation of Binary Graph Classifier via GDPA Linearization [59.87663954467815]
  アルゴリズムの展開は、モデルベースのアルゴリズムの各イテレーションをニューラルネットワーク層として実装することにより、解釈可能で類似のニューラルネットワークアーキテクチャを生成する。 本稿では、Gershgorin disc perfect alignment (GDPA)と呼ばれる最近の線形代数定理を利用して、二進グラフの半定値プログラミング緩和(SDR)のためのプロジェクションフリーアルゴリズムをアンロールする。 実験結果から,我々の未学習ネットワークは純粋モデルベースグラフ分類器よりも優れ,純粋データ駆動ネットワークに匹敵する性能を示したが,パラメータははるかに少なかった。
  論文  参考訳（メタデータ） (2021-09-10T07:01:15Z)
• Pseudoinverse Graph Convolutional Networks: Fast Filters Tailored for Large Eigengaps of Dense Graphs and Hypergraphs [0.0]
  Graph Convolutional Networks (GCNs) は、グラフベースのデータセットで半教師付き分類を行うツールとして成功している。 本稿では,三部フィルタ空間が高密度グラフを対象とする新しいGCN変種を提案する。
  論文  参考訳（メタデータ） (2020-08-03T08:48:41Z)
• Gradient Free Minimax Optimization: Variance Reduction and Faster Convergence [120.9336529957224]
  本稿では、勾配のないミニマックス最適化問題の大きさを非強設定で表現する。 本稿では,新しいゼロ階分散還元降下アルゴリズムが,クエリの複雑さを最もよく表すことを示す。
  論文  参考訳（メタデータ） (2020-06-16T17:55:46Z)
• Spectral Learning on Matrices and Tensors [74.88243719463053]
  テンソル分解は行列法で欠落する潜伏効果を拾うことができることを示す。 また,効率的なテンソル分解法を設計するための計算手法についても概説する。
  論文  参考訳（メタデータ） (2020-04-16T22:53:00Z)

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

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