Hermitian matrix method improves directed graph clustering and signal denoising
Hierarchical Clustering and Signal Denoising on Digraphs
Machine Learning
Summary
Grouping nodes in directed networks and cleaning noisy signals on them is a tricky problem. The authors create a new way to represent directed graphs using special matrices that capture both connections and directions of edges. They then use this representation to cluster the graph’s nodes into groups, organizing these groups in a tree-like hierarchy. Using this structure, they can break down noisy signals on the graph into simpler parts to remove noise and recover a cleaner signal. Their approach works well on various types of directed graphs and helps with tasks like clustering and signal recovery.
What this means in practice
- •For network analysts: Cluster directed networks to identify hierarchical community structures considering edge directions, enhancing analysis of complex network relationships.
- •For signal processing engineers: Denoise signals collected on directed graphs by decomposing them using multilevel splines derived from graph cluster hierarchies for improved recovery accuracy.
Authors
Yi Wang, Sippanon Kitimoon, Hrushikesh N. Mhaskar, Xiaosheng Zhuang
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.