PaperlayerView exact revision on arXiv

Source-linked AI summary

Hierarchical Clustering and Signal Denoising on Digraphs

Yi Wang, Sippanon Kitimoon, Hrushikesh N. Mhaskar, Xiaosheng Zhuang

arXiv:2609.34670v1eess.SPcs.LG

TL;DR

The paper addresses how to cluster digraphs consistently across levels with limited supervision and how to derive spline knots from their multilevel structure. It combines a direction-aware spectral hierarchy with degree-derived knot sequences for signal denoising. Experiments report clustering effectiveness across real-world networks and structural regimes, and signal-recovery utility for the proposed knots.

  • Problem

    The paper asks how to cluster digraphs consistently across levels with limited supervision and how to derive valid spline knot sequences from multilevel clusters and directed adjacency.

    Source: §I · p. 2

  • Method

    SpecHDC recursively coarsens digraphs using a generalized Hermitian representation, then maps hierarchical in-degree and out-degree intervals to nested knots for multilevel spline quasi-interpolation and denoising.

    Source: §I · p. 2, C. Spectral Hierarchical Digraph… · p. 7, A. Digraph Signal Processing · p. 18

  • Results

    Comparisons on five labeled and two unlabeled real-world networks demonstrate clustering effectiveness, and denoising experiments validate the utility of hierarchy-induced in-degree and out-degree knots for signal recovery.

    Source: §I · p. 3

  • Takeaways & Limitations

    The hierarchy-derived knots provide a structure-adaptive basis for reconstructing noisy graph signals from a coarse approximation and thresholded inter-level details.

    Source: §VI · p. 19

Abstract

from arXiv · show

In this paper, we propose a representation of a digraph (directed graph) as a Hermitian matrix derived from its adjacency matrix. This representation characterizes both the connectivity and the edge orientation of the digraph. Based on the spectral decomposition of the Hermitian matrix, a digraph clustering algorithm with $k$-means is introduced to produce a partition on the graph. Applying this algorithm (bottom-up) recursively to a digraph with partially labeled vertices yields a spectral hierarchical digraph clustering (\myproj) algorithm that produces consistent nested partitions of the digraph, or equivalently, a tree structure. Furthermore, based on the in-degree and out-degree of each cluster in the digraph clustering, a pair of hierarchical interval partitions (filtrations) can be derived in a top-down manner to produce a pair of nested knot sequences. These knot sequences facilitate the construction of multilevel spline quasi-interpolants, enabling a noisy graph signal to be decomposed into a coarse approximation and inter-level details, followed by adaptive thresholding and reconstruction. Experiments on synthetic and real-world digraphs demonstrate the superiority of our {\myproj} algorithm for digraph clustering across diverse graph structural properties (homophily and heterophily) and supervision settings. Moreover, experiments on digraph signal processing using multilevel spline quasi-interpolants further demonstrate the effectiveness of signal recovery on digraphs in terms of RMSE and SNR.

I. INTRODUCTION

The introduction identifies a gap in direction-aware hierarchical clustering with partial labels and in deriving spline knots from digraph structure. The paper connects recursive clustering to degree-based knot sequences and evaluates the resulting methods on digraphs and graph signals.

I. INTRODUCTION

  • Partial labels, asymmetric interactions, and consistent coarse-level relations complicate hierarchical digraph clustering, while spline construction needs ordered intervals derived from partitions and directed adjacency.The introduction frames these as coupled challenges for connecting digraph hierarchies with spline approximation.Source: §I · p. 2

B. Contributions

  • Comparisons on five labeled and two unlabeled real-world networks demonstrate clustering effectiveness, while denoising experiments support the utility of hierarchy-induced in-degree and out-degree knots for signal recovery.Controlled synthetic experiments examine homophilic and heterophilic digraphs.Source: §I · p. 3, B. Contributions · p. 4

A. Related work

  • Prior digraph clustering methods use symmetrization, source–target representations, random walks, and Hermitian operators, but direction-aware hierarchical clustering with partial labels remains less explored.Most existing methods produce single-level partitions at prescribed granularities.Source: A. Related work · p. 3

