Consistent line clustering using geometric hypergraphs

• URL: http://arxiv.org/abs/2505.24868v1
• Date: Fri, 30 May 2025 17:59:17 GMT
• Title: Consistent line clustering using geometric hypergraphs
• Authors: Kalle Alaluusua, Konstantin Avrachenkov, B. R. Vinay Kumar, Lasse Leskelä,
• Abstract summary: We show how a 3-uniform hypergraph can be used to group lines in a Euclidean space.<n>In contrast to classical block models, latent geometric constraints in this construction introduce significant dependencies between hyperedges.<n>We derive information-theoretic thresholds for exact and almost exact recovery for data generated from intersecting lines on a plane with additive noise.
• Score: 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.

Related papers

• HyperGCT: A Dynamic Hyper-GNN-Learned Geometric Constraint for 3D Registration [60.01977041900338]
  We propose HyperGCT, a flexible dynamic Hyper-GNN-learned geometric constraint.<n>Our method is robust to graph noise, demonstrating a significant advantage in terms of generalization.
  arXiv  Detail & Related papers  (2025-03-04T02:05:43Z)
• Provably Extending PageRank-based Local Clustering Algorithm to Weighted Directed Graphs with Self-Loops and to Hypergraphs [40.215737469808026]
  This work focuses on graph local clustering, which has broad applications beyond graphs because of the internal connectivities within various modalities.<n>We extend the non-approximating Andersen-Chung-Lang ("ACL") algorithm beyond discrete graphs and generalize its quadratic optimality to a wider range of graphs.<n>We theoretically prove that, under two mild conditions, both algorithms can identify a quadratically optimal local cluster in terms of conductance with at least 1/2 probability.
  arXiv  Detail & Related papers  (2024-12-04T03:56:14Z)
• Improving embedding of graphs with missing data by soft manifolds [51.425411400683565]
  The reliability of graph embeddings depends on how much the geometry of the continuous space matches the graph structure. We introduce a new class of manifold, named soft manifold, that can solve this situation. Using soft manifold for graph embedding, we can provide continuous spaces to pursue any task in data analysis over complex datasets.
  arXiv  Detail & Related papers  (2023-11-29T12:48:33Z)
• One-step Bipartite Graph Cut: A Normalized Formulation and Its Application to Scalable Subspace Clustering [56.81492360414741]
  We show how to enforce a one-step normalized cut for bipartite graphs, especially with linear-time complexity. In this paper, we first characterize a novel one-step bipartite graph cut criterion with normalized constraints, and theoretically prove its equivalence to a trace problem. We extend this cut criterion to a scalable subspace clustering approach, where adaptive anchor learning, bipartite graph learning, and one-step normalized bipartite graph partitioning are simultaneously modeled.
  arXiv  Detail & Related papers  (2023-05-12T11:27:20Z)
• Contrastive Graph Clustering in Curvature Spaces [74.03252813800334]
  We present a novel end-to-end contrastive graph clustering model named CONGREGATE. To support geometric clustering, we construct a theoretically grounded Heterogeneous Curvature Space. We then train the graph clusters by an augmentation-free reweighted contrastive approach.
  arXiv  Detail & Related papers  (2023-05-05T14:04:52Z)
• Geometry Contrastive Learning on Heterogeneous Graphs [50.58523799455101]
  This paper proposes a novel self-supervised learning method, termed as Geometry Contrastive Learning (GCL) GCL views a heterogeneous graph from Euclidean and hyperbolic perspective simultaneously, aiming to make a strong merger of the ability of modeling rich semantics and complex structures. Extensive experiments on four benchmarks data sets show that the proposed approach outperforms the strong baselines.
  arXiv  Detail & Related papers  (2022-06-25T03:54:53Z)
• Nonbacktracking spectral clustering of nonuniform hypergraphs [2.408714894793063]
  We study spectral clustering for nonuniform hypergraphs based on the hypergraph nonbacktracking operator. We propose an alternating algorithm for inference in a hypergraph blockmodel via linearized belief-propagation.
  arXiv  Detail & Related papers  (2022-04-27T01:14:06Z)
• Spatial-Spectral Clustering with Anchor Graph for Hyperspectral Image [88.60285937702304]
  This paper proposes a novel unsupervised approach called spatial-spectral clustering with anchor graph (SSCAG) for HSI data clustering. The proposed SSCAG is competitive against the state-of-the-art approaches.
  arXiv  Detail & Related papers  (2021-04-24T08:09:27Z)
• Generative hypergraph clustering: from blockmodels to modularity [26.99290024958576]
  We propose an expressive generative model of clustered hypergraphs with heterogeneous node degrees and edge sizes. We show that hypergraph Louvain is highly scalable, including as an example an experiment on a synthetic hypergraph of one million nodes. We use our model to analyze different patterns of higher-order structure in school contact networks, U.S. congressional bill cosponsorship, U.S. congressional committees, product categories in co-purchasing behavior, and hotel locations.
  arXiv  Detail & Related papers  (2021-01-24T00:25:22Z)
• Hypergraph Random Walks, Laplacians, and Clustering [9.488853155989615]
  We propose a flexible framework for clustering hypergraph-structured data based on recently proposed random walks. We show that the proposed methods produce higher-quality clusters and conclude by highlighting avenues for future work.
  arXiv  Detail & Related papers  (2020-06-29T20:58:15Z)
• Parameterized Correlation Clustering in Hypergraphs and Bipartite Graphs [15.36202554903105]
  We consider new clustering objectives in hypergraphs and bipartite graphs. These objectives are parameterized by one or more resolution parameters in order to enable diverse knowledge discovery in complex data.
  arXiv  Detail & Related papers  (2020-02-21T18:26:53Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.