Spectral clustering

GraphPartitioningandSpectralClusteringOutlineOverviewofGraphPartitioningGraphrepresentationHowdowedefinea“good”graphpartition?Howdowefinda“good”graphpartition?SpectralGraphTheoryMatrixrepresentationTheoreticalbackgroundSpectralClusteringAlgorithmBi-partitioningK-waypartitioningCo-clusteringConclusion0.10.20.80.70.60.80.80.8E={wij}Setofweightededgesindicatingpair-wisesimilaritybetweenpointsSimilarityGraphRepresentdatasetasaweightedgraphG(V,E)Exampledataset},...,,{621xxx123456V={xi}SetofnverticesrepresentingdatapointsGraphPartitioningClusteringcanbeviewedaspartitioningasimilaritygraphBi-partitioningtask:Divideverticesintotwodisjointgroups(A,B)123456ABRelevantIssues:Howcanwedefinea“good”partitionofthegraph?Howcanweefficientlyidentifysuchapartition?ClusteringObjectivesTraditionaldefinitionofa“good”clustering:1.Pointsassignedtosameclustershouldbehighlysimilar.2.Pointsassignedtodifferentclustersshouldbehighlydissimilar.2.Minimiseweightofbetween-groupconnections0.10.21.Maximiseweightofwithin-groupconnections0.80.70.60.80.80.8123456ApplytheseobjectivestoourgraphrepresentationGraphCutsExpresspartitioningobjectivesasafunctionofthe“edgecut”ofthepartition.Cut:Setofedgeswithonlyonevertexinagroup.BjAiijwBAcut,),(0.10.20.80.70.60.80.81234560.8ABcut(A,B)=0.3GraphCutCriteriaCriterion:Minimum-cutMinimiseweightofconnectionsbetweengroupsmincut(A,B)OptimalcutMinimumcutProblem:OnlyconsidersexternalclusterconnectionsDoesnotconsiderinternalclusterdensityDegeneratecase:GraphCutCriteria(continued)Criterion:Normalised-cut(Shi&Malik,’97)Considertheconnectivitybetweengroupsrelativetothedensityofeachgroup.Normalisetheassociationbetweengroupsbyvolume.Vol(A):ThetotalweightoftheedgesoriginatingfromgroupA.)(),()(),(),(minBvolBAcutAvolBAcutBANcutWhyusethiscriterion?Minimisingthenormalisedcutisequivalenttomaximisingnormalisedassociation.Producesmorebalancedpartitions.Howdoweefficientlyidentifya“good”partition?Problem:ComputinganoptimalcutisNP-hardSpectralGraphTheoryPossibleapproachRepresentasimilaritygraphasamatrixApplyknowledgefromLinearAlgebra…SpectralGraphTheoryAnalysethe“spectrum”ofmatrixrepresentingagraph.Spectrum:Theeigenvectorsofagraph,orderedbythemagnitudeoftheircorrespondingeigenvalues.},...,,{21nTheeigenvaluesandeigenvectorsofamatrixprovideglobalinformationaboutitsstructure.nnnnnnxxλxxaaaa111111MatrixRepresentationsAdjacencymatrix(A)nxnmatrix:edgeweightbetweenvertexxiandxjx1x2x3x4x5x6x100.80.600.10x20.800.8000x30.60.800.200x40.800.200.80.7x50.1000.800.8x60000.70.800.10.20.80.70.60.80.81234560.8Importantproperties:SymmetricmatrixEigenvectorsarerealandorthogonal][ijwAMatrixRepresentations(continued)Importantapplication:NormaliseadjacencymatrixDegreematrix(D)nxndiagonalmatrix:totalweightofedgesincidenttovertexxix1x2x3x4x5x6x11.500000x201.60000x3001.6000x40002.500x500001.70x6000001.50.10.20.80.70.60.80.81234560.8jijwiiD),(MatrixRepresentations(continued)Laplacianmatrix(L)nxnsymmetricmatrixImportantproperties:Eigenvaluesarenon-negativerealnumbersEigenvectorsarerealandorthogonalEigenvaluesandeigenvectorsprovideaninsightintotheconnectivityofthegraph…0.10.20.80.70.60.80.81234560.8L=D-Ax1x2x3x4x5x6x11.5-0.8-0.60-0.10x2-0.81.6-0.8000x3-0.6-0.81.6-0.200x4-0.80-0.22.5-0.8-0.7x5-0.1000.81.7-0.8x6000-0.7-0.81.5FindAnOptimalMin-Cut(Hall’70,Fiedler’73)Expressabi-partition(A,B)asavectorBif1Aif1iiixxpTheRayleighTheoremshows:Theminimumvalueforf(p)isgivenbythe2ndsmallesteigenvalueoftheLaplacianL.Theoptimalsolutionforpisgivenbythecorrespondingeigenvectorλ2,referredastheFiedlerVector.2,)()(jiVjiijppwpfWecanminimisethecutofthepartitionbyfindinganon-trivialvectorpthatminimisesthefunctionpLpTLaplacianmatrixSofar…Howcanwedefinea“good”partitionofagraph?Minimiseagivengraphcutcriterion.SpectralClustering(Simonet.al,’90)Howcanweefficientlyidentifysuchapartition?Approximateusinginformationprovidedbytheeigenvaluesandeigenvectorsofagraph.SpectralClusteringAlgorithmsThreebasicstages:1.Pre-processingConstructamatrixrepresentationofthedataset.2.DecompositionComputeeigenvaluesandeigenvectorsofthematrix.Mapeachpointtoalower-dimensionalrepresentationbasedononeormoreeigenvectors.3.GroupingAssignpointstotwoormoreclusters,basedonthenewrepresentation.SpectralBi-partitioningAlgorithm(Simon,’90)x11.5-0.8-0.60-0.10x2-0.81.6-0.8000x3-0.6-0.81.6-0.200x4-0.80-0.22.5-0.8-0.7x5-0.1000.81.7-0.8x6000-0.7-0.81.51.Pre-processingBuildLaplacianmatrixLofthegraph0.90.80.5-0.2-0.70.4-0.2-0.6-0.8-0.4-0.70.4-0.6-0.40.20.9-0.40.40.6-0.20.0-0.20.20.40.30.4-0.0.10.20.4-0.9-0.20.40.10.20.43.02.52.32.20.40.0Λ=X=2.DecompositionFindeigenvaluesXandeigenvectorsΛofthematrixLHowdowefindtheclusters?-0.7x6-0.7x5-0.4x40.2x30.2x20.2x1Mapverticestocorrespondingcomponentsofλ2SpectralBi-partitioning(continued)GroupingSortcomponentsofreduced1-dimensionalvector.Identifyclustersbysplittingthesortedvectorintwo.Howtochooseasplittingpoint?Naïveapproaches:Splitat0,meanorm