Graph Degree Linkage: Agglomerative Clustering on a Directed Graph

This paper proposes a simple but effective graph-based agglomerative algorithm, for clustering high-dimensional data. We explore the different roles of two fundamental concepts in graph theory, indegree and outdegree, in the context of clustering. The average indegree reflects the density near a sample, and the average outdegree characterizes the local geometry around a sample. Based on such insights, we define the affinity measure of clusters via the product of average indegree and average outdegree. The product-based affinity makes our algorithm robust to noise. The algorithm has three main advantages: good performance, easy implementation, and high computational efficiency. We test the algorithm on two fundamental computer vision problems: image clustering and object matching. Extensive experiments demonstrate that it outperforms the state-of-the-arts in both applications.

• Publication year

  2012

• Venue

  European Conference on Computer Vision

• Publication date

  2012-08-25

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1007/978-3-642-33718-5_31arXiv 1208.5092
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Common visual pattern discovery via spatially coherent correspondences

  2010influential reference
• Feature correspondence and deformable object matching via agglomerative correspondence clustering

  2009influential reference
• The Elements of Statistical Learning: Data Mining, Inference, and Prediction, 2nd Edition

  2009influential reference
• Cyclizing Clusters via Zeta Function of a Graph

  2008cited by this paper
• Measurement and analysis of online social networks

  2007cited by this paper
• Local learning projections

  2007cited by this paper
• Clustering by Passing Messages Between Data Points

  2007cited by this paper
• Fast Agglomerative Clustering Using a k-Nearest Neighbor Graph

  2006cited by this paper
• A Local Learning Approach for Clustering

  2006cited by this paper
• Isoperimetric graph partitioning for image segmentation

  2006cited by this paper
• Learning from labeled and unlabeled data on a directed graph

  2005influential reference
• A spectral technique for correspondence problems using pairwise constraints

  2005cited by this paper
• Self-Tuning Spectral Clustering

  2004influential reference
• Efficient Graph-Based Image Segmentation

  2004cited by this paper
• The Elements of Statistical Learning: Data Mining, Inference, and Prediction

  2004cited by this paper
• Laplacian Eigenmaps for Dimensionality Reduction and Data Representation

  2003cited by this paper
• Finding Clusters of Different Sizes, Shapes, and Densities in Noisy, High Dimensional Data

  2003cited by this paper
• Multiclass spectral clustering

  2003cited by this paper
• On Spectral Clustering: Analysis and an algorithm

  2001influential reference
• Authoritative sources in a hyperlinked environment

  1999cited by this paper
• Chameleon: Hierarchical Clustering Using Dynamic Modeling

  1999cited by this paper
• Density-Based Clustering in Spatial Databases: The Algorithm GDBSCAN and Its Applications

  1998cited by this paper
• Normalized cuts and image segmentation

  1997influential reference
• Ieee Transactions on Knowledge and Data Engineering 1 Learning Semi-riemannian Metrics for Semi-supervised Feature Extraction

  year unknowncited by this paper

• Individual Fairness in Community Detection: Quantitative Measure and Comparative Evaluation

  2026cites this paper
• Global understanding via local extraction for data clustering and visualization

  2025cites this paper
• CBDRA-IS: Centrality-Based Defense Resource Allocation for Securing Interdependent Systems

  2025cites this paper
• Hyperoctant Search Clustering: A Method for Clustering Data in High-Dimensional Hyperspheres

  2025cites this paper
• SGAC: A stable-graph-based adaptive clustering algorithm with fewer parameters

  2025cites this paper
• Reinforcement learning-enhanced variable neighborhood search strategies for the k-clustering minimum biclique completion problem

  2025cites this paper
• Time series-based metadata extraction for the creation of semantic digital twins of building systems

  2025cites this paper
• Overlapping community detection with a new modularity measure in directed weighted networks

  2025cites this paper
• Local density based on weighted K-nearest neighbors for density peaks clustering

  2024cites this paper
• PR-DRA: PageRank-based defense resource allocation methods for securing interdependent systems modeled by attack graphs

  2024cites this paper
• Community detection with Greedy Modularity disassembly strategy

  2024cites this paper
• An augmented swarm optimization algorithm for k-clustering minimum biclique completion problems

  2024cites this paper
• Towards Adaptive Neighborhood for Advancing Temporal Interaction Graph Modeling

  2024cites this paper
• Community detection in complex networks via node similarity, graph representation learning, and hierarchical clustering

  2023cites this paper
• An overview on density peaks clustering

  2023cites this paper
