論文の概要: Cheeger Inequalities for Directed Graphs and Hypergraphs Using
Reweighted Eigenvalues
- arxiv url: http://arxiv.org/abs/2211.09776v1
- Date: Thu, 17 Nov 2022 18:51:32 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-18 17:35:31.019428
- Title: Cheeger Inequalities for Directed Graphs and Hypergraphs Using
Reweighted Eigenvalues
- Title（参考訳）: 重み付き固有値を用いたグラフとハイパーグラフのチーガー不等式
- Authors: Lap Chi Lau, Kam Chuen Tung, Robert Wang
- Abstract要約: 我々は、有向グラフのための新しいスペクトル理論と、ハイパーグラフのための代替スペクトル理論を開発する。
我々は、重み付けされた固有値アプローチを用いて、有向グラフとハイパーグラフに対するチェーガーの不等式を導出する。
- 参考スコア（独自算出の注目度）: 6.094384342913063
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We derive Cheeger inequalities for directed graphs and hypergraphs using the
reweighted eigenvalue approach that was recently developed for vertex expansion
in undirected graphs [OZ22,KLT22,JPV22]. The goal is to develop a new spectral
theory for directed graphs and an alternative spectral theory for hypergraphs.
The first main result is a Cheeger inequality relating the vertex expansion
$\vec{\psi}(G)$ of a directed graph $G$ to the vertex-capacitated maximum
reweighted second eigenvalue $\vec{\lambda}_2^{v*}$: \[ \vec{\lambda}_2^{v*}
\lesssim \vec{\psi}(G) \lesssim \sqrt{\vec{\lambda}_2^{v*} \cdot \log
(\Delta/\vec{\lambda}_2^{v*})}. \] This provides a combinatorial
characterization of the fastest mixing time of a directed graph by vertex
expansion, and builds a new connection between reweighted eigenvalued, vertex
expansion, and fastest mixing time for directed graphs.
The second main result is a stronger Cheeger inequality relating the edge
conductance $\vec{\phi}(G)$ of a directed graph $G$ to the edge-capacitated
maximum reweighted second eigenvalue $\vec{\lambda}_2^{e*}$: \[
\vec{\lambda}_2^{e*} \lesssim \vec{\phi}(G) \lesssim \sqrt{\vec{\lambda}_2^{e*}
\cdot \log (1/\vec{\lambda}_2^{e*})}. \] This provides a certificate for a
directed graph to be an expander and a spectral algorithm to find a sparse cut
in a directed graph, playing a similar role as Cheeger's inequality in
certifying graph expansion and in the spectral partitioning algorithm for
undirected graphs.
We also use this reweighted eigenvalue approach to derive the improved
Cheeger inequality for directed graphs, and furthermore to derive several
Cheeger inequalities for hypergraphs that match and improve the existing
results in [Lou15,CLTZ18]. These are supporting results that this provides a
unifying approach to lift the spectral theory for undirected graphs to more
general settings.
- Abstract（参考訳）: 有向グラフとハイパーグラフのチーガー不等式を,最近,非有向グラフの頂点展開のために開発された再重み付け固有値法(oz22,klt22,jpv22])を用いて導出する。
目的は、有向グラフの新しいスペクトル理論とハイパーグラフの代替スペクトル理論を開発することである。
最初の結果は、頂点拡大に関するチーガーの不等式である: $\vec{\psi}(G)$ of a directed graph $G$ to the vertex-capacitated maximum reweighted second eigen value $\vec{\lambda}_2^{v*}$: \[ \vec{\lambda}_2^{v*} \lesssim \vec{\psi}(G) \lesssim \sqrt{\vec{\lambda}_2^{v*} \cdot \log (\Delta/\vec{\lambda}_2^{v*})}。
これは、有向グラフの頂点展開による最速混合時間の組合せ的特徴を提供し、有向グラフに対する再重み付き固有値、頂点展開、および最速混合時間の間の新たな接続を構築する。
第二の主な結果は、有向グラフのエッジコンダクタンス $\vec{\phi}(g)$ を、エッジ容量の最大再重み付き第二の固有値 $\vec{\lambda}_2^{e*}$: \[ \vec{\lambda}_2^{e*} \lesssim \vec{\phi}(g) \lesssim \sqrt{\vec{\lambda}_2^{e*} \cdot \log (1/\vec{\lambda}_2^{e*})} に関連付けるより強いチーガーの不等式である。
これは、有向グラフを展開する有向グラフの証明書と、有向グラフでスパースカットを見つけるスペクトルアルゴリズムを提供し、グラフ展開の証明と非有向グラフのスペクトル分割アルゴリズムにおいてチーガーの不等式と同様の役割を果たす。
さらに, [lou15,cltz18] における既存の結果にマッチし改善するハイパーグラフに対するいくつかのチーガー不等式を導出するために, この再重み付け固有値法を用いて, 有向グラフに対するチーガー不等式の改良を導出する。
これらの結果は、無向グラフのスペクトル理論をより一般的な設定へ持ち上げるための統一的なアプローチを提供する。
関連論文リスト
- Graph Generation via Spectral Diffusion [51.60814773299899]
本稿では,1)グラフラプラシア行列のスペクトル分解と2)拡散過程に基づく新しいグラフ生成モデルGRASPを提案する。
具体的には、固有ベクトルと固有値のサンプリングにデノナイジングモデルを用い、グラフラプラシアン行列と隣接行列を再構成する。
我々の置換不変モデルは各ノードの固有ベクトルに連結することでノードの特徴を扱える。
論文 参考訳（メタデータ） (2024-02-29T09:26:46Z) - Efficient Signed Graph Sampling via Balancing & Gershgorin Disc Perfect
Alignment [51.74913666829224]
強い反相関を持つデータセットに対して、適切なグラフは正および負のエッジ重みの両方を含むことを示す。
本稿では,平衡符号グラフの概念に着目した線形時間符号グラフサンプリング手法を提案する。
実験結果から, 署名付きグラフサンプリング手法は, 各種データセットにおいて, 既存の高速サンプリング方式よりも優れた性能を示した。
論文 参考訳（メタデータ） (2022-08-18T09:19:01Z) - Bi-stochastically normalized graph Laplacian: convergence to manifold Laplacian and robustness to outlier noise [10.418647759223965]
双確率正規化 (bi-stochastic normalization) はグラフベースのデータ解析においてグラフラプラシアンの代替正規化を提供する。
両階層正規化グラフ Laplacian から (重み付き) Laplacian への収束を速度で証明する。
多様体データが外乱ノイズによって破損した場合、理論的にはラプラシア点の整合性を証明する。
論文 参考訳（メタデータ） (2022-06-22T21:08:24Z) - Matching recovery threshold for correlated random graphs [9.12788494573002]
共通 ErdHos-R'enyi グラフ $mathbfG(n, p)$ から独立にサブサンプリングされた2つの相関グラフに対して、これらの2つのグラフのアンフィグアウトラベルの観測からそれらのエンフィラテントマッチングを回復したい。
この結果は,近年のWu,Xu,Yuによる研究において一定の要因を導出する。
論文 参考訳（メタデータ） (2022-05-29T13:04:20Z) - Fast Computation of Generalized Eigenvectors for Manifold Graph
Embedding [38.902986549367434]
我々は、高速実行に既存の高速極端固有ベクトル計算アルゴリズムを利用する。
我々の埋め込みは文献の中では最速であり、多様体グラフのクラスタリング性能は最高のものとなっている。
論文 参考訳（メタデータ） (2021-12-15T03:45:39Z) - AnchorGAE: General Data Clustering via $O(n)$ Bipartite Graph
Convolution [79.44066256794187]
我々は、グラフ畳み込みネットワーク(GCN)を構築するために使用される生成グラフモデルを導入することにより、グラフに非グラフデータセットを変換する方法を示す。
アンカーによって構築された二部グラフは、データの背後にある高レベル情報を利用するために動的に更新される。
理論的には、単純な更新が退化につながることを証明し、それに従って特定の戦略が設計される。
論文 参考訳（メタデータ） (2021-11-12T07:08:13Z) - Fast Graph Sampling for Short Video Summarization using Gershgorin Disc
Alignment [52.577757919003844]
高速グラフサンプリングの最近の進歩を利用して,短い動画を複数の段落に効率よく要約する問題について検討する。
実験結果から,本アルゴリズムは最先端の手法と同等の映像要約を実現し,複雑さを大幅に低減した。
論文 参考訳（メタデータ） (2021-10-21T18:43:00Z) - Settling the Sharp Reconstruction Thresholds of Random Graph Matching [19.54246087326288]
2つのエッジ関連ランダムグラフ間の隠れた対応を復元する問題について検討する。
p=n-o(1)$のグラフに対して、鋭いしきい値が存在することが証明される。
sparse ErdHos-R'enyi graphs with $p=n-Theta(1)$ に対して、オール・オー・ナッシング現象はもはや成り立たないことを示す。
論文 参考訳（メタデータ） (2021-01-29T21:49:50Z) - Random Graph Matching with Improved Noise Robustness [2.294014185517203]
本稿では確率モデルに基づくグラフマッチングの新しいアルゴリズムを提案する。
我々のアルゴリズムは、$alpha le 1 / (log log n)C$ のとき、その基礎となるマッチングを高い確率で復元する。
これにより、以前の作業で達成された条件 $alpha le 1 / (log n)C$ が改善される。
論文 参考訳（メタデータ） (2021-01-28T02:39:27Z) - Adversarial Linear Contextual Bandits with Graph-Structured Side
Observations [80.95090605985042]
学習エージェントは、$d$-dimensionalコンテキストベクトルで提示された後、一連の$k$アクションから繰り返し選択する。
エージェントは選択されたアクションの損失を誘発し、観察するが、観察構造における隣り合うアクションの損失も観察する。
textttEXP3に基づく2つの効率的なアルゴリズムが開発された。
論文 参考訳（メタデータ） (2020-12-10T15:40:07Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。