PaperlayerView exact revision on arXiv

Source-linked AI summary

Admissible Hierarchical Clustering Methods and Algorithms for Asymmetric Networks

Gunnar Carlsson, Facundo Mémoli, Alejandro Ribeiro, Santiago Segarra

arXiv:1607.06335v1cs.LGstat.ML

TL;DR

The paper asks how hierarchical clustering can satisfy two axioms on asymmetric networks while allowing methods between reciprocal and nonreciprocal clustering. It characterizes three intermediate families and derives dioid-algebra algorithms, finding distinct and bounded clustering behavior in a U.S. economic-sector application.

  • Problem

    The paper addresses how to characterize hierarchical clustering methods satisfying the value and transformation axioms on asymmetric networks.

    Source: §I · p. 1

  • Method

    The paper develops grafting, convex combination, and semi-reciprocal families and computes them using matrix operations in a min-max dioid algebra.

    Source: §I · p. 1

  • Results

    In the U.S. economic-sector network, semi-reciprocal clustering recognizes heavy-industry relations while avoiding some long-cycle structures considered counter-intuitive by nonreciprocal clustering.

    Source: §V · pp. 10, 12

  • Takeaways & Limitations

    Admissible methods can interpolate between reciprocal and nonreciprocal clustering while preserving their theoretical bounds, with semi-reciprocal clustering offering a bounded cyclic-influence alternative.

    Source: §V · p. 12, §VI · p. 13

Abstract

from arXiv · show

This paper characterizes hierarchical clustering methods that abide by two previously introduced axioms -- thus, denominated admissible methods -- and proposes tractable algorithms for their implementation. We leverage the fact that, for asymmetric networks, every admissible method must be contained between reciprocal and nonreciprocal clustering, and describe three families of intermediate methods. Grafting methods exchange branches between dendrograms generated by different admissible methods. The convex combination family combines admissible methods through a convex operation in the space of dendrograms, and thirdly, the semi-reciprocal family clusters nodes that are related by strong cyclic influences in the network. Algorithms for the computation of hierarchical clusters generated by reciprocal and nonreciprocal clustering as well as the grafting, convex combination, and semi-reciprocal families are derived using matrix operations in a dioid algebra. Finally, the introduced clustering methods and algorithms are exemplified through their application to a network describing the interrelation between sectors of the United States (U.S.) economy.

I. INTRODUCTION

The paper characterizes admissible hierarchical clustering methods for asymmetric networks and develops tractable algorithms for implementing them. It introduces three intermediate method families and demonstrates their use on U.S. economic-sector networks.

I. INTRODUCTION

  • Admissible methods satisfy value and transformation axioms and are bounded between reciprocal and nonreciprocal clustering on asymmetric networks.Reciprocal clustering requires low-dissimilarity bidirectional links, whereas nonreciprocal clustering permits small-dissimilarity cycles.Source: §I · p. 1
  • The paper characterizes intermediate clustering methods and proposes a dioid-algebra framework to implement them together with reciprocal and nonreciprocal clustering.These are the paper’s two stated contributions.Source: §I · p. 1
  • Grafting, convex combination, and semi-reciprocal methods form three intermediate families that preserve admissibility.Grafting exchanges dendrogram branches, convex combinations operate in dendrogram space, and semi-reciprocal methods restrict cyclic influence between the other two extremes.Source: §I · p. 1
  • Matrix powers in a min-max dioid algebra compute minimax chain costs underlying reciprocal, nonreciprocal, and modified-dissimilarity clustering methods.The (i,j)-entry of an l-th dioid power represents the minimax cost of a chain from i to j with at most l edges.Source: §I · pp. 1–2
  • The U.S. economic-sector application compares the information extracted by the different methods and motivates semi-reciprocal clustering as an intermediate behavior.Reciprocal influence may be too restrictive, while arbitrarily long nonreciprocal cycles may be undesirable for economic sectors.Source: §I · p. 2

II. PRELIMINARIES

The preliminaries define asymmetric networks, dendrograms, ultrametrics, chains, and admissibility axioms. They establish reciprocal and nonreciprocal clustering as bounding admissible methods, coinciding with single linkage on symmetric networks.

