論文の概要: Cospectrality preserving graph modifications and eigenvector properties
via walk equivalence of vertices
- arxiv url: http://arxiv.org/abs/2007.07609v3
- Date: Fri, 16 Apr 2021 09:28:37 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-09 09:12:43.548959
- Title: Cospectrality preserving graph modifications and eigenvector properties
via walk equivalence of vertices
- Title（参考訳）: 頂点の歩行同値性によるグラフ修正と固有ベクトル特性の共スペクトル保存
- Authors: Christian V. Morfonios, Maxim Pyzh, Malte R\"ontgen, Peter Schmelcher
- Abstract要約: コスペクトル性は交換対称性の強力な一般化であり、すべての実数値対称行列に適用できる。
余スペクトル頂点を持つ行列のパワーは固有ベクトルのさらなる局所的関係を誘導することを示す。
我々の研究は、汎用的な複雑なネットワークのようなシステムの設計において、隠れた構造対称性を柔軟に活用する方法を開拓する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Originating from spectral graph theory, cospectrality is a powerful
generalization of exchange symmetry and can be applied to all real-valued
symmetric matrices. Two vertices of an undirected graph with real edge weights
are cospectral iff the underlying weighted adjacency matrix $M$ fulfills
$[M^k]_{u,u} = [M^k]_{v,v}$ for all non-negative integer $k$, and as a result
any eigenvector $\phi$ of $M$ has (or, in the presence of degeneracies, can be
chosen to have) definite parity on $u$ and $v$. We here show that the powers of
a matrix with cospectral vertices induce further local relations on its
eigenvectors, and also can be used to design cospectrality preserving
modifications. To this end, we introduce the concept of \emph{walk equivalence}
of cospectral vertices with respect to \emph{walk multiplets} which are special
vertex subsets of a graph. Walk multiplets allow for systematic and flexible
modifications of a graph with a given cospectral pair while preserving this
cospectrality. The set of modifications includes the addition and removal of
both vertices and edges, such that the underlying topology of the graph can be
altered. In particular, we prove that any new vertex connected to a walk
multiplet by suitable connection weights becomes a so-called unrestricted
substitution point (USP), meaning that any arbitrary graph may be connected to
it without breaking cospectrality. Also, suitable interconnections between walk
multiplets within a graph are shown to preserve the associated cospectrality.
Importantly, we demonstrate that the walk equivalence of cospectral vertices
$u,v$ imposes a local structure on every eigenvector $\phi$ obeying $\phi_{u} =
\pm \phi_{v} \ne 0$ (in the case of degeneracies, a specific choice of the
eigenvector basis is needed). Our work paves the way for flexibly exploiting
hidden structural symmetries in the design of generic complex network-like
systems.
- Abstract（参考訳）: スペクトルグラフ理論から派生したコスペクトル性は交換対称性の強力な一般化であり、すべての実数値対称行列に適用できる。
実辺重み付き無向グラフの2つの頂点は、コスペクトル iff であり、下記の重み付き隣接行列 $M$ fulfills $[M^k]_{u,u} = [M^k]_{v,v}$ for all non- negative integer $k$, その結果、任意の固有ベクトル $\phi$ of $M$ has (あるいは、退化が存在する場合には、$u$ と $v$ の任意のパリティを持つことができる)。
本稿では,共スペクトル頂点を持つ行列のパワーが固有ベクトルに対するさらなる局所関係を誘導することを示すとともに,共スペクトル性保存修正の設計にも利用できることを示す。
この目的のために、グラフの特殊頂点部分集合である \emph{walk multits} に関して、コスペクトル頂点の \emph{walk equivalence} の概念を導入する。
ウォーク多重化は、与えられたコスペクトル対を持つグラフの体系的で柔軟な修正を可能にし、このコスペクトル性を保存する。
修正のセットには、頂点と辺の両方の追加と削除が含まれており、グラフの基底トポロジーを変更することができる。
特に、適切な接続重みによってウォーク多重に連結された任意の新しい頂点がいわゆる非制限置換点 (USP) となり、任意のグラフがコスペクタリティを壊さずにそれと接続できることを示す。
また、グラフ内のウォークマルチプレクレット間の適切な相互接続は、関連するコスペクタリティを保存するために示される。
重要なことに、余スペクトル頂点の歩行同値性である u,v$ は、すべての固有ベクトル $\phi$ に対して、$\phi_{u} = \pm \phi_{v} \ne 0$ に従う局所構造を課す(縮退の場合、固有ベクトル基底の特定の選択が必要である)。
我々の研究は、複合ネットワークのようなシステムの設計において、隠れた構造対称性を柔軟に活用する方法を開拓する。
関連論文リスト
- Linear Transformer Topological Masking with Graph Random Features [52.717865653036796]
重み付き隣接行列の学習可能な関数としてトポロジカルマスクをパラメータ化する方法を示す。
私たちの効率的なマスキングアルゴリズムは、画像およびポイントクラウドデータのタスクに対して、強力なパフォーマンス向上を提供します。
論文 参考訳（メタデータ） (2024-10-04T14:24:06Z) - Graph Generation via Spectral Diffusion [51.60814773299899]
本稿では,1)グラフラプラシア行列のスペクトル分解と2)拡散過程に基づく新しいグラフ生成モデルGRASPを提案する。
具体的には、固有ベクトルと固有値のサンプリングにデノナイジングモデルを用い、グラフラプラシアン行列と隣接行列を再構成する。
我々の置換不変モデルは各ノードの固有ベクトルに連結することでノードの特徴を扱える。
論文 参考訳（メタデータ） (2024-02-29T09:26:46Z) - The Exact Determinant of a Specific Class of Sparse Positive Definite
Matrices [5.330240017302621]
スパースガウス図形モデルの特定のクラスに対して、共分散行列の行列式に対する閉形式解を提供する。
私たちのフレームワークでは、グラフィカルなインタラクションモデルは$mathcalK_n$と$mathcalK_n-1$の代替製品と同等です。
論文 参考訳（メタデータ） (2023-11-11T18:31:25Z) - Transformers as Support Vector Machines [54.642793677472724]
自己アテンションの最適化幾何と厳密なSVM問題との間には,形式的等価性を確立する。
勾配降下に最適化された1層変圧器の暗黙バイアスを特徴付ける。
これらの発見は、最適なトークンを分離し選択するSVMの階層としてのトランスフォーマーの解釈を刺激していると信じている。
論文 参考訳（メタデータ） (2023-08-31T17:57:50Z) - Matrix logistic map: fractal spectral distributions and transfer of
chaos [0.0]
ここでは, 間隔$[0, 1]$で支持される連続レベル密度を持つエルミート確率行列の初期アンサンブルに対して, レベル密度はロジスティック写像の不変測度に収束することを示す。
このアプローチは、結合ロジスティックマップの既知のモデルを一般化し、複雑なネットワークや多次元システムにおけるカオスへの移行の研究を可能にする。
論文 参考訳（メタデータ） (2023-03-10T19:19:56Z) - Cheeger Inequalities for Directed Graphs and Hypergraphs Using
Reweighted Eigenvalues [6.094384342913063]
我々は、有向グラフのための新しいスペクトル理論と、ハイパーグラフのための代替スペクトル理論を開発する。
我々は、重み付けされた固有値アプローチを用いて、有向グラフとハイパーグラフに対するチェーガーの不等式を導出する。
論文 参考訳（メタデータ） (2022-11-17T18:51:32Z) - Graph Spectral Embedding using the Geodesic Betweeness Centrality [76.27138343125985]
本稿では、局所的な類似性、接続性、グローバル構造を教師なしで表現するグラフSylvester Embedding (GSE)を紹介する。
GSEはシルヴェスター方程式の解を用いて、ネットワーク構造と近傍の近接を1つの表現で捉える。
論文 参考訳（メタデータ） (2022-05-07T04:11:23Z) - Fast Computation of Generalized Eigenvectors for Manifold Graph
Embedding [38.902986549367434]
我々は、高速実行に既存の高速極端固有ベクトル計算アルゴリズムを利用する。
我々の埋め込みは文献の中では最速であり、多様体グラフのクラスタリング性能は最高のものとなっている。
論文 参考訳（メタデータ） (2021-12-15T03:45:39Z) - Dist2Cycle: A Simplicial Neural Network for Homology Localization [66.15805004725809]
単純複体は多方向順序関係を明示的にエンコードするグラフの高次元一般化と見なすことができる。
単体錯体の$k$-homological特徴によってパラメータ化された関数のグラフ畳み込みモデルを提案する。
論文 参考訳（メタデータ） (2021-10-28T14:59:41Z) - Learning Sparse Graph Laplacian with K Eigenvector Prior via Iterative
GLASSO and Projection [58.5350491065936]
グラフ Laplacian 行列 $L$ 上の構造的仮定を考える。
最初の$K$ eigenvectors of $L$は、例えばドメイン固有の基準に基づいて事前選択される。
本稿では,H_u+$$$$barC$で最も適切なグラフラプラシアン行列$L*を計算するために,効率的なハイブリッドグラフラッソ/投影アルゴリズムを設計する。
論文 参考訳（メタデータ） (2020-10-25T18:12:50Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。