B. Contributions

  • The paper introduces a generalized Hermitian matrix that represents reciprocal connectivity and asymmetric edge orientation, and SpecHDC recursively coarsens digraphs to form nested partitions using available labels.Level-wise in-degree and out-degree intervals are assembled into multi-level knot sequences for spline approximation.Source: B. Contributions · p. 4
  • Because the proposed knots are non-equidistant, the de Boor inequality does not provide the needed spline stability bounds; the paper instead obtains bounds with respect to a doubling measure.Source: B. Contributions · p. 4

C. Structure of the paper

  • The paper proceeds from digraph clustering and synthetic and real-world evaluation to spline stability, then to multilevel spline signal denoising and conclusions.Source: C. Structure of the paper · p. 4

II. DIGRAPH CLUSTERING

  • SpecHDC and its induced hierarchical interval partitions are introduced as the section’s method, with synthetic examples illustrating the approach.Source: §II · p. 4

A. Notation and Preliminary on Graph Clustering

B. Digraph Clustering

The digraph clustering method embeds vertices using a generalized Hermitian operator that represents reciprocal connectivity and directional imbalance. It applies constrained spectral clustering recursively to coarsened digraphs to produce nested partitions.

B. Digraph Clustering

  • The generalized Hermitian matrix combines reciprocal connectivity and asymmetric edge orientation, with α and β controlling the contributions of its symmetric and skew-symmetric components.Its Hermitian structure gives real eigenvalues and an orthonormal eigenbasis.Source: B. Digraph Clustering · p. 5
  • The spectral clustering procedure retains eigenvectors with |λ_j| > ϵ and uses the resulting vertex representations for k-means, subject to any known labels.A real-valued implementation can concatenate the real and imaginary parts while preserving Euclidean distances.Source: B. Digraph Clustering · pp. 5–6
  • SpecHDC recursively clusters the current digraph, contracts clusters into coarse vertices, and aggregates inter-cluster edge weights to construct each coarse adjacency matrix.The procedure repeats the spectral clustering operation on the coarsened digraphs while incorporating known labels.Source: B. Digraph Clustering · p. 6
  • The recursive procedure produces nested partitions and corresponding coarse directed graphs, with the single-level clustering operation serving as its basic step.The hierarchy is organized as a tree with the original vertices as leaves and the whole vertex set as root.Source: B. Digraph Clustering · p. 6

C. Spectral Hierarchical Digraph Clustering

SpecHDC recursively coarsens a digraph to create nested partitions, while known labels can constrain assignments. A top-down construction then associates the hierarchy with paired in-degree and out-degree interval partitions and nested knot sequences.

C. Spectral Hierarchical Digraph Clustering

  • SpecHDC recursively clusters successively coarsened digraphs, imposing known labels as fixed assignment constraints when available.Each cluster becomes a coarse vertex, and ordered-pair aggregation preserves asymmetric inter-cluster interactions.Source: C. Spectral Hierarchical Digraph… · pp. 6–7
  • The resulting partitions form a containment hierarchy, with original vertices as leaves and the single all-vertex cluster as root.This bottom-up hierarchy defines a tree of nested partitions.Source: C. Spectral Hierarchical Digraph… · p. 7

D. Hierarchy-Induced Interval Partitions

E. Illustration and Synthetic Examples

The synthetic example uses a directed stochastic block model to illustrate SpecHDC's bottom-up hierarchy and its corresponding interval partitions. With 30 vertices, the example progresses from five clusters to two and induces increasingly refined rectangular partitions.

E. Illustration and Synthetic Examples

  • The DSBM example uses p = q = 0.5, N = 30, k = 2, n = 15, and η = 0 in an unsupervised run with K = (2, 5).The model parameters p and q control within- and between-cluster edge probabilities, while F specifies direction probabilities between clusters.Source: E. Illustration and Synthetic Examples · p. 8
  • The 30 original vertices are grouped into five clusters at level 2 and then two at level 1, forming nested partitions.The corresponding bottom-row partitions have five blocks at level 2 and one cell per vertex at the finest level.Source: E. Illustration and Synthetic Examples · p. 8

III. EXPERIMENTS ON DIGRAPH CLUSTERING

