論文の概要: Consistent line clustering using geometric hypergraphs

• arxiv url: http://arxiv.org/abs/2505.24868v1
• Date: Fri, 30 May 2025 17:59:17 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-02 19:47:53.127521
• Title: Consistent line clustering using geometric hypergraphs
• Title（参考訳）: 幾何ハイパーグラフを用いたラインクラスタリング
• Authors: Kalle Alaluusua, Konstantin Avrachenkov, B. R. Vinay Kumar, Lasse Leskelä,
• Abstract要約: ユークリッド空間において3ユニフォームハイパーグラフを用いて線をグループ化する方法を示す。 古典的ブロックモデルとは対照的に、この構成における潜在幾何学的制約はハイパーエッジ間の重要な依存関係をもたらす。 付加雑音のある平面上の交差線から発生するデータの正確かつほぼ正確に回復するための情報理論しきい値を導出する。
• 参考スコア（独自算出の注目度）: 0.6749750044497732
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Traditional data analysis often represents data as a weighted graph with pairwise similarities, but many problems do not naturally fit this framework. In line clustering, points in a Euclidean space must be grouped so that each cluster is well approximated by a line segment. Since any two points define a line, pairwise similarities fail to capture the structure of the problem, necessitating the use of higher-order interactions modeled by geometric hypergraphs. We encode geometry into a 3-uniform hypergraph by treating sets of three points as hyperedges whenever they are approximately collinear. The resulting hypergraph contains information about the underlying line segments, which can then be extracted using community recovery algorithms. In contrast to classical hypergraph block models, latent geometric constraints in this construction introduce significant dependencies between hyperedges, which restricts the applicability of many standard theoretical tools. We aim to determine the fundamental limits of line clustering and evaluate hypergraph-based line clustering methods. To this end, we derive information-theoretic thresholds for exact and almost exact recovery for data generated from intersecting lines on a plane with additive Gaussian noise. We develop a polynomial-time spectral algorithm and show that it succeeds under noise conditions that match the information-theoretic bounds up to a polylogarithmic factor.
• Abstract（参考訳）: 従来のデータ分析は、データをペアの類似性を持つ重み付きグラフとして表現することが多いが、多くの問題は自然にこのフレームワークに適合しない。 直線クラスタリングにおいて、ユークリッド空間内の点は、各クラスタが線分によって十分に近似されるようにグループ化されなければならない。 任意の2つの点が直線を定義するので、対の類似性は問題の構造を捉えることができず、幾何学的ハイパーグラフによってモデル化された高次相互作用を使用する必要がある。 我々は3点の集合をほぼコリニアであるときにハイパーエッジとして扱うことで、幾何学を3ユニフォームなハイパーグラフにエンコードする。 得られたハイパーグラフには、基盤となる線分に関する情報が含まれており、コミュニティリカバリアルゴリズムを用いて抽出することができる。 古典的ハイパーグラフブロックモデルとは対照的に、この構成における潜在幾何学的制約は、多くの標準的な理論ツールの適用性を制限するハイパーエッジ間の重要な依存関係をもたらす。 本研究の目的は,線クラスタリングの基本的限界を決定し,ハイパーグラフに基づく線クラスタリング手法を評価することである。 この目的のために、付加的なガウス雑音を持つ平面上の交差線から生成されたデータの正確かつほぼ正確に回復するための情報理論しきい値を導出する。 多項式時間スペクトルアルゴリズムを開発し、情報理論上の境界値とポリ対数係数を一致させる雑音条件下では成功することを示す。

関連論文リスト

• HyperGCT: A Dynamic Hyper-GNN-Learned Geometric Constraint for 3D Registration [60.01977041900338]
  フレキシブルな動的Hyper-GNN学習型幾何制約であるHyperGCTを提案する。 本手法はグラフ雑音に対して頑健であり,一般化の点で大きな優位性を示す。
  論文  参考訳（メタデータ） (2025-03-04T02:05:43Z)
• Provably Extending PageRank-based Local Clustering Algorithm to Weighted Directed Graphs with Self-Loops and to Hypergraphs [40.215737469808026]
  この研究はグラフ局所クラスタリングに重点を置いており、様々なモダリティの内部接続性のため、グラフ以外の幅広い応用がある。 非近似型Andersen-Chung-Lang(ACL)アルゴリズムを離散グラフを超えて拡張し、その二次最適性をより広い範囲のグラフに一般化する。 理論的には、2つの穏やかな条件下では、両方のアルゴリズムが少なくとも1/2確率のコンダクタンスの観点から2次最適局所クラスターを識別できることが証明される。
  論文  参考訳（メタデータ） (2024-12-04T03:56:14Z)