• Semantic-conditioned Dual Adaptation for Cross-domain Query-based Visual Segmentation

  2023influential citation
• DMS: Differentiable Mean Shift for Dataset Agnostic Task Specific Clustering Using Side Information

  2023cites this paper
• Graph analysis using a GPU-based parallel algorithm: quantum clustering

  2023cites this paper
• Multi-View Adjacency-Constrained Hierarchical Clustering

  2023cites this paper
• Consolidating Industrial Small Files Using Robust Graph Clustering

  2023cites this paper
• A Reciprocity-Based Method for Improving Community Detection on Directed Friendship Networks

  2022cites this paper
• Comprehensive survey on hierarchical clustering algorithms and the recent developments

  2022cites this paper
• A multi-view clustering algorithm for attributed weighted multi-edge directed networks

  2022cites this paper
• Current status, application, and challenges of the interpretability of generative adversarial network models

  2022cites this paper
• Unsupervised Time-Aware Sampling Network With Deep Reinforcement Learning for EEG-Based Emotion Recognition

  2022influential citation
• CEP3: Community Event Prediction with Neural Point Process on Graph

  2022cites this paper
• Truncated representation graph with adaptive weighted and manifold regularization for agglomerative clustering

  2022cites this paper
• Image Clustering Algorithm Based on Predefined Evenly-Distributed Class Centroids and Composite Cosine Distance

  2022cites this paper
• Consolidation of structure of high noise data by a new noise index and reinforcement learning

  2022cites this paper
• Towards Direct Comparison of Community Structures in Social Networks

  2022cites this paper
• A split-merge clustering algorithm based on the k-nearest neighbor graph

  2022cites this paper
• A Generic Self-Supervised Framework of Learning Invariant Discriminative Features

  2022cites this paper
• Deep graph clustering with enhanced feature representations for community detection

  2022cites this paper
• Optimization of the Structure of Power System Multi-Agent Control

  2022cites this paper
• Twin Contrastive Learning for Online Clustering

  2022cites this paper
• HCSC: Hierarchical Contrastive Selective Coding

  2022cites this paper
• A Review of Data and Document Clustering pertaining to various Distance Measures

  2022cites this paper
• Linking Complex Concepts in Argumentation Knowledge Graphs

  2021cites this paper
• Clustering Diagnoses From 58 Million Patient Visits in Finland Between 2015 and 2018

  2021cites this paper
• 3SHACC: Three stages hybrid agglomerative constrained clustering

  2021cites this paper
• Clustering Diagnoses from 58M Patient Visits in Finland 2015–2018 (Preprint)

  2021cites this paper
• Revisiting k-Nearest Neighbor Graph Construction on High-Dimensional Data : Experiments and Analyses

  2021cites this paper
• Adapting k-means for graph clustering

  2021cites this paper
• Review of Data Science Trends and Issues in Porous Media Research With a Focus on Image‐Based Techniques

  2021cites this paper
• Cluster analysis on the example of work data of the National Power System. Part 2. Research and selected results

  2021cites this paper
• fMBN-E: Efficient Unsupervised Network Structure Ensemble and Selection for Clustering

  2021cites this paper
• Mapping social exclusion in STEM to men’s implicit bias and women’s career costs

  2021cites this paper
• From Ensemble Clustering to Subspace Clustering: Cluster Structure Encoding

  2021cites this paper
• Improving ClusterGAN Using Self-AugmentedInformation Maximization of Disentangling LatentSpaces

  2021cites this paper
• Unsupervised Ensemble Selection for Multilayer Bootstrap Networks

  2021cites this paper
• Deep Clustering for Improved Inter-Cluster Separability and Intra-Cluster Homogeneity with Cohesive Loss

  2021cites this paper
• Use and validation of text mining and cluster algorithms to derive insights from Corona Virus Disease-2019 (COVID-19) medical literature

  2021cites this paper
• Density Gain-Rate Peaks for Spectral Clustering

  2021cites this paper
• Information Maximization Clustering via Multi-View Self-Labelling

  2021cites this paper
• Unsupervised deep clustering via adaptive GMM modeling and optimization

  2021cites this paper
• Agglomerative Clustering of Network Traffic Based on Various Approaches to Determining the Distance Matrix

  2021cites this paper
• EEGFuseNet: Hybrid Unsupervised Deep Feature Characterization and Fusion for High-Dimensional EEG With an Application to Emotion Recognition

  2021cites this paper
• Benchmark and application of unsupervised classification approaches for univariate data

  2021cites this paper
