論文の概要: Sparsification of the regularized magnetic Laplacian with multi-type
spanning forests
- arxiv url: http://arxiv.org/abs/2208.14797v1
- Date: Wed, 31 Aug 2022 12:23:53 GMT
- ステータス: 処理完了
- システム内更新日: 2022-09-01 13:16:14.363897
- Title: Sparsification of the regularized magnetic Laplacian with multi-type
spanning forests
- Title(参考訳): 多型スパンニング林による磁化ラプラシアンのスカラー化
- Authors: Micha\"el Fanuel and R\'emi Bardenet
- Abstract要約: 磁気ラプラシアンのスペーサー、すなわち、エッジが少ない部分グラフに基づくスペクトル近似について検討する。
一言で言えば、MTSFは、接続されたコンポーネントが木またはサイクルルート木のいずれかであるスパンニング部分グラフである。
- 参考スコア(独自算出の注目度): 0.0
- 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 which is
simply conjugated under orientation flip. A natural replacement for the
combinatorial Laplacian is then the so-called magnetic Laplacian, an Hermitian
matrix that includes information about the graph's connection. Connection
graphs and 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, 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 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 information contained in the connection.
Interestingly, when this connection graph has weakly inconsistent cycles,
samples of this distribution can be obtained by using a random walk with cycle
popping. We provide statistical guarantees for a choice of natural estimators
of the connection Laplacian, and investigate the practical application of our
sparsifiers in two applications.
- Abstract(参考訳): 本稿では,各向きのエッジに,単純に向きのフリップの下で共役する単位モジュラー複素数を与えるグラフについて,${\rm U}(1)$-connection graphを考える。
組合せラプラシアンの自然な置換は、グラフの接続に関する情報を含むエルミート行列と呼ばれる磁気ラプラシアンのものである。
例えば角同期問題において、接続グラフと磁気ラプラシアンが現れる。
大規模で密度の高いグラフの文脈では、磁気ラプラシアンのスペーサー、すなわち、エッジの少ない部分グラフに基づくスペクトル近似について研究する。
提案手法は,多種間伐採林(MTSF)を,多様性を優先するエッジ上の分布であるカスタム決定点プロセスを用いてサンプリングすることに依存する。
言い換えると、mtsfは、連結されたコンポーネントが木またはサイクルルート木のいずれかであるスパンディングサブグラフである。
後者は接続グラフの角の不一致を部分的に捉え、接続に含まれる情報を圧縮する方法を提供する。
興味深いことに、この連結グラフが不整合なサイクルを持つ場合、この分布のサンプルはランダムウォークとサイクルポップアップを用いて得られる。
ラプラシアン接続の自然推定器の選択に関する統計的保証を提供し、2つの応用におけるスペーサーの実践的応用について検討する。
関連論文リスト
- On the Equivalence of Graph Convolution and Mixup [71.8932383179048]
本稿では,グラフ畳み込みと混合手法の関係について検討する。
2つの穏やかな条件の下では、グラフの畳み込みはMixupの特別な形式と見なすことができる。
グラフ畳み込みネットワーク(GCN)と単純化グラフ畳み込み(SGC)をミックスアップの形で表現できることを証明し、数学的にこの等価性を確立する。
論文 参考訳(メタデータ) (2023-09-29T23:09:54Z) - Graph Fourier MMD for Signals on Graphs [67.68356461123219]
本稿では,グラフ上の分布と信号の間の新しい距離を提案する。
GFMMDは、グラフ上で滑らかであり、期待差を最大化する最適な目撃関数によって定義される。
グラフベンチマークのデータセットと単一セルRNAシークエンシングデータ解析について紹介する。
論文 参考訳(メタデータ) (2023-06-05T00:01:17Z) - You Only Transfer What You Share: Intersection-Induced Graph Transfer
Learning for Link Prediction [79.15394378571132]
従来見過ごされていた現象を調査し、多くの場合、元のグラフに対して密に連結された補グラフを見つけることができる。
より密度の高いグラフは、選択的で有意義な知識を伝達するための自然なブリッジを提供する元のグラフとノードを共有することができる。
この設定をグラフインターセクション誘導トランスファーラーニング(GITL)とみなし,eコマースや学術共同オーサシップ予測の実践的応用に動機づけられた。
論文 参考訳(メタデータ) (2023-02-27T22:56:06Z) - 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 [8.271859911016719]
双構造正規化グラフ Laplacian to manifold (weighted-)Laplacian は Sinkhorn-Knopp (SK) の反復によって効率的に計算できる。
多様体データが外乱ノイズによって破壊されるとき、理論的にはラプラシア点の整合性を証明する。
論文 参考訳(メタデータ) (2022-06-22T21:08:24Z) - Large sample spectral analysis of graph-based multi-manifold clustering [3.383942690870476]
マルチマニフォールドクラスタリング(MMC)のためのグラフベースアルゴリズムの統計的性質について検討する。
MMC の目標は、与えられたユークリッドデータセットの根底にある多重多様体構造を取得することである。
我々は、角度制約付き環状近接グラフと呼ばれる類似性グラフの族を例に挙げる。
論文 参考訳(メタデータ) (2021-07-28T19:39:12Z) - A Thorough View of Exact Inference in Graphs from the Degree-4
Sum-of-Squares Hierarchy [37.34153902687548]
各エッジの1つの破損した観測からノードの未知の接地型バイナリラベリングを正確に回収する問題に取り組む。
この問題に対して、和の平方階層と呼ばれるリラクゼーションの階層を適用します。
我々は、緩和問題の双対の解がジョンソングラフとクネーサーグラフのエッジウェイトを見つけることに関連していることを示した。
論文 参考訳(メタデータ) (2021-02-16T08:36:19Z) - Joint Inference of Multiple Graphs from Matrix Polynomials [34.98220454543502]
ノード上の観測からグラフ構造を推定することは重要かつ一般的なネットワーク科学課題である。
ノードの信号の観測から複数のグラフを共同で推定する問題について検討する。
本稿では,真のグラフの回復を保証するための凸最適化手法を提案する。
論文 参考訳(メタデータ) (2020-10-16T02:45:15Z) - Factorizable Graph Convolutional Networks [90.59836684458905]
本稿では,グラフに符号化された相互に絡み合った関係を明示的に解消する新しいグラフ畳み込みネットワーク(GCN)を提案する。
FactorGCNは単純なグラフを入力として取り、それをいくつかの分解グラフに分解する。
提案したFacterGCNは,合成および実世界のデータセットに対して質的かつ定量的に評価する。
論文 参考訳(メタデータ) (2020-10-12T03:01:40Z) - Testing correlation of unlabeled random graphs [18.08210501570919]
ラベルなしノードを持つ2つのランダムグラフ間のエッジ相関を検出する問題について検討する。
これは仮説テスト問題として定式化され、ヌル仮説の下では、2つのグラフは独立に生成される。
代替として、2つのグラフは、ある潜在ノード対応の下ではエッジ関連であるが、ヌルと同じ辺分布を持つ。
論文 参考訳(メタデータ) (2020-08-23T19:19:45Z) - Wasserstein-based Graph Alignment [56.84964475441094]
我々は,より小さいグラフのノードと大きなグラフのノードをマッチングすることを目的とした,1対多のグラフアライメント問題に対する新しい定式化を行った。
提案手法は,各タスクに対する最先端のアルゴリズムに対して,大幅な改善をもたらすことを示す。
論文 参考訳(メタデータ) (2020-03-12T22:31:59Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。