3.4. Spectral approaches to clustering
25
Graph cut approaches to clustering
For social network data, the graph cut approach is as follows: find a partition of the
network into clusters such that the number of edges between different clusters is low,
and each cluster has a higher density of edges than the network as a whole. When
this is the case, the nodes within a cluster are similar to another, and the nodes in
different clusters are dissimilar to one another. Finding an optimum partition is done
by solving the min-cut problem, defined as minimizing:
cut(A 1 , ..., A k ) :=
1
2
k
∑
i=1
W (A i , A i ),
where k is the number of groups, A i is the complement of A i , and 1/2 accounts for
the fact that we count each edge twice.
However, in practice, this does not lead to satisfactory partitions because simply separating the node with the lowest degree from the rest of the graph may give
the minimum cut value [101]. To avoid this problem, two more sophisticated graph
cuts, RatioCut and NCut, were introduced by Hagen and Kahng [38], and Shi and
Malik [84], respectively. The definitions are:
RatioCut(A 1 , ..., A k ) :=
k
∑
i=1
W (A i , A i )
|A i |
=
k
∑
i=1
cut(A i , A i )
|A i |
,
and
NCut(A 1 , ..., A k ) :=
k
∑
i=1
W (A i , A i )
vol(A i )
=
k
∑
i=1
cut(A i , A i )
vol(A i )
,
where |A i | is the number of the nodes in group A i , and vol(A i ) is the sum of the
degrees of the nodes in group A i . Both approaches try to find an optimal partition
that not only achieves a small cut value, but also keeps the groups in “balance”.
Solving min-cut problems with balance conditions is NP-hard and so is intractable for large datasets [105]. Fortunately, spectral clustering can be viewed as
an approximate way to solve these problems. Relaxing NCut leads to normalized
spectral clustering, and relaxing RatioCut leads to unnormalized spectral clustering. The details of proof and discussion can be found in the tutorial written by von
Luxburg [101]. However, the quality of the solution to the relaxed problem is not
guaranteed, so they should be interpreted with some caution. Spielman and Teng
[91] and Kannan et al. [43] have explored some of the relationships between graph
properties and clustering solution quality.
Random walk approaches to clustering
Another way to explain spectral clustering is based on a random walk in the network.
We want to find an embedding in which it is easy for a random walker to travel among
the nodes of one cluster but hard to travel to nodes in a different cluster. The effect
of placing all nodes at the same spot, and the effect of the size of the graph, have
25
Graph cut approaches to clustering
For social network data, the graph cut approach is as follows: find a partition of the
network into clusters such that the number of edges between different clusters is low,
and each cluster has a higher density of edges than the network as a whole. When
this is the case, the nodes within a cluster are similar to another, and the nodes in
different clusters are dissimilar to one another. Finding an optimum partition is done
by solving the min-cut problem, defined as minimizing:
cut(A 1 , ..., A k ) :=
1
2
k
∑
i=1
W (A i , A i ),
where k is the number of groups, A i is the complement of A i , and 1/2 accounts for
the fact that we count each edge twice.
However, in practice, this does not lead to satisfactory partitions because simply separating the node with the lowest degree from the rest of the graph may give
the minimum cut value [101]. To avoid this problem, two more sophisticated graph
cuts, RatioCut and NCut, were introduced by Hagen and Kahng [38], and Shi and
Malik [84], respectively. The definitions are:
RatioCut(A 1 , ..., A k ) :=
k
∑
i=1
W (A i , A i )
|A i |
=
k
∑
i=1
cut(A i , A i )
|A i |
,
and
NCut(A 1 , ..., A k ) :=
k
∑
i=1
W (A i , A i )
vol(A i )
=
k
∑
i=1
cut(A i , A i )
vol(A i )
,
where |A i | is the number of the nodes in group A i , and vol(A i ) is the sum of the
degrees of the nodes in group A i . Both approaches try to find an optimal partition
that not only achieves a small cut value, but also keeps the groups in “balance”.
Solving min-cut problems with balance conditions is NP-hard and so is intractable for large datasets [105]. Fortunately, spectral clustering can be viewed as
an approximate way to solve these problems. Relaxing NCut leads to normalized
spectral clustering, and relaxing RatioCut leads to unnormalized spectral clustering. The details of proof and discussion can be found in the tutorial written by von
Luxburg [101]. However, the quality of the solution to the relaxed problem is not
guaranteed, so they should be interpreted with some caution. Spielman and Teng
[91] and Kannan et al. [43] have explored some of the relationships between graph
properties and clustering solution quality.
Random walk approaches to clustering
Another way to explain spectral clustering is based on a random walk in the network.
We want to find an embedding in which it is easy for a random walker to travel among
the nodes of one cluster but hard to travel to nodes in a different cluster. The effect
of placing all nodes at the same spot, and the effect of the size of the graph, have