Graph degree linkage
Algorithms AIMech:GraphDegreeLinkage DRAFT
Aliases: GDL, Graph degree linkage clustering
An agglomerative clustering algorithm that merges the pair with greatest symmetric graph-degree affinity, formed by summing products of cluster-normalized incoming and outgoing edge weights on a fixed directed nearest-neighbor graph.
Identity Notes & Concept Scope
GDL is the graph-degree clustering procedure of Zhang et al. Its affinity uses a product of directed degree averages, not average pairwise distance or a symmetrized graph. GDL-U is the paper’s exact update implementation of this same merge criterion; AGDL restricts candidate search and is represented separately. JULE incorporates graph-degree affinity while also learning representations and changing merge selection, so it is not the same algorithm. No normalized identity match was found across all 442 pinned AIO labels/scoped synonyms and 214 preceding native IDs/names/aliases. Word-delimited fixed-string searches of both full checkouts, including ignored and hidden files, returned 31 lines each: existing SimCLR/InfoNCE component discussion, shared primary-source references and discovery/review context. Five native neighbors and seven exact AIO nodes with scoped synonyms and outgoing relations were inspected.
Claims & Grounded Evidence
1 Claim
Mechanism
#method
Construct a directed K-nearest-neighbor graph with w_ij=exp(−dist(i,j)^2/sigma^2) for retained edges and zero otherwise. Keep W fixed during clustering. Initialize clusters as weakly connected components of a smaller K0-nearest-neighbor graph. For vertex i and cluster C, define d_in(i,C)=sum_(j in C) w_ji/|C| and d_out(i,C)=sum_(j in C) w_ij/|C|. The directed affinity A(B→C)=sum_(i in B) d_in(i,C)d_out(i,C); the symmetric merge affinity is A(B,C)=A(B→C)+A(C→B). Repeatedly choose a pair with maximum affinity over all current pairs, merge it, and stop at the requested cluster count. The exact update implementation uses A((A union B)→C)=A(A→C)+A(B→C), while the opposite direction must be computed from the original degree expression; both directions are not generally additive.
⚠️ Curated Limitations & Negative Results
- The distance, K, K0, bandwidth and requested cluster count determine the construction. Weak-component initialization can already join observations irreversibly; the merge-only procedure cannot recover a requested count larger than the initial number of components.
- Degree products encode two-way connectivity but do not prove recovery of true semantic clusters or universal robustness to noise. The graph is directed even though the final pair affinity is symmetric.
- GDL-U preserves the exact criterion when updates and tie handling agree. The paper’s AGDL approximation can choose different merges and is not an exact synonym.
- The published complexity analysis distinguishes naive GDL from its update and approximate implementations, and assumes fixed neighborhood parameters and sparsity. This record asserts no universal runtime or benchmark advantage. No implementation or benchmark was executed.
Artificial Intelligence Ontology (AIO) Grounding
Mapped AIO Classes
| AIO Target Class | Mapping Relation | Mapping Rationale |
|---|---|---|
AIO:UnsupervisedClustering
Unsupervised Clustering
|
related_match | GDL groups unlabeled observations using a specified graph-based merge procedure. The AIO target is a clustering task, so this algorithm-to-task association does not assert equivalence or an is-a relation. |
AIO:HierarchicalClustering
Hierarchical Clustering
|
related_match | GDL repeatedly merges clusters to build an agglomerative hierarchy. The target describes hierarchy construction without prescribing this linkage or candidate-search procedure. |
Evidence Sources & Primary Literature
1 Source| Source ID | Publication / Document | Type / Access | Reference & Checksum |
|---|---|---|---|
method-source
|
Wei Zhang, Xiaogang Wang, Deli Zhao, Xiaoou Tang
|
primary paper
full_text
|
ID: https://arxiv.org/abs/1208.5092v1
sha256:eea827c754d6…
|
Curation Provenance
Curator: Codex
Method: ai_assisted
Model: GPT-6
Created: 2026-10-11T09:15:34Z
Updated: 2026-10-11T09:15:34Z
Source File:
data/curated/GraphDegreeLinkage.yaml