II. PRELIMINARIES

  • A network uses nonnegative, potentially asymmetric dissimilarities, and hierarchical clustering is represented by nested partitions or equivalently finite ultrametrics.The dendrogram begins with singleton clusters and eventually places all nodes in one cluster.Source: §II · p. 2
  • A chain’s cost is its largest traversed dissimilarity, while directed minimum chain cost minimizes this maximum over all chains between two nodes.This chain-cost construction supplies the basic quantity used by the clustering methods.Source: §II · p. 2
  • The value axiom merges two mutually influencing nodes at the larger directed dissimilarity, while transformation requires dissimilarity contractions to produce no larger ultrametric distances.A method satisfying both axioms is called admissible.Source: §II · p. 2
  • Reciprocal clustering uses one bidirectional chain whose links are evaluated in both directions, whereas nonreciprocal clustering independently optimizes forward and backward chains.Thus, reciprocal chains are special cases of nonreciprocal chains.Source: §II · pp. 2–3
  • Theorem 1 bounds every admissible ultrametric between the reciprocal and nonreciprocal ultrametrics for every pair of nodes.Nonreciprocal clustering is uniformly minimal and reciprocal clustering uniformly maximal among methods satisfying the axioms.Source: §II · p. 3
  • For symmetric networks, reciprocal and nonreciprocal clustering coincide, yielding the unique admissible method equivalent to single linkage.The distinction between the two methods therefore concerns asymmetric networks.Source: §II · p. 3

III. INTERMEDIATE CLUSTERING METHODS

The paper develops three admissible methods intermediate between reciprocal and nonreciprocal clustering: grafting, convex combinations, and semi-reciprocal clustering. Semi-reciprocal clustering limits cyclic influence by allowing bounded-length loops.

III. INTERMEDIATE CLUSTERING METHODS

  • Grafting, convex combinations, and semi-reciprocal clustering provide intermediate methods between reciprocal and nonreciprocal clustering.The latter is also motivated as a natural intermediate method from the algorithmic perspective.Source: §III · p. 3

C. Semi-reciprocal

  • Nonreciprocal clustering permits different forward and backward chains, while semi-reciprocal clustering restricts both directions to chains of at most t nodes.Setting t = 2 recovers reciprocal chains.Source: Figure 2 · p. 3

A. Grafting

Grafting constructs intermediate admissible clustering methods by replacing selected reciprocal-dendrogram branches with corresponding nonreciprocal branches. The paper establishes validity for HR/NR(β) and HR/Rmax(β), while showing several alternative combinations are invalid.

Grafting

  • HR/NR(β) replaces reciprocal branches cut at resolution β with corresponding nonreciprocal branches, producing an intermediate dendrogram.The method keeps reciprocal ultrametric values for large reciprocal dissimilarities and uses nonreciprocal values for small ones.Source: A. Grafting · pp. 3–4
  • HR/NR(β) is a valid ultrametric and satisfies axioms (A1) and (A2), so it is admissible.The paper proves the ultrametric property through the strong triangle inequality and verifies both axioms.Source: A. Grafting · pp. 3–4
  • Figure 3 illustrates HR, HNR, and HR/NR(β = 4) for a network whose nonreciprocal dendrogram connects all nodes at resolution 1, while reciprocal clustering joins all nodes at resolution 5.The grafted dendrogram replaces reciprocal branches whose reciprocal ultrametric values are below β = 4.Source: Figure 3 · p. 4, A. Grafting · p. 4
  • The alternative HR/R(β), HNR/NR(β), and HNR/R(β) combinations are invalid for some networks because they can violate the strong triangle inequality.For HR/R(β), the paper gives a counterexample in which the resulting function is not an ultrametric.Source: A. Grafting · p. 4
  • HR/Rmax(β) is a second valid and admissible grafting method that saturates small nonreciprocal ultrametric values at β.It retains reciprocal values for small reciprocal ultrametrics and permits nonreciprocal values at larger resolutions.Source: A. Grafting · pp. 4–5
  • HR/NR(β) allows nonreciprocal influence below β but requires reciprocal influence at higher resolutions.This supports tight clusters formed through influence loops while requiring bidirectional links for looser clusters.Source: A. Grafting · p. 5

B. Convex combinations

Convex combinations create intermediate clustering methods from admissible methods by combining their dissimilarities and applying single linkage to recover an ultrametric. The resulting method remains admissible, and the construction extends to any number of admissible methods.

Convex combinations

  • The construction combines the output ultrametrics into a symmetric dissimilarity network before applying single linkage.The direct combined dissimilarity need not itself satisfy the strong triangle inequality, so single linkage restores the ultrametric structure.Source: B. Convex combinations · p. 5
  • Given two admissible methods, the convex combination method is a well-defined ultrametric satisfying axioms (A1) and (A2).The construction combines the methods' outputs through a parameter θ and then applies single linkage to the resulting symmetric network.Source: B. Convex combinations · p. 5
  • Admissibility of the component methods transfers to the convex combination because their axiom inequalities combine under the same parameter θ.The paper separately verifies the two-node condition for (A1) and the dissimilarity-reducing-map condition for (A2).Source: B. Convex combinations · p. 5
  • Convex combinations generalize recursively from two admissible methods to any number of admissible methods while preserving axioms (A1) and (A2).The paper characterizes this as a family of intermediate admissible methods.Source: B. Convex combinations · p. 5