Across the reported real-world settings, SpecHDC performs strongly for class-aligned coarse partitions, highly supervised fine partitions, and stability on unlabeled digraphs. Synthetic DSBM results show that clustering depends on structural separation, directional randomness, and the balance between connectivity and directionality.

A. Experimental Setup

  • The experiments compare spectral clustering methods on synthetic and real-world digraphs, including parameter sensitivity and normalization strategies.The setup includes seven real-world datasets and evaluates Modularity and F-measure on real-world networks, with ARI used for synthetic graphs.Source: §III · p. 9, A. Experimental Setup · p. 9

B. Results for the DSBM

  • On DSBM graphs, ARI increases as the difference between within-cluster p and between-cluster q grows, whether the structure is homophilic or heterophilic.When p and q are close, cluster boundaries are less distinct and performance decreases.Source: B. Results for the DSBM · p. 10, Figure 2 · p. 10
  • Greater directional randomness η affects weakly separated DSBM structures more than clearly homophilic or heterophilic ones.Strongly separated graphs remain stable as η increases, while weaker separation is more sensitive to directional randomness.Source: B. Results for the DSBM · p. 10, Figure 2 · p. 10
  • The preferred α/β balance depends on graph structure: asymmetry helps when q ≫ p, while larger α or a more balanced combination suits p ≫ q.No single parameter combination is optimal for every digraph; α and β control symmetric and asymmetric matrix components.Source: B. Results for the DSBM · pp. 10–11, Figure 3 · p. 11

C. Results for Real-World Data

  • On Wisconsin, SpecHDC's Level 1 F rises from 0.5836 without labels to 0.9358 with 90% labeled nodes; its Level 2 F is best at 70% and 80%.The reported Level 1 F is best at 0%, 20%, 30%, 40%, 50%, and 60% labeled nodes; Table I compares Modularity and F-measure.Source: C. Results for Real-World Data · pp. 11–12, Table I · p. 11
  • SpecHDC has the highest run-to-run stability on Telegram (ARI 0.97) and ties DD-Sym on Blog (ARI 0.88).For these unlabeled networks, ARI measures consistency across repeated unsupervised runs; Table II compares the models.Source: C. Results for Real-World Data · p. 12, Table II · p. 12
  • SpecHDC performs strongly across unsupervised and semi-supervised settings, especially for class-aligned coarse partitions, highly supervised fine partitions, and stability on unlabeled digraphs.The Wisconsin and unlabeled-network results illustrate these reported strengths.Source: Table I · p. 11, C. Results for Real-World Data · p. 12, Table II · p. 12

IV. STABILITY OF SPLINE QUASI-INTERPOLATION WITH DOUBLING MEASURES

This section introduces notation and spline quasi-interpolation concepts, then presents stability results for quasi-interpolatory spline representations as groundwork for the paper's digraph signal processing.

IV. STABILITY OF SPLINE QUASI-INTERPOLATION WITH DOUBLING MEASURES

  • The section sets out stability results for quasi-interpolatory spline representations, which the paper uses in its digraph signal processing.The section is based on prior work,.Source: §IV · p. 12, B. Splines · p. 13

A. Notation

  • The notation fixes m ≥ 1 and a probability measure μ supported on [0, 1], with comparison constants allowed to depend on μ, m, and the norms.Source: A. Notation · p. 13

B. Splines

  • The B-splines are piecewise polynomials, nonnegative, supported on knot intervals, and form a partition of unity on the specified interval.The splines are also linearly independent there.Source: B. Splines · p. 13
  • A quasi-interpolation operator uses local linear functionals and reproduces every polynomial in Πm.The defining support for each functional is [ξj, ξj+m].Source: B. Splines · p. 13

C. Orthogonal polynomials

The orthogonal-polynomial and stability results are framed for doubling measures. The stability theorem concerns quasi-interpolation and norm comparison between splines and their coefficient sequences.

C. Orthogonal polynomials

  • For an interval I, the orthogonal-polynomial construction assumes a doubling measure with at least m + 1 support points in I and specifies a basis with positive leading coefficients.The supplied lemma and basis passages state these conditions but do not include the lemma’s full conclusion.Source: C. Orthogonal polynomials · p. 14
  • The proof of Lemma 4.1 invokes Markov, Schwarz, and Parseval inequalities and a conformal mapping argument.The cited proposition summarizes these facts as the proof’s ingredients.Source: C. Orthogonal polynomials · p. 14

