論文の概要: Local Equivalence Classes of Distance-Hereditary Graphs using Split Decompositions

• arxiv url: http://arxiv.org/abs/2602.23825v1
• Date: Fri, 27 Feb 2026 09:07:41 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-03-02 19:48:24.344061
• Title: Local Equivalence Classes of Distance-Hereditary Graphs using Split Decompositions
• Title（参考訳）: スプリット分解を用いた距離ヘリディタリーグラフの局所等価クラス
• Authors: Nicholas Connolly, Shin Nishio, Kae Nemoto,
• Abstract要約: 局所補集合は、選択されたエッジ補集合の近傍をそのエッジ補集合に置き換えるグラフ演算である。 結果の同値クラスのサイズを決定することは 一般に難しい問題です 距離遺伝グラフの幅広い族に対する明示的な公式を導出することにより、これらの結果を拡張する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Local complement is a graph operation formalized by Bouchet which replaces the neighborhood of a chosen vertex with its edge-complement. This operation induces an equivalence relation on graphs; determining the size of the resulting equivalence classes is a challenging problem in general. Bouchet obtained formulas only for paths and cycles, and brute-force methods are limited to very small graphs. In this work, we extend these results by deriving explicit formulas for several broad families of distance-hereditary graphs, including complete multipartite graphs, clique-stars, and repeater graphs. Our approach uses a technique known as split decomposition to establish upper bounds on equivalence class sizes, and we prove these bounds are tight through a combinatorial enumeration of the graphs' decomposed structure up to symmetry.
• Abstract（参考訳）: 局所補集合はブーシェによって形式化されたグラフ演算であり、選択された頂点の近傍をエッジ補集合に置き換える。 この演算はグラフ上の同値関係を誘導し、結果の同値類のサイズを決定することは一般に難しい問題である。 ブーシェは経路やサイクルにのみ公式を得ることができ、ブルートフォース法は非常に小さなグラフに限られる。 本研究では, 完全多部グラフ, クリプスターグラフ, リピータグラフを含む, 距離遺伝グラフの幅広い族に対する明示的な公式を導出することにより, これらの結果を拡張する。 提案手法は分割分解と呼ばれる手法を用いて同値類の大きさの上限を定め、これらの境界はグラフの分解された構造を対称性まで組み合わせて列挙することによってきついことを証明している。

関連論文リスト

• Algorithm for Interpretable Graph Features via Motivic Persistent Cohomology [0.0]
  図形アレンジメントによる重み付きグラフの永続的コホモロジー特徴を計算するイベント駆動方式であるクロマティックパーシステンスアルゴリズム(CPA)を提案する。 CPAは最悪の場合指数関数であり、木幅で引き出せる固定パラメータであり、木、サイクル、および直列並列グラフのような一般的なグラフ族に対してほぼ線形である。
  論文  参考訳（メタデータ） (2025-12-23T12:29:58Z)
• HeNCler: Node Clustering in Heterophilous Graphs via Learned Asymmetric Similarity [48.62389920549271]
  HeNClerは、重み付けされたカーネル特異値分解に基づいてクラスタリング固有の目的を最適化することで類似性グラフを学習する。 提案手法は,非対称類似グラフ上でのスペクトルクラスタリングを可能にし,有向グラフと無向グラフの両方に柔軟性を提供する。
  論文  参考訳（メタデータ） (2024-05-27T11:04:05Z)
• Hyperbolic Heterogeneous Graph Attention Networks [3.0165549581582454]
  以前の不均一グラフ埋め込みモデルは、低次元ユークリッド空間におけるベクトル表現として不均一グラフの要素を表す。 メタパスインスタンスを用いた双曲空間におけるベクトル表現を学習するハイパーボリック不均一グラフ注意ネットワーク(HHGAT)を提案する。 本研究では,HHGATがノード分類やクラスタリングタスクにおいて,最先端のヘテロジニアスグラフ埋め込みモデルより優れていることを示す3つの実世界のヘテロジニアスグラフデータセットの実験を行った。
  論文  参考訳（メタデータ） (2024-04-15T04:45:49Z)
