論文の概要: Sparsification of the regularized magnetic Laplacian with multi-type spanning forests
- arxiv url: http://arxiv.org/abs/2208.14797v2
- Date: Wed, 20 Mar 2024 09:44:53 GMT
- ステータス: 処理完了
- システム内更新日: 2024-03-21 23:26:53.503723
- Title: Sparsification of the regularized magnetic Laplacian with multi-type spanning forests
- Title（参考訳）: 多型スパンニング林による磁化ラプラシアンのスカラー化
- Authors: Michaël Fanuel, Rémi Bardenet,
- Abstract要約: 磁気ラプラシアン$Delta$,すなわち,エッジの少ない部分グラフに基づくスペクトル近似のスペーサーについて検討する。
ラプラシアン接続の自然推定器の選択に関する統計的保証を提供する。
本稿では,角度同期型ランキングとグラフに基づく半教師付き学習の2つの実用的応用について検討する。
- 参考スコア（独自算出の注目度）: 8.30255326875704
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper, we consider a ${\rm U}(1)$-connection graph, that is, a graph where each oriented edge is endowed with a unit modulus complex number that is conjugated under orientation flip. A natural replacement for the combinatorial Laplacian is then the magnetic Laplacian, an Hermitian matrix that includes information about the graph's connection. Magnetic Laplacians appear, e.g., in the problem of angular synchronization. In the context of large and dense graphs, we study here sparsifiers of the magnetic Laplacian $\Delta$, i.e., spectral approximations based on subgraphs with few edges. Our approach relies on sampling multi-type spanning forests (MTSFs) using a custom determinantal point process, a probability distribution over edges that favours diversity. In a word, an MTSF is a spanning subgraph whose connected components are either trees or cycle-rooted trees. The latter partially capture the angular inconsistencies of the connection graph, and thus provide a way to compress the information contained in the connection. Interestingly, when the connection graph has weakly inconsistent cycles, samples from the determinantal point process under consideration can be obtained \`a la Wilson, using a random walk with cycle popping. We provide statistical guarantees for a choice of natural estimators of the connection Laplacian, and investigate two practical applications of our sparsifiers: ranking with angular synchronization and graph-based semi-supervised learning. From a statistical perspective, a side result of this paper of independent interest is a matrix Chernoff bound with intrinsic dimension, which allows considering the influence of a regularization -- of the form $\Delta + q \mathbb{I}$ with $q>0$ -- on sparsification guarantees.
- Abstract（参考訳）: 本稿では,向きの反転の下で共役する単位モジュラー複素数を持つグラフとして,${\rm U}(1)$-connection graphを考える。
組合せラプラシアンの自然な置換は、グラフの接続に関する情報を含むエルミート行列である磁気ラプラシアンである。
磁気ラプラシアン(英語版)は角同期の問題に現れる。
大規模で高密度なグラフの文脈では、磁気ラプラシアン$\Delta$、すなわち、エッジの少ない部分グラフに基づくスペクトル近似のスペーサーについて研究する。
提案手法は, 多様性を優先するエッジ上の確率分布である, カスタム決定点プロセスを用いて, MTSF(Multi-type spanning forests)をサンプリングすることに依存する。
一言で言えば、MTSFは、接続されたコンポーネントが木またはサイクルルート木のいずれかであるスパンニング部分グラフである。
後者は接続グラフの角不整合を部分的に捉え、接続に含まれる情報を圧縮する方法を提供する。
興味深いことに、接続グラフが不整合なサイクルを持つ場合、決定点プロセスから検討中のサンプルは、サイクルのポップアップを伴うランダムウォークを用いて、‘a la Wilson’が得られる。
ラプラシアン接続の自然推定器の選択に関する統計的保証を提供し、このスペーサーの2つの実用的応用として、角同期によるランク付けとグラフに基づく半教師付き学習について検討する。
統計学的見地からすると、この論文の副作用は、内在次元で有界なチェルノフ行列であり、これは正規化の -- $\Delta + q \mathbb{I}$ with $q>0$ -- がスパース化保証に与える影響を考えることができる。
関連論文リスト
- Efficient Learning of Balanced Signed Graphs via Iterative Linear Programming [26.334739062500674]
データから直接バランスの取れたラプラシアングラフを学習する高速な手法を提案する。
合成および実世界のデータセットに対する実験により、バランスの取れたグラフ学習法が競合する手法より優れていることが示された。
論文 参考訳（メタデータ） (2024-09-12T06:53:50Z) - Graph Generation via Spectral Diffusion [51.60814773299899]
本稿では,1)グラフラプラシア行列のスペクトル分解と2)拡散過程に基づく新しいグラフ生成モデルGRASPを提案する。
具体的には、固有ベクトルと固有値のサンプリングにデノナイジングモデルを用い、グラフラプラシアン行列と隣接行列を再構成する。
我々の置換不変モデルは各ノードの固有ベクトルに連結することでノードの特徴を扱える。
論文 参考訳（メタデータ） (2024-02-29T09:26:46Z) - Information-Theoretic Thresholds for Planted Dense Cycles [52.076657911275525]
本研究では,社会科学や生物科学においてユビキタスな小世界ネットワークのランダムグラフモデルについて検討する。
植え込み高密度サイクルの検出と回復の両面において、情報理論の閾値を$n$, $tau$、エッジワイド信号対雑音比$lambda$で特徴づける。
論文 参考訳（メタデータ） (2024-02-01T03:39:01Z) - Graph Fourier MMD for Signals on Graphs [67.68356461123219]
本稿では,グラフ上の分布と信号の間の新しい距離を提案する。
GFMMDは、グラフ上で滑らかであり、期待差を最大化する最適な目撃関数によって定義される。
グラフベンチマークのデータセットと単一セルRNAシークエンシングデータ解析について紹介する。
論文 参考訳（メタデータ） (2023-06-05T00:01:17Z) - 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) - Learning Sparse Graph with Minimax Concave Penalty under Gaussian Markov
Random Fields [51.07460861448716]
本稿では,データから学ぶための凸解析フレームワークを提案する。
三角凸分解はその上部に対応する変換によって保証されることを示す。
論文 参考訳（メタデータ） (2021-09-17T17:46:12Z) - Large sample spectral analysis of graph-based multi-manifold clustering [3.383942690870476]
マルチマニフォールドクラスタリング(MMC)のためのグラフベースアルゴリズムの統計的性質について検討する。
MMC の目標は、与えられたユークリッドデータセットの根底にある多重多様体構造を取得することである。
我々は、角度制約付き環状近接グラフと呼ばれる類似性グラフの族を例に挙げる。
論文 参考訳（メタデータ） (2021-07-28T19:39:12Z) - Testing correlation of unlabeled random graphs [18.08210501570919]
ラベルなしノードを持つ2つのランダムグラフ間のエッジ相関を検出する問題について検討する。
これは仮説テスト問題として定式化され、ヌル仮説の下では、2つのグラフは独立に生成される。
代替として、2つのグラフは、ある潜在ノード対応の下ではエッジ関連であるが、ヌルと同じ辺分布を持つ。
論文 参考訳（メタデータ） (2020-08-23T19:19:45Z) - Lipschitz regularity of graph Laplacians on random data clouds [1.2891210250935146]
グラフポアソン方程式の解に対する高確率内部および大域リプシッツ推定を証明した。
我々の結果は、グラフラプラシア固有ベクトルが、高い確率で、本質的には、対応する固有値に明示的に依存する定数を持つリプシッツ正則であることが示せる。
論文 参考訳（メタデータ） (2020-07-13T20:43:19Z) - Block-Approximated Exponential Random Graphs [77.4792558024487]
指数乱グラフ(ERG)の分野における重要な課題は、大きなグラフ上の非自明なERGの適合である。
本稿では,非自明なERGに対する近似フレームワークを提案する。
我々の手法は、数百万のノードからなるスパースグラフにスケーラブルである。
論文 参考訳（メタデータ） (2020-02-14T11:42:16Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。