D. Stability theorem

  • The operator Q is a quasi-interpolant that reproduces every spline in S.Its local functionals are supported on one interval, and the theorem establishes stability for the resulting construction.Source: D. Stability theorem · pp. 15–16
  • The stability theorem compares the spline norm with the discrete norm of its coefficient sequence for 1 ≤ p < ∞ under a doubling measure.The proof obtains both directions of the comparison; the p = ∞ case is handled separately, and other finite p values follow by Riesz-Thorin interpolation.Source: D. Stability theorem · pp. 15–16

V. DIGRAPH SIGNAL PROCESSING VIA SPLINE QUASI-INTERPOLANTS

The section applies the SpecHDC hierarchy to construct splines and quasi-interpolation operators for digraph signal processing.

  • The hierarchical partitions produced by SpecHDC provide the structure used for spline construction.Source: §V · p. 17
  • The section applies the partition hierarchy to construct splines for digraph signals.Source: §V · p. 17
  • The construction also includes the splines’ associated quasi-interpolation operators for digraph signal processing.Source: §V · p. 17

A. Digraph Signal Processing

The digraph hierarchy induces paired in-degree and out-degree knot sequences for multilevel spline quasi-interpolation. The resulting approximations and inter-level details are thresholded to reconstruct noisy graph signals.

  • Each hierarchical block partition is converted into in-degree and out-degree knot sequences, which are nested across levels.The knot endpoints define the directional spline bases, and finest-level vertex coordinates associate vertices with the signal representation.Source: A. Digraph Signal Processing · p. 17
  • At each level, local linear functionals use signal samples within spline-basis support to compute quasi-interpolation coefficients without a global interpolation system.Evaluating the quasi-interpolant at the finest-level vertex coordinates gives graph-signal approximations.Source: A. Digraph Signal Processing · p. 17
  • The coarsest knot sequence yields a smoother structural approximation, while finer sequences capture more local variations.The final denoised signal averages results from the in-degree and out-degree spline quasi-interpolants.Source: A. Digraph Signal Processing · pp. 17–19
  • The denoising procedure forms successive-resolution details by subtracting approximations, then adaptively thresholds those details and reconstructs from a coarse component.The noisy observation is used for reconstruction; the clean signal is reserved for evaluating recovery quality.Source: A. Digraph Signal Processing · pp. 17–18

B. Denoising Performance Analysis

Across the evaluated datasets, spline-based reconstruction generally lowers RMSE and raises SNR, with added fine-scale detail improving Cora results. The experiments span directed graphs with varied scales, heterophily, and supervision availability.

B. Denoising Performance Analysis

  • At 20% noise, the best reconstruction reduces RMSE from 0.0211 to 0.0141 on Cora and from 0.0185 to 0.0093 on Squirrel, with SNR rising from 14.1183 to 17.6025 dB and from 14.0223 to 19.9570 dB, respectively.Three-level reconstruction further improves Cora; other datasets show similar or identical results across reconstruction depths.Source: B. Denoising Performance Analysis · p. 19

VI. CONCLUSIONS

  • The conclusion reports effective clustering across structural and supervision settings, while the hierarchy-induced knots yield lower RMSE and higher SNR for signal recovery.Future work is directed toward scalable implementations and extensions to more complex directed graph structures.Source: §VI · p. 19

2) Datasets:

  • The seven real-world directed graphs range from 183 to 5201 vertices and 298 to 217073 directed edges, covering labeled and unlabeled networks.The reported dataset statistics include vertices, edges, classes, and homophily ratio.Source: 2) Datasets · p. 22
  • The five labeled datasets have homophily ratios from 0.0695 to 0.3347, while Telegram and Blog are unlabeled and used for unsupervised community discovery.The labeled graphs therefore include predominantly heterophilic connectivity.Source: 2) Datasets · p. 22

3) Competitors:

The section compares five directed-graph spectral clustering baselines spanning symmetrization, singular-vector, and Hermitian or skew-symmetric strategies, then specifies the clustering metrics used for evaluation.

