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

Jun 23, 2026cs.LG

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

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.

Carlos Mundo-Levano, Nicolás Bello, Daniel L. Lau +1

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

Ask PDF

Oct 1, 2022cs.LG

Parametrized Power-Iteration Clustering for Directed Graphs

Vertex-level clustering for directed graphs (digraphs) remains challenging as edge directionality breaks the key assumptions underlying popular spectral methods, which also incur the overhead of eigen-decomposition. This paper proposes Parametrized Power-Iteration Clustering (ParPIC), a random-walk-based clustering method for weakly connected digraphs. This builds over the Power-Iteration Clustering paradigm, which uses the rows of the iterated diffusion operator as a data embedding. ParPIC has three important features: the use of parametrized reversible random walk operators, the automatic tuning of the diffusion time, and the efficient truncation of the final embedding, which produces low-dimensional data representations and reduces complexity. Empirical results on synthetic and real-world graphs demonstrate that ParPIC achieves competitive clustering accuracy with improved scalability relative to spectral and teleportation-based methods.

Gwendal Debaussart-Joniec, Harry Sevi, Matthieu Jonckheere +1

Universit´e Paris-Saclay, ENS Paris-Saclay, Centre Borelli, CNRS, France · CNRS, LAAS, France

Community Detection Clustering Graph Representations Spectral Decomposition Newton

Ask PDF

May 19, 2026math.NA

Graph Neural Networks for Community Detection in Graph Signal Analysis

Community detection is a central problem in graph analysis, with applications ranging from network science to graph signal processing. In recent years, Graph Neural Networks (GNNs) have emerged as effective tools for learning low-dimensional representations of graph-structured data and have shown strong performance in clustering tasks, particularly on large and high-dimensional graphs. This paper investigates the use of GNN-based community detection within a graph signal interpolation framework. After reviewing the main classes of GNN architectures for community detection according to a standard taxonomy, we integrate the resulting graph communities into a Partition of Unity Method (PUM) for interpolation with Graph Basis Functions (GBFs). In this approach, GNN-derived communities are used to construct local subdomains on which GBF interpolants are computed and subsequently combined into a global approximation. Numerical experiments on benchmark %graph datasets, including geometric and urban network examples demonstrate that the proposed combination of GNN-based clustering and GBF-PUM interpolation yields accurate signal reconstructions. The results indicate that deep learning-based community detection can provide effective graph partitions for localized interpolation schemes, supporting its use in scalable graph signal analysis.

Roberto Cavoretto, Alessandra De Rossi, Enrico Montini

Department of Mathematics “Giuseppe Peano”, University of Torino, via Carlo Alberto 10, 10123 Torino, Italy

Community Detection Graph Neural Networks Basis Functions Interpolation

Ask PDF