論文の概要: Parameterised graph theory for tensor networks: entanglement rerouting, structural simplification, and agnostic tomography

• arxiv url: http://arxiv.org/abs/2609.04165v1
• Date: Thu, 03 Sep 2026 17:50:38 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-04 18:28:39.192027
• Title: Parameterised graph theory for tensor networks: entanglement rerouting, structural simplification, and agnostic tomography
• Title（参考訳）: テンソルネットワークのパラメータ化グラフ理論:絡み合い再帰、構造単純化、および非依存トモグラフィ
• Abstract要約: グラフパラメーターは、テンソル・ネットワーク状態(TNS)がトラクタブル行列積状態(MPS)かツリーテンソルネットワーク(TTN)表現を許容するか否かを判断し、状態の学習の複雑さを制御するかを示す。 実効性TNSトモグラフィーのサンプルと計算複雑性に基づいてグラフ依存上界を導出し、カット幅、ツリーカット幅、新しいグラフパラメータ、学習複雑性、次数およびツリー幅の面でのバウンドに依存する指数を導出する。
• 参考スコア（独自算出の注目度）: 0.6117371161379209
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Parameterised graph theory studies how the complexity of graph-theoretic problems depends on structural parameters of the input graph. This perspective has proved useful in analysing tensor-network simulation (Markov and Shi, 2008). Its implications for tensor-network representations and tomography are less well understood. In particular, which graph parameters determine whether a tensor-network state (TNS) admits a tractable matrix product state (MPS) or tree tensor network (TTN) representation, and which control the complexity of learning the state? We address these questions using parameterised graph theory. First, we show that cutwidth and tree-cutwidth bound the bond dimension overhead required to represent a TNS as an MPS or TTN. In the TTN case, tree-cutwidth also bounds the local dimension of the grouped subsystems. The proofs are based on entanglement rerouting, a tensor-network analogue of rerouting information in a classical network. Second, we derive graph-dependent upper bounds on the sample and computational complexity of realisable TNS tomography, with exponents that depend on cutwidth, tree-cutwidth, and a new graph parameter, learning complexity, which we bound in terms of degree and treewidth. We obtain these results by extending the disentangling MPS learner of (Cramer et al., 2010), as analysed further in (Bakshi et al., 2025; Lin et al., 2025), to TTNs and to tensor networks on arbitrary known graphs. Finally, we extend the framework beyond the realisable setting. For an arbitrary input state, our agnostic learner outputs a pure state whose fidelity is within additive error $ε$ of the optimum over tensor-network states on the given graph with a given bond dimension, with explicit graph-dependent bounds on sample and computational complexity.
• Abstract（参考訳）: パラメータ付きグラフ理論は、グラフ理論上の問題の複雑さが入力グラフの構造的パラメータに依存するかを研究する。 この観点はテンソル・ネットワークシミュレーション(Markov and Shi, 2008)の解析に有用であることが証明された。 テンソル・ネットワーク表現やトモグラフィーに対するその意味は理解されていない。 特に、テンソル・ネットワーク状態(TNS)がトラクタブル行列積状態(MPS)またはツリーテンソルネットワーク(TTN)表現を許容するかどうかを判断し、状態の学習の複雑さを制御するグラフパラメータを決定する。 パラメータ化グラフ理論を用いてこれらの問題に対処する。 まず, TNS を MPS あるいは TTN として表すのに必要な結合次元のオーバーヘッドを, カット幅とツリーカット幅が有することを示す。 TTNの場合、ツリー・カット幅はグループ化されたサブシステムの局所次元も有界である。 これらの証明は、古典的ネットワークにおける情報の再帰のテンソル・ネットワークのアナログであるエンタングルメント・リルーティングに基づいている。 第2に、実測可能なNSトモグラフィーのサンプルと計算複雑性に関するグラフ依存上界を導出し、カット幅、ツリーカット幅、新しいグラフパラメータ、学習複雑性、次数とツリー幅の面でのバウンドに依存する指数を導出する。 これらの結果は (Bakshi et al , 2025; Lin et al , 2025), TTN や任意の既知のグラフ上のテンソルネットワークに拡張して得られる。 最後に、実現可能な設定を超えてフレームワークを拡張します。 任意の入力状態に対して、我々の知能学習者は、与えられた結合次元を持つグラフ上のテンソル-ネットワーク状態に対する最適値のε$の加算誤差内にある純状態を、サンプルと計算複雑性に明示的なグラフ依存境界で出力する。

関連論文リスト

• Graph Edge Representation via Tensor Product Graph Convolutional Representation [23.021660625582854]
  本稿では,Product Graph Convolution (TPGC) と呼ばれるエッジ特徴を持つグラフ上の効率的な畳み込み演算子を定義する。 従来のグラフ畳み込み(GC)を補完するモデルを提供し、ノードとエッジの両方でより一般的なグラフデータ解析に対処する。 いくつかのグラフ学習タスクの実験結果から,提案したTPGCの有効性が示された。
  論文  参考訳（メタデータ） (2024-06-21T03:21:26Z)
