論文の概要: Congestion bounds via Laplacian eigenvalues and their application to tensor networks with arbitrary geometry

• arxiv url: http://arxiv.org/abs/2510.02725v1
• Date: Fri, 03 Oct 2025 04:58:40 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-06 16:35:52.270061
• Title: Congestion bounds via Laplacian eigenvalues and their application to tensor networks with arbitrary geometry
• Title（参考訳）: ラプラシア固有値による混雑境界とその任意の幾何学的テンソルネットワークへの応用
• Authors: Sayan Mukherjee, Shinichiro Akiyama,
• Abstract要約: 我々は、$n$-vertex graph $G$の頂点を$n$-leafのルートツリー$mathcalB$の葉に埋め込む問題を考える。 我々は、グラフの異なる族における渋滞境界を、正規構造(ハイパーキューブと格子)、ランダムグラフ、量子回路のテンソルネットワーク表現と数値的に比較する。
• 参考スコア（独自算出の注目度）: 2.6140509675507384
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: Embedding the vertices of arbitrary graphs into trees while minimizing some measure of overlap is an important problem with applications in computer science and physics. In this work, we consider the problem of bijectively embedding the vertices of an $n$-vertex graph $G$ into the leaves of an $n$-leaf rooted binary tree $\mathcal{B}$. The congestion of such an embedding is given by the largest size of the cut induced by the two components obtained by deleting any vertex of $\mathcal{B}$. The congestion $\mathrm{cng}(G)$ is defined as the minimum congestion obtained by any embedding. We show that $\lambda_2(G)\cdot 2n/9\le \mathrm{cng} (G)\le \lambda_n(G)\cdot 2n/9$, where $0=\lambda_1(G)\le \cdots \le \lambda_n(G)$ are the Laplacian eigenvalues of $G$. We also provide a contraction heuristic given by hierarchically spectral clustering the original graph, which we numerically find to be effective in finding low congestion embeddings for sparse graphs. We numerically compare our congestion bounds on different families of graphs with regular structure (hypercubes and lattices), random graphs, and tensor network representations of quantum circuits. Our results imply lower and upper bounds on the memory complexity of tensor network contraction in terms of the underlying graph.
• Abstract（参考訳）: 任意のグラフの頂点を木に埋め込み、重複度を最小化することは、コンピュータ科学や物理学の応用において重要な問題である。 本研究では、$n$-vertex graph $G$ の頂点を $n$-leaf の根付き二分木 $\mathcal{B}$ の葉に単射的に埋め込む問題を考える。 そのような埋め込みの混雑は、$\mathcal{B}$の頂点を削除して得られる2つの成分によって引き起こされるカットの最大サイズによって与えられる。 混雑$\mathrm{cng}(G)$は、埋め込みによって得られる最小の混雑として定義される。 ここで、$0=\lambda_1(G)\le \cdots \le \lambda_n(G)$が$G$のラプラシア固有値であることを示す。 また、元のグラフを階層的にスペクトルクラスタリングすることで得られる収縮ヒューリスティックも提供し、スパースグラフの低混雑埋め込みを見つけるのに有効であることを示す。 我々は、グラフの異なる族における混雑境界を、正規構造(ハイパーキューブと格子)、ランダムグラフ、量子回路のテンソルネットワーク表現と数値的に比較する。 本研究の結果は, テンソルネットワーク収縮のメモリ複雑性について, 基礎となるグラフの点から, 下位および上界を示唆するものである。

関連論文リスト

• Differentially Private Synthetic Graphs Preserving Triangle-Motif Cuts [3.652509571098291]
  微分プライベート (DP) 合成グラフ $G'$ を、任意のグラフ $G'$ のすべてのカットの三角形-モチーフサイズをよく近似する問題について検討する。 このようなグラフの非公開バージョンは、グラフクラスタリング、グラフスペーシフィケーション、ソーシャルネットワーク分析といった様々な分野に応用されている。
  論文  参考訳（メタデータ） (2025-07-20T06:20:53Z)
• Graph Unfolding and Sampling for Transitory Video Summarization via Gershgorin Disc Alignment [48.137527345353625]
  携帯電話からYouTubeやTikTokなどのソーシャルメディアサイトにアップロードされたユーザー生成ビデオ(UGV)は、短くて繰り返しではない。 我々は、ガーシュゴリンディスクアライメント(GDA)に基づく高速グラフサンプリングにより、遷移UGVを複数のディスクに線形時間で要約する。 提案アルゴリズムは,最先端の手法と比較して,映像の要約性能が向上し,複雑さが大幅に低減されていることを示す。
  論文  参考訳（メタデータ） (2024-08-03T20:08:02Z)
• Neural network learns low-dimensional polynomials with SGD near the information-theoretic limit [75.4661041626338]
  単一インデックス対象関数 $f_*(boldsymbolx) = textstylesigma_*left(langleboldsymbolx,boldsymbolthetarangleright)$ の勾配勾配勾配学習問題について検討する。 SGDに基づくアルゴリズムにより最適化された2層ニューラルネットワークは、情報指数に支配されない複雑さで$f_*$を学習する。
  論文  参考訳（メタデータ） (2024-06-03T17:56:58Z)
• Planted Bipartite Graph Detection [13.95780443241133]
  ランダムグラフに隠れた二部グラフを検出するタスクについて検討する。 ヌル仮説の下では、このグラフは、エッジ密度$q$の$n$上のアードホスラーイランダムグラフの実現である。 k_mathsfR times k_mathsfL$ bipartite subgraph with edge density $p>q$。
  論文  参考訳（メタデータ） (2023-02-07T18:18:17Z)
• Cheeger Inequalities for Directed Graphs and Hypergraphs Using Reweighted Eigenvalues [6.094384342913063]
  我々は、有向グラフのための新しいスペクトル理論と、ハイパーグラフのための代替スペクトル理論を開発する。 我々は、重み付けされた固有値アプローチを用いて、有向グラフとハイパーグラフに対するチェーガーの不等式を導出する。
  論文  参考訳（メタデータ） (2022-11-17T18:51:32Z)
• Efficient Signed Graph Sampling via Balancing & Gershgorin Disc Perfect Alignment [51.74913666829224]
  強い反相関を持つデータセットに対して、適切なグラフは正および負のエッジ重みの両方を含むことを示す。 本稿では,平衡符号グラフの概念に着目した線形時間符号グラフサンプリング手法を提案する。 実験結果から, 署名付きグラフサンプリング手法は, 各種データセットにおいて, 既存の高速サンプリング方式よりも優れた性能を示した。
  論文  参考訳（メタデータ） (2022-08-18T09:19:01Z)
• 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)
• Accelerated Gradient Tracking over Time-varying Graphs for Decentralized Optimization [59.65871549878937]
  実用的な単一ループ加速勾配追跡には$O(fracgamma1-sigma_gamma)2sqrtfracLepsilon)$が必要であることを証明している。 我々の収束率は$O(frac1epsilon5/7)$と$O(fracLmu)5/7frac1(1-sigma)1.5logfrac1epsilon)$よりも大幅に改善した。
  論文  参考訳（メタデータ） (2021-04-06T15:34:14Z)

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

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