C. Semi-reciprocal

Semi-reciprocal clustering interpolates between reciprocal and nonreciprocal clustering by limiting the length of secondary chains used for cyclic influence. Its parameter t recovers reciprocal clustering at t = 2 and nonreciprocal clustering when t ≥ n, while remaining admissible.

C. Semi-reciprocal

  • Semi-reciprocal clustering permits cyclic influence through secondary chains of at most t nodes in each direction, with an unrestricted main chain.This generalizes reciprocal bidirectional chains while limiting the cycle lengths allowed by nonreciprocal clustering.Source: C. Semi-reciprocal · p. 6
  • The method is valid and admissible: its output is an ultrametric satisfying axioms (A1) and (A2).The proof establishes the strong triangle inequality and verifies the value and transformation axioms.Source: C. Semi-reciprocal · p. 6
  • t = 2 recovers reciprocal clustering, whereas t ≥ n recovers nonreciprocal clustering.At t = 2, only two-node reciprocal chains are available; for t ≥ n, all minimizing chains are available and the main chain need not impose an intermediate meeting point.Source: C. Semi-reciprocal · p. 7
  • In the illustrated network, the ultrametric between x and x′ is 4 for reciprocal clustering, 1 for nonreciprocal clustering, 3 at t = 3, and 2 at t = 4.For t ≥ 5, the semi-reciprocal value equals 1.Source: C. Semi-reciprocal · p. 7
  • The parameter t provides an intermediate control over influence propagation, allowing cycles while bounding their maximum secondary-chain length.This is intended for settings where bidirectional influence is too restrictive but arbitrarily long unidirectional cycles are undesirable.Source: C. Semi-reciprocal · p. 7

IV. ALGORITHMS

The algorithms represent reciprocal and nonreciprocal clustering through directed and symmetrized minimum-cost chains. These computations are implemented as matrix powers in the min-max dioid algebra.

IV. ALGORITHMS

  • Dioid matrix powers compute minimum-cost chains, with reciprocal clustering using symmetrized dissimilarities and nonreciprocal clustering using directed dissimilarities.Reciprocal clustering takes maximums across opposite directions before chain minimization, whereas nonreciprocal clustering preserves directed paths.Source: §IV · p. 7
  • In the dioid algebra, addition is minimum and multiplication is maximum, so compatible matrix products combine alternative paths by minimum bottleneck cost.The resulting matrix operations provide the algorithmic basis for the clustering ultrametrics.Source: §IV · p. 7

A. Dioid powers and ultrametrics

Dioid powers encode minimum bottleneck costs of directed chains, and quasi-inverses connect these powers to the directed minimum-chain ultrametric. Ultrametric structure is characterized by dioid idempotency and the strong triangle inequality.

A. Dioid powers and ultrametrics

  • The (i,j)-entry of the l-th dioid power represents the minimum cost of a chain from node i to j containing at most l hops.This makes dioid powers directly useful for constructing ultrametric matrices from network dissimilarities.Source: A. Dioid powers and ultrametrics · pp. 7–8
  • A nonnegative matrix is an ultrametric when it has null diagonal, positive off-diagonal entries, symmetry, and the strong triangle inequality.The strong triangle inequality is equivalent to the relevant dioid idempotency property.Source: A. Dioid powers and ultrametrics · pp. 7–8
  • The quasi-inverse A† of a dissimilarity matrix yields the directed minimum chain costs of the associated network.Its entries correspond to the directed ultrametric precursor obtained by minimizing bottleneck costs over directed chains.Source: A. Dioid powers and ultrametrics · p. 8

B. Algorithms for admissible clustering methods

The paper derives dioid-algebra algorithms for reciprocal, nonreciprocal, semi-reciprocal, grafting, convex-combination, and broader intermediate clustering methods. These procedures preserve admissibility and have polynomial complexity, with faster implementations available for reciprocal and nonreciprocal clustering.

