SING: Stability-Incorporated Neighborhood Graph

Information

• Publication Type: Conference Paper
• Workgroup(s)/Project(s):
  • Modeling the World at Scale
• Date: December 2024
• ISBN: 979-8-4007-1131-2
• Publisher: Association for Computing Machinery
• Location: Tokyo
• Lecturer: Diana Marin
• Event: SA '24: SIGGRAPH Asia 2024
• Editor: Igarashi, Takeo and Shamir, Ariel and Zhang, Hao
• DOI: 10.1145/3680528.3687674
• Booktitle: SA '24: SIGGRAPH Asia 2024 Conference Papers
• Pages: 10
• Conference date: 3. December 2024 – 6. December 2024
• Pages: 1 – 10
• Keywords: Proximity graphs, Stipple art editing, Pattern design, Network topology, clustering, point patterns, similarity metric, discrete distributions, persistence analysis, Neighborhood graph, topological data analysis, K-means, Rips complexes

Abstract

We introduce the Stability-Incorporated Neighborhood Graph (SING), a novel density-aware structure designed to capture the intrinsic geometric properties of a point set. We improve upon the spheres-of-influence graph by incorporating additional features to offer more flexibility and control in encoding proximity information and capturing local density variations. Through persistence analysis on our proximity graph, we propose a new clustering technique and explore additional variants incorporating extra features for the proximity criterion. Alongside the detailed analysis and comparison to evaluate its performance on various datasets, our experiments demonstrate that the proposed method can effectively extract meaningful clusters from diverse datasets with variations in density and correlation. Our application scenarios underscore the advantages of the proposed graph over classical neighborhood graphs, particularly in terms of parameter tuning.

Additional Files and Images

Weblinks

• Entry in reposiTUm (TU Wien Publication Database)
• DOI: 10.1145/3680528.3687674

BibTeX

@inproceedings{marin-2024-sing,
  title =      "SING: Stability-Incorporated Neighborhood Graph",
  author =     "Diana Marin and Amal Dev Parakkat and Stefan Ohrhallinger
               and Michael Wimmer and Steve Oudot and Pooran Memari",
  year =       "2024",
  abstract =   "We introduce the Stability-Incorporated Neighborhood Graph
               (SING), a novel density-aware structure designed to capture
               the intrinsic geometric properties of a point set. We
               improve upon the spheres-of-influence graph by incorporating
               additional features to offer more flexibility and control in
               encoding proximity information and capturing local density
               variations. Through persistence analysis on our proximity
               graph, we propose a new clustering technique and explore
               additional variants incorporating extra features for the
               proximity criterion. Alongside the detailed analysis and
               comparison to evaluate its performance on various datasets,
               our experiments demonstrate that the proposed method can
               effectively extract meaningful clusters from diverse
               datasets with variations in density and correlation. Our
               application scenarios underscore the advantages of the
               proposed graph over classical neighborhood graphs,
               particularly in terms of parameter tuning.",
  month =      dec,
  isbn =       "979-8-4007-1131-2",
  publisher =  "Association for Computing Machinery",
  location =   "Tokyo",
  event =      "SA '24: SIGGRAPH Asia 2024",
  editor =     "Igarashi, Takeo and Shamir, Ariel and Zhang, Hao",
  doi =        "10.1145/3680528.3687674",
  booktitle =  "SA '24: SIGGRAPH Asia 2024 Conference Papers",
  pages =      "10",
  pages =      "1--10",
  keywords =   "Proximity graphs, Stipple art editing, Pattern design,
               Network topology, clustering, point patterns, similarity
               metric, discrete distributions, persistence analysis,
               Neighborhood graph, topological data analysis, K-means, Rips
               complexes",
  URL =        "https://www.cg.tuwien.ac.at/research/publications/2024/marin-2024-sing/",
}