論文の概要: Polynomial-time derivation of optimal k-tree topology from Markov networks
- arxiv url: http://arxiv.org/abs/2404.05991v1
- Date: Tue, 9 Apr 2024 03:52:58 GMT
- ステータス: 処理完了
- システム内更新日: 2024-04-10 15:58:48.236498
- Title: Polynomial-time derivation of optimal k-tree topology from Markov networks
- Title（参考訳）: マルコフネットワークからの最適k-ツリートポロジーの多項式時間導出
- Authors: Fereshteh R. Dastjerdi, Liming Cai,
- Abstract要約: 確率変数の大規模ネットワークに対する結合確率分布のキャラクタリゼーションは、データサイエンスにおいて難しい課題である。
本稿では,k木トポロジーを用いたマルコフネットワークの最適近似について検討する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: Characterization of joint probability distribution for large networks of random variables remains a challenging task in data science. Probabilistic graph approximation with simple topologies has practically been resorted to; typically the tree topology makes joint probability computation much simpler and can be effective for statistical inference on insufficient data. However, to characterize network components where multiple variables cooperate closely to influence others, model topologies beyond a tree are needed, which unfortunately are infeasible to acquire. In particular, our previous work has related optimal approximation of Markov networks of tree-width k >=2 closely to the graph-theoretic problem of finding maximum spanning k-tree (MSkT), which is a provably intractable task. This paper investigates optimal approximation of Markov networks with k-tree topology that retains some designated underlying subgraph. Such a subgraph may encode certain background information that arises in scientific applications, for example, about a known significant pathway in gene networks or the indispensable backbone connectivity in the residue interaction graphs for a biomolecule 3D structure. In particular, it is proved that the \beta-retaining MSkT problem, for a number of classes \beta of graphs, admit O(n^{k+1})-time algorithms for every fixed k>= 1. These \beta-retaining MSkT algorithms offer efficient solutions for approximation of Markov networks with k-tree topology in the situation where certain persistent information needs to be retained.
- Abstract（参考訳）: 確率変数の大規模ネットワークに対する結合確率分布のキャラクタリゼーションは、データサイエンスにおいて難しい課題である。
単純なトポロジによる確率的グラフ近似は、一般的には木のトポロジは共同確率計算をはるかに単純化し、不十分なデータに対する統計的推測に有効である。
しかし、複数の変数が密接に協力して他の変数に影響を与えるネットワークコンポーネントを特徴づけるためには、木以外のモデルトポロジが必要であり、残念ながら取得は不可能である。
特に,本研究では,木幅 k >= 2 のマルコフネットワークの最適近似を,最大スパンニング k-ツリー (MSkT) を求めるグラフ理論問題と密接に関連付ける。
本稿では,k木トポロジーを用いたマルコフネットワークの最適近似について検討する。
このようなサブグラフは、例えば遺伝子ネットワークにおける既知の重要な経路や、生体分子3D構造のための残基相互作用グラフにおける必須のバックボーン接続について、科学的な応用で発生する特定の背景情報を符号化することができる。
特に、グラフの多くのクラス \beta に対する \beta-retaining MSkT 問題は、すべての固定 k>= 1 に対して O(n^{k+1}) 時間アルゴリズムを認めることが証明されている。
これらの<beta-retaining MSkT algorithmは、ある永続的な情報を保持する必要がある状況において、k-treeトポロジーを持つマルコフネットワークを近似するための効率的なソリューションを提供する。
関連論文リスト
- ARTree: A Deep Autoregressive Model for Phylogenetic Inference [6.935130578959931]
グラフニューラルネットワーク(GNN)に基づく系統推定のための深層自己回帰モデルを提案する。
本研究では,本手法の有効性と効率を,実データツリーのトポロジー密度推定と変分系統推定問題のベンチマークで実証する。
論文 参考訳（メタデータ） (2023-10-14T10:26:03Z) - NodeFormer: A Scalable Graph Structure Learning Transformer for Node
Classification [70.51126383984555]
本稿では,任意のノード間のノード信号を効率的に伝搬する全ペアメッセージパッシング方式を提案する。
効率的な計算は、カーナライズされたGumbel-Softmax演算子によって実現される。
グラフ上のノード分類を含む様々なタスクにおいて,本手法の有望な有効性を示す実験を行った。
論文 参考訳（メタデータ） (2023-06-14T09:21:15Z) - Semantic Strengthening of Neuro-Symbolic Learning [85.6195120593625]
ニューロシンボリックアプローチは一般に確率論的目的のファジィ近似を利用する。
トラクタブル回路において,これを効率的に計算する方法を示す。
我々は,Warcraftにおける最小コストパスの予測,最小コスト完全マッチングの予測,スドクパズルの解法という3つの課題に対して,アプローチを検証した。
論文 参考訳（メタデータ） (2023-02-28T00:04:22Z) - Semi-Supervised Clustering of Sparse Graphs: Crossing the
Information-Theoretic Threshold [3.6052935394000234]
ブロックモデルは、ネットワーク構造データのクラスタリングとコミュニティ検出のための標準ランダムグラフモデルである。
ネットワークトポロジに基づく推定器は、モデルパラメータが一定の閾値以下である場合、スパースグラフの確率よりも大幅に向上する。
パラメータ領域全体でラベルの任意の部分で実現可能であることを示す。
論文 参考訳（メタデータ） (2022-05-24T00:03:25Z) - Dist2Cycle: A Simplicial Neural Network for Homology Localization [66.15805004725809]
単純複体は多方向順序関係を明示的にエンコードするグラフの高次元一般化と見なすことができる。
単体錯体の$k$-homological特徴によってパラメータ化された関数のグラフ畳み込みモデルを提案する。
論文 参考訳（メタデータ） (2021-10-28T14:59:41Z) - Joint Network Topology Inference via Structured Fusion Regularization [70.30364652829164]
結合ネットワークトポロジ推論は、異種グラフ信号から複数のグラフラプラシア行列を学習する標準的な問題を表す。
新規な構造化融合正規化に基づく一般グラフ推定器を提案する。
提案するグラフ推定器は高い計算効率と厳密な理論保証の両方を享受できることを示す。
論文 参考訳（メタデータ） (2021-03-05T04:42:32Z) - Joint Inference of Multiple Graphs from Matrix Polynomials [34.98220454543502]
ノード上の観測からグラフ構造を推定することは重要かつ一般的なネットワーク科学課題である。
ノードの信号の観測から複数のグラフを共同で推定する問題について検討する。
本稿では,真のグラフの回復を保証するための凸最適化手法を提案する。
論文 参考訳（メタデータ） (2020-10-16T02:45:15Z) - Multipole Graph Neural Operator for Parametric Partial Differential
Equations [57.90284928158383]
物理系をシミュレーションするためのディープラーニングベースの手法を使用する際の大きな課題の1つは、物理ベースのデータの定式化である。
線形複雑度のみを用いて、あらゆる範囲の相互作用をキャプチャする、新しいマルチレベルグラフニューラルネットワークフレームワークを提案する。
実験により, 離散化不変解演算子をPDEに学習し, 線形時間で評価できることを確認した。
論文 参考訳（メタデータ） (2020-06-16T21:56:22Z) - Latent Poisson models for networks with heterogeneous density [0.0]
経験的ネットワークは、ネットワークの総サイズと比較すると、ノード当たりの平均接続数が少ないため、グローバルに疎結合であることが多い。
隠れた多グラフを生成する潜在ポアソンモデルがこの密度を捉えるのにいかに効果的かを示すとともに、単純なグラフを直接モデル化するいくつかの選択肢よりも数学的に計算可能であることを示す。
論文 参考訳（メタデータ） (2020-02-18T18:58:13Z) - Block-Approximated Exponential Random Graphs [77.4792558024487]
指数乱グラフ(ERG)の分野における重要な課題は、大きなグラフ上の非自明なERGの適合である。
本稿では,非自明なERGに対する近似フレームワークを提案する。
我々の手法は、数百万のノードからなるスパースグラフにスケーラブルである。
論文 参考訳（メタデータ） (2020-02-14T11:42:16Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。