論文の概要: A Thorough View of Exact Inference in Graphs from the Degree-4
Sum-of-Squares Hierarchy
- arxiv url: http://arxiv.org/abs/2102.08019v1
- Date: Tue, 16 Feb 2021 08:36:19 GMT
- ステータス: 処理完了
- システム内更新日: 2021-02-17 15:22:25.311437
- Title: A Thorough View of Exact Inference in Graphs from the Degree-4
Sum-of-Squares Hierarchy
- Title（参考訳）: Degree-4の正方形階層からのグラフの厳密な推測
- Authors: Kevin Bello, Chuyang Ke and Jean Honorio
- Abstract要約: 各エッジの1つの破損した観測からノードの未知の接地型バイナリラベリングを正確に回収する問題に取り組む。
この問題に対して、和の平方階層と呼ばれるリラクゼーションの階層を適用します。
我々は、緩和問題の双対の解がジョンソングラフとクネーサーグラフのエッジウェイトを見つけることに関連していることを示した。
- 参考スコア（独自算出の注目度）: 37.34153902687548
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Performing inference in graphs is a common task within several machine
learning problems, e.g., image segmentation, community detection, among others.
For a given undirected connected graph, we tackle the statistical problem of
exactly recovering an unknown ground-truth binary labeling of the nodes from a
single corrupted observation of each edge. Such problem can be formulated as a
quadratic combinatorial optimization problem over the boolean hypercube, where
it has been shown before that one can (with high probability and in polynomial
time) exactly recover the ground-truth labeling of graphs that have an
isoperimetric number that grows with respect to the number of nodes (e.g.,
complete graphs, regular expanders). In this work, we apply a powerful
hierarchy of relaxations, known as the sum-of-squares (SoS) hierarchy, to the
combinatorial problem. Motivated by empirical evidence on the improvement in
exact recoverability, we center our attention on the degree-4 SoS relaxation
and set out to understand the origin of such improvement from a graph
theoretical perspective. We show that the solution of the dual of the relaxed
problem is related to finding edge weights of the Johnson and Kneser graphs,
where the weights fulfill the SoS constraints and intuitively allow the input
graph to increase its algebraic connectivity. Finally, as byproduct of our
analysis, we derive a novel Cheeger-type lower bound for the algebraic
connectivity of graphs with signed edge weights.
- Abstract（参考訳）: グラフにおける推論の実行は、イメージセグメンテーションやコミュニティ検出など、いくつかの機械学習問題において一般的なタスクである。
与えられた非有向連結グラフに対して、各辺の1つの破損した観測からノードの未知の接地対数ラベルを正確に復元する統計的問題に取り組む。
このような問題はブールハイパーキューブ上の二次組合せ最適化問題として定式化することができ、そこではノード数(例えば、完全グラフ、正規拡大器)に関して増大する等尺数を持つグラフの基底トラストラベルを(高い確率と多項式時間で)正確に復元することができることが以前に示されている。
本研究では,Summit-of-quares(SoS)階層と呼ばれるリラクゼーションの強力な階層を組合せ問題に適用する。
精度回復性の向上に関する実証的証拠に動機付けられ,我々は次数4のSoS緩和に注意を集中させ,その起源をグラフ理論の観点から理解しようとした。
緩和された問題の双対解はジョンソングラフとクネーサーグラフの辺重みを求めることに関係しており、そこでは重みがSoSの制約を満たし、入力グラフが代数的接続性を高めることを直感的に許容する。
最後に、我々の分析の副産物として、符号付き辺重みを持つグラフの代数的接続に対するチェーガー型下界を新たに導き出す。
関連論文リスト
- Contrastive Graph Clustering in Curvature Spaces [74.03252813800334]
本研究では,CONGREGATE という新しいグラフクラスタリングモデルを提案する。
幾何学的クラスタリングを支援するため、理論的に基底とした不均一曲率空間を構築した。
次に、拡張不要な再重み付きコントラスト的アプローチでグラフクラスタをトレーニングする。
論文 参考訳（メタデータ） (2023-05-05T14:04:52Z) - Gradient scarcity with Bilevel Optimization for Graph Learning [0.0]
勾配不足は、ノードのサブセットの損失を最小限にすることでグラフを学習する際に発生する。
我々は、この現象の正確な数学的特徴を与え、双レベル最適化にも現れることを証明した。
この問題を緩和するために,グラフ・ツー・グラフモデル(G2G)を用いた潜時グラフ学習,グラフに先行構造を課すグラフ正規化,あるいは直径を縮小した元のグラフよりも大きなグラフを最適化することを提案する。
論文 参考訳（メタデータ） (2023-03-24T12:37:43Z) - Matching Correlated Inhomogeneous Random Graphs using the $k$-core
Estimator [5.685589351789462]
我々は、両グラフの大きな共通部分グラフを誘導する対応を出力するいわゆるemph$k$-core推定器について検討する。
相関ブロックモデル,Chung-Lu幾何グラフ,および相関ランダムグラフの精度と部分的回復に関する新たな結果を導出するために,我々の一般的な枠組みを専門化している。
論文 参考訳（メタデータ） (2023-02-10T18:21:35Z) - Joint graph learning from Gaussian observations in the presence of
hidden nodes [26.133725549667734]
本稿では,隠れ変数の存在を考慮した共同グラフ学習法を提案する。
従来の考察から得られた構造を利用して凸最適化問題を提案する。
提案したアルゴリズムを異なるベースラインで比較し、合成グラフと実世界のグラフ上での性能を評価する。
論文 参考訳（メタデータ） (2022-12-04T13:03:41Z) - Learning Graphs from Smooth Signals under Moment Uncertainty [23.868075779606425]
与えられたグラフ信号の集合からグラフ構造を推測する問題を検討する。
従来のグラフ学習モデルは、この分布の不確実性を考慮していない。
論文 参考訳（メタデータ） (2021-05-12T06:47:34Z) - Multilayer Clustered Graph Learning [66.94201299553336]
我々は、観測された層を代表グラフに適切に集約するために、データ忠実度用語として対照的な損失を用いる。
実験により,本手法がクラスタクラスタw.r.tに繋がることが示された。
クラスタリング問題を解くためのクラスタリングアルゴリズムを学習する。
論文 参考訳（メタデータ） (2020-10-29T09:58:02Z) - Hamiltonian systems, Toda lattices, Solitons, Lax Pairs on weighted
Z-graded graphs [62.997667081978825]
グラフ上の解に対して一次元の解を持ち上げることができる条件を特定する。
位相的に興味深いグラフの簡単な例であっても、対応する非自明なラックス対と関連するユニタリ変換は、Z階数グラフ上のラックス対に持ち上げないことを示す。
論文 参考訳（メタデータ） (2020-08-11T17:58:13Z) - Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
我々は高密度サブグラフ発見のための新しい学習問題を導入する。
まず,確率の高いほぼ最適解を求めるエッジ時間アルゴリズムを提案する。
そして、理論的保証のあるよりスケーラブルなアルゴリズムを設計する。
論文 参考訳（メタデータ） (2020-06-24T11:37:33Z) - Wasserstein-based Graph Alignment [56.84964475441094]
我々は,より小さいグラフのノードと大きなグラフのノードをマッチングすることを目的とした,1対多のグラフアライメント問題に対する新しい定式化を行った。
提案手法は,各タスクに対する最先端のアルゴリズムに対して,大幅な改善をもたらすことを示す。
論文 参考訳（メタデータ） (2020-03-12T22:31:59Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。