• Improving embedding of graphs with missing data by soft manifolds [51.425411400683565]
  グラフ埋め込みの信頼性は、連続空間の幾何がグラフ構造とどの程度一致しているかに依存する。 我々は、この問題を解決することができる、ソフト多様体と呼ばれる新しい多様体のクラスを導入する。 グラフ埋め込みにソフト多様体を用いることで、複雑なデータセット上のデータ解析における任意のタスクを追求するための連続空間を提供できる。
  論文  参考訳（メタデータ） (2023-11-29T12:48:33Z)
• Latent Random Steps as Relaxations of Max-Cut, Min-Cut, and More [30.919536115917726]
  クラスタリングと単純化を統一する非負行列分解に基づく確率モデルを提案する。 ハードクラスタリングをソフトクラスタリングに緩和することにより、ハードクラスタリングの潜在的な問題をトラクタブルクラスタに緩和する。
  論文  参考訳（メタデータ） (2023-08-12T02:47:57Z)
• One-step Bipartite Graph Cut: A Normalized Formulation and Its Application to Scalable Subspace Clustering [56.81492360414741]
  両部グラフの1ステップ正規化カットを、特に線形時間複雑性で実施する方法を示す。 本稿では、まず、正規化制約付き一段階二分グラフカット基準を特徴付けるとともに、そのトレース問題に対する等価性を理論的に証明する。 このカット基準を、適応アンカー学習、二部グラフ学習、一段階正規化二部グラフ分割を同時にモデル化するスケーラブルなサブスペースクラスタリングアプローチに拡張する。
  論文  参考訳（メタデータ） (2023-05-12T11:27:20Z)
• Matching Correlated Inhomogeneous Random Graphs using the $k$-core Estimator [5.685589351789462]
  我々は、両グラフの大きな共通部分グラフを誘導する対応を出力するいわゆるemph$k$-core推定器について検討する。 相関ブロックモデル,Chung-Lu幾何グラフ,および相関ランダムグラフの精度と部分的回復に関する新たな結果を導出するために,我々の一般的な枠組みを専門化している。
  論文  参考訳（メタデータ） (2023-02-10T18:21:35Z)
• Geometry Contrastive Learning on Heterogeneous Graphs [50.58523799455101]
  本稿では,幾何学コントラスト学習(Geometry Contrastive Learning, GCL)と呼ばれる,新しい自己指導型学習手法を提案する。 GCLはユークリッドと双曲的な視点からヘテロジニアスグラフを同時に見ることができ、リッチな意味論と複雑な構造をモデル化する能力の強い融合を目指している。 4つのベンチマークデータセットの大規模な実験は、提案手法が強いベースラインよりも優れていることを示している。
  論文  参考訳（メタデータ） (2022-06-25T03:54:53Z)
• Heterogeneous manifolds for curvature-aware graph embedding [6.3351090376024155]
  グラフ埋め込みは、広範囲のGraph MLアプリケーションで使用されている。 そのような埋め込みの質は、空間の幾何学がグラフの幾何学と一致するかどうかに決定的に依存する。
  論文  参考訳（メタデータ） (2022-02-02T18:18:35Z)
• Hamiltonian systems, Toda lattices, Solitons, Lax Pairs on weighted Z-graded graphs [62.997667081978825]
  グラフ上の解に対して一次元の解を持ち上げることができる条件を特定する。 位相的に興味深いグラフの簡単な例であっても、対応する非自明なラックス対と関連するユニタリ変換は、Z階数グラフ上のラックス対に持ち上げないことを示す。
  論文  参考訳（メタデータ） (2020-08-11T17:58:13Z)
• Graph Pooling with Node Proximity for Hierarchical Representation Learning [80.62181998314547]
  本稿では,ノード近接を利用したグラフプーリング手法を提案し,そのマルチホップトポロジを用いたグラフデータの階層的表現学習を改善する。 その結果,提案したグラフプーリング戦略は,公開グラフ分類ベンチマークデータセットの集合において,最先端のパフォーマンスを達成できることが示唆された。
  論文  参考訳（メタデータ） (2020-06-19T13:09:44Z)
• Wasserstein-based Graph Alignment [56.84964475441094]
  我々は,より小さいグラフのノードと大きなグラフのノードをマッチングすることを目的とした,1対多のグラフアライメント問題に対する新しい定式化を行った。 提案手法は,各タスクに対する最先端のアルゴリズムに対して,大幅な改善をもたらすことを示す。
  論文  参考訳（メタデータ） (2020-03-12T22:31:59Z)

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

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