論文の概要: Compact Geometric Representations of Hierarchies

• arxiv url: http://arxiv.org/abs/2606.18520v1
• Date: Tue, 16 Jun 2026 22:20:52 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-18 17:16:50.914595
• Title: Compact Geometric Representations of Hierarchies
• Title（参考訳）: 階層のコンパクトな幾何学的表現
• Authors: Prashant Gokhale, Piotr Indyk, Yuhao Liu, Sandeep Silwal, Tony Chang Wang, Haike Xu,
• Abstract要約: 任意の有向木に対して、木の大きさや深さによらず、定数次元3に埋め込まれた到達可能性が存在することを証明する。 構造グラフパラメータに依存する埋め込みを用いて階層を表現するための理論的保証を提供する。 私たちの埋め込みは、現実世界のデータセット上に構築することができ、高いリコールレシエーションにおいて、はるかに小さな次元を提供することができます。
• 参考スコア（独自算出の注目度）: 20.884220139918014
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Computing geometric representations of data is a cornerstone of modern machine learning, typically achieved by training dual encoders which map queries and documents into a shared embedding space. Recent work of You et al. [NeurIPS '25] has extended this approach to hierarchical retrieval, where relevance is determined by the ancestor-descendant relationships in a Directed Acyclic Graph (DAG). While previous work has shown that valid embeddings exist when the number of descendants is small, these bounds degrade significantly for deep hierarchies, requiring dimensions as large as the total number of nodes. In this paper, we investigate compact reachability embeddings for more general graph classes and provide theoretical guarantees for representing hierarchies using embeddings whose dimension depends on structural graph parameters. We prove that for any directed tree, there exists a reachability embedding in constant dimension 3, independent of the tree's size or depth. We generalize this result to graphs characterized by treewidth $t$, constructing embeddings of dimension $O(t \log n)$, where $n$ is the number of nodes. Complementing these upper bounds, we provide matching or near-matching lower bounds, showing that dimension $Ω(n)$ is necessary for general DAGs and $Ω(t/\log(n/t))$ is required for graphs of treewidth $t$. We also obtain upper and lower bounds parameterized by the number of cross-edges in the DAG. We additionally show that our embeddings can be constructed on real world datasets, and that they give much smaller dimensions in high recall regimes compared to prior embeddings with theoretical guarantees.
• Abstract（参考訳）: データの幾何学的表現は、クエリとドキュメントを共有埋め込み空間にマッピングするデュアルエンコーダのトレーニングによって達成される、現代の機械学習の基盤である。 近年のYou et al [NeurIPS '25] の研究は、階層的検索にアプローチを拡張しており、DAG(Directed Acyclic Graph)における祖先-子孫関係によって関連性が決定されている。 以前の研究では、子孫の数が少ないときに有効な埋め込みが存在することが示されているが、これらの境界は深い階層性のために著しく低下し、ノードの総数と同じ次元を必要とする。 本稿では、より一般的なグラフクラスに対するコンパクトな到達可能性埋め込みについて検討し、構造グラフパラメータに依存する埋め込みを用いて階層を表現する理論的保証を提供する。 任意の有向木に対して、木の大きさや深さによらず、定数次元3に埋め込まれた到達可能性が存在することを証明する。 この結果を木幅$t$を特徴とするグラフに一般化し、次元$O(t \log n)$の埋め込みを構成する。 これらの上界を補足すると、一致するあるいはほぼ一致する下界を提供し、一般のDAGには$Ω(n)$、ツリー幅$t$のグラフには$Ω(t/\log(n/t))$が必要であることを示す。 また,DAGのクロスエッジ数によってパラメータ化された上下境界も得られる。 さらに、我々の埋め込みは、実世界のデータセット上に構築でき、理論的な保証のある以前の埋め込みと比較して、高いリコールレシエーションの次元がはるかに小さいことを示す。

関連論文リスト

• GraphTreeGen: Subtree-Centric Approach to Efficient and Supervised Graph Generation [6.138671548064356]
  GraphTreeGen(GTG)は、効率的な正確なコネクトーム合成のためのサブツリー中心の生成フレームワークである。 GTGはそれぞれのコネクトームをエントロピー誘導のkホップ木に分解し、情報的局所構造を捉える。 モジュラー設計により、超解像とクロスモダリティ合成を接続できる。
  論文  参考訳（メタデータ） (2025-08-13T11:02:38Z)
• The Geometry of Meaning: Perfect Spacetime Representations of Hierarchical Structures [0.0]
  3次元ミンコフスキー時空に階層構造を埋め込む高速アルゴリズムが存在することを示す。 我々の結果は、すべての離散データが3次元の完全な幾何学的表現を持っていることを示唆しているように思われる。
  論文  参考訳（メタデータ） (2025-05-07T20:41:06Z)
• Heterogeneous Graph Neural Network on Semantic Tree [11.810900066591861]
  HetTreeは、グラフ構造とヘテロジニアスの両方をスケーラブルで効果的な方法でモデル化する、新しいHGNNである。 セマンティックツリーを効果的にエンコードするために、HetTreeは、親子関係をエンコードするのに役立つメタパスを強調するために、新しいサブツリーアテンションメカニズムを使用している。 さまざまな実世界のデータセット上でのHetTreeの評価は、既存のすべてのベースラインをオープンベンチマークで上回っていることを示す。
  論文  参考訳（メタデータ） (2024-02-21T03:14:45Z)
• Hierarchical Aggregations for High-Dimensional Multiplex Graph Embedding [7.271256448682229]
  HMGEは高次元多重グラフの階層的アグリゲーションに基づく新しい埋め込み手法である。 我々は、ローカルパッチとグローバルサマリー間の相互情報を活用して、監督なしにモデルを訓練する。 合成および実世界のデータに関する詳細な実験は、下流監視タスクに対する我々のアプローチの適合性を示している。
  論文  参考訳（メタデータ） (2023-12-28T05:39:33Z)
• Data Topology-Dependent Upper Bounds of Neural Network Widths [52.58441144171022]
  まず、3層ニューラルネットワークがコンパクトな集合上のインジケータ関数を近似するように設計可能であることを示す。 その後、これは単純複体へと拡張され、その位相構造に基づいて幅の上界が導かれる。 トポロジカルアプローチを用いて3層ReLUネットワークの普遍近似特性を証明した。
  論文  参考訳（メタデータ） (2023-05-25T14:17:15Z)
• Hierarchical clustering with dot products recovers hidden tree structure [53.68551192799585]
  本稿では,階層構造の回復に着目した凝集クラスタリングアルゴリズムの新しい視点を提案する。 クラスタを最大平均点積でマージし、例えば最小距離やクラスタ内分散でマージしないような、標準的なアルゴリズムの単純な変種を推奨する。 このアルゴリズムにより得られた木は、汎用確率的グラフィカルモデルの下で、データ中の生成的階層構造をボナフェイド推定することを示した。
  論文  参考訳（メタデータ） (2023-05-24T11:05:12Z)
• Tight and fast generalization error bound of graph embedding in metric space [54.279425319381374]
  非ユークリッド計量空間へのグラフ埋め込みは、既存の有界よりもはるかに少ない訓練データを持つユークリッド空間におけるグラフ埋め込みよりも優れていることを示す。 我々の新しい上限は、既存の上限よりもかなり強く速く、最大で$R$と$O(frac1S)$に指数関数できる。
  論文  参考訳（メタデータ） (2023-05-13T17:29:18Z)
• Hierarchies over Vector Space: Orienting Word and Graph Embeddings [14.367560758244624]
  非秩序な平坦な埋め込み空間から固有階層特性をキャプチャするデータ構造を提案する。 テキスト分布の一般性の概念に着想を得て,本アルゴリズムは,ノードをエンティティパワーの順に挿入することにより,アーボラッセンス(有向根木)を構築する。 本研究は,3つの課題(ハイパーネム関係探索,単語間の最小共用者探索,ウィキペディアページリンク回復)における木構造の性能を評価する。
  論文  参考訳（メタデータ） (2022-11-02T18:54:44Z)
• Graph Neural Networks with Composite Kernels [60.81504431653264]
  カーネル重み付けの観点からノード集約を再解釈する。 本稿では,アグリゲーション方式における特徴類似性を考慮したフレームワークを提案する。 特徴空間における特徴類似性をエンコードするために,元の隣り合うカーネルと学習可能なカーネルの合成として特徴集約を提案する。
  論文  参考訳（メタデータ） (2020-05-16T04:44:29Z)

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

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