Hierarchical Clustering and Signal Denoising on Digraphs

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

eess.SPSep 28, 2026

Hierarchical Clustering and Signal Denoising on Digraphs

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

Organizations: Department of Mathematics, City University of Hong Kong, Hong Kong, SAR China · Data Science Research Center, Faculty of Science, Chiang Mai University, Chiang Mai 50200, Thailand · Institute of Mathematical Sciences, Claremont Graduate University, Claremont, CA 91711, USA

Abstract

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.

Figures & tables

Panel of Figure 1 — Fig. 1: The top presents the original digraph and the hierarchical clustering results obtained with our algorithm using $\alpha(A+A^{T})+\beta(A-A^{T})\mathrm{i}$ . The bottom displays the corresponding rectangular partition of $I^{2}=[0,1]\times[0,1]$ , derived from the hierarchical structure of the trees above.

Fig. 2: Sensitivity of clustering performance to three key parameters

p,q,\eta

on DSBM graphs. The top panel varies the within-cluster probability

p

while fixing

q=0.0045

, producing graphs with increasing homophily ratios. The bottom panel varies the between-cluster probability

q

while fixing

p=0.0045

, producing graphs with decreasing homophily ratios.

Panel of Figure 3 — Fig. 3: Investigating the effect of $\alpha$ and $\beta$ : Model parameter sensitivity on different directed graph structures.

$\mathcal{M}$	Trains (%)	0 (USL)	10	20	30	40	50	60	70	80	90
	Level 2 (10)	0.2262	0.2505	0.2484	0.1880	0.1549	0.0923	0.0933	0.0327	0.0593	0.0330
Bi-Sym	Level 1 (5)	0.1524	0.0971	0.0848	0.3868	0.1712	0.2787	0.1995	0.0940	0.2439	0.0071
	Level 2 (10)	0.5171	0.5031	0.3864	0.1777	0.2956	0.1919	0.0829	0.0299	0.0415	0.0048
DD-Sym	Level 1 (5)	0.5305	0.2839	0.3454	0.2318	0.0751	0.0999	0.2017	0.1596	0.2086	0.1823
	Level 2 (10)	0.5192	0.3690	0.5065	0.3297	0.2122	0.1023	0.1046	0.0007	0.0012	0.0421
DI-SIM	Level 1 (5)	0.1281	0.3061	0.1822	0.3266	0.1528	0.1686	0.2333	0.1802	0.3917	0.0638

TABLE I: Clustering algorithms on the Wisconsin dataset: a comparative analysis of modularity (

\mathcal{M}

), and F-measure (

\mathcal{F}

). The best-performing model is highlighted in bold , and the second-best is marked with an underline .

Datasets	Bi-Sym	DD-Sym	DI-SIM	Herm	Skew	SpecHDC
telegram	0.91	0.95	0.47	0.89	0.89	0.97
blog	0.82	0.88	0.64	0.84	0.84	0.88

TABLE II: Clustering algorithms on the two unlabeled datasets: a comparative analysis of ARI (

\mathcal{A}

). The reported ARI measures clustering stability across repeated unsupervised runs. The best results are shown in bold , and the second-best are underlined .

Noise Level	Signal Pairs	Metrics	Cora	Cornell	Texas	Wisconsin	Squirrel
5%	$\bm{y}_{T}$ and $\bm{y}_{O}$	RMSE	0.0053	0.0078	0.0078	0.0068	0.0046
	$\bm{y}_{T}$ and $\bm{y}_{O}$	SNR	26.1595	26.4977	26.4977	26.3257	26.0635
	$\bm{y}_{T}$ and $\bm{L}_{2}+\tilde{\bm{d}}_{2}$	RMSE	0.0041	0.0056	0.0063	0.0044	0.0023
	$\bm{y}_{T}$ and $\bm{L}_{2}+\tilde{\bm{d}}_{2}$	SNR	28.2786	29.3331	28.3221	30.0617	31.9974
	$\bm{y}_{T}$ and $\bm{L}_{1}+\tilde{\bm{d}}_{1}+\tilde{\bm{d}}_{2}$	RMSE	0.0035	0.0056	0.0063	0.0044	0.0023
		SNR	29.6455	29.3331	28.3221	30.0617	31.9974

TABLE III: Denoising performance of graph signals under varying noise ratios, comparing raw corrupted signals with spline-smoothed reconstructions using multi-resolution hierarchical structures.

