169
Similarly, (B.2) implies
d V 2x vol(A)vol(A)
≤ cut(A, A)
−vol(A)(2d V 1x + d V 2x ) + vol(A)(2d V 1x + d V 2x ) + (2d V 1x + d V 2x )
2
.
By adding the above two equations together, we get
(d V 1x + d V 2x )vol(A)vol(A)
≤ cut(A,A)
vol(A)(−d V 1x +d V 2x )+vol(A)(d V 1x −d V 2x )+5d
2
V 1x +5d
2
V 2x +8d V 1x d V 2x
.
Combining with (B.3), we get
4d
2
V 1x + 4d
2
V 2x + 10d V 1x d V 2x ≤ (vol(A) − vol(A))(d V 1x − d V 2x ).
(B.4)
In the inequality (B.1), the left numerator is greater than or equal to the right numerator. Thus, the left denominator has to be greater than or equal to the right
denominator:
vol(A)vol(A) ≥ (vol(A) + d V 1x + 2d V 2x )(vol(A) − d V 1x − 2d V 2x ).
If vol(A) ≤ vol(A), then the above inequality implies
=⇒ vol(A) ≤ vol(A) + d V 1x + 2d V 2x .
When d V 1x < d V 2x , the right side of (B.4) is less than 0.
When d V 1x ≥ d V 2x , by applying the above inequality to (B.4), we get
4d
2
V 1x + 4d
2
V 2x + 10d V 1x d V 2x
≤ vol(A)(−d V 1x + d V 2x ) + (vol(A) + d V 1x + 2d V 2x )(d V 1x − d V 2x )
=⇒ 3d
2
V 1x + 6d
2
V 2x + 9d V 1x d V 2x ≤ 0.
Since d V 1x ≥ 0, d V 1x ≥ 0 and d V 1x + d V 2x > 0 for a connected graph, the above
inequality is not true. Similarly we can prove that, if vol(A) ≥ vol(A), the inequality
(B.4) is not true either. Thus, based on the proof above, the assumption is not true.
In other words, there does not exist a minimum NCut which separates at least a pair
of nodes x V 1 and x V 2 into different groups in a NCut of two clusters. Similarly, the
NCut consistency of more than two clusters can be proved, since the cut variables in
the unrelated clusters are constant.
Therefore, the NCut clustering results would not separate the two versions of
any node x V 1 and x V 2 into two different groups by using our approach.
Proof of NCut consistency with multiple versions of each node (c ≥ 3): The
property still holds for optimum NCut results when there is more than two roles of
each node. The proof is similar to the one for c = 2. Again we assume there is a
minimum NCut in which there is at least a node whose copies are separated into two
different groups A and A.
Let x A and x A be the copies of x in the two partitions;
Similarly, (B.2) implies
d V 2x vol(A)vol(A)
≤ cut(A, A)
−vol(A)(2d V 1x + d V 2x ) + vol(A)(2d V 1x + d V 2x ) + (2d V 1x + d V 2x )
2
.
By adding the above two equations together, we get
(d V 1x + d V 2x )vol(A)vol(A)
≤ cut(A,A)
vol(A)(−d V 1x +d V 2x )+vol(A)(d V 1x −d V 2x )+5d
2
V 1x +5d
2
V 2x +8d V 1x d V 2x
.
Combining with (B.3), we get
4d
2
V 1x + 4d
2
V 2x + 10d V 1x d V 2x ≤ (vol(A) − vol(A))(d V 1x − d V 2x ).
(B.4)
In the inequality (B.1), the left numerator is greater than or equal to the right numerator. Thus, the left denominator has to be greater than or equal to the right
denominator:
vol(A)vol(A) ≥ (vol(A) + d V 1x + 2d V 2x )(vol(A) − d V 1x − 2d V 2x ).
If vol(A) ≤ vol(A), then the above inequality implies
=⇒ vol(A) ≤ vol(A) + d V 1x + 2d V 2x .
When d V 1x < d V 2x , the right side of (B.4) is less than 0.
When d V 1x ≥ d V 2x , by applying the above inequality to (B.4), we get
4d
2
V 1x + 4d
2
V 2x + 10d V 1x d V 2x
≤ vol(A)(−d V 1x + d V 2x ) + (vol(A) + d V 1x + 2d V 2x )(d V 1x − d V 2x )
=⇒ 3d
2
V 1x + 6d
2
V 2x + 9d V 1x d V 2x ≤ 0.
Since d V 1x ≥ 0, d V 1x ≥ 0 and d V 1x + d V 2x > 0 for a connected graph, the above
inequality is not true. Similarly we can prove that, if vol(A) ≥ vol(A), the inequality
(B.4) is not true either. Thus, based on the proof above, the assumption is not true.
In other words, there does not exist a minimum NCut which separates at least a pair
of nodes x V 1 and x V 2 into different groups in a NCut of two clusters. Similarly, the
NCut consistency of more than two clusters can be proved, since the cut variables in
the unrelated clusters are constant.
Therefore, the NCut clustering results would not separate the two versions of
any node x V 1 and x V 2 into two different groups by using our approach.
Proof of NCut consistency with multiple versions of each node (c ≥ 3): The
property still holds for optimum NCut results when there is more than two roles of
each node. The proof is similar to the one for c = 2. Again we assume there is a
minimum NCut in which there is at least a node whose copies are separated into two
different groups A and A.
Let x A and x A be the copies of x in the two partitions;