Signed Laplacians for Constrained Graph Clustering
Authors: John Stewart Fabila Carrasco
He Sun
Venue: ICML 2025 spotlightposter (2025)
Keywords: signed Laplacians
constrained clustering
Cheeger inequality
Primary area: general_machine_learning->clustering
TL;DR: we propose an algorithm that solves the constrained clustering problem with the signed Laplacians

Abstract: 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.

Signed Laplacians for Constrained Graph Clustering
John Stewart Fabila Carrasco He Sun
Abstract
domain knowledge is represented by two types of pairwise constraints: (1) MUST-LINK constraints, requiring that a pair of data points must be assigned to the same cluster, and (2) CANNOT-LINK constraints, requiring that a pair of data points must be assigned different clusters. In the context of graph clustering, the goal is to partition the vertices of graph based edge connectivity while satisfying the given constraints.
Given two weighted graphs G = (V, E, wG) and = (V. F, wH) defined on the same vertex set, the constrained clustering problem seeks to find subset C V that minimises the cut ratio between (S \ S) and wH(S, V \ S). In this work, we establish Cheeger-type inequality that relates the solution of the constrained clus- tering 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 solv- ing a generalised eigenvalue problem, our pro- posed algorithm achieves notable performance improvements, particularly in challenging scenar- ios where traditional spectral clustering methods struggle. We demonstrate its practical effective- ness through experiments on both synthetic and real-world datasets.
In this paper, we examine the constrained clustering prob- lem by formalising these constraints using the graphs G =
(V, EV, E,w) and = EV, 1.E",ii w"), in which every data point corresponds to graph vertex, every MUST- LINK (resp. CANNOT-LINK, constraint corresponds an edge in G (resp. H), and the edge weights capture the strength of the user's preference for satisfying the corre- sponding constraint. For any set S S V, we define the cut ratio of S between G and H by
w (S.V w (S.V\S)
( V V..V ()
(I)
and the objective is to find S that achieves
1. Introduction
$ min cut (S, V S). CCSCV
Clustering is fundamental technique in machine learning, with extensive applications across computer science and various scientific disciplines. The primary goal of cluster- ing is to partition data points into clusters, such that points within each cluster are more densely connected than those in other clusters. Traditional clustering, such spectral clus- tering (von Luxburg, 2007) relies solely on the structure of the data. However, in many real-world scenarios, additional domain knowledge is available, introducing specific con- straints that should be incorporated into the clustering pro- cess to achieve more accurate and meaningful results (Basu et al., 2008).
We develop an efficient approximation algorithm for the constrained graph clustering problem. The key to our algo- rithm is a Cheeger-type inequality that upper bounds &C with respect to A2 (A C and 22(A "), where
(x. A G x) A2 (A min
(2)
ril
(x, A A x))
(x. A "1 (I, xx)
Ao (A
min r11
(3)
and A and A are the Laplacian operators of G and H respectively. By introducing several techniques to adjust G and H, we significantly reduce the time complexity for solving the generalised eigenvalue problem, while maintain- ing the one-to-one correspondence between the solution of the reduced instance and the initial one. The empiri- cal studies on both the synthetic and real-world data sets confirm that with the two sets of constraints our algorithm presents significantly better performance than the classical spectral clustering algorithm, and the running time of our algorithm is close traditional spectral clustering methods.
Constrained clustering focuses on developing algorithms that effectively incorporate this domain knowledge to hance clustering performance (Wagstaff et al., 2001). The
'Scool of Informatics, University of Edinburgh, Ed- inburgh, United Kingdom. Correspondence to: He Sun <h.sun ad.u...>>.
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Signed Laplacians for Constrained Graph Clustering
Related work. Cheeger-type inequalities for constrained graph clustering studied in the literature. For example, Cucuringu et al. (2016) proved that &2 4% S 4 H); this inequality is based on a third graph K, which they call the demand graph. Koutis et al. (2023) showed that 2 S 16A2( A ()) (GG), where (G)) is the standard con- ductance of G. These two results cannot be directly com- pared with ours, since both inequalities upper bound H with respect 2² (²(A and parameters of H, i.e., Φ% in (Cucuringu et al., 2016) and (G) in (Koutis et al., 2023).
For Vo: Vi V, we denote the set of unoriented edges between Vo and Vi as E(V.. Vi) = {ur E E Vo and E ViJ. We denote by E, the set of all edges connected to v, and No the neighbourhood of v as the set of vertices adjacent to e, i.e., E. = F((u), V) and No = {u E V I y ~ uj. The edge weights on a graph determine a weighted degree of vertex, defined by deg(v) = w( = EeEE. We.
The Laplacian. We define some standard spaces related to finite and weighted graph G = (V,E) with weight function w. We define the Hilbert spaces (v(V, w) and (E,,w) as
In contrast, we upper bound &6 with respect to ( and (A) Trevisan (2013) studied the computational complexity of the problem and proved that under the Unique Games Conjecture, it's impossible to find a cut that achieves /
( (p: (E = {y: E RR..
approximation in polynomial time.
Our work also relates to the studies on constrained graph clustering from practical perspectives (Jia et al., 2021; Wang & Davidson, 2010; Wang et al., 2014) and signed cuts us- ing the signed Laplacian (Knyazev, 2017). Most of these studies, however, lack the rigorous analysis of the quality of the resulting clusters compared to the optimal solution. Our work is further linked to Cheeger-type inequalities for different graph Laplacians (Lange et al., 2015; Li et al., 2019) including the signed Laplacian (Atay & Liu, 2020), and their higher-order generalisations (Lee et al., 2014).
Furthermore, we consider the natural inner product for these spaces. For b w), the inner product between functions &p and & is defined (12, b)y =Erev (()))((() deg(v). For (E w), the inner product between functions 7 and & is defined as (n. E) = E.ee We Let G = (V, W, w) be weighted graph. The derivative d is defined as
d : (2(V, - - +2(Eww), (dæ)c=(u,)) = s(u) - ((v).
The adjoint d' : E2(E, w) - Eg (V, w) is given by
Contribution. We propose a novel method for constrained graph clustering that establishes Cheeger-type inequality explicitly linking the cut ratio objective to the spectral prop- erties of two graphs G and H. Our approach introduces a signed Laplacian- based implementation, which avoids addi- tional parameters while improving both numerical stability and computational efficiency. Finally, our experiments on synthetic and real-world datasets confirm the robustness and scalability of our algorithm, significantly outperforming standard spectral clustering under challenging scenarios.
(d' = deg(u)
Σ
Welle-
EEE.
The weighted Laplacian A (2) _ E2(V, w) is de- fined A d' d, and acts
(Ap)(t) deg(v)
Σ (v(1)) - (p())(()uuu Wan- WEN.
Let G (V, F, w) be a weighted graph, and for all yp e (V w) we have that
2. Background & Preliminaries
(9,, (g.0p)): = (g,ddddp)es (dp, (p))
Σ Idyuol 2 Σ -
We consider a finite, undirected graph G = (V, F),, where Vi is the set of vertices and E the set of edges. Each edge Wv E E denotes an undirected connection between vertices and v. A self-loop in this context is represented by wu, indicating an edge that starts and ends at the same vertex u. The notation u ~ v means that u and v are connected by an edge. We define weights in the graph G through the function w : E' + RR,, where Wee = Won specifies the weight of the edge between vertices u and v. By definition, each self-loop un contributes twice the degree of vertex
Graph Signature. A signature of a graph G = (V, E') is a map a E + (11,-1}, which assigns a sign to each edge. Let G = (V,E, E, w) be a weighted graph with a signature a. The signed Laplacian, denoted as A.. is a linear operator Ao (V, w) + (2 w), defined by
(A))) = deg(v)
1
Σ (p(t) - awwpp(u) MEN.
Wou. Wou-
For Ep C E, we interpret w as discrete measure on the cor- where Way is the weight of the edge uv, and Oue indicates the sign of the edge as given by the signature a. Observe that the Laplacian is particular case of the signed Laplacian by
responding sets, using the notation wi Eo)) = EnveE, Ep Wuy-
2

---

Signed Laplacians for Constrained Graph Clustering
taking Ouv for all edges and the signless Laplacian by taking O'ue -1 for all edges. The signed Laplacian can be viewed as special case of the magnetic Laplacian with discrete magnetic potential taking values in {0. The operators Aa (and therefore A) are positive, semi-definite, and self-adjoint, hence all of their eigenvalues are real and non-negative.
This choice of co guarantees that for the scaled graph G(eo), the degree of each vertex deg deg(lco)()) (v) I deg"(u) (v) for all E V. With this scaling factor co established, we now proceed to study the properties of the graph G (V, w) and its corresponding minimum cut value & in comparison to H = =VV E', w') under the assumption that deg (v) S deg (v) for all v E V.
V satisfies that
3. Algorithm& & Analysis
Equalising the Degrees of G. To further refine this com- parison, consider the subset of vertices
In this section, we present a constrained graph clustering algorithm called CC++. At a high level, our algorithm con- sists of the following: in the preprocessing step, we adjust the edge weights of G and add self-loops to the vertices of G, such that both of and H have the same degree se- quence. Then, we show that desired cut can be found by sweep-set algorithm when the eigenvector corresponding to generalised eigenvalue problem is given as input. Taking the practical implementation into account, we introduce negative self-loop in H for efficient computation, and justify its performance both in theory and in practice. Due to page limitations, proofs omitted from this section can be found in the appendix.
Vo= = { V deg legS(e (v) < deg (v)}
We now construct a new graph T = (V. E, w). where E- = E {(v, u)]uevo and the weight function w is defined by
deg (v) (eg"(r) deg G (v)
w == and Wer
Vu Vo-
Observe that the construction ensures that deg (v) = deg "f (v) for all v E V. Indeed, we have that
deg (v) = Σ
Σ
Wav + 2 Σ w(t, v)
Was =
u: ane
:: are
(1,00)
= -deg
G (v) + (deg" " (v) - deg G (v)) = deg " (v).
3.1. Preprocessing G and H
This modification of G demonstrates that, despite the ad- ditional restriction imposed by co. the problems remain equivalent. Specifically, we observe that
In the preprocessing step, our algorithm first scales the weights of all the edges in G by the same factor, and adds self-loops to the resulting graph G. These two operations ensure that the constructed graph G and И have the same degree sequence, while maintaining the optimal cut of the input instance.
(S. V S) min w W(S, V () WH (S.V
G min H
SCV w (S. SCV
Therefore, the generalized cut problem for G and remains equivalent to that of G and H, despite the degree adjust- ments made in G. The following remark will be used in our analysis.
Scaling the graph G. For any E Rt, we scale the edge weights of G by a factor of c and define G(c)- = (V, E, e-w),
where (c. x w)e = c We for each edge e. By (1), we have that
Remark 3.1. For the weighted graph G = (V, w). the pre- vious G = (V. É, w) where E includes additional selfs at some vertices, and any function o : V(G) = V(G) IR, the following holds: adding self-loops does not affect the quadratic form associated with the graph Laplacian, i.c..
(S V ()) =c w V (S) (S V S)
G(d) cut (S.
(S,V S))
= c. cut (S, V SS).
(e, 5) = (p, A²)) Specifically,
Thus, the minimum cut problem for the scaled graph can be expressed as
(p, Σ Isp(4) Fwv
G(d) c -6
Σ lp(u)= p(()) Tww = (1p, A w~ge
Pww
This equivalence indicates that choosing an appropriate seal- ing factor e is crucial for balancing the edge weights be- tween G and H. To ensure that the degrees of the vertices in the scaled graph G'(co) do not exceed those in H, we define the scaling factor co by
However, the addition of self-loops does affect the norm in the space of vertices:
(4,, se)e = Σ (()) dega(v)
vEV
H1 deg (v) deg (v)
S Σ (cgz()) = (4p, ())s()
min co
(4)
VEV
3

---

Signed Laplacians for Constrained Graph Clustering
Therefore, while the first quadratic form remains unchanged, the vertex norm in the extended space is generally increased due to the additional self-loops.
Step 2. We reduce the problem to proving (6) for scaled
version of æ; defined scaling ensures the invariance of the expression:
cr, where a + of 1. The
3.2. A Cheeger-type Inequality for Constrained Clustering
(2, 2z)) Az 2) (z, A2))
(2,2)
(rr ACx)
(x,
V
(1z,, A"x) V
(lr AHx)
Next we relate the constrained clustering problem to the generalised eigenvalue problem. Our key result is a Cheeger- type inequality proving that the value of &G can be upper bounded with respect to A @)
(z))
(x,2)
(x, Aa) V
(x,, A.
( and A² (). and the cut
with the proven approximation guarantee can be found by a sweep-set algorithm. Our result is as follows:
Thus, the next equation is sufficient to establish (6):
Theorem 3.2. Let G = (V, E, w) and H = EV, w²) be graphs such that deg deg((v) (v) = deg" (v) for all v E V. Then, holds that
GG (S, \S) wH (5, V 5) $V
(z, (z,)Oz) (2,z) (z, A A 2)2
D S VV A2(A"))
(5)
Step 3. We now consider sweep sets S,, defined as S, = {u E V Ev S t]. To establish (7), it suffices to prove that
where H denotes the normalised L Laplacian of the graph H, Ag is the operator given by
there exists a threshold tu E [21, 2nl and defining S S
(Sto V ( Sta) wH V V Sto)
(z,AGz) (z, (2)
(2,2)
(x) (x, x) (x. AT)
S
V
2z,
(8)
and Ag is the smallest non-trivial eigenvalue of the corre- sponding operator defined in (2). Moreover, the cut achiev- ing this approximation guarantee can be found with sweep- set algoritim.
Step 4. To establish (8), we will find probability density function over [2), =n). and prove
E [wa (S,, V (.)) E (wH (S,, V S.))
(z, (2) S 44 2z)
(9)
Notice that we can assume that G is a connected graph. If H has m connected components, we will work with Am-1(A (A ). i.e. x I 1c for each connected component, ensuring x 1. ker(A ). Before presenting the proof, no- tice that we can assume without loss of generality that the graphs G and H have the same degree sequence due to the preprocessing step.
Thus, (8) holds because the existence of a threshold to is guaranteed by the next equation:
we(S V StO)))
E (WG (St, V St))
<
WH ( V St.)
E (wHH(S (S,, V (s))
and this implies
Proof Sketch of Theorem 3.2. At high level, our proof is similar with the one of the Cheeger inequality for graphs. We present the proof sketch here, and the full proof can be found in Appendix A.
(G V ((D))) P
(z, (2, (z,
sAy (2,A²2) 2)2
0.
WH (Sto V V(aao)
Step 1.
Let 31 S 82 S ... S xy be the eigenvector associated with )² It suffices to prove the existence of a non-empty, proper subset S C such that
Step 5. To establish (9), it suffices to find a probability distribution over [21, 2n] such that
E (we V St))
wa (S V () WH( (S, V ()) = 4V
(x, A Gx) (x,x)
(6)
E (wH (St, V \ S))) DuNge 1zu
(z, A H N2)²
2 (1 + 120 Deae
(10)
This suffices because the above inequality implies
Eneov
Ey =ol? Way
2
b < S4 (2)
V(r,z) < 54 AVA2(A A²(A"))
1
Using the and the property deg (w) deg H
inequality, the definition of A.
V (z, x)
(v), we can derive (9)
4

---

Signed Laplacians for Constrained Graph Clustering
from (10) as follows:
Algorithm The Constrained Clustering Algorithm
Input: Graph G and graph H
Σ uniga
Fu
Zu| (|zul + (2ll) Woe
Output: A bi-partition of the vertex sets
Compute the scaling factor co defined in (4).
2v 2
Scale all edge weights in G' by multiplying them with co.
Wav
for each vertex v E V do if de (v) dega (v) then
Σ u
1zu Zol Wwe)
Σ
(lzul + 12v1)2 Way
Add loop with weight & (degg(()) (v) dega(v)). end if end for Compute the Laplacians G and A for the graphs G and H.
ungo
(z, AH
(z, A22 (2, A 2
$ 4
Solve the generalised eigenvalue problem
(f,4f) ff
Thus, finding a distribution that satisfies (10) is sufficient to complete the proof.
subject to f 1 1,
(11)
Step 6.
We define a distribution, and choose according to the probability density function 2| Specifically, the
where f the eigenvector that minimises the ratio. Apply a sweep-set algorithm on the eigenvector f to partition the vertices of G into two clusters. Return: a bi- bi-partition of the vertex set
probability that value between [a. b] is chosen is
2/t|dt = (2.) 2 sgn( (z) 2g. f 2o
Plt E [Bv:Zul] =
graph with was = 1 for all edges, then it is straightforward to show that
Since 27 2/ = 1, we have that Pit E [,,, 1.
Wo V S) BCSCV IS| V ST S 4/>2
Step 7. For this distribution, and regardless of the sign of Zu and R.o we have
min
where (2 is the second smallest eigenvalue of the normalised graph Laplacian of G. Similarly, if we consider the graph H = (V, E', w as the complete graph with self-loops where w deg" (x) "
E (S,, V [()]==
Σ Plz S f and t < 2o] Wae
u
Σ
1zu - 201(1zul + D2ol)
then
Gol()
u
min wG V S)
and
# CCSCV min(vol(S), vol(V \ SS)
Gol(G) wG V \S)
E (S, V (S))= = Σ
pl < t and t < 2n] Wae
s min
#CSCV
vol(S) vol(V (S)
< 4 A2(A
2u
2z
Wav.
2
3.3. Practical Considerations
The proof of Theorem 3.2 not only establishes the general cut bound but also provides a constructive method to find a subset S S V that is close to minimising the generalised cut problem. However, this approach can be computation- ally expensive, particularly because the Laplacian H not invertible. To address this issue, we modify the graph I by adding "negative" self-loop any vertex, effectively making the Laplacian invertible. This modification lever- ages the signed Laplacian, which adjusts the operator to ensure invertibility, and the introduction of a negative self- loop has little impact on the overall results, which will be demonstrated in Section through experiments.
This establishes (10) and concludes the proof. The complete details are in the appendix.
D
Based on the proof of Theorem 3.2, to find the cut with the guaranteed approximation, we only need to order the vertices based on the entries of the cigenvector for the gener- alised eigenvalue problem, and construct sweep sets. See Algorithm for the formal description of our algorithm.
Remark 3.3. Theorem 3.2 can be viewed as a generalisation of the classical Cheeger inequality for graphs (Chung. 1997). Specifically, if we consider the graph H the complete
5

---

Signed Laplacians for Constrained Graph Clustering
Formally, we prove that adding a negative self-loop to H makes the signed Laplacian A# invertible, ensuring (A > O. Since A ( S ))) we can replace A2(A") " with A1 (1 in Theorem 3.2, maintaining the theorem's validity.
and invertible. For dense matrices, this property allows for the use of the Cholesky decomposition, reducing the problem to standard eigenvalue problem (Saad, 201 1), This is an improvement over the general case for the QZ algorithm (the generalised Schur decomposition). Moreover, the Cholesky decomposition enhances numerical stability, leading to fewer round-off errors. For large, sparse graphs and positive definite operators, iterative methods such as the Lanczos algorithm could be used. The complexity of these solvers is ((kkm), where A is the number of eigenvalues to find and related to the iterations required for convergence and the condition number.
Lemma 3.4. Let H= = (V, F, w) be a weighted graph, and let H' = (V, E', w²) be another weighted graph such that E' = U {1V., vo)}. where Up is a vertex with a self-loop. Assume that w'le = w and consider the signature s for all E and 200 = -. Then,
<<>A S )²
where A is the Laplacian of graph H.
4. Experiments
The proof of Lemma 3.4 shows that (g. A.' 9) (g. 9 for a small weight in the self-loop, then we will solve (11) for the self-loop, because
We conducted experiments to compare the spectral cluster- ing method with the constrained clustering approach, using both synthetic and real-world datasets. The clustering accu- racy was evaluated using the Adjusted Rand Index (ARI). All simulations were run on a PC equipped with an Intel@) CMre 17-10610U CPU running at 1.80 GHz and 32 GB of RAM, using MATLAB R2024a for computation. The three clustering algorithms compared in our experiments are as follows:
(f, A (1 (H (
The problem involves identifying the eigenfunction and eigenvalue of a linear operator using a Lagrangian-based framework. The Lagrangian [(p,, A) is defined as
A) = (A p. pp 2((1 sp) - 1),
SPECTRAL CLUSTERING (SC): We computed the nor- malized Laplacian A and used its second smallest eigen- vector (Fiedler vector) for clustering the vertices.
where y is the function to be optimised, and À is the La- grange multiplier. To find the minimiser yp, we set the
CONSTRAINED CLUSTERING (CC): We solved (11) and used the eigenvector corresponding to the smallest posi- tive eigenvalue (excluding the trivial zero eigenvalue) for clustering.
gradient of L with respect to yp to zero, i.e., Ve X) = 0. Expanding this condition yields that 2 2 4p- = 0, which simplifies to A A AA! sp. This formulation leads to generalised eigenvalue problem where yp is the eigen- function, and À is the eigenvalue. If A is invertible, the equation can be reformulated as
CONSTRAINED CLUSTERING WITH NEGATIVE SELF- LOOPS (CC++): Our algorithm consisted in adding negative self-loop and solved (11) for the signed Lapla- cian.
(A H1 ) AA'AAp=
illustrating the relationship between the linear operators and providing solution to the eigenvalue problem via the Lagrange multiplier method. This eigenvalue equation is crucial for extracting the optimal partitions of the graph based on the constraints encoded within A We prove that solving the generalised eigenvalue problem for A G and Al' produces all feasible solutions, as eigenvalues are real and non-negative. This contrasts with the approach by Wang et al. (2014).
4.1. Stochastic Block Model
We considered binary Stochastic Block Model (SBM) with n = 1, 0,0 vertices divided into two equal-sized commu- nities. Edges between vertices were generated based on intra-cluster probability p and inter-cluster probability q. Specifically, we fixed p = 0.2 and varied from 0.12 to 0.2 in 30 equidistant steps. For each value of q, we generated two graphs generated from the SBM:
Lemma 3.5. Let AH' be the signed Laplacian of the weighted graph H', and A the normalized Laplacian of the weighted graph G. The operator (A is posi-
G: a graph with intra-cluster edge probability p and inter- cluster edge probability q-
tive, self-adjoint operator, with all its eigenvalues being real and non non-negative
H: a graph generated with intra-cluster edge probabil- ity q and inter-cluster edge probability p. effectively the complement of G in terms of edge probabilities.
We remark that solving (11) becomes significantly more efficient for H' because it symmetric positive definite
The vertex labels were kept consistent between and H.
6

---

Signed Laplacians for Constrained Graph Clustering
This variation allows us observe how the clustering per- formance changes as the distinction between communities becomes less pronounced (since higher g implies more inter- cluster edges). The experimental results, visualised in Fig- ure 1, illustrate the superior performance of CC++ com- pared to traditional SC, particularly as the inter-cluster edge probability y increases.
Mean ARI q with Error Bars
Adjusted Rand Index (ARI)
0.9
0.8
0.7
0.6
0.5
CC++
At low values of q both methods perform well, achieving near-perfect ARI values. As seen in Figure 1, both methods maintain the ARI values close to 1.0 when y S 0.14. This is expected, as the strong intra-cluster edge probability p 0.2 dominates the inter-cluster connections, making the community structure relatively easy to detect.
0.4
CC
SC
0.12
0.14
0.15
0.16
0.17
0.18
0.18
Inter-cluster Edge Probability (q)
However, as q increases, the performance SC deteriorates rapidly. For instance, between q 0.16 and q 0.18, the ARI for SC drops sharply from approximately 0.7 to near 0.1. This decline occurs because higher values of y increase the number of inter-cluster edges, blurring the distinction between communities. SC relies solely on the structure of G. and struggles to correctly partition the vertices under these conditions.
Figure I. Mcan ARI versus inter-cluster edge probability with error bars. CC (red) and CC++ (blue) consistently outperform SC (yellow). especially as g increases.
each containing 500 points, randomly distributed within two-dimensional circular regions (disks) of radius 0.2. The separation between the clusters' centroids varied between -0.35 and 0.35, in 25 equidistant steps. This range allows us to simulate different levels of overlap between the clusters. Each configuration of cluster separation was repeated 10 times, and we generated G and H on the same set of vertices but with different connectivity structures:
In contrast, both of CC and CC++ significantly more robust to increasing q. Even q approaches 0.17, the ARI remains above 0.5, significantly outperforming SC in this regime. This robustness stems from the ability of the generalised eigenvalue method to leverage the structural information of both G and H, the method mitigates the negative impact of increased inter-cluster edges, thus main- taining better clustering accuracy even when the community structure is less pronounced.
G: vertices within the same cluster were connected with a large radius Tintr = 0.1, and vertices between clusters were connected with a smaller radius Tinter = 0.05.
This set of experimental results clearly demonstrates that the CC++ algorithm outperforms the traditional SC, partic- ularly in challenging scenarios where the inter-cluster edge
H: the intra-cluster connection radius is reduced to Tintr 0.05, while the inter-cluster radius is increased to Tinter = 0.1. Edges more likely connect vertices across the two clusters
probability q is high.
Figure 2 compares the mean execution time of SC, CC, and CC++ the number of vertices increases. For smaller graphs, CC++ has nearly the same runtime as standard spectral clustering (SC), indicating minimal overhead from incorporating the second graph's 's constraints. As the graph size grows, however, CC++ clearly scales more efficiently than the original CC: the runtime of CC++ increases only modestly with n, remaining close to SC's runtime, whereas CC's runtime rises sharply. This demonstrates that CC++ retains the computational efficiency of SC while handling larger graphs far more effectively than CC, underscoring its superior scalability.
Figure 3 shows the RGG used in the experiments. The clus- ter distance varied to simulate different levels of overlap between clusters. Figure 4 shows the ARI scores for both methods across different cluster distances. Each point repre- sents the mean ARI, with error bars indicating the standard error across 10 repetitions.
When the cluster distance is large (above 0.3), both methods achieve near-perfect ARI values. The separation between the clusters clear, and both algorithms can detect the un- derlying structure accurately. As the clusters get closer, SC shows significant drop in performance. For distances near zero, where clusters overlap. the ARI scores for SC drop to nearly zero, indicating its struggle to differentiate overlapping clusters. In contrast, the generalised eigenvalue method is more resilient to cluster overlap, maintaining sig- nificantly higher ARI values even when the clusters become indistinguishable by conventional means. This robustness
4.2. Varying Cluster Distance
Based on the (RGG) (Avrachenkov et al., 2021; Dall & Chris- tensen, 2002), we generated two clusters of vertices,
Geometric Random Graphs
7

---

Signed Laplacians for Constrained Graph Clustering
Mean Execution Time vs Number of Vertices
Mean ARI vs Cluster Distance with Standard Error Bars
60
CC
0.9
Mean Execution Time (seconds)
CC++
50
SC
0.5
Adualed Rand (ARI)
0.7
40
0.5
0.5
30
80
0.4
0.3
20
10
0.1
0.3
-0.2
-3.
0.2
0.3
08
Cluster Distance
1000
1500
Number Vertices
Figure 4. Comparison of ART vs Cluster Distance SC, CC, and CC++.
Figure 2. Mean execution time versus the number of vertices. The plot shows that CC++ (blue) performs similarly to SC (yellow) for smaller graphs but scales more efficiently than CC (red) the number of vertices increases.
factors.
We construct graph from the input data follows: every station is represented as vertex, and the edge weight is defined by spatial similarity via Gaussian kernel: Wij
disaance of dusters
a(t.j)² if d(i.j) S o2, and 0 otherwise, where d(i.j) is the Euclidean distance. Parameters were set to of x 10 and 02 = 10 (Girault, 2015). SC primarily grouped stations by proximity (Figure 5a).
exp
20
To construct the constraint graph H, we the tempera- ture values and an inverse Gaussian kernel, assigning edge weights close to for large temperature differences and 0 for similar temperatures, analogous to how G is built using spatial proximity. This allows the clustering algorithm to in- corporate both geographical and temperature constraints for more nuanced partition. The output of CC++ is shown in Figure 5b, where only two cities differ from the clustering based on spatial proximity alone (SC). Finally, we com- pute the mean and standard eтror (SE) for every clustering method. For this specific hour, SC shows overlap between clusters' temperature values, whereas CC++ achieves no overlap, indicating better clustering stations with similar temperatures (Figure 5c).
Figure 3. Clusters generated by a RGG with varying separation.
is due to the method's ability to leverage information from both graphs G and H, capturing both intra- and inter-cluster relationships.
4.3. Experiments with Temperature Data
OC+.
We evaluated SC and CC++ on real-world temperature data from ground stations in Brittany, January 2014 (Girault, 2015). The experiments considered three data types: tem- perature, maximal temperature. and minimal temperature. Temperature values can be seen as graph signals (Ortega al., 2018), with vertices representing readings. The objec- tive is to cluster stations by proximity and similar tempera- ture patterns, combining spatial and temperature data. This approach can be applied to identify micro climates (Cao et al., 2021) and segment regions for agricultural (Yao et al., 2022), where both location and temperature are important
Temportuurg
Dunker
Gureer
Longtade
50
CCH
Figure 5. Clustering based SC, grouping stations by geo- graphical proximity. (b) Clustering using CC++, which considers both location and temperature similarity.
(c) Mean and SE of tem- perature, illustrating no overlap for CC++ compared to SC.
8

---

Signed Laplacians for Constrained Graph Clustering
We repeated this process for all available measurements, per hour, across 24 hours over 31 days, totaling 744 observations. To evaluate clustering accuracy, calculated the mean and SE for clustering using both methods. A separation was considered correct if the clusters' values did not overlap, as determined by their SE. Table summarises the results, showing the percentage of correct separations for each temperature data type when comparing SC and CC++, and demonstrates that CC++ consistently outperformed CC across all temperature data types. This can be attributed to the method's ability to leverage both the spatial structure of the stations and the actual temperature data. In contrast, SC, which relies solely on the graph structure, struggled to accurately separate stations into distinct clusters when the temperature differences were subtle.
specifically highlighted here.
Acknowledgements
This work is supported by EPSRC Early Career Fellowship (EP/T00729X/1).
References
Atay, F. M. and Liu, S. Cheeger constants, structural bal- ance, and spectral clustering analysis for signed graphs. Discrete Mathematics, 343(():111616) 2020.
Avrachenkov, K., Bobu, A., and Dreveton, M. Higher- order spectral clustering for geometric graphs. Journal of Fourier Analysis and Applications, 27(2)222, 2021.
Table 1. Percentage of successful separation of regions using tem- perature and location data.
Basu, S., Davidson, I., and Wagstaff, K. Constrained clus- tering: Advances in algorithms, theory, and applications. Chapman and Hal//CRC 2008.
Data Type
SC
CC
CC++
Temperature
63.30%
79.16%
79.16%
Cao, J., Zhou, W., Zheng, Z., Ren, T., and Wang, W. Within- city spatial and temporal heterogeneity of air temperature and its relationship with land surface temperature. Land- scape and Urban Planning, 206:103979 2021.
Maximal Temperature
62.90%
80.91% %
81.04%
Minimal Temperature
62.63%
79.16%
77.95%
5. Conclusion
Chung, F. R. K. Spectral Graph Theory, American Mathe- matical Society, 1997.
In this paper, we introduced a novel spectral method for the constrained clustering problem that incorporates MUST- LINK and CANNOT-LINK constraints on the same vertex set. We established Cheeger-type inequality that provides a theoretical approximation guarantee, relating the optimal constrained cut value to the spectral properties of the graphs. Building on this insight, we proposed efficient algorithm (CC++) that solves generalised eigenvalue problem in- volving the signed Laplacian of the constraint graph, which significantly reduces computational complexity while main- taining accuracy.
Cucuringu, M., Koutis, I., Chawla, S., Miller, G., and Peng, Simple and scalable constrained clustering: gen- eralized spectral method. In Artificial Intelligence and Statistics, pp. 445 454,,54, 2016.
Dall, J. and Christensen, M. Random geometric graphs. Physical review E, 66(1):01611,, 2002.
Girault, B. Stationary graph signals using an isometric graph translation. In 2015 23rd European Signal Processing Conference (EUSIPCO), pp. 1516-1520, 2015.
Empirically, CC++ demonstrated superior clustering per- formance on both synthetic and real- world datasets, partic- ularly in challenging scenarios with weak noisy cluster structure. It also achieved runtime comparable to standard spectral clustering (SC) and scaled much better than the original constrained clustering method (CC). These results highlight the significance of our proposed CC++ method as principled and practical solution for constrained graph clustering, bridging the gap between theoretical guarantees and scalable real-wort sal-world performance.
Jia, Y., Hou, J., and Kwong, S. Constrained clustering with dissimilarity nopagation-guidee graph-laplacian pea. IEEE Transactions on Neural Networks and Learn-
ing Systems, 32(9):3985-3997, 2021.
Knyazev, A. V. Signed Laplacian for spectral clustering revisited. arXiv preprint arXiv:1701.013344 1, 2017.
Koutis, I., Miller, G., and Peng, R. A generalized Cheeger inequality. Linear Algebra and its Applications, pp. 139 152, 2023.
Impact Statement
Lange, C., Liu, S., Peyerimhoff, N., and Post, O. Frustration index and Cheeger inequalities for discrete and contin- uous magnetic Laplacians. Calculus of variations and partial differential equations, 54:4165-4196 2015.
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none of which we feel must be

---

Signed Laplacians for Constrained Graph Clustering
Lee, J. R., Gharan, S. O., and Trevisan, L. Multiway spec- tral partitioning and higher-order cheeger inequalities. Journal of the ACM (JACM), 61(6):1-30, 2014.
Li, H., Sun, H., and Zanetti, L. Hermitian Laplacians and Cheeger inequality for the Max-2-Lin problem. In 27th Annual European Symposium Algorithms, pp. 71:1- 71:14, 2019.
Ortega, A., Frossard, P., Kovačević, J., Moura, J. M., and Vandergheynst, P. Graph signal processing: Overview, challenges, and applications. Proceedings of the IEEE, 106(5):808-88) 828, 2018.
Saad, Numerical methods for large eigenvalue problems: revised edition. SIAM, 2011.
Trevisan, L. Is Cheeger-type approximation possible for nonuniform sparsest cut? CoRR, abs/1303.2730, 2013.
von Luxburg, U. A tutorial on spectral clustering. Statistics and computing,
2007.
Wagstaff, K., Cardie, C., Rogers, S., Schrödl, S., et Con- strained k-means clustering with background knowledge. In ICML, pp. 577-584, 2001.
Wang, X. and Davidson, I. Flexible constrained spectral clustering. In Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 563-572, 2010.
Wang, X.,
Qian, B., and Davidson, I. On constrained spec- tral clustering and its applications. Data Mining and Knowledge Discovery, 28:1-30. 2014.
Yao, Y.-D., Li, X., Cui, Y.P., Wang, J.-J,, and Wang, C. Energy-efficiens routing protocol based on multi- threshold segmentation in wireless sensors networks for precision agriculture. IEEE Sensors Journal, 22(7))6216 6231, 2022.
10

---

Signed Laplacians for Constrained Graph Clustering
A. Omitted Details from Section 3
This section presents the details omitted from Section
Proof of Theorem 3.2. Our objective is to prove that
22 A
$ S 41
(12)
Step 1. Let V R be the eigenfunction associated with ( Without loss of generality, we renumber the vertices such that the coordinates of satisfy I1 I 22 ... Zn. It suffices to prove the existence of non-empty, proper subset 9 C S C V such that
(G V (5 wH (S, {S =1V
(r, ACx)) (x. (z, A x
(13)
This is sufficient because
$ - (S V \ ()) (H V (5
(Definition of 43 the minimum ratio cut)
(x, AGx)
x))
VV (or, A
| (rrAHR
(By (13))
V(e,z)
=4V )2(A
(Using xr is the eigenvector of )z(A
(z, A
1
(x, x))
S 4 (2
(Since
(I, 2 ))(
A²(A")
This inequality proves that establishing (13) suffices to derive (12).
Step 2. We now show that proving (13) for is equivalent to proving the existence of S such that
wG (S, V (S) wH (S, V (() = - (2,A"2)² 2)2
(z,
(14)
where is scaled version of xr defined such that =? + =f = 1.
Because x I 1, we have
< 0 < Wns and thus scaling x does not affect the ratio. Specifically,
(2, Az2
(2,2)
(lx, ACr) 2(2,z) V 2(2, Azz) A(x
(x. Azx)
(x, x)
(z, 22)
(2, 2))
|
(x, Ax))
Thus, proving (14) suffices to establish (13).
Step 3. Let E R, and define the set
S (u E 2 S}},
commonly referred to as sweep set. To establish (14), suffices to prove that there exists threshold f, such that
(a V V.St)) < (S V St..)
(2,
(2,2)
(15)
(2) V (2,A"2)
Establishing Stg= (15) directly implies (14).

---

Signed Laplacians for Constrained Graph Clustering
Step 4. To establish (15), suffices show that there exists distribution f(() over (21, zn] such that the expectation satisfies
E (S V | S:)) E (ww (Sc, V St)) S 4V
(z, (2, (z, 2)
(16)
Here, S, is treated as a random variable parameterized by E [21, where drawn from probability density function f(t). S, depends on the distribution which influences the likelihood of including a vertex v in S, based on its value 2..
This suffices because, if we define
E (wa (St, V St))
4 = E (wH (St, V S:)) E IR
then, by linearity of expectation it holds that
[we(S V St) & wH V S:] = E [wo (St V \SS)) St) p [e[ V (S(]] = 0.
This implies that for some to:
P (St, (V wunn V St,) s > 0.
(17)
because for all we have would follow that wa wa(S, (St, V St) - y wn V S;) > 0 for all f, contradicting the fact that
P (St V \ St) 8 w (S., V (. - 0 = 0,
E (S: V 5.) wn (St, V St)] = 0.
Thus, (17) holds, which implics that for some to we have
we V \ Sto) - 4 ( V Sta) S 0,
and equivalently
WC V Vl 1(,))
E E(wa Sr, V 8,))
<
WH (Seg V St,.)
E ( Se, \ S)))
Combining this with (17), obtain that
(St. V(S,,)
E (wa (t. V S:))
<
E (wH( (Se, V S))) > 0.
WH (Seo V Sta)
From Eq. (16), follows that
wG (Sto V \1500 Sto)
(2, (2) 2) (z, A 2)2
I
<
> 0.
WH St., V Se,)
Establishing (16) thus guarantees the existence of satisfying (15).
Step To establish (16), it suffices find a probability distribution over [21, 2n. such that the following inequality holds:
E (St. VV (())
E Eungo 1eo 2 1 12 Dwav
<
(18)
E (w (S₁, V S))
Enego 2 Way
1=.-
12

---

Signed Laplacians for Constrained Graph Clustering
We now show that (18) implies (16) follows:
(we (St, V \ St)) E (WH (St, V St))
E Eurar 1zu
20 200(12ul + (20
(By (18)
Enrgy
1z--z,
Wuv 2
Euwan 12m 2ul2uau
Σ nnroo (1zul + 12y 2wwe
inequality)
Euagr
lsu 1 12
Wav
2
V (2)) V
Euvou I + |Zee 1e Wiv
(Definition of A A
Σ Enwwo
2
Wuv
(2, V 2 Eumor (22 + 22) Weo
(Since (a + +)² + 2 +)))
Wmo Euwyr I/u 30
A2,) 2) V4(Z 2)
(Definition of the inner product in G)
Σ Eungr
By -u Wav
2
(2, A22
2 (2, 2)
(Definition of A
(2, AH 2)
(2, A22) (
$41
(Since deg deg" "l (v)).
22)
Thus, (18) implies (16).
Step 6. Consider the non-negative function 2/6| defined on the interval [21, This function serves probability density function (PDF) over (z1, Zn] because =î z 1, is negative, and 2, is positive. Specifically,
2 dt sgn(zn) 2 sgn(z1) 27 = 1.
The normalization in step 2 ensures that the integral of 2/1/ over 2n] equals 1, validating it as PDF Hence, the probability that a value between [Zus ze] is given by
P [Ze, zull = f
2/t]dt sgn(zu) 2 sgn(2x) 2
The expectation E (S V \ S.)] threshold t sampled from the previously defined probability density function. By the linearity of expectation holds that
represents the expected weight of the cut wa V),,), which depends on the random
E [wa(S,, V [S..]
Σ u
E [lues, and sgs, Wav:
where 1ues, and vgs, is the indicator function that equals 1 when a E S, and v & S,, and 0 otherwise.
Using the definition of probability, the expectation simplifies to
E (w V S.]] - Σ Plzu S t and t 20] Wov-
we can establish
Za 2
2 << P [2, < and < 20] $ (1zal + 12.1)/z0 - 2ul-
(19)
13

---

Signed Laplacians for Constrained Graph Clustering
then bound the expectation of the weight of the eut as follows:
E (w V (S)] ك Σ (1zul + 120 - Zz War.
um-g
Similarly, for H, we have
E (s V
Σ Plz. S t and < 2p] Wuv 2
Σ 12x Zol Wul
These last two inequalities establish (18). Therefore, to conclude the proof, it remains to prove (19). Step 7. To prove (19), recall that
Az 2/t| dt
= 2 if sgn(2z) = sgn(z.),
&2 S t and < 2p1 =
2 + 2 if sgggg(a (2a) + sgn(zz))
Fu
We first establish the upper bound in (19):
P [zu l and < zul (|zu| |zol)]zu -z0l-
(20)
Case 1: sgn(2u) sgn(ze). In this case, have
201 -
(zu + zy (2 2,)l 1zm z0|1zz Z
Since 1zu 2ol //2u1
12o1, we have
12 201 S (12ul + 12e1))2 -zol.
Case 2: sgn(zu) # sgn(ze)- In this case, we have
Zu Zu < (Zu zv02 = 1žz Zv ?
and thus
2 + 2 < (1 + 1201)22 - 2u1-
Combining both cases establishes the upper bound in (20). Now, we establish the lower bound (19):
Zu
Ze 12
P
|zu and =
(21)
Case 1: sgn(zu)= = sgn(zo). In this case we have
>
z = =|2
zn| Izn + nn
Since |zu + zol 2 1za - zu/o we have
(2u 2x
12 2
1zu - 2x 2 >
Case 2: sgn(zu) & sgn(zo). Using
0 < (zu + z0)2 =2(02 + +²) - (Zzs - )
follows that
(zu - )2
< 2 +
2
2
Combining both cases establishes the lower bound (21).
Finally, combining (20) and (21) proves (19), completing the proof.
14

---

Signed Laplacians for Constrained Graph Clustering
Proof of Lemma 3.4. Let be the eigenfunction corresponding A2(A Consider the function g : V IR, defined as: Do Jo Swo: for all E V, hence Goo 0. By computing the Rayleigh quotient for g with respect the Laplacian of
H:
H ,)
Σ 19h. gol Wwwe
Σ 15u Sol >2 W.
The Rayleigh quotient for 9 with respect to A !1' is given by
(g, A H H)
Σ
1ga gol wul + 2/ 3 Wooooo = Σ 1 Sul:unr (g, A g)H.
The norm of g with respect to H' satisfies that
H. = Σ
gel deg
(v) = Σ
1arl deg (v) + (degn(()))) +2) = =( H)
NEV
Thus, we have, since f is eigenfunction f + 1, hence 0 (f.1)
(9.9)
Σ 1s. Sool deg H (v) (J.S - 25 1).1 + (1, (1.1)n 2 (1,S
VEV
Using this, we apply the Rayleigh quotient to bound Y1 (1 as
(g. A H' 9)
(g. A H g)
( >2(A
A
(g.9)
(g. (1.9)
USSSH
Finally, let f be non-zero function. Consider the following expression:
( f)
Σ 1f - wol + 2f Wepvp-
We have S (f, A f), and equality holds if and only if: (J, = - Sa So Vu, v and Svo 0. This implies that 0 for all v V, which contradicts the assumption that f non-zero function. Therefore, (A H >>> 0.
Proof of Lemma 3.5. Since A is positive-defintt and self-adjoint, its inverse (A and its square root )1/2 exist and are self-adjoint operators. Define the operator C' as
C= -1/2 1/2
Self-adjointness of C: The adjoint of C' is
C ) ) -12"))=1"(
= (A 1/2 " (A
1//2 C,
1/2
since H! and G are self-adjoint operators. Positive Semi- defiiiefintteness of For any function yp (V, w), consider
(C(,,)) = ((4 - (A -
Let & = ) Then, (Cp, sp) = (ACh,e)) wt Since A is positive semi-definite, we have (A 1)) 2 0. Therefore, (C4, xp 0, which means C is positive semi-definite
15

---

Signed Laplacians for Constrained Graph Clustering
Because C' is self-adjoint and positive semi-definite, it is diagonalizable with real, non-negative eigenvalues. Thus, there exists an orthogonal matrix W and diagonal matrix with non-negative entries such that
C= WAW".
We express
- as
(A A - -AA ( (4"")""" (A )1/
H' y1/2 -"W" (A = ) -
Let V = -A --/2 Then,
t ) = - VVV*
Since V is invertible (as the product of invertible matrices), ues. This completes the proof.
is diagonalizable with real, non-negative eigenval-
B. Additional Experiments from Section
In this section, we present additional experiments to evaluate the performance of our algorithm. To provide comprehensive analysis, we include comparisons with the following method
FLEXIBLE CONSTRAINED SPECTRAL CLUSTERING (FC): This method is presented in Wang Davidson (2010).
As in Subsection 4.1, we evaluate the performance of clustering methods using synthetic graphs generated by the stochastic block model (SBM). We analyse the algorithms for graphs varying sizes, focusing particularly on smaller graphs, where subtle variations are more prominent. For larger graphs, the performance trends tend to stabilize and exhibit fewer differences. In these experiments, graphs were generated with the number of nodes varying across four sizes: 250, 500, 750, 1000.
The results are summarised in Figure 6, which illustrates the performance of the four clustering methods- Clustering (SC), Constrained Clustering (CC), Constrained Clustering with Self-loops (CC++), and Flexible Clustering (FC) for varying inter-cluster edge probabilities g and different graph sizes.
Based on the results presented in Figure 6, we highlight the following key observations and advantages of our method compared to the baseline approaches:
Smaller Graphs: Our method demonstrates superior performance smaller graphs (n 250, in terms of the mean Adjusted Rand Index (ARI), shown in panels (a) and (b). As the graph size increases 750 1000), the performance of our approach becomes comparable to that of the other methods, indicating that our algorithm is robust across different graph sizes.
Improved Performance
Parameter- Free Advantage: The Flexible Clustering (FC) method presented in Wang & Davidson (2010) requires the user to define an additional parameter (3) that directly influences the solution of the generalized eigenvalue problem. This parameter must be carefully chosen to ensure at least one feasible solution exists, incorrect parameter selection can result in negative eigenvalues and infeasible outcomes. In contrast, method avoids this issue entirely. As shown in Lemma 3.5, the -' is positive and self-adjoint, with all eigenvalues guaranteed
introduction of self-loops ensures that the operator (A! A to be real and non-negative.
Cheeger-type inequality: Unlike the FC method, which does not provide a theoretical guarantee linking the eigenfunctions used for clustering to the optimization objective, our approach establishes a Cheeger-type incquality.
16

---

Signed Laplacians for Constrained Graph Clustering
Mean ARI vs (n 250)
Mean ARI vs q (n 500)
CC++
CC++
Adjusted Rand Index (ARI)
0.9
CC
Adjusted Rand Index (ARI) (ARI)
0.9
CC
SC
SC
FC
0.7
0.7
0.6
0.5
0.5
0.3
0.3
0.2
0.2
0.1
0.12
0.13
0.14
0.15
0.16
0.17
0.18
0.19
0.2
0.12
0.13
0.14
0.15
0.16
0.17
0.18
0.19
0.2
Inter-cluster Edge Probability (q)
Inter-cluster Edge Probability (q)
(a)
250
(b) n 500
Mean ARI vs (n = 750)
Mean ARI vs q (n 1000)
CC
0.9
Adjusted Rand Index (ARI)
Adjusted Rand Index (ARI)
SC
0.8
FC
0.7
0.6
0.6
0.5
0.4
0.3
CC++
0.2
CC
0.1
SC
FC
Inter-cluster Edge Probability (q)
Inter-cluster Edge Probability (q)
(C)
(d) n 1000
Figure 6. Mean Adjusted Rand Index (ARI) as a function of inter-cluster edge probability for four clustering methods. Each panel represents different graph size: (a) n 250, (b) 500, (c) 750, and (d) n 1000.
17


Reviews:
[{"review_id": "WlgnJ5CT2X", "reviewer": "Reviewer_wvht", "summary": "This paper considers the constrained clustering problems over two graphs.\nThis paper establishes the Cheeger inequality for the proposed algorithm for constrained clustering, which can be a counterpart of Cheeger inequality to the standard spectral clustering over a graph. The proposed algorithm improves spectral clustering, in a scenario that is challenigin for spectral clustering. This paper also experimentally demonstrates the effectiveness of the proposed algorithm.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer  their positive evaluation,  and constructive feedback. Here is our response to their questions:\n\n**Response to _Relation To Broader Scientific Literature_:**\n\nOur Cheeger-type inequality improves previous related results (including that of Koutis et al. (2023)). Our main theoretical result  states that\n\t$$\n\t\\Phi_H^G \\leq  4\\sqrt{ \\frac{\\lambda_2(\\Delta^G_H)}{\\lambda_2(\\Delta^H)}},\n\t$$\n\twhere $\\lambda_2(\\Delta^H)$ is the Fiedler eigenvalue of the Laplacian of constraint graph $H$. In contrast to Koutis et al., our bound does not rely on an auxiliary demand graph $D_G$. Instead, it incorporates both graphs $G$ and $H$ directly through the generalized eigenvalue problem. Koutis et al.'s bound is based on a product of isoperimetric constants $\\Phi_G$, $\\Phi_H^G$, $\\Phi^G_{D_G}$, where the influence of $H$ is less direct. As a result, their bound remains tied to the structure of $G$ and a third graph $D_G$, whereas ours explicitly improves with the connectivity of $H$. Even as additional constraints are added to $H$, modelled by a graph $H + e$, our bound becomes tighter due to the fact\n\t\t$\n\t\t\\lambda_2(\\Delta^H) \\leq \\lambda_2(\\Delta^{H+e}),\n\t\t$\n\t\twhich reflects the improved connectivity of $H$. Hence, our inequality rewards richer and more informative constraint graphs. \n\nAs a concrete example, let's consider the case in which   $H$ is the complete bipartite graph $K_{n,m}$ with normalized weights. The spectrum of its normalized Laplacian is known to be $ \\{ 0, 1 \\text{ (with multiplicity } n + m - 2), 2 \\}$, so $ \\lambda_2(\\Delta^H) = 1 $. In this case, our bound simplifies to $ \\Phi_H^G \\leq 4 \\sqrt{\\lambda_2(\\Delta_H^G)} $, which depends directly on the spectral relationship between $G$ and $H$. \t\t\n\t\tThis contrasts with the bound in Koutis et al. (2023), which involves an additional graph $D_G$ and the product $\\Phi_H^G \\cdot \\Phi_{D_G}^G$, making the analysis more involved. Our formulation, in settings like $K_{n,m}$, yields a cleaner and more interpretable bound in terms of the original input graphs.\n\n**Response to _Essential References Not Discussed_:** We thank the reviewer for the suggestion. In the next version of the paper, we will give a more detailed discussion on existing work around graph constructed clustering, and in particular emphasise the work on classical Cheeger inequality including [1] and [2].", "claims_and_evidence": "Claims seem sound. This paper provides the Cheeger type inequality for the constrained clustering problem. As far as written in related work, no previous work provided the proposed type of the Cheeger inequality. The proposed inequality is elegant; that is well adapted from the classical Cheeger inequality, and see clear contrast between the proposed and classical inequality. \n\nSome may criticize this paper from a view where this paper only provides the bound when the number of clusters is two. However, in the classical Cheeger inequality for higher order has a different flavor even in the classical setting, like (Lee et al., 2014). Thus, I expect the higher order Cheeger inequality may be similar to the classical setting (much different than the current discussion), and therefore I do not think that this paper is not enough for this view point; this can be a distinct future work.", "methods_and_evaluation_criteria": "I think the methods make sense; that is streamlined with the existing view form the spectral clustering community.", "theoretical_claims": "Although I have not checked every single detail of the proof, the claim seems be valid as far as I read.", "experimental_designs_or_analyses": "I think the experimental design is fair.", "relation_to_broader_scientific_literature": "I am curious that in which setting the proposed bound is tighter than the existing bound \n\n$ \n\\Phi^{G}_{H} \\leq 16 \\lambda_{2}(\\Delta^{G}_{H})/\\Phi(G) \n$ \n\nby Koutis et al. (2023), since the both provide the bound for $\\Phi^{G}_{H}$.", "essential_references_not_discussed": "This does not affect to my overall evaluation, but it is nicer if the author can wrap up the existing work around graph constrained clustering, maybe in Appendix. Also, it would be nice to emphasize that the Cheeger inequality is a very established one by citing the classical literature such as [1] and [2].\n\n[1] N. Alon. Eigenvalues and expanders. Combinatorica, 6(2):83–96, 1986. \n[2] N. Alon and V. D. Milman. $\\lambda_{1}$, isoperimetric inequalities for graphs, and superconcentrators. J. Comb.\nTheory B, 38(1):73–88, 1985.", "other_strengths_and_weaknesses": "N/A", "other_comments_or_suggestions": "N/A\n\n\n\n--\npost rebuttal comment: I am satisfied with the answers and therefore I increased my score from three to four.", "questions_for_authors": "It is nice if the authors can answer the questions in my responses.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "nv72f26VSr", "reviewer": "Reviewer_SYBT", "summary": "The paper considers the constrained graph clustering problem.\nThe input consists of two graphs, G and H, defined on the same set of nodes.\nThe clustering challenge is to group together nodes that are connected with large\nweights  in G and small weights in H.\n\nThe paper considers only clustering into two clusters, which requires\nidentifying a single subset S of nodes. It defines a clustering criterion\nas the ratio between the cut of S in G and the cut of S in H.\nClustering is achieved by finding S that minimizes this criterion.\n\nThe paper proves an upper bound on this criterion, which can be expressed\nin terms of eigenvalues. The proof is constructive, and suggests a method\nof computing S that achieves the bound. Still, the solution requires solving a\ngeneralized eigenvalue problem. The paper shows how to do that efficiently\nby introducing the signed Laplacian, a generalization of the standard Laplacian\noperator. \n\nThe paper evaluates the algorithm on artificial and real data.\nThey show that the algorithm is practical, and compares favorably\nwith other clustering techniques (that operate only on G without a knowledge of\nH).", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their positive evaluation and insightful questions. Here is our response to the raised questions:\n\n> My main concern is with identifying applications of this approach. Where would the graph $H$ come from?\n\nWe agree that clarifying the role and origin of the constraint graph $H$ is essential for broader applicability. In practice, $H$ encodes side information, domain knowledge, or external constraints — often available in real-world settings but not directly encoded in the similarity graph $G$. Examples include:\n\n- _Image segmentation:_ The graph $G$ connects each pixel to its spatial neighbors (e.g., via a 4- or 8-connected grid), with edge weights reflecting feature similarity such as color or texture. The constraint graph $H$ is constructed from user-provided annotations (e.g., brush strokes indicating foreground/background): MUST-LINK edges are added between pixels marked as belonging to the same object, and CANNOT-LINK edges are introduced between pixels annotated as different regions. This enforces spatial coherence guided by user intent.\n\n- _Social networks:_ In signed or trust networks, $G$ encodes positive relationships (e.g., friendship, following, co-authorship) where the presence of an edge implies mutual affinity. In contrast, $H$ captures negative interactions (e.g., distrust, blocking, or rivalry) by placing edges between users that should not be clustered together. This dual representation supports community detection that respects both cooperation and conflict.\n\n- _Complement graph:_ A practical and widely applicable construction is to set $H = \\overline{G}$, i.e., the complement of $G$. Here, edges in $G$ represent strong (positive) similarities — interpreted as MUST-LINK constraints — while the absence of an edge in $G$ is interpreted as a weak or negative relation, thus becoming a CANNOT-LINK constraint in $H$. This approach is especially useful when no explicit constraint data is available, and could be defined as a default setting $H$ in that case.\n\n We will clarify this construction and its practical relevance in the introduction of the revised manuscript.\n\t\n> Another point I am uncomfortable with is that the criterion does not reduce to normalized cut when $H$ is selected as the complete graph. \n\nThank you for raising this thoughtful point. In fact, in earlier versions of our manuscript we included the following remark after Theorem 3.2, which answered the question above but was dropped due to page limit. We will add the the following remark in the next version of the paper.\n\n_Remark 1_: Theorem 3.2 can be viewed as a generalization of the classical Cheeger inequality. Specifically, if we consider the graph $H$ as the complete graph with $w_{uv} = 1$ for all edges, then it is straightforward to show that\n\t$$\n\t\\min_{\\emptyset \\subset S \\subset V} \\frac{w_G(S, V \\setminus S)}{|S| \\cdot |V \\setminus S|} \\leq 4 \\sqrt{ \\lambda_2(\\Delta^G)},\n\t$$\n\twhere $\\lambda_2(\\Delta^G)$ is the second smallest eigenvalue of the normalized graph Laplacian of $G$.  \tSimilarly, if we consider the graph $H = (V, E', w^H)$ as the complete graph with self-loops where\n\t$$\n\tw^H_{uv} = \\frac{\\deg^G(u)\\deg^G(v)}{\\mathrm{vol}(G)},\n\t$$\n\tthen\n\t$$\n\t\\min_{\\emptyset \\subset S \\subset V} \\frac{w_G(S, V \\setminus S)}{\\min(\\mathrm{vol}(S), \\mathrm{vol}(V \\setminus S))} \n\t\\leq \\min_{\\emptyset \\subset S \\subset V} \\frac{\\mathrm{vol}(G)\\, w_G(S, V \\setminus S)}{\\mathrm{vol}(S) \\cdot \\mathrm{vol}(V \\setminus S)} \n\t\\leq 4 \\sqrt{ \\lambda_2(\\Delta^G)}.\n\t$$\nThese reductions confirm that our constrained cut formulation includes both the regular (combinatorial) and normalized Cheeger cuts as special cases, depending on how the constraint graph $H$ is chosen.\n\nWe thank the reviewer once more   for the suggestions and  questions. We're happy to answer any further questions during the discussion phase.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "Only superficially.", "experimental_designs_or_analyses": "Yes.", "relation_to_broader_scientific_literature": "I am not familiar with the constrained clustering. But the paper discusses\nin detail comparison to recent results that are most likely the current\nstate of the art.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "As someone who is not familiar with this area I like this result very much.\nThe presentation is very clear, \nthe proofs are deep, and as much as I can tell they are valid.\n\nMy main concern is with identifying applications of this approach.\nWhere would the graph H come from?\n\nAnother point I am uncomfortable with is that the criterion does not\nreduce to normalized cut when H is selected as the complete graph.\nInstead, it reduced to regular cut, which is known not to be useful\nin data analysis.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "N/A", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "r33CC3kxlQ", "reviewer": "Reviewer_eq7q", "summary": "The paper provides a spectral method for approximately optimising the cut ratio for a graph $G$ and a constraint graph $H$ using the smallest non-zero eigenvalues of two particular graph Laplacians. This is based on a proof of Cheeger-type inequality similar to the min-cut approach for a single graph. Practical considerations are made to approximate this problem using a signed Laplacian which provides computational speed-up and improved results. Small experiments are run on two synthetic datasets and one temperature/spatial real-world example.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We  thank the reviewer  for their thoughtful review and valuable suggestions. Here is our response to the raised questions.\n\n**Response to _Claims And Evidence_:**\n\n>  Why would sweep-cut versions based on these inequalities not work for the constraint clustering problem? \n\nIn our setting, sweep-cut is adapted from the classical Cheeger setting to work with eigenvectors of the generalized eigenproblem $ \\Delta^G x = \\lambda \\Delta^H x $. Although standard in spectral clustering, here the procedure ensures that cuts reflect the joint structure of both graphs. We will clarify this briefly in the next version of the paper.\n\n**Response to _Methods And Evaluation Criteria_:**\n\nWe agree that further comparison with state-of-the-art constrained clustering methods would enrich the paper. In this version, we compared our method with classical spectral clustering (SC), flexible constrained spectral clustering (FC), and our variants using self-loops (CC++). These are meaningful baselines given our focus on spectral guarantees. However, we acknowledge the importance of broader comparisons and plan to include these in the next version of our paper.\n\n**Response to _Theoretical Claims_:**\n\nThe self-loop weights method serve a dual purpose. First, adding self-loops to $G$ balances the graph by equalizing the degree sequences of $G$ and $H$ (as noted in the manuscript, lines 118–119, right column). Second, including a small self-loop (with weight $\\epsilon = 0.0001$) in $H$ ensures that the Laplacian $\\Delta^H$ is invertible, which is necessary for solving the generalized eigenvalue problem $\\Delta^G \\mathbf{x} = \\lambda\\Delta^H \\mathbf{x}$. This perturbation $\\epsilon$ provides numerical stability, and we observed that the performance remains robust for other comparably small values of $\\epsilon$.\n\n**Response to _Experimental Designs Or Analyses_:**\n\nWe appreciate the suggestion to improve the statistical evaluation of the temperature dataset. In our current version, we evaluated the separation via differences in mean temperature between clusters. We agree that formal statistical tests (e.g., t-tests) would provide stronger evidence and intend to include them in a future revision. Despite this, our current metric demonstrated effective alignment between spatial structure and temperature variation. Nonetheless, even the simple metric showed that the separation achieved by our method aligned well with the underlying temperature variation. \n\n**Response to _Other Comments Or Suggestions_:**\n\nThank you for catching the typo (“Cheer-type”). We will correct this in the next version of the paper.\n\t\n**Response to _Questions For Authors_:**\n\nWe thank the reviewer for this insightful question. Indeed, we are currently exploring an extension of Theorem 3.2 that avoids the degree-sequence equalization and instead expresses the bound using the original graphs $G$ and $H$. To do this, we consider the more general setting of weighted graphs with vertex weights.\n\t\nSpecifically, for weighted graphs $(G, w^G)$ and $(H, w^H)$, we assign weights to the vertices such that $w^G(v) = w^H(v)$. While the normalized Laplacian typically assumes $w^G(v) = \\deg_G(v)$, our setting leads to a weighted unnormalized Laplacian $\\Delta^{(G, w)}$. This operator remains positive and self-adjoint, and satisfies that $\\lambda_2(\\Delta^{(G, w)}) > 0$.\n\t\nIn this formulation, the degree-sequence equalization step becomes unnecessary, albeit at the cost of working with a more general Laplacian operator. We believe a similar Cheeger-type inequality can be established under this setting, though doing so will require both theoretical and algorithmic adjustments. This is an interesting and nontrivial direction for future research rather than a mere corollary of the current work.", "claims_and_evidence": "Main claims of paper where theoretical claims (see below).\n\nIt wasn't clear to me why the approaches in the related work at the top of page 2 were unsuitable for this problem. Why would sweep-cut versions based on these inequalities not work for the constraint clustering problem? Below this, the authors mention papers with a practical perspective (lines 068-070), which are not compared against in the experimentation, which may still be useful if currently lacking the same theoretical rigour.", "methods_and_evaluation_criteria": "It seemed unfair to compare CC and CC++ using graphs $G$ and $H$ only to spectral clustering techniques that only considered $G$. If the metric is to optimise ARI, then spectral methods acting jointly on $G$ and $H$ (or $G$ and $\\bar{H}$) could be use, for example, using the unfolded adjacency matrix or its Laplacian. I think a fairer and wider comparison necessary for the paper to be accepted.", "theoretical_claims": "Theorem 3.2 gives an upper bound for $\\Phi_G^H$ with a convincing proof and sketch proof. I need more convincing about the statement about the approximation at the bottom of page 5 especially as the paper does not outline how the negative self-loop weight should be chosen.", "experimental_designs_or_analyses": "Real-world example could be more impactful given some of the image segmentation experiments explored in referenced CC papers.\n\nThe metric used for successful separation in the temperature experiment is unusual. It would be more natural to perform a statistical test to see if the temperature are significantly different to better account for more variance when one cluster has relatively fewer data points.", "relation_to_broader_scientific_literature": "I do not know how much work relies on solving the graph constraint clustering problem.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "Interesting problem that I have not considered before and I very much enjoyed learning about the theory of spectral CC. More motivation for the real-world application would help explain why this is a relevant problem as I felt I didn't get that feeling under the very end of the paper after reading some of the referenced work.", "other_comments_or_suggestions": "\"Cheer-type inequalities\" should be \"Cheeger-type inequalities\" on page 1 by Related work.", "questions_for_authors": "Is it possible to create a corollary of Theorem 3.2 that expresses the upper bound in terms of the original graphs $G$ and $H$ rather the degree sequence equalised versions?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "bhvPaGMAdT", "reviewer": "Reviewer_VAfm", "summary": "This paper addresses the constrained graph clustering problem, where the goal is to partition a graph into clusters while incorporating domain knowledge in the form of MUST-LINK and CANNOT-LINK constraints. The authors establish a Cheeger-type inequality that relates the solution of the constrained clustering problem to the spectral properties of the graphs $G$ and $H$. The proposed algorithm solves a generalized eigenvalue problem and demonstrates performance improvements over traditional spectral clustering methods.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for  their   positive evaluation and and valuable suggestions.  Here is our response to the raised questions:\n\n**Response to _Methods and Evaluation Criteria_:** \n\nWe agree that further comparison between our work with the state-of-the-art constrained clustering algorithms will significantly improve the value of our work. Following the suggestion, we will add more experimental results in the next version of our paper.\n\n**Response to Q1:**\n\n> Does the \"sweep-set algorithm\" in Algorithm 1 refer to $k$-means?\n\nNo. The sweep-set algorithm used in Algorithm 1 is a spectral procedure commonly used in classical Cheeger inequalities. This method involves sorting vertices according to their corresponding entries in the eigenvector solution obtained from the generalized eigenvalue problem. Then, the optimal clustering cut is identified by sequentially evaluating the constrained cut ratio for each prefix set of the sorted vertices. \n\t\nIt is worth mentioning that, in our preliminary experiments, we tried to replace the sweep-set step with $k$-means on the eigenvectors, and received almost identical results as the current approach. Hence, we decided to retain the classical sweep-set approach in our final experiments to maintain consistency with the classical Cheeger inequality applications. We will add necessary discussion in the next version of the paper.\n    \n**Response to Q2:**\n\n> Does the proposed method generalize to $k$-way ($k>2$) clustering problems?\n\t\nGeneralizing our approach to the $k$-way  clustering  for $k>2$  is an important and natural direction of research, and we are currently working on this direction. Our initial work has indicated that  the techniques required for the multi-way extension differ substantially from our currently presented one. Specifically, it requires us to develop a new objective function and substantially different spectral arguments to analyze the algorithm's performance. Given the  amount of work needed for this generalization, we decided to make it as a separate and future work.\n\nThank you once more for the suggestions and  questions. We're happy to answer any further questions during the discussion phase.", "claims_and_evidence": "The claims are well-supported.", "methods_and_evaluation_criteria": "This work addresses the problem of constrained clustering, where two graphs, $G$ and $H$, are provided as input. However, the experiments section solely compares the proposed method with the original spectral clustering algorithm, which is not inherently designed for constrained clustering tasks. Although Appendix B includes a comparison with the FC algorithm, it is important to note that FC represents an outdated baseline and does not reflect state-of-the-art performance.", "theoretical_claims": "I checked the proof sketch and it appears to be correct.", "experimental_designs_or_analyses": "The experimental design is proper.", "relation_to_broader_scientific_literature": "The established Cheeger-type inequality for constrained clustering is a generalization of the classical one as identified in Remark 3.3", "essential_references_not_discussed": "n/a", "other_strengths_and_weaknesses": "* The establishment of a Cheeger-type inequality provides a strong theoretical foundation, linking the constrained clustering problem to the spectral properties of the graphs.\n* While the idea of adding self-loops to ensure the invertibility of the Laplacian matrix, thereby accelerating computation, cannot be claimed as entirely original, it demonstrates a notable level of creativity.", "other_comments_or_suggestions": "Appendix B writes \"This section will be further updated with more comparative methods as we expand our experiment\"", "questions_for_authors": "1. Does the \"sweep-set algorithm\" in Algorithm 1 refer to kmeans?\n2. Does the proposed method generalize to k-way (k > 2) clustering problems?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper introduces a new spectral method for constrained clustering, supported by a Cheeger-type inequality. It seeks to minimize the ratio of cuts of two graphs (with shared set of nodes). The theory is solid and well-written. The algorithm uses a generalized eigenproblem and performs well on synthetic and real data.

Reviewers agreed that the theoretical part is strong and the proofs are correct. The main concern was the limited experimental comparison. The method was mostly compared to standard spectral clustering and one older baseline. Reviewers also asked for more explanation about how the second graph H is chosen in practice. The authors explained real-world cases where H comes from, showed that the method reduces to known cases when H is complete, and promised to add more experimental baselines. Overall, this is a strong theoretical paper with a clear contribution. The authors responded well to concerns, and I recommend accept the paper.
Decision: Accept (spotlight poster)