Datasets	Cora	Squirrel	Cornell	Wisconsin	Texas	Telegram	Blog
#Nodes, $\|\mathcal{V}\|$	2708	5201	183	251	183	245	5201
#Edges, $\|\mathcal{E}\|$	5429	217073	298	515	325	8912	19024
#Classes, $c$	7	5	5	5	5	-	-
Hom. Ratio, $\mathcal{H}$	0.3347	0.0854	0.1153	0.1325	0.0695	N/A	N/A

TABLE IV: Statistics of real-world directed graphs.

Fig. 4: Illustration of the asymmetric orientation pattern.

Fig. 5: The models’ performance is compared across varying numbers of nodes under three scenarios:

p=q

(left),

p\gg q

(middle), and

q\gg p

(right).

Fig. 6: The models’ performance is compared across varying numbers of clusters under three scenarios:

p=q

(left),

p\gg q

(middle), and

q\gg p

(right).

Panel of Figure 11 — Fig. 7: Performance comparison of the models across varying levels of $\eta$ under two distinct $F$ matrix patterns: (a) Circular Pattern and (b) Complete Meta-Graph.

Panel of Figure 12 — Fig. 8: Investigating the effect of $\alpha$ and $\beta$ : Model parameter sensitivity on different directed graph structures.

$\mathcal{M}$	Trains (%)	0 (USL)	10	20	30	40	50	60	70	80	90
	Level 2 (70)	0.4392	0.3759	0.3760	0.4318	0.4313	0.4651	0.5622	0.5964	0.6482	0.7083
Bi-Sym	Level 1 (7)	0.2624	0.2546	0.2233	0.2625	0.1476	0.2048	0.2752	0.3033	0.0907	0.0309
	Level 2 (70)	0.4983	0.4089	0.3501	0.4219	0.4076	0.4667	0.5405	0.5944	0.6365	0.7078
DD-Sym	Level 1 (7)	0.4789	0.3494	0.3652	0.3888	0.4120	0.3817	0.2040	0.4070	0.2990	0.1125
	Level 2 (70)	0.6091	0.4782	0.4076	0.4730	0.4436	0.4679	0.5671	0.6081	0.6464	0.7089
DI-SIM	Level 1 (7)	0.4456	0.4293	0.3047	0.2351	0.2629	0.2622	0.2127	0.2855	0.2282	0.1297

TABLE V: Clustering algorithms on the Cora dataset: a comparative analysis of modularity (

\mathcal{M}

), and F-measure (

\mathcal{F}

). The best-performing model is highlighted in bold , and the second-best is marked with an underline .

$\mathcal{M}$	Trains (%)	0 (USL)	10	20	30	40	50	60	70	80	90
	Level 2 (50)	0.1110	0.1043	0.0942	0.0934	0.0734	0.0730	0.0457	0.0426	0.0474	0.0518
Bi-Sym	Level 1 (5)	0.1365	0.1379	0.1328	0.2097	0.1385	0.2942	0.1899	0.1746	0.1866	0.2097
	Level 2 (50)	0.2289	0.2137	0.1929	0.2062	0.1400	0.1280	0.1172	0.0756	0.0606	0.0792
DD-Sym	Level 1 (5)	0.4736	0.2888	0.2644	0.1445	0.2056	0.1856	0.1916	0.1852	0.1686	0.0962
	Level 2 (50)	0.1743	0.1643	0.1409	0.1237	0.2747	0.0844	0.0753	0.0672	0.0511	0.0587
DI-SIM	Level 1 (5)	0.2091	0.2107	0.1437	0.1579	0.1681	0.1937	0.1546	0.1504	0.1160	0.0653

TABLE VI: Clustering algorithms on the Squirrel dataset: a comparative analysis of modularity (

\mathcal{M}

), and F-measure (

\mathcal{F}

). The best-performing model is highlighted in bold , and the second-best is marked with an underline .

$\mathcal{M}$	Trains (%)	0 (USL)	10	20	30	40	50	60	70	80	90
	Level 2 (10)	0.1615	0.1126	0.1359	0.0933	0.0814	0.0835	0.1410	0.0724	0.1280	0.1811
Bi-Sym	Level 1 (5)	0.0781	0.1328	0.0589	0.0954	0.1048	0.1523	0.0246	0.1480	0.0187	0.1809
	Level 2 (10)	0.2014	0.1592	0.1187	0.2003	0.1826	0.1282	0.2048	0.0779	0.0896	0.2090
DD-Sym	Level 1 (5)	0.0597	0.2724	0.2941	0.0461	0.2301	0.1811	0.3907	0.0608	0.0027	0.1023
	Level 2 (10)	0.3187	0.2820	0.4102	0.2320	0.1026	0.0637	0.1783	0.1409	0.1112	0.1924
