Given two weighted graphs $G = (V, E, w_G)$ and $H = (V, F, w_H)$ defined on the same vertex set, the constrained clustering problem seeks to find a subset $S \subset V$ that minimises the cut ratio between $w_G(S, V \setminus S)$ and $w_H(S, V \setminus S)$. In this work, we establish a Cheeger-type inequality that relates the solution of the constrained clustering problem to the spectral properties of $ G$ and $H$. To reduce computational complexity, we utilise the signed Laplacian of $H$, streamlining calculations while maintaining accuracy. By solving a generalised eigenvalue problem, our proposed algorithm achieves notable performance improvements, particularly in challenging scenarios where traditional spectral clustering methods struggle. We demonstrate its practical effectiveness through experiments on both synthetic and real-world datasets.

Permutation Entropy (PE) is a powerful nonlinear analysis technique for univariate time series. Recently, Permutation Entropy for Graph signals (PEG) has been proposed to extend PE to data residing on irregular domains. However, PEGis limited as it provides a single value to characterise a whole graph signal. Here, we introduce a novel approach to evaluate graph signals at the vertex level: graph-based permutation patterns. Synthetic datasets show the efficacy of our method. We reveal that dynamics in graph signals, undetectable with PEG, can be discerned using our graph-based patterns. These are then validated in DTI and fMRI data acquired during a working memory task in mild cognitive impairment, where we explore functional brain signals on structural white matter networks. Our findings suggest that graph-based permutation patterns in individual brain regions change as the disease progresses, demonstrating potential as a method of analyzing graph-signals at a granular scale.