• Machine-learning-assisted insight into spin ice Dy2Ti2O7

  2020cites this paper
• Hierarchical clustering with optimal transport

  2020cites this paper
• Segmentation of biomedical images with joint unsupervised learning

  2020cites this paper
• Machine learning for neutron scattering at ORNL*

  2020cites this paper
• Machine learning for magnetic phase diagrams and inverse scattering problems

  2020cites this paper
• Efficient synthetical clustering validity indexes for hierarchical clustering

  2020cites this paper
• Image Clustering Using an Augmented Generative Adversarial Network and Information Maximization

  2020cites this paper
• An adaptive kernelized rank-order distance for clustering non-spherical data with high noise

  2020influential citation
• Acoustic Scene Clustering Using Joint Optimization of Deep Embedding Learning and Clustering Iteration

  2020cites this paper
• Agglomerative Constrained Clustering Through Similarity and Distance Recalculation

  2020cites this paper
• GDPC: generalized density peaks clustering algorithm based on order similarity

  2020cites this paper
• Geometry consistency aware confidence evaluation for feature matching

  2020cites this paper
• Graph Degree Linkage Clustering for Identify Student’s Performance on Kompetisi Sains Madrasah in Indonesia

  2020cites this paper
• The Impact of Isolation Kernel on Agglomerative Hierarchical Clustering Algorithms

  2020influential citation
• Multi-level Feature Learning on Embedding Layer of Convolutional Autoencoders and Deep Inverse Feature Learning for Image Clustering

  2020cites this paper
• Analysis of Cattle Social Transitional Behaviour: Attraction and Repulsion

  2020cites this paper
• Latent Space Clustering via Dual Discriminator GAN

  2020cites this paper
• First Results in Leak Localization in Water Distribution Networks using Graph-Based Clustering and Deep Learning

  2020influential citation
• Learning a Deep Part-based Representation by Preserving Data Distribution

  2020cites this paper
• Adaptive bag-of-visual word modelling using stacked-autoencoder and particle swarm optimisation for the unsupervised categorisation of images

  2020cites this paper
• Interpretable Visualizations with Differentiating Embedding Networks

  2020cites this paper
• Universal approach for unsupervised classification of univariate data

  2020cites this paper
• CPGAN: Curve Clustering Architecture Based on Projected Latent Vector of Generative Adversarial Network

  2020cites this paper
• A new similarity combining reconstruction coefficient with pairwise distance for agglomerative clustering

  2020cites this paper
• SES-RREF: The Machine Learning Approach to Credible Metrics of Scholastic Evidence via Recursive Referencing

  2019cites this paper
• Research Front Detection and Topic Evolution Based on Topological Structure and the PageRank Algorithm

  2019cites this paper
• Time-series Clustering with Jointly Learning Deep Representations, Clusters and Temporal Boundaries

  2019cites this paper
• Review of the application of machine learning to the automatic semantic annotation of images

  2019influential citation
• An Image Clustering Auto-Encoder Based on Predefined Evenly-Distributed Class Centroids and MMD Distance

  2019cites this paper
• RECAL: Reuse of Established CNN classifer Apropos unsupervised Learning paradigm

  2019influential citation
• CDLIB: a python library to extract, compare and evaluate communities from complex networks

  2019cites this paper
• Spectral Analysis Network for Deep Representation Learning and Image Clustering

  2019cites this paper
• Density Peak Clustering Based on Cumulative Nearest Neighbors Degree and Micro Cluster Merging

  2019cites this paper
• Local gap density for clustering high-dimensional data with varying densities

  2019cites this paper
• Clustering by Directly Disentangling Latent Space

  2019cites this paper
• Dependence of Unsupervised and Supervised Segment of Three Dimensional Medical Images on Clustering and Deep Learning Formation

  2019cites this paper
• A Deep Unsupervised Learning Method for SAR Object Classification

  2019cites this paper
• Graph Analysis and Applications in Clustering and Content-based Image Retrieval

  2019cites this paper
• Machine Learning Assisted Insight to Spin Ice Dy$_2$Ti$_2$O$_7$

  2019cites this paper
• Using a Data Science Pipeline for Course Data: A Case Study Analyzing Heterogeneous Student Data in Two Flipped Classes

  2019cites this paper
• ClusterGAN : Latent Space Clustering in Generative Adversarial Networks

  2018cites this paper
• An Unsupervised Deep Learning Framework via Integrated Optimization of Representation Learning and GMM-Based Modeling

  2018cites this paper