3) Competitors:

  • Five baselines cover matrix symmetrization, singular-vector decomposition, and Hermitian or skew-symmetric spectral formulations.Bi-Sym and DD-Sym use predecessor–successor similarities; DI-SIM uses left and right singular vectors, while Herm and Skew encode directed connectivity spectrally.Source: 3) Competitors · pp. 22–23

4) Metrics:

  • The evaluation uses Modularity (M), Adjusted Rand Index (A), and F-measure (F), with higher values indicating better clustering quality.Modularity compares within-cluster edges with their expectation under a random graph with the same degree distribution.Source: 4) Metrics · p. 23

5) Directed Stochastic Block Model:

The directed stochastic block model represents inter-cluster edge orientation through a cluster-level matrix, while the clustering procedure partitions vertices using spectral features and can incorporate known labels.

5) Directed Stochastic Block Model:

  • The DSBM extends the SBM with an orientation matrix F that represents directional interactions between clusters as a weighted directed meta-graph.The model also includes within- and between-cluster connection probabilities p and q.Source: 5) Directed Stochastic Block Model · p. 24
  • Conditional on an edge between clusters Ci and Cj, Fij and Fji give the probabilities of its two possible directions; smaller η means stronger directional preference.When η = 1/2, the directional bias is removed.Source: 5) Directed Stochastic Block Model · p. 24
  • In the p = q example, cluster distinctions come from asymmetric inter-cluster orientations rather than edge density.Within-cluster directions are uniform, while the specified preferred directions between clusters follow F.Source: 5) Directed Stochastic Block Model · p. 24
  • The k-means procedure assigns vertices to the nearest centroid and updates centroids iteratively; known labels constrain assignments in the semi-supervised setting.The unsupervised setting has no known labels, and the iterative procedure converges, though not necessarily to a global optimum.Source: 6) k-Means Clustering · p. 25

B. Supplementary Experiments

The supplementary experiments show that DSBM clustering difficulty depends on graph scale, cluster structure, directional pattern, and spectral balance; on real networks, SpecHDC’s results vary by metric, dataset, and hierarchy level.

1) Results for the DSBM:

  • Larger graphs generally improve recovery, while clear homophilic or heterophilic structure reduces the data needed; increasing cluster count chiefly hurts when structure is ambiguous.Under p = q, ARI falls as k increases; with clear separation, SpecHDC is robust across tested granularities.Source: Figure 5 · p. 26, Figure 6 · p. 26, 1) Results for the DSBM · p. 26
  • With cyclic directional patterns, SpecHDC tolerates directional noise when p ≠ q; under complete patterns, conflicting biases produce performance oscillations across algorithms.In the heterophilic setting, SpecHDC degrades more slowly than baselines; in the homophilic setting, the proposed methods maintain a lead.Source: Figure 7 · p. 27, 1) Results for the DSBM · p. 27
  • The best α–β balance depends on structure: β matters more for direction-dominated graphs, while stronger α is beneficial when homophilic connectivity drives clustering.For p ≫ q, performance drops when the asymmetric term dominates excessively.Source: 1) Results for the DSBM · pp. 27–28, Figure 8 · p. 28

2) Results for Real-World Data:

  • On Cora, SpecHDC’s modularity advantage is strongest at Level 2 under moderate-to-high supervision; on Squirrel, it is mainly at Level 1.The reported modularity patterns vary by dataset and hierarchical level.Source: Table V · p. 29, Table VI · p. 29, 2) Results for Real-World Data · pp. 29–30
  • Across the real-world results, F-measure improves more consistently than modularity, particularly at Level 1, where cluster count matches the number of classes.SpecHDC uses limited supervision to obtain class-consistent partitions; its modularity advantage is more dataset- and resolution-dependent.Source: 2) Results for Real-World Data · p. 30
  • On Cornell and Texas, modularity results are irregular, with SpecHDC strongest only at selected resolutions and supervision levels.The authors attribute the irregularity to small networks whose structural communities may not align closely with class labels.Source: 2) Results for Real-World Data · p. 30, Table VII · p. 31, Table VIII · p. 31

Related papers

Loading 2609.34670v1…