Source-linked AI summary
Graph Degree Linkage: Agglomerative Clustering on a Directed Graph
Wei Zhang, Xiaogang Wang, Deli Zhao, Xiaoou Tang
TL;DR
The paper addresses the difficulty of clustering high-dimensional data with varying structures, densities, noise, and outliers. It proposes directed K-nearest-neighbor graph clustering using a product of average indegree and outdegree as cluster affinity, and reports superior performance across image clustering and object matching. The method is also presented as simple and fast, though its neighbor-set updates rely on stated nearest-cluster assumptions.
Problem
High-dimensional computer-vision data contain varying densities, sizes, shapes, manifold structures, noise, and outliers that conventional distance-based agglomerative methods struggle to handle.
Method
The method builds K-nearest-neighbor graphs and defines cluster affinity by aggregating the product of average indegree, reflecting local density, and average outdegree, reflecting local structure.
Results
The algorithm is reported to outperform state-of-the-art methods on image clustering and object matching, including a higher F-score in 95.6% of AGDL's random trials across tested object-matching settings.
Takeaways & Limitations
The paper presents graph degree linkage as a simple, effective, and computationally efficient approach for agglomerative clustering in computer-vision applications.
Takeaways & Limitations
Neighbor-set updates rely on assumptions that nearest-cluster relationships are likely preserved when clusters are merged.
Abstract
from arXiv · showhide
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.
1 Introduction
The paper introduces a graph-based agglomerative clustering algorithm for high-dimensional data, designed to handle varying densities, manifold structures, noise, and outliers. It uses directed-graph degree information to define a robust cluster affinity and reports strong performance with simple, fast implementation.
- High-dimensional computer-vision data often contain clusters with different densities, sizes, shapes, manifold structures, noise, and outliers.
- The algorithm builds K-nearest-neighbor graphs and uses indegree to reflect local density while outdegree captures manifold structure and vertex-cluster similarity.
- The product affinity separates nearby clusters with different densities and reduces the effect of noise by requiring both directed-degree components to be large.
- On synthetic multiscale data, the algorithm perfectly discovers three clusters with different shapes, sizes, and densities.
- Cluster affinity is defined from the product of average indegree and average outdegree, then aggregated across vertices in the two clusters.
- The method is reported as high-performing, easy to implement with vector operations, and much faster than spectral clustering, especially on large-scale data.
2 Related Work
The related work contrasts distance-based, density-based, spectral, message-passing, and directed-graph approaches with the proposed graph-degree linkage perspective. The paper emphasizes limitations involving complex structures, high dimensionality, noise, outliers, and computational cost.
- Classical linkage methods use pairwise distances, which may miss global data structure and remain sensitive to noise.
- DBSCAN and related variants can perform satisfactorily but usually struggle with the challenges posed by high-dimensional spaces.
- Chameleon defines affinity through relative interconnectivity and closeness based on min-cut bisection, but incurs high computational cost.
- K-means is sensitive to initialization and struggles with varying densities, sizes, and manifold-shaped clusters, while spectral clustering is vulnerable to noise and outliers.
- Unlike directed-graph spectral methods that symmetrize before clustering, the proposed approach preserves direction during clustering and symmetrizes only cluster affinity.
3 Graph Degree Linkage
Graph Degree Linkage clusters high-dimensional data by building a directed K-NN graph and agglomeratively merging clusters using degree-based affinities. Its product affinity combines local density and neighborhood similarity, while efficient updates yield quadratic-time implementations and robustness to noisy edges.
- 3.2 Algorithm Overview: GDL builds a directed weighted K-NN graph and starts from weakly connected components before repeatedly merging the pair of clusters with maximum affinity.The graph uses directed edges between K-nearest neighbors, and the initial clusters come from a smaller-neighborhood K0-NN graph.
- 3.3 Affinity Measure via Product of Indegree and Outdegree: Indegree reflects density near a vertex, whereas outdegree measures its K-NN similarity to a cluster and captures local manifold structure.Cluster-size normalization prevents the procedure from favoring large clusters over smaller clusters with dense connections.
- 3.3 Affinity Measure via Product of Indegree and Outdegree: The vertex-to-cluster affinity is the product of average indegree and average outdegree, because strong membership should produce large values for both degrees.The resulting cluster affinity is formed from asymmetric affinities and can be expressed using weighted adjacency submatrices and all-one vectors.
- 3.3 Affinity Measure via Product of Indegree and Outdegree: The product affinity is robust to noisy inter-cluster edges because it can be zero when inedges and outedges do not coincide.Compared with graph-based average linkage, which uses the sum of indegree and outdegree after symmetrization, GDL retains the directed graph and a more noise-robust product.
- 3.4 Implementations of GDL: GDL-U and AGDL achieve O(n^2) time complexity, while the basic GDL algorithm has a loose upper bound of O(n^3).GDL-U uses affinity updates, and AGDL updates neighbor sets to avoid computing affinities against every other cluster.
4 Experiments
Experiments evaluate GDL and AGDL on image clustering and feature correspondence clustering for object matching. Across these tasks, the methods achieve strong clustering performance, robustness to noise, and low computational cost.
- Image Clustering: Experiments use six public image benchmarks and compare GDL-U and AGDL with eight representative clustering algorithms using NMI.The benchmarks include object, digit, and facial image databases; larger NMI indicates better clustering.
- Image Clustering: GDL-U and AGDL achieve the best NMI results among the compared algorithms, with AGDL producing results nearly identical to GDL-U.The authors attribute this performance to the effective and robust affinity measure for agglomerative clustering.
- Image Clustering: GDL-U and AGDL are more robust than other graph-based methods to graph-building σ and image noise.On COIL-20, the noise added to images greatly degrades other algorithms, while the proposed methods are barely affected.
- Image Clustering: AGDL has the lowest time cost among the graph-based algorithms, while GDL is faster than NCuts, NJW-SC, DGSC, and Zell.G-Link has worse performance than AGDL but comparable time cost.
- Feature Correspondence Clustering for Object Matching: The object-matching experiment uses feature correspondence clustering to group inliers and separate outliers in cluttered, warped image pairs.Performance is evaluated from precision and recall of detected correspondences, using ground-truth labels from the image-warping model.
- Feature Correspondence Clustering for Object Matching: AGDL consistently outperforms ACC and GS across varied outlier counts, deformation levels, and numbers of common sub-images.Its F-score exceeds both methods in 95.6% of random trials across all setting combinations, with results averaged over 30 trials per comparison.
5 Conclusion
The paper presents graph degree linkage as a fast, effective agglomerative clustering method based on directed-graph indegree and outdegree. It demonstrates the method on image clustering and object matching.
- Graph degree linkage uses indegree and outdegree to model data structure in directed graphs.
- The method provides a fast and effective approach to agglomerative clustering on a directed graph.
- Experiments demonstrate the algorithm's superiority on image clustering and object matching.
- The work analyzes how indegree and outdegree characterize structures in graph representations of data.
6 Implementations of GDL
The implementations construct graph-based initial clusters, maintain cluster affinities, and repeatedly merge the most-affine pair. GDL-U uses update formulas, while AGDL restricts searches through cluster neighbor sets.
- GDL-U: GDL-U initializes clusters from weakly connected components of a K0-NN graph and constructs a weighted K-NN adjacency matrix.
- GDL-U: GDL-U repeatedly merges the pair with maximum affinity, then updates affinities to the merged cluster using Eqs. (8) and (9).
- AGDL: AGDL initializes cluster neighbor sets as the Kc-nearest clusters before iterative merging.
- AGDL: AGDL searches maximum-affinity pairs only among clusters associated through neighbor sets.
- AGDL: After merging, AGDL updates affected neighbor sets and constructs the merged cluster's Kc-nearest-cluster set.
7 Proof of Theorem 3
The complexity analysis gives a loose O(n^3) bound for GDL and O(n^2) bounds for both GDL-U and AGDL. These improvements arise from affinity-update formulas and restricted neighbor-set searches.
- GDL: O(n^3) is the loose upper bound for the original GDL algorithm.The bound follows after replacing the initial and current cluster counts with their upper bound n.
- GDL-U: O(n^2) is the total complexity of GDL-U.The update scheme reduces each iteration's complexity and computes new affinities using the sparse adjacency matrix.
- AGDL: AGDL replaces the full cluster-affinity table with cluster neighbor sets.
- AGDL: AGDL searches maximum affinities within neighbor sets and updates only affected sets after merging.
- AGDL: O(n^2) is the time complexity of AGDL.Its per-iteration complexity is at most O(n) under the stated neighbor-set assumptions.
8 Quantitative Results in Clustering Error for Image Clustering
The clustering results are evaluated using clustering error (CE), where lower values indicate better agreement between clusters and true class labels.
- CE is the minimum overall error rate across all permutation mappings between true class labels and clusters.
- A smaller CE value indicates a better clustering result.
9 Outlier Elimination for Object Matching
AGDL identifies outlier clusters through connectivity scores: inlier clusters contain more internal edges, whereas outlier clusters in low-density regions contain fewer. It ranks clusters by score and removes those below the largest score gap.
- Inlier clusters contain many internal inedges and outedges, while outlier clusters contain fewer edges because they lie in low-density regions.
- AGDL assigns each cluster a connectivity score based on its internal graph connectivity.The supplied passage introduces the score definition but does not include the completed formula.
- Connectivity scores show large differences between inlier and outlier clusters.The paper refers to Fig. 7 as evidence for this separation.
- Clusters are ranked by connectivity score in descending order, and the largest gap between consecutive scores divides them into two subsets.The subset with smaller scores is treated as outliers and removed.