DI-SIM	Level 1 (5)	0.1017	0.1436	0.3105	0.1153	0.1512	0.3072	0.0758	0.1284	0.0679	0.1857

TABLE VII: Clustering algorithms on the Cornell dataset: a comparative analysis of modularity (

\mathcal{M}

), and F-measure (

\mathcal{F}

). The best-performing model is highlighted in bold , and the second-best is marked with an underline .

$\mathcal{M}$	Trains (%)	0 (USL)	10	20	30	40	50	60	70	80	90
	Level 2 (10)	0.2244	0.1420	0.1308	0.1396	0.0791	0.1368	0.1125	0.0252	0.0166	0.0059
Bi-Sym	Level 1 (5)	0.1530	0.1084	0.1091	0.1560	0.1151	0.0090	0.1340	0.0426	0.0828	0.1817
	Level 2 (10)	0.3540	0.2166	0.1529	0.2291	0.0915	0.1632	0.1231	0.0240	0.0086	0.0051
DD-Sym	Level 1 (5)	0.2601	0.2492	0.2350	0.2553	0.0586	0.2800	0.3242	0.1634	0.1351	0.2755
	Level 2 (10)	0.3876	0.2241	0.2727	0.2515	0.2709	0.1580	0.1096	0.0043	0.0058	0.0017
DI-SIM	Level 1 (5)	0.3251	0.2191	0.1324	0.0864	0.1995	0.0180	0.1261	0.1324	0.2356	0.3472

TABLE VIII: Clustering algorithms on the Texas dataset: a comparative analysis of modularity (

\mathcal{M}

), and F-measure (

\mathcal{F}

). The best-performing model is highlighted in bold , and the second-best is marked with an underline .

Explore similar work

A Framework for Directed Hypergraph Signal Processing via tensor t-SVD
Jun 23, 2026Carlos Mundo-Levano, Nicolás Bello, Daniel L. Lau +1Hypergraphs Graph Edge Sparsification
Department of Electrical and Computer Engineering, University of Delaware, Newark, DE 19716, USA · Institute for Financial Services Analytics, University of Delaware, Newark, DE 19716, USA · Department of Electrical and Computer Engineering, University of Kentucky, Lexington, KY 40506, USA
Parametrized Power-Iteration Clustering for Directed Graphs
Oct 1, 2022Gwendal Debaussart-Joniec, Harry Sevi, Matthieu Jonckheere +1Community Detection Clustering
Universit´e Paris-Saclay, ENS Paris-Saclay, Centre Borelli, CNRS, France · CNRS, LAAS, France
Graph Neural Networks for Community Detection in Graph Signal Analysis
May 19, 2026Roberto Cavoretto, Alessandra De Rossi, Enrico MontiniCommunity Detection Graph Neural Networks
Department of Mathematics “Giuseppe Peano”, University of Torino, via Carlo Alberto 10, 10123 Torino, Italy

Jun 23, 2026, cs.LGJ/K move · Enter open · S save

A Framework for Directed Hypergraph Signal Processing via tensor t-SVD

Carlos Mundo-Levano, Nicolás Bello, Daniel L. Lau, Gonzalo R. Arce

Department of Electrical and Computer Engineering, University of Delaware, Newark, DE 19716, USA · Institute for Financial Services Analytics, University of Delaware, Newark, DE 19716, USA · Department of Electrical and Computer Engineering, University of Kentucky, Lexington, KY 40506, USA

Hypergraphs Graph Edge Sparsification Graph Signal Processing Singular Value Decomposition Fourier

Open paper AskPDF arXiv

We introduce Directed Hypergraph Signal Processing (DHGSP), a unified framework that extends graph signal processing to accommodate both higher-order (polyadic) and asymmetric (directional) relationships simultaneously. Using the tensor singular value decomposition (t-SVD) within the t-product algebra, we define a novel adjacency tensor for directed hypergraphs, a topologically faithful shift operator, and a lossless Directed Hypergraph Fourier Transform (t-DHGFT). Experiments on real traffic networks demonstrate that DHGSP outperforms matrix-based (graph and digraph) and undirected tensor-based (hypergraph) baselines in denoising tasks.

Abstract

Explore similar work

A Framework for Directed Hypergraph Signal Processing via tensor t-SVD

Parametrized Power-Iteration Clustering for Directed Graphs

Graph Neural Networks for Community Detection in Graph Signal Analysis