Cyclizing Clusters via Zeta Function of a Graph
Deli Zhao and Xiao ou Tang Multimedia Laboratory, Department of Information Engineering, Chinese University of Hong Kong

Cluster Character
Motivation: Let C denote a group of data and W be the weighted adjacency matrix of its graph G . We model the structural complexity of C by dynamics of cycles in G , quantified by Zeta function of the graph:

z = exp   = 1 1 Cluster Character: C = n ln  z

Figure:
20 1000 5 80 10 0 -10

Schematic of Cyclic dynamics.
800 1500

20 10

5 0 -5 -10

= n

1 det(I - z W)

,

500 1000

0 -10

50

-1 (p , p ). p =1 (I - z W)

-20 -60 x 10
Minimum Delta popularity
-6

400 300 40 -40 -30

-15

100 -20 -10 0

-20 -60 -50 -40 -30 -20
8 Minimum Delta popularity 6 4 2 0 x 10
-7

-20

-50

-10

0

-60

-50

-40
-7

-30

First-order di erence 5 10 Number of clusters 15

Zeta Merging
Given a group of initial clusters {C1 , . . . , Cm }, Zeta merging proceeds by the maximum incremental reciprocal popularity:
{Ci , Cj } = arg max  C C , i j i ,j where

5 4 3 2 1 0 -1 -2

x 10

3

2

1

0

0

20

40

Figure: Clustering on toy by Zell.

60 80 100 Number of clusters

120

140

160

5 10 Number of clusters

15

 C C = (C |C C -C )+(C |C C -C ). i j i j ii j ji j The number of clusters can be automatically detected for data that have block-diagonal adjacency matrices.

Exp eriment
The 98.1% accuracy is obtained on the Face Recognition Grand Challenge (FRGC) database of 16028 samples and 466 clusters. NIPS 2008 Spotlight: Poster ID #M29

Neural Information Pro cessing Systems, Dec. 8, 2008