PaperlayerView exact revision on arXiv

Source-linked AI summary

Hierarchical Quasi-Clustering Methods for Asymmetric Networks

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

arXiv:1404.4655v1cs.LGstat.ML

TL;DR

Hierarchical clustering produces symmetric dendrograms, which do not directly represent asymmetric network relations. The paper introduces quasi-dendrograms and quasi-clustering methods, proves that directed single linkage is uniquely admissible under two axioms, and establishes stability, invariance, algorithms, and a migration application.

  • Problem

    Conventional dendrograms impose symmetric output on asymmetric networks, creating a mismatch between the input relations and clustering structure.

    Source: §1 · p. 1

  • Method

    The paper defines quasi-dendrograms and quasi-ultrametrics, formalizes admissibility with directed axioms, and develops directed single linkage with stability, invariance, and an algorithmic formulation.

    Source: §1 · pp. 1–2, §3.1 · p. 4

  • Results

    Directed single linkage is the unique method admissible under the two directed axioms, and it is stable and invariant under the proposed framework.

    Source: §1 · p. 2, §3.4 · p. 6

  • Takeaways & Limitations

    Asymmetric quasi-clustering preserves directional influence in cluster outputs, including geographic and California-centered migration influence in the 2011 U.S. application.

    Source: §1 · pp. 1–2

    Directed single linkage may be sensitive to a directed chaining effect; weakening the transformation axiom removes the uniqueness result and admits density-aware alternatives.

    Source: Remark 2 (Axiomatic strength and… · p. 7

Abstract

from arXiv · show

This paper introduces hierarchical quasi-clustering methods, a generalization of hierarchical clustering for asymmetric networks where the output structure preserves the asymmetry of the input data. We show that this output structure is equivalent to a finite quasi-ultrametric space and study admissibility with respect to two desirable properties. We prove that a modified version of single linkage is the only admissible quasi-clustering method. Moreover, we show stability of the proposed method and we establish invariance properties fulfilled by it. Algorithms are further developed and the value of quasi-clustering analysis is illustrated with a study of internal migration within United States.

1. Introduction

The paper generalizes hierarchical clustering to asymmetric networks by allowing asymmetric quasi-dendrogram outputs. It establishes directed admissibility, stability, invariance, and an application to U.S. migration.

1. Introduction

  • Asymmetric networks create a mismatch because conventional dendrograms impose symmetric outputs on asymmetric relations.Different clustering stages can symmetrize the input, yielding multiple admissible methods rather than a unique choice.Source: §1 · p. 1
  • Quasi-dendrograms generalize dendrograms by preserving asymmetric relations through quasi-partitions with influence structures between clusters.The influence structure induces a partial order over blocks.Source: §1 · pp. 1–2
  • The directed axioms of value and transformation uniquely identify an asymmetric version of single linkage as the admissible quasi-clustering method.The analysis relies on the equivalence between quasi-dendrograms and quasi-ultrametrics.Source: §1 · p. 2
  • The proposed method is stable for similar networks and satisfies several invariance properties.These properties are developed using a quantitative stability notion for quasi-clustering methods.Source: §1 · p. 2
  • A matrix-power algorithm applies quasi-clustering to 2011 U.S. migration data, revealing geographic dominance and California’s influence over the West Coast.The application uses an asymmetric network encoding internal migration between states.Source: §1 · p. 2

2. Preliminaries

The preliminaries define networks and conventional hierarchical clustering through dissimilarities, partitions, equivalence relations, and resolution-indexed dendrograms. They also introduce directed chains and chain costs for asymmetric clustering.

2. Preliminaries

  • A network is a finite node set equipped with a nonnegative dissimilarity that may be asymmetric and need not satisfy the triangle inequality.The dissimilarity is zero exactly for identical nodes.Source: §2 · p. 2
  • A partition divides nodes into pairwise-disjoint blocks covering the full node set and corresponds to an equivalence relation.Equivalence requires reflexivity, symmetry, and transitivity.Source: §2 · p. 2
  • A dendrogram is a nested collection of partitions indexed by resolution, with singleton clusters at resolution 0 and progressively merged clusters as resolution increases.Nodes are equivalent at a resolution precisely when they occupy the same cluster.Source: §2 · p. 2
  • A chain is an ordered sequence of nodes linking a start node to an end node through directed consecutive edges.Its cost is the maximum directed dissimilarity encountered along the chain.Source: §2 · p. 2

3. Quasi-Clustering methods

This section generalizes partitions and dendrograms to asymmetric networks through quasi-partitions, quasi-dendrograms, and quasi-ultrametrics, and characterizes directed single linkage under directed value and transformation axioms. It examines DSL’s stability and invariance, presents an algorithm based on dioid matrix powers, and considers weaker axioms for density-aware methods while noting a directed chaining limitation.

3. Quasi-Clustering methods

  • A quasi-partition is a partition whose blocks are connected by unidirectional, transitive influence edges, generalizing ordinary partitions to asymmetric data.Quasi-equivalence relations are reflexive and transitive but need not be symmetric; ordinary partitions arise when the edge set is empty.Source: §3 · pp. 2–3

3.1. Quasi-dendrograms

  • Quasi-dendrograms are nested quasi-partitions indexed by resolution, with clusters and influence edges persisting toward coarser resolutions under boundary, hierarchy, and continuity conditions.Their partition component is a dendrogram, and ordinary dendrograms are exactly the special case with empty edge sets.Source: §3.1 · p. 4

3.2. Quasi-ultrametrics

  • Quasi-dendrograms and quasi-ultrametric networks are structure-preservingly equivalent through mutually inverse maps Ψ and Υ.This equivalence provides a mathematically convenient quasi-ultrametric representation while retaining quasi-dendrograms for data visualization.Source: §3.2 · p. 5

3.3. Admissible quasi-clustering methods

  • Admissibility requires preserving every two-node network exactly and preventing dissimilarity-reducing transformations from weakening output influence relations.These requirements are encoded by the Directed Axiom of Value and Directed Axiom of Transformation.Source: §3.3 · p. 6

3.4. Existence and uniqueness of admissible quasi-clustering methods: directed single linkage

  • Directed single linkage uses minimum directed chain cost to produce a quasi-ultrametric and is both valid and admissible.The method extends single linkage to asymmetric networks by measuring the least costly directed chain between nodes.Source: §3.4 · p. 6
  • Directed single linkage is the unique valid hierarchical quasi-clustering method satisfying the Directed Axioms of Value and Transformation.Theorem 2 establishes that every admissible method equals directed single linkage, recovering uniqueness for asymmetric networks through asymmetric outputs.Source: §3.4 · pp. 6–7

Remark 2 (Axiomatic strength and directed chaining effect)

  • Weakening the stringent axiom (˜A2) removes DSL’s uniqueness guarantee and admits density-aware methods that can avoid the directed chaining effect.The passage presents this as an avenue for future research, drawing on analogous success for finite metric spaces (Carlsson & Mémoli, 2013).Source: Remark 2 (Axiomatic strength and… · p. 7

3.5. Stability and invariance properties of DSL

  • Nearby input networks produce nearby DSL quasi-ultrametrics, so noise has limited effect on quasi-dendrograms, and DSL is permutation invariant.Theorem 3 upper-bounds output distance by input-network distance.Source: §3.5 · p. 7
  • DSL is invariant to changes of units: transforming dissimilarities by ψ preserves influence order while changing the quasi-dendrogram’s resolution according to ψ.This follows because the quasi-ultrametric outcome is transformed by the same change-of-scale function ψ.Source: §3.5 · p. 7

3.6. Algorithms

  • DSL computes directed-chain costs through dioid matrix powers, and for n-node networks its quasi-ultrametric output is obtained using the (n−1)st power.The dioid algebra uses minimization as addition and maximization as multiplication; subcubic algorithms achieve complexity O(n2.688).Source: §3.6 · pp. 7–8
  • Tarjan’s method runs in O(n2 log n) for complete networks but symmetrizes its output, motivating investigation of faster algorithms compatible with DSL’s asymmetric construction.The paper notes that related methods can have lower complexity than the dioid-power approach.Source: §3.6 · p. 8

4. Applications

The migration application shows that DSL preserves both hierarchical clusters and asymmetric influence relations, revealing geographically structured and directionally unequal migration patterns.

4. Applications

  • The migration dissimilarity from state s to state s′ decreases as the fraction of immigrants entering s′ from s increases.The network includes every U.S. state and the District of Columbia, with zero self-dissimilarities.Source: §4 · p. 8
  • Figure 3 displays four relevant resolutions of the restricted quasi-ultrametric, with colors marking clusters, white states as singletons, and arrows marking migrational influence.The displayed states form an extended West Coast subset including Arizona and Nevada.Source: §4 · p. 8, Figure 3 · p. 8
  • DSL captures both cluster formation and asymmetric influence between clusters in the extended West Coast migration network.The method represents influence relations as directed edges between blocks at each resolution.Source: §4 · p. 8
  • At resolution δ = 0.859, California influences every other regional state, supporting its interpretation as the dominant migration force.The paper relates this pattern to California’s large urban areas attracting immigrants from across the country.Source: §4 · p. 8
  • At resolution δ = 0.921, California outranks the Oregon–Washington and Arizona–Nevada clusters, while Arizona precedes Nevada and other pairwise orderings remain undefined.The influence structure therefore forms a partial order at this resolution.Source: §4 · p. 8
  • At resolution δ = 0.922, the three-state West Coast cluster precedes Arizona and Nevada, and the partial order becomes total because Arizona precedes Nevada.The paper notes that total ordering does not occur at every resolution.Source: §4 · p. 9

5. Conclusion

The conclusion argues that quasi-dendrograms generalize dendrograms to asymmetric networks while retaining directed relations. It identifies DSL as uniquely admissible and establishes its structural, stability, and invariance properties.

5. Conclusion

  • Quasi-dendrograms avoid imposing symmetric outputs on asymmetric networks and generalize ordinary dendrograms to directed relations.The paper defines quasi-clustering methods for these asymmetric output structures.Source: §5 · p. 9
  • DSL is the unique method admissible under the paper’s two directed axioms.The conclusion also notes that weakening the Directed Axiom of Transformation could yield additional admissible methods.Source: §5 · p. 9
  • The paper proves equivalence between quasi-dendrograms and quasi-ultrametrics, generalizing the corresponding dendrogram–ultrametric relationship.It also establishes stability and invariance properties for DSL.Source: §5 · p. 9
  • An internal migration network illustrates the application of DSL to asymmetric relational data.Source: §5 · p. 9

A.1. Proof of Theorem 1

The proof establishes mutually inverse constructions between quasi-ultrametrics and quasi-dendrograms. It verifies that each construction is well-defined and that the resulting structures satisfy the required hierarchical and metric properties.

A.1. Proof of Theorem 1

  • The map Ψ converts a quasi-dendrogram into a quasi-ultrametric by taking the smallest resolution at which nodes merge or one influences the other.Source: §A.1 · p. 10
  • The resulting quasi-ultrametric satisfies nonnegativity, identity, and the strong triangle inequality through the quasi-dendrogram axioms and transitivity.The triangle inequality uses δ0 = max(δ1, δ2) and the transitivity of the quasi-partition at that resolution.Source: §A.1 · p. 10
  • The map Υ converts a quasi-ultrametric into nested quasi-partitions satisfying equivalence, influence, and right-continuity conditions.The construction uses relations induced by the quasi-ultrametric at each resolution.Source: §A.1 · pp. 10–11
  • Right continuity ensures that the minimum resolution defining Ψ is well-defined and that Υ produces valid quasi-dendrograms.Source: §A.1 · pp. 10–11
  • The compositions Ψ ◦ Υ and Υ ◦ Ψ are identities, proving a structure-preserving equivalence between quasi-ultrametrics and quasi-dendrograms.Source: §A.1 · p. 11

A.2. Proof of Proposition 2

The proof verifies that the DSL chain construction defines a valid quasi-ultrametric and satisfies the directed admissibility axioms. It also shows that reducing dissimilarities cannot increase the resulting chain costs.

A.2. Proof of Proposition 2

  • Chain concatenation supplies the path construction needed to compare indirect DSL costs across pairs of nodes.Source: §A.2 · p. 11
  • The DSL output has zero distance exactly for identical nodes and satisfies the strong triangle inequality through concatenation of minimum-cost chains.The maximum link cost of a concatenated chain is bounded by the costs of its component chains.Source: §A.2 · p. 11
  • On a two-node asymmetric network, DSL preserves the original directed dissimilarities in each direction, satisfying the directed value axiom.The proof considers dissimilarities α and β for the two opposite directions.Source: §A.2 · pp. 11–12
  • Under a transformation that reduces dissimilarities, every transformed chain has no greater linkwise cost than its original counterpart.Applying the minimum over transformed chains yields the directed transformation axiom.Source: §A.2 · p. 12

A.3. Proof of Theorem 2

The proof bounds every admissible quasi-ultrametric between the directed minimum chain cost and itself, forcing equality with the modified single-linkage output.

A.3. Proof of Theorem 2

  • For the leftmost bound, Lemma 1 supplies a two-block partition whose cross-block dissimilarities support a two-node reduction at the target quasi-ultrametric value.A dissimilarity-reducing map to the two-node network and admissibility then establish the reverse inequality.Source: §A.3 · pp. 12–13
  • By contradiction, the recursive construction is repeated n −1 times; the resulting distinct nodes exhaust the n-node network, yielding a contradiction and proving a partition satisfying (32) exists.Source: §A.3 · pp. 12–13
  • The rightmost bound follows because the input dissimilarity upper-bounds admissible outputs, and the strong triangle inequality extends this bound along every directed chain.Minimizing over chains yields the directed minimum chain cost.Source: §A.3 · p. 13
  • The bounds in (42) force every admissible quasi-ultrametric to equal the modified single-linkage construction, so the admissible method is unique.The proof establishes both inequalities and concludes that ˜H ≡ ˜H∗ for every network.Source: §A.3 · p. 13

A.4. The metric on N

The paper defines a correspondence-based distance between finite asymmetric networks and proves that it is a legitimate metric modulo network isomorphism.

A.4. The metric on N

  • Network distance minimizes correspondence distortion, where distortion is the maximum difference between paired directed dissimilarities.This construction parallels the Gromov–Hausdorff distance while applying to the paper’s network setting.Source: §A.4 · p. 14
  • The correspondence-based network distance is a legitimate metric on networks modulo isomorphism.Theorem 4 establishes the metric claim.Source: §A.4 · p. 14
  • Composing correspondences yields the triangle inequality because the distortion of the composite is bounded by the sum of the two component distortions.The composed relation is shown to remain a correspondence.Source: §A.4 · p. 14
  • Zero distance implies isomorphism: equal dissimilarities along a zero-distortion correspondence produce injections both ways and therefore a bijection.Injectivity follows from the network condition that dissimilarity is zero only for identical nodes.Source: §A.4 · p. 14

A.5. Proof of Theorem 3

The stability proof compares outputs of the proposed method on networks linked by a low-distortion correspondence and bounds paired output dissimilarities by the network distance.

A.5. Proof of Theorem 3

  • If η = dN(NX, NY), the corresponding quasi-ultrametric values differ by at most 2η.The proof chooses a correspondence with distortion 2η and transfers a minimum-cost chain from one network to the other.Source: §A.5 · pp. 14–15
  • A chain attaining the output value in NX can be paired nodewise through the correspondence to bound the output value in NY.Symmetry supplies the reverse inequality.Source: §A.5 · p. 15

A.6. Proof of Proposition 3

The proposed method is invariant under non-decreasing changes of scale because its explicit directed minimum-chain structure commutes with such transformations.

A.6. Proof of Proposition 3

  • Applying a non-decreasing change-of-scale function Ψ to the output quasi-ultrametric gives the same result as applying Ψ to its explicit construction.The proof follows directly from equation (13) and monotonicity of Ψ.Source: §A.6 · p. 15

A.7. Further invariances: vertex permutations and the metric closure

This section examines invariance properties of DSL under vertex relabeling and metric closure, while using migration and economic networks to illustrate asymmetric hierarchical structures. It also distinguishes within-resolution cluster relations from hierarchy across resolutions and shows how asymmetric influence affects clustering behavior.

A.7. Further invariances: vertex permutations and the metric closure

  • DSL commutes with vertex permutations: relabeling network nodes before clustering yields the correspondingly relabeled output quasi-dendrogram.The distance between a network and its node-permuted version, and between their output quasi-dendrograms, is null.Source: §A.7 · p. 15
  • Replacing a network dissimilarity function by its maximal directed-triangle-inequality-satisfying minorant leaves the DSL output quasi-dendrogram unchanged.The metric closure ¯A_X is defined pointwise below A_X and satisfies the directed triangle inequality.Source: §A.7 · p. 15

A.8. Proof of Proposition 4

  • The proof of Proposition 4 connects the quasi inverse A*_X to minimum infinity norms of directed chains in the network, extending the symmetric analysis to asymmetric networks.The cited analysis interprets [A*_X]i,j as the minimum infinity norm over chains connecting node i to node j.Source: §A.8 · p. 15

A.9. Applications

  • DSL applications reveal directed structure beyond ordinary clusters: migration groupings follow geography, while economic-sector quasi-partitions encode influence and relative importance across resolutions.In the migration network, highlighted groups include New England and East Coast states; in the economic network, influence edges form partial orders among sector blocks.Source: §A.9 · pp. 16, 18
  • The edge component E∗_C captures hierarchical structure between clusters at a fixed resolution, while D∗_C captures hierarchy across resolutions.Source: §A.9 · p. 20
  • MAN influences more nodes than MIN and therefore plays a more important role as clustering resolutions increase, despite appearing equivalent in the dendrogram.Source: §A.9 · p. 20
  • δ = 0.960 is the first merging resolution between mining MIN and utilities UTI after removing the three strongest-influence sectors, PRO, FIR, and MAN.The reduced analysis uses the remaining 11 nodes.Source: §A.9 · p. 20
  • Removing influential sectors decreases the remaining sectors’ tendency to cluster, compared with the original 12-node cluster formed at the same resolution.The original cluster excludes OSE and EHS.Source: §A.9 · p. 20
Loading 1404.4655v1…