論文の概要: A Polyhedral Study of Lifted Multicuts

• arxiv url: http://arxiv.org/abs/2202.08068v1
• Date: Wed, 16 Feb 2022 13:50:39 GMT
• ステータス: 処理完了
• システム内更新日: 2022-02-17 16:18:00.405025
• Title: A Polyhedral Study of Lifted Multicuts
• Title（参考訳）: リフト型マルチカットの多面体解析
• Authors: Bjoern Andres, Silvia Di Gregorio, Jannik Irmai, Jan-Hendrik Lange
• Abstract要約: グラフ $G = (V, E)$ から拡張グラフ $hat G = (V, E cup F)$ へのマルチカットの持ち上げは、画像解析の分野で提案されている。 我々は、$mathbbRE cup F$ のポリトープを詳細に研究し、その頂点は正確に$G$ から $hat G$ のマルチカットの特徴的なベクトルである。
• 参考スコア（独自算出の注目度）: 11.282130587928384
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Fundamental to many applications in data analysis are the decompositions of a graph, i.e. partitions of the node set into component-inducing subsets. One way of encoding decompositions is by multicuts, the subsets of those edges that straddle distinct components. Recently, a lifting of multicuts from a graph $G = (V, E)$ to an augmented graph $\hat G = (V, E \cup F)$ has been proposed in the field of image analysis, with the goal of obtaining a more expressive characterization of graph decompositions in which it is made explicit also for pairs $F \subseteq \tbinom{V}{2} \setminus E$ of non-neighboring nodes whether these are in the same or distinct components. In this work, we study in detail the polytope in $\mathbb{R}^{E \cup F}$ whose vertices are precisely the characteristic vectors of multicuts of $\hat G$ lifted from $G$, connecting it, in particular, to the rich body of prior work on the clique partitioning and multilinear polytope.
• Abstract（参考訳）: データ分析における多くの応用の基礎は、グラフの分解、すなわち、ノードセットをコンポーネント誘導サブセットに分割することである。 分解を符号化する1つの方法は、異なるコンポーネントにまたがるエッジのサブセットであるマルチカットである。 最近では、グラフ $G = (V, E)$ から拡張グラフ $\hat G = (V, E \cup F)$ への多重カットの持ち上げが、画像解析の分野で提案されており、グラフ分解のより表現力豊かな特徴づけを得るために、ペアに対して$F \subseteq \tbinom{V}{2} \setminus E$ は、それらが同じまたは異なる成分であるかどうかに関わらず、非隣ノードに対して明示される。 本研究では,その頂点が正確には$g$ から持ち上げられた$\hat g$ の多重カットの標数ベクトルである$\mathbb{r}^{e \cup f}$ のポリトープについて詳細に研究し,特に,クランク分割と多重線形ポリトープに関する先行研究の豊富な体系と接続する。

関連論文リスト

• Neural network learns low-dimensional polynomials with SGD near the information-theoretic limit [75.4661041626338]
  単一インデックス対象関数 $f_*(boldsymbolx) = textstylesigma_*left(langleboldsymbolx,boldsymbolthetarangleright)$ の等方的ガウスデータの下で勾配降下学習の問題を考察する。 SGDアルゴリズムで最適化された2層ニューラルネットワークは、サンプル付き任意のリンク関数の$f_*$を学習し、実行時の複雑さは$n asymp T asymp C(q) cdot dであることを示す。
  論文  参考訳（メタデータ） (2024-06-03T17:56:58Z)
• Spectral clustering in the Gaussian mixture block model [2.668787455520979]
  本研究では,高次元ガウス混合ブロックモデルから得られたクラスタリングと埋め込みグラフについて検討する。 このようなグラフに対する標準スペクトルクラスタリングと埋め込みアルゴリズムの性能を解析する。
  論文  参考訳（メタデータ） (2023-04-29T23:56:55Z)
