Appendix A
RatioCut consistency
with two versions of
each node
Figure A.1: A cut with the V1 and V2 copies of a node x in two different clusters
Figure A.1 is a graph cut partition by using our layered model construction,
where a pair of nodes x V 1 and x V 2 are separated into two different groups of A and A,
and the cut value is cut(A, A). Let d V 1x and d V 2x be the degree of nodes x V 1 and x V 2
without the added edges (without the edge between x V 1 and x V 2 in this case). Thus,
the total degrees of nodes x V 1 and x V 2 in the layered model matrix M are 2d V 1x +d V 2x
and d V 1x + 2d V 2x , respectively. Let p be the sum of edge’s weight from x V 1 to nodes
in A except x V 2 . Let q be the sum of edge’s weight from x V 2 to nodes in A except
x V 1 . This cut would always be worse than the cut that puts x V 1 and x V 2 in the same
group based on RatioCut and NCut theory.
Theorem 1: The two versions of a node will be placed in the same cluster
based on RatioCut with two versions of each node, when the added edge weight
between two versions of a same node is equal to the sum of the degrees of the two
versions.
Proof of RatioCut Consistency with two versions of each node (c = 2):
Assume there is a minimum RatioCut which separates at least a pair of nodes x V 1
163