paperdirected-graphspectral-clusteringhermitian-laplacianflow-ratiocheeger-inequalityneurips-2020sparsification

Laenen & Sun (NeurIPS 2020) — Higher-Order Spectral Clustering of Directed Graphs

Authors: Steinar Laenen (Oxford Research Group, FiveAI; then MSc at University of Edinburgh), He Sun (School of Informatics, University of Edinburgh).

Venue: NeurIPS 2020 (Vancouver, Canada). Hash 0a5052334511e344f15ae0bfafd47a67.

Contribution

Introduces the Hermitian Laplacian for directed graphs: A_{uv} = w(u,v) \cdot \omega_{2\pi/k} \quad \text{if } u \rightsquigarrow v, \quad L_G = I - D^{-1/2} A D^{-1/2} and the flow ratio objective (a chain-structure objective summing only over consecutive cluster pairs in an ordered partition).

Three technical contributions:

  1. Spectral embedding theorem (Theorem 3.2): optimal flow-ratio partition's indicator vectors are exactly the components of L_G's smallest eigenvector in \mathbb{C}^n, with cluster position encoded as k-th roots of unity phases.
  2. Cheeger-style approximation guarantee (Theorem 4.4): SimpleHerm returns a partition A_0, \ldots, A_{k-1} satisfying \text{vol}(A_j \triangle S_j) \le \epsilon \cdot \text{vol}(S_j) for \epsilon = O(k^3 / (\gamma_k - 1)). First such guarantee for general digraphs (not just DSBM).
  3. Nearly-linear time via spectral sparsification (Spielman-Srivastava 2011) → total O(m \cdot \log^c n), beating Herm-RW's O(kp^2) for p \gg 10^3.

SimpleHerm algorithm uses only 1 eigenvector (the smallest), in \mathbb{C}^2; beats Herm-RW (which needs \lceil k/2 \rceil) and DD-SYM (Satuluri 2011, needs k + matrix multiplication).

Experimental highlights

  • Synthetic DSBM (n=1000-2000, k=4-8, path topology): SimpleHerm ARI \sim 1.0, significantly outperforms Herm-RW (0.2-0.5) and DD-SYM (0.0).
  • UN Comtrade international oil trade (2002-2017, 246 countries, k=4): stable 2006-2008, dramatic shift 2008-2009 (financial crisis), and another peak 2004-2005 (Venezuelan oil strike + Iraq war → −5.4 mbpd production cut).
  • UN Comtrade international wood trade (k=4): cluster 1 = Canada / Brazil / Russia / Germany / China (forest-rich), with 2008-2009 shift moving Eastern Europe / Middle East / Central Asia across clusters.
  • COVID-19 South Korea infection graph (67 vertices, 66 edges, k=4): identifies a single super-spreader cluster.

Importance to this wiki

Canonical citation for theoretical foundation of Hermitian clustering on directed graphs — complementary to entities/Cucuringu Li Sun Zanetti 2020 Hermitian Adjacency which provides the algorithm, and entities/Bennett Cucuringu Reinert 2022 Lead-Lag Network Clustering which applies Hermitian RW to financial lead-lag.

The chain structure assumption (cluster along a directed path) fits naturally to trade networks (export → transit → processing → import), information diffusion, and epidemic spread — making this paper the standard reference when clusters are ordered, not just lead/lag.

See also