A parameter-free graph reduction for spectral clustering and SpectralNet

• URL: http://arxiv.org/abs/2302.13165v1
• Date: Sat, 25 Feb 2023 21:19:30 GMT
• Title: A parameter-free graph reduction for spectral clustering and SpectralNet
• Authors: Mashaan Alshammari, John Stavrakakis, Masahiro Takatsuka
• Abstract summary: We introduce a graph reduction method that does not require any parameters. First, distances from every point $p$ to its neighbors are filtered using an adaptive threshold to only keep neighbors with similar surrounding density. The edges that survive two steps form the constructed graph that was passed to spectral clustering SpectralNet.
• Score: 1.5469452301122175
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Graph-based clustering methods like spectral clustering and SpectralNet are very efficient in detecting clusters of non-convex shapes. Unlike the popular $k$-means, graph-based clustering methods do not assume that each cluster has a single mean. However, these methods need a graph where vertices in the same cluster are connected by edges of large weights. To achieve this goal, many studies have proposed graph reduction methods with parameters. Unfortunately, these parameters have to be tuned for every dataset. We introduce a graph reduction method that does not require any parameters. First, the distances from every point $p$ to its neighbors are filtered using an adaptive threshold to only keep neighbors with similar surrounding density. Second, the similarities with close neighbors are computed and only high similarities are kept. The edges that survive these two filtering steps form the constructed graph that was passed to spectral clustering and SpectralNet. The experiments showed that our method provides a stable alternative, where other methods performance fluctuated according to the setting of their parameters.

Related papers

• Multiscale Graph Construction Using Non-local Cluster Features [10.922757310575307]
  We consider graph and node-wise features simultaneously for multiscale clustering of a graph. In experiments on multiscale image and point cloud segmentation, we demonstrate the effectiveness of the proposed method.
  arXiv  Detail & Related papers  (2024-11-13T06:42:03Z)
• HeNCler: Node Clustering in Heterophilous Graphs through Learned Asymmetric Similarity [55.27586970082595]
  HeNCler is a novel approach for Heterophilous Node Clustering. We show that HeNCler significantly enhances performance in node clustering tasks within heterophilous graph contexts.
  arXiv  Detail & Related papers  (2024-05-27T11:04:05Z)
• MeanCut: A Greedy-Optimized Graph Clustering via Path-based Similarity and Degree Descent Criterion [0.6906005491572401]
  spectral clustering is popular and attractive due to the remarkable performance, easy implementation, and strong adaptability. We propose MeanCut as the objective function and greedily optimize it in degree descending order for a nondestructive graph partition. The validity of our algorithm is demonstrated by testifying on real-world benchmarks and application of face recognition.
  arXiv  Detail & Related papers  (2023-12-07T06:19:39Z)
• Latent Random Steps as Relaxations of Max-Cut, Min-Cut, and More [30.919536115917726]
  We present a probabilistic model based on non-negative matrix factorization which unifies clustering and simplification. By relaxing the hard clustering to a soft clustering, our algorithm relaxes potentially hard clustering problems to a tractable ones.
  arXiv  Detail & Related papers  (2023-08-12T02:47:57Z)
• Dink-Net: Neural Clustering on Large Graphs [59.10189693120368]
  A deep graph clustering method (Dink-Net) is proposed with the idea of dilation and shrink. By discriminating nodes, whether being corrupted by augmentations, representations are learned in a self-supervised manner. The clustering distribution is optimized by minimizing the proposed cluster dilation loss and cluster shrink loss. Compared to the runner-up, Dink-Net 9.62% achieves NMI improvement on the ogbn-papers100M dataset with 111 million nodes and 1.6 billion edges.
  arXiv  Detail & Related papers  (2023-05-28T15:33:24Z)
• Rethinking k-means from manifold learning perspective [122.38667613245151]
  We present a new clustering algorithm which directly detects clusters of data without mean estimation. Specifically, we construct distance matrix between data points by Butterworth filter. To well exploit the complementary information embedded in different views, we leverage the tensor Schatten p-norm regularization.
  arXiv  Detail & Related papers  (2023-05-12T03:01:41Z)
• Refining a $k$-nearest neighbor graph for a computationally efficient spectral clustering [1.5469452301122175]
  approximate spectral clustering (ASC) uses sampling or quantization to select data representatives. We propose a refined version of $k$-nearest neighbor graph, in which we keep data points and aggressively reduce number of edges. Compared to ASC methods, the proposed method delivered a consistent performance despite significant reduction of edges.
  arXiv  Detail & Related papers  (2023-02-22T11:31:32Z)
• Spectral-Spatial Global Graph Reasoning for Hyperspectral Image Classification [50.899576891296235]
  Convolutional neural networks have been widely applied to hyperspectral image classification. Recent methods attempt to address this issue by performing graph convolutions on spatial topologies.
  arXiv  Detail & Related papers  (2021-06-26T06:24:51Z)
• Structured Graph Learning for Clustering and Semi-supervised Classification [74.35376212789132]
  We propose a graph learning framework to preserve both the local and global structure of data. Our method uses the self-expressiveness of samples to capture the global structure and adaptive neighbor approach to respect the local structure. Our model is equivalent to a combination of kernel k-means and k-means methods under certain condition.
  arXiv  Detail & Related papers  (2020-08-31T08:41:20Z)
• Average Sensitivity of Spectral Clustering [31.283432482502278]
  We study the stability of spectral clustering against edge perturbations in the input graph. Our results suggest that spectral clustering is stable against edge perturbations when there is a cluster structure in the input graph.
  arXiv  Detail & Related papers  (2020-06-07T09:14:44Z)
• Local Graph Clustering with Network Lasso [90.66817876491052]
  We study the statistical and computational properties of a network Lasso method for local graph clustering. The clusters delivered by nLasso can be characterized elegantly via network flows between cluster boundary and seed nodes.
  arXiv  Detail & Related papers  (2020-04-25T17:52:05Z)

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.