• Improving embedding of graphs with missing data by soft manifolds [51.425411400683565]
  グラフ埋め込みの信頼性は、連続空間の幾何がグラフ構造とどの程度一致しているかに依存する。 我々は、この問題を解決することができる、ソフト多様体と呼ばれる新しい多様体のクラスを導入する。 グラフ埋め込みにソフト多様体を用いることで、複雑なデータセット上のデータ解析における任意のタスクを追求するための連続空間を提供できる。
  論文  参考訳（メタデータ） (2023-11-29T12:48:33Z)
• One-step Bipartite Graph Cut: A Normalized Formulation and Its Application to Scalable Subspace Clustering [56.81492360414741]
  両部グラフの1ステップ正規化カットを、特に線形時間複雑性で実施する方法を示す。 本稿では、まず、正規化制約付き一段階二分グラフカット基準を特徴付けるとともに、そのトレース問題に対する等価性を理論的に証明する。 このカット基準を、適応アンカー学習、二部グラフ学習、一段階正規化二部グラフ分割を同時にモデル化するスケーラブルなサブスペースクラスタリングアプローチに拡張する。
  論文  参考訳（メタデータ） (2023-05-12T11:27:20Z)
• Contrastive Graph Clustering in Curvature Spaces [74.03252813800334]
  本研究では,CONGREGATE という新しいグラフクラスタリングモデルを提案する。 幾何学的クラスタリングを支援するため、理論的に基底とした不均一曲率空間を構築した。 次に、拡張不要な再重み付きコントラスト的アプローチでグラフクラスタをトレーニングする。
  論文  参考訳（メタデータ） (2023-05-05T14:04:52Z)
• Geometry Contrastive Learning on Heterogeneous Graphs [50.58523799455101]
  本稿では,幾何学コントラスト学習(Geometry Contrastive Learning, GCL)と呼ばれる,新しい自己指導型学習手法を提案する。 GCLはユークリッドと双曲的な視点からヘテロジニアスグラフを同時に見ることができ、リッチな意味論と複雑な構造をモデル化する能力の強い融合を目指している。 4つのベンチマークデータセットの大規模な実験は、提案手法が強いベースラインよりも優れていることを示している。
  論文  参考訳（メタデータ） (2022-06-25T03:54:53Z)
• Nonbacktracking spectral clustering of nonuniform hypergraphs [2.408714894793063]
  非一様ハイパーグラフに対するスペクトルクラスタリングをハイパーグラフ非追跡演算子を用いて検討する。 本稿では,線形化された信念伝達を用いたハイパーグラフブロックモデルにおける推論の交互化アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-04-27T01:14:06Z)
• Spatial-Spectral Clustering with Anchor Graph for Hyperspectral Image [88.60285937702304]
  本稿では、HSIデータクラスタリングのための空間スペクトルクラスタリングとアンカーグラフ(SSCAG)という新しい非監視アプローチを提案する。 提案されたSSCAGは最先端のアプローチと競合する。
  論文  参考訳（メタデータ） (2021-04-24T08:09:27Z)
• Generative hypergraph clustering: from blockmodels to modularity [26.99290024958576]
  異質なノード度とエッジサイズを持つクラスタ化ハイパーグラフの表現的生成モデルを提案する。 我々は,100万ノードの合成ハイパーグラフを用いた実験など,ハイパーグラフ・ルーバインは高度にスケーラブルであることを示す。 このモデルを用いて,学校連絡ネットワークにおける高次構造の異なるパターン,米国議会法案共同提案,米国議会委員会,共同購入行動における製品カテゴリ,ホテルロケーションを分析した。
  論文  参考訳（メタデータ） (2021-01-24T00:25:22Z)
• Hypergraph Random Walks, Laplacians, and Clustering [9.488853155989615]
  最近提案されたランダムウォークに基づくハイパーグラフ構造化データのクラスタリングのためのフレキシブルなフレームワークを提案する。 提案手法は,高品質なクラスタを創出し,今後の作業への道のりを強調して結論付ける。
  論文  参考訳（メタデータ） (2020-06-29T20:58:15Z)
• Parameterized Correlation Clustering in Hypergraphs and Bipartite Graphs [15.36202554903105]
  ハイパーグラフと二部グラフにおける新たなクラスタリングの目的について考察する。 これらの目的は、複雑なデータにおける多様な知識発見を可能にするために、1つ以上の解決パラメータによってパラメータ化される。
  論文  参考訳（メタデータ） (2020-02-21T18:26:53Z)

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

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