• Near-optimal fitting of ellipsoids to random points [68.12685213894112]
  楕円体をランダムな点に合わせるという基本的な問題は、低ランク行列分解、独立成分分析、主成分分析に関係している。 我々はこの予想を、ある$n = Omega(, d2/mathrmpolylog(d))$ に対する適合楕円体を構成することで対数的因子まで解決する。 我々の証明は、ある非標準確率行列の便利な分解を用いて、サンダーソン等最小二乗構成の実現可能性を示す。
  論文  参考訳（メタデータ） (2022-08-19T18:00:34Z)
• Graph Spectral Embedding using the Geodesic Betweeness Centrality [76.27138343125985]
  本稿では、局所的な類似性、接続性、グローバル構造を教師なしで表現するグラフSylvester Embedding (GSE)を紹介する。 GSEはシルヴェスター方程式の解を用いて、ネットワーク構造と近傍の近接を1つの表現で捉える。
  論文  参考訳（メタデータ） (2022-05-07T04:11:23Z)
• Effects of Graph Convolutions in Deep Networks [8.937905773981702]
  多層ネットワークにおけるグラフ畳み込みの効果に関する厳密な理論的理解を示す。 単一のグラフ畳み込みは、多層ネットワークがデータを分類できる手段間の距離のレギュレーションを拡大することを示す。 ネットワーク層間の異なる組み合わせに配置されたグラフ畳み込みの性能に関する理論的および実証的な知見を提供する。
  論文  参考訳（メタデータ） (2022-04-20T08:24:43Z)
• Spectral embedding and the latent geometry of multipartite networks [67.56499794542228]
  多くのネットワークはマルチパーティションであり、ノードはパーティションに分割され、同じパーティションのノードは接続されない。 本稿では,高次元空間の分割特異的な低次元部分空間近傍のスペクトル埋め込みにより得られるノード表現について述べる。 スペクトル埋め込み後の追従ステップとして,周辺次元ではなく固有次元のノード表現を復元する手法を提案する。
  論文  参考訳（メタデータ） (2022-02-08T15:52:03Z)
• Fast Computation of Generalized Eigenvectors for Manifold Graph Embedding [38.902986549367434]
  我々は、高速実行に既存の高速極端固有ベクトル計算アルゴリズムを利用する。 我々の埋め込みは文献の中では最速であり、多様体グラフのクラスタリング性能は最高のものとなっている。
  論文  参考訳（メタデータ） (2021-12-15T03:45:39Z)
• Fast Graph Sampling for Short Video Summarization using Gershgorin Disc Alignment [52.577757919003844]
  高速グラフサンプリングの最近の進歩を利用して,短い動画を複数の段落に効率よく要約する問題について検討する。 実験結果から,本アルゴリズムは最先端の手法と同等の映像要約を実現し,複雑さを大幅に低減した。
  論文  参考訳（メタデータ） (2021-10-21T18:43:00Z)
• Correlation detection in trees for partial graph alignment [3.5880535198436156]
  グラフのアライメントは,エッジの大部分を保存する2つのグラフのノード間のマッピングを探索する。 我々のアプローチは、2つのグラフの局所構造を比較し、その近傍が相関グラフに対して「十分近い」場合、2つのノードをマッチングすることである。 この問題は、一対の分岐木が積分布または相関分布から引き出されるかどうかの検定の観点から説明できる。
  論文  参考訳（メタデータ） (2021-07-15T22:02:27Z)
• A deep network construction that adapts to intrinsic dimensionality beyond the domain [79.23797234241471]
  本稿では,ReLUを活性化したディープネットワークを用いて,2層合成の近似を$f(x) = g(phi(x))$で検討する。 例えば、低次元埋め込み部分多様体への射影と、低次元集合の集合への距離である。
  論文  参考訳（メタデータ） (2020-08-06T09:50:29Z)
• Cospectrality preserving graph modifications and eigenvector properties via walk equivalence of vertices [0.0]
  コスペクトル性は交換対称性の強力な一般化であり、すべての実数値対称行列に適用できる。 余スペクトル頂点を持つ行列のパワーは固有ベクトルのさらなる局所的関係を誘導することを示す。 我々の研究は、汎用的な複雑なネットワークのようなシステムの設計において、隠れた構造対称性を柔軟に活用する方法を開拓する。
  論文  参考訳（メタデータ） (2020-07-15T10:54:31Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。