B. Algorithms for admissible clustering methods

  • Reciprocal and nonreciprocal ultrametrics are computed by symmetrizing and taking dioid powers in opposite orders.This ordering emphasizes their extremal roles and motivates intermediate procedures that alternate matrix powers and symmetrization.Source: B. Algorithms for admissible… · p. 8
  • Semi-reciprocal ultrametrics are computed by taking directed dioid powers for secondary chains, symmetrizing them, and applying an outer dioid power for main chains.The inner powers encode bounded secondary chains, while the outer power finds minimizing main chains.Source: B. Algorithms for admissible… · pp. 8–9
  • The semi-reciprocal algorithm recovers reciprocal clustering at t = 2 and nonreciprocal clustering at t = n.These endpoint recoveries show that the semi-reciprocal family is algorithmically intermediate between the two methods.Source: B. Algorithms for admissible… · p. 9
  • The asymmetric family Ht,t′ allows different forward and backward secondary-chain limits, remains admissible, and contains reciprocal and semi-reciprocal methods as special cases.Ht,t is equivalent to HSR(t+1), HR is H1,1, and HNR is Hn−1,n−1 for networks with at most n nodes.Source: B. Algorithms for admissible… · p. 9
  • Grafting methods use simple matrix combinations, while convex-combination methods use convex combinations of ultrametric matrices followed by dioid powers.For symmetric networks, all admissible algorithms reduce to the single-linkage ultrametric.Source: B. Algorithms for admissible… · p. 10
  • The general dioid implementations require O(n^4) operations, reducible to O(n^3 log n) by repeated squaring and to O(n^2.688 log n) with subcubic multiplication.Reciprocal clustering can reach O(n^2), while nonreciprocal clustering can reach O(n^2 log n) using specialized methods.Source: B. Algorithms for admissible… · p. 10

V. NUMERICAL RESULTS

The U.S. economic-sector network illustrates how reciprocal, nonreciprocal, and semi-reciprocal clustering produce distinct dendrogram structures and interpretations. Semi-reciprocal clustering preserves admissible bounds while filtering long-cycle artifacts.

Network construction

  • The 61-sector U.S. input network is normalized so each directed dissimilarity reflects the proportion of a sector’s production input supplied by another sector.This focuses the analysis on input composition rather than sector size.Source: §V · p. 10

Reciprocal clustering

  • Reciprocal clustering groups sectors with balanced bidirectional influence, first merging administrative and professional services at δ = 0.887.The reciprocal dendrogram also reveals service-sector groupings, but direct bidirectional requirements can produce counter-intuitive mergers.Source: §V · pp. 10–11

Comparison

  • Across the economic-sector examples, reciprocal clustering emphasizes balanced exchanges, nonreciprocal clustering captures directed cycles, and semi-reciprocal clustering moderates both behaviors.The three dendrograms therefore expose different structural interpretations of the same asymmetric network.Source: §V · pp. 10, 12

Nonreciprocal clustering

  • Nonreciprocal clustering merges sectors through directed cycles, joining OG, PC, and CO at δ = 0.885 before progressively incorporating service and financial sectors.The OG-PC-CO cluster is supported by the cycle [OG, PC, CO, OG], while later five- and seven-node cycles incorporate AS, MP, RL, WH, SC, and FR.Source: §V · pp. 11–12
  • Although nonreciprocal clustering can identify plausible relationships missed by reciprocal clustering, arbitrarily long cycles can also create artifact-like clusters.The AS-MP merger with CO-PC-OG at δ = 0.887 exemplifies the problem of allowing influence to propagate through long loops.Source: §V · pp. 11–12

Semi-reciprocal clustering

  • Semi-reciprocal clustering bounds every merger between reciprocal and nonreciprocal resolutions, as FR and SC merge at δNR = 0.900, δSR = 0.909, and δR = 0.925.This ordering follows the admissible-method bounds.Source: §V · p. 12
  • HSR(3) combines short cyclic influence with bidirectional structure, forming OG-PC-CO at δ = 0.885 while keeping AS and MP together before their later merger with the heavy-industry cluster.It is insensitive to intricate influences represented by long cycles.Source: §V · pp. 12–13
  • HSR(3) also identifies a distinct FR-RA-SC cluster at δSR 1 = 0.909 through the three-node cycle [RA, SC, FR, RA].The semi-reciprocal restriction prevents these sectors from joining the main cluster through longer loops.Source: §V · p. 13

VI. CONCLUSION

The paper identifies three admissible intermediate clustering families, develops tractable dioid-algebra algorithms for them and reciprocal/nonreciprocal clustering, and applies them to U.S. economic sectors.

  • Three admissible families—grafting, convex combination, and semi-reciprocal methods—are characterized between reciprocal and nonreciprocal clustering.They satisfy the axioms of value and transformation; semi-reciprocal methods permit cyclic influence up to a fixed maximum length.Source: §VI · p. 13
  • Matrix operations in a min-max dioid algebra yield computationally tractable algorithms for all introduced clustering methods.The constructions use finite matrix powers, including symmetrization for reciprocal clustering and the opposite operation for nonreciprocal clustering.Source: §VI · p. 13
  • The methods and algorithms are applied to study relationships among sectors of the United States economy.Source: §VI · p. 13
  • Future work would further restrict admissible methods by requiring stability and scale invariance.These properties concern similar networks producing similar dendrograms and cluster formation remaining independent of dissimilarity scale.Source: §VI · p. 13

Related papers

Loading 1607.06335v1…