• Tensor-view Topological Graph Neural Network [16.433092191206534]
  グラフニューラルネットワーク(GNN)は最近、グラフ学習において注目を集めている。 既存のGNNは、各ノード周辺の非常に限られた地区からのローカル情報のみを使用する。 本稿では,単純かつ効果的な深層学習のクラスであるTopological Graph Neural Network (TTG-NN)を提案する。 実データ実験により,提案したTTG-NNは,グラフベンチマークにおいて20の最先端手法より優れていた。
  論文  参考訳（メタデータ） (2024-01-22T14:55:01Z)
• NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification [70.51126383984555]
  本稿では,任意のノード間のノード信号を効率的に伝搬する全ペアメッセージパッシング方式を提案する。 効率的な計算は、カーナライズされたGumbel-Softmax演算子によって実現される。 グラフ上のノード分類を含む様々なタスクにおいて,本手法の有望な有効性を示す実験を行った。
  論文  参考訳（メタデータ） (2023-06-14T09:21:15Z)
• Efficient tensor network simulation of quantum many-body physics on sparse graphs [0.0]
  疎結合な基礎グラフ上に定義されたテンソルネットワーク状態について検討する。 メッセージパッシング推論アルゴリズムは、局所的な期待値の効率的な計算に繋がる可能性がある。
  論文  参考訳（メタデータ） (2022-06-09T18:00:03Z)
• Learning Graph Structure from Convolutional Mixtures [119.45320143101381]
  本稿では、観測されたグラフと潜伏グラフのグラフ畳み込み関係を提案し、グラフ学習タスクをネットワーク逆(デコンボリューション)問題として定式化する。 固有分解に基づくスペクトル法の代わりに、近似勾配反復をアンロール・トランケートして、グラフデコンボリューションネットワーク(GDN)と呼ばれるパラメータ化ニューラルネットワークアーキテクチャに到達させる。 GDNは、教師付き方式でグラフの分布を学習し、損失関数を適応させることでリンク予測やエッジウェイト回帰タスクを実行し、本質的に帰納的である。
  論文  参考訳（メタデータ） (2022-05-19T14:08:15Z)
• Graph Kernel Neural Networks [53.91024360329517]
  本稿では、グラフ上の内部積を計算するカーネル関数であるグラフカーネルを用いて、標準畳み込み演算子をグラフ領域に拡張することを提案する。 これにより、入力グラフの埋め込みを計算する必要のない完全に構造的なモデルを定義することができる。 私たちのアーキテクチャでは,任意の種類のグラフカーネルをプラグインすることが可能です。
  論文  参考訳（メタデータ） (2021-12-14T14:48:08Z)
• Spectral Graph Convolutional Networks With Lifting-based Adaptive Graph Wavelets [81.63035727821145]
  スペクトルグラフ畳み込みネットワーク(SGCN)はグラフ表現学習において注目を集めている。 本稿では,適応グラフウェーブレットを用いたグラフ畳み込みを実装した新しいスペクトルグラフ畳み込みネットワークを提案する。
  論文  参考訳（メタデータ） (2021-08-03T17:57:53Z)
• Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting [63.04999833264299]
  グラフサブストラクチャネットワーク(GSN)は,サブストラクチャエンコーディングに基づくトポロジ的に認識可能なメッセージパッシング方式である。 Wesfeiler-Leman (WL) グラフ同型テストよりも厳密に表現可能であることを示す。 グラフ分類と回帰タスクについて広範囲に評価を行い、様々な実世界の環境において最先端の結果を得る。
  論文  参考訳（メタデータ） (2020-06-16T15:30:31Z)
• Tensor Graph Convolutional Networks for Multi-relational and Robust Learning [74.05478502080658]
  本稿では,テンソルで表されるグラフの集合に関連するデータから,スケーラブルな半教師付き学習(SSL)を実現するためのテンソルグラフ畳み込みネットワーク(TGCN)を提案する。 提案アーキテクチャは、標準的なGCNと比較して大幅に性能が向上し、最先端の敵攻撃に対処し、タンパク質間相互作用ネットワーク上でのSSL性能が著しく向上する。
  論文  参考訳（メタデータ） (2020-03-15T02:33:21Z)
• Graph Signal Processing -- Part III: Machine Learning on Graphs, from Graph Topology to Applications [19.29066508374268]
  このモノグラフのパートIIIは、グラフトポロジーを学ぶ方法に対処することから始まる。 特に注目されるのは、観測データの相関および精度行列に基づくグラフトポロジーの定義である。 スパースグラフの学習には、LASSOとして知られる最小絶対縮小と選択演算子を用いる。
  論文  参考訳（メタデータ） (2020-01-02T13:14:27Z)

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

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