Clustering noder i en graf är en användbar allmän teknik i datautvinning av stora nätverk dataset. I detta sammanhang föreslog Newman och Girvan [9] nyligen en objektiv funktion för grafklustring som kallas Q-funktionen och som möjliggör automatiskt urval av antalet kluster. Empiriskt har högre värden av Q-funktionen visat sig korrelera väl med bra grafkluster. I detta dokument visar vi hur optimering av Q-funktionen kan omformuleras som ett spektralavslappningsproblem och föreslår två nya spektralklusteralgoritmer som försöker maximera Q. Experimentella resultat visar att de nya algoritmerna är effektiva och effektiva när det gäller att hitta både bra kluster och lämpligt antal kluster i en mängd olika verkliga grafdatamängder. Dessutom är de spektralalalgoritmer mycket snabbare för stora glesa grafer, skalning ungefär linjärt med antalet noder n i grafen, jämfört med O(n 2 ) för tidigare kluster algoritmer med Q-funktionen. Inledning Stora komplexa grafer som representerar relationer mellan grupper av enheter är ett allt vanligare fokus för vetenskaplig undersökning. Exempel är sociala nätverk, webbgrafer, telekommunikationsnät, semantiska nätverk och biologiska nätverk. En av de viktigaste frågorna när det gäller att förstå sådana data är "Hur många samhällen finns det och vilka är communitymedlemskapen"? Algoritmer för att hitta sådana samhällen, eller automatiskt gruppera noder i en graf i kluster, har utvecklats inom en mängd olika områden, inklusive VLSI design, parallella datorer, datorseende, sociala nätverk, och på senare tid inom maskininlärning. Goda algoritmer för grafklustring är beroende av kvaliteten på den objektiva funktion som används. En mängd olika objektiva funktioner och klusteralgoritmer har föreslagits för detta problem, allt från hierarkisk klusterbildning till maxflödes-/minskärningsmetoder till metoder som bygger på trunkering av eigenrymden hos en lämpligt definierad matris. Under de senaste åren har mycket uppmärksamhet ägnats åt spektralklusteralgoritmer (t.ex. [11], [12], [14] ) som, explicit eller implicit, försöker * Forskningen i denna uppsats stöddes av National Science Foundation under Grant IRI-9703120 som en del av programmet Knowledge Discovery and Dissemination. SW stöddes också av ett nationellt Defense Science and Engineering Graduate Fellowship. † Institutionen för datavetenskap, University of California, Irvine globalt optimerar kostnadsfunktioner som Normalized Cut åtgärd [12]. De flesta av dessa metoder försöker balansera storleken på kluster samtidigt minimera interaktionen mellan olika noder. För de typer av komplexa heterogena nätverk som uppstår naturligt på många områden kan dock den fördomsfullhet som dessa strategier har gentemot kluster av lika storlek ses som en nackdel. Dessutom kan många av dessa åtgärder, såsom Normalized Cut, inte användas direkt för att välja antalet kluster, k, eftersom de ökar (eller minskar) monotont som k varierar. Nyligen utvecklades ett nytt tillvägagångssätt av Newman och Girvan [9] för att övervinna begränsningar av tidigare åtgärder för att mäta samhällsstrukturen. De föreslog "moduleringsfunktionen" Q, som direkt mäter kvaliteten på en viss klustring av noder i en graf. Det kan också användas för att automatiskt välja det optimala antalet kluster k, genom att hitta värdet av k för vilken Q maximeras, i motsats till de flesta andra objektiva funktioner som används för graf klustring. Låt G(V, E, W ) vara en oriktad graf som består av uppsättningen noder V, uppsättningen av kanter E, och en symmetrisk vikt matris W  på n×n, där n är antalet hörn. Vikterna w ij = w ji = [W ] ij är positiva om det finns en kant mellan hörn v i och v j, och 0 annars. Modularitetsfunktionen Q kan definieras som där P k är en partition av hörnen i k-grupper och där A(V, V ) = i-V,j-V w(i, j). Således A(V c, V c ) mäter inom-kluster summan av vikter, A(V c, V ) mäter summan av vikter över alla kanter fästa vid noder i kluster c, och A(V, V ) mäter summan av alla kantvikter i grafen. Med tanke på binära vikter för enkelhet, termen är den empiriska sannolikhetp c,c att båda ändarna av en slumpmässigt vald kant från G ligger i kluster c. Likaså Newman [10] och Newman och Girvan [9] visade över ett brett utbud av simulerade och verkliga grafer att större Q-värden korreleras med bättre graf kluster. Dessutom fann de att oviktade nätverk i verkligheten med hög samhällsstruktur i allmänhet har Q-värden inom ett intervall från 0,3 till 0,7. Figur 1 visar ett exempel på en enkel leksaksgraf med binära vikter, där grafens struktur visuellt tyder på 3 kluster. Även de maximala värdena för Q-funktionen visas för olika antal kluster k, och Q maximeras faktiskt för k = 3. Som påpekades i [10], Om inga kanter finns som ansluter hörn över kluster sedan Q = 1, och omvänt om antalet inter-cluster kanter är inte bättre än slumpmässiga då Q = 0. Vi har funnit empiriskt att Q-måttet fungerar bra i praktiken både när det gäller a) att hitta bra kluster av noder i grafer där samhällsstrukturen är uppenbar, och b) att ange vad lämpligt antal kluster k är för en sådan graf. I den här artikeln visar vi hur Newmans Q-mått kan relateras till den bredare familjen av spektralklustermetoder. Specifikt: • Vi visar hur problemet med maximering av modularitetsmåttet Q kan omformuleras som ett eigenvekatorproblem med en matris som vi kallar "Q-Laplacien". På detta sätt länkar vi arbetet med grafklustring med hjälp av Q-måttet till relevant arbete på spektralklustring (t.ex., • Vi använder eigenvektorns formulering av maximering Q för att härleda två nya spektralgrafikklusteralgoritmer. En av dessa algoritmer söker direkt en global optimal av Q-funktionen. Den andra algoritmen liknar Newmans agglomerativa klusteralgoritm [10], eftersom den försöker maximera Q via lokal iterativ förbättring. • Vi jämför de nya algoritmerna med Newmans algoritm på olika grafdatauppsättningar och illustrerar empiriskt att: -den spektrala metoden för att maximera Q ger resultat som, när det gäller klusterkvalitet, är jämförbara eller bättre än resultat från Newmans hierarkiska algoritm, och -de föreslagna algoritmerna är linjära per iteration i antalet noder och kanter i grafen, jämfört med kvadratisk komplexitet i antalet noder för den ursprungliga algoritmen som föreslogs av Newman [10]. 2 Spektrala metoder för att maximera Q-funktionen Överväg för det ögonblick som antalet kluster, k, är fast. Vi använder följande strategi för att ta itu med problemet med att hitta en partitionering som maximerar Q(P k ) enligt följande: 1. Omformulera problemet med att maximera Newmans Q-funktion som ett diskret kvadratiskt uppdragsproblem. 2. Utgångspunkten är följande: Ungefär det resulterande uppdragsproblemet genom att koppla det till en kontinuerlig som kan lösas analytiskt med eigen-dekomposition tekniker. 3. Vad är det som händer? Beräkna de översta k − 1 eigenvektorerna av denna lösning för att bilda en k‐1-dimensionell inbäddning av grafen i ett euklideanskt utrymme. Använd "hard-assignment" geometrisk klusterbildning (k-means algoritm) på detta inbäddande för att generera en klusterering P k. Copyright © by SIAM. Otillåten reproduktion av denna artikel är förbjuden 275 Nedan beskriver vi var och en av dessa steg. I avsnittet som följer, Avsnitt 3, beskriver vi sedan beräkningsdetaljer för två föreslagna klusteralgoritmer baserade på detta tillvägagångssätt. Vi antar att G är enkel, d.v.s., G innehåller inga själv-loops eller parallella kanter, och är ansluten, dvs., det finns en väg från någon vertex till någon annan vertex. Låt D N×n vara en diagonal matris som har d it ith diagonala ingång och 0 överallt annars, där d i = j w ij. Vi betecknar diagonalmatrisen som härleds från en n × n-matris X som diag(X) n×n där [diag(X)] ij = [X] ij om i = j och 0 annars. Låt slutligen st(X) = i [X] ii vara spår av matris X. För att förenkla notationen skriver vi om Q enligt följande:, och x ic = 0 annars, för 1 ≤ c ≤ k. Observera att eftersom varje vertex bara kan vara i ett kluster, X1 k = 1 n. Vi kan omformulera Q i termer av tilldelningsmatrisen X enligt följande: där d  till n×1 sådan att komponenten d i är lika med den viktade graden av vertex i och vi skriver om A(V, V ) som vol G, volymen av grafen G. Således, där D = dd T. Eftersom för varje matris A och tilldelningsmatris X, tr ( Ax c, kan vi ytterligare minska Q enligt följande: där W = V G W. Problemet med maximering Q kan sedan uttryckas som: där M  på k×k är en diagonal matris med diagonal post [M ] ii =  och V i..  för att förenkla antalet noder i klustret V i. Att hitta en uppdragsmatris X som maximerar (2.3) är NP-komplett. För att ta itu med detta kan vi försöka härleda en bra approximation genom att slappna av diskretion begränsningar som X ij  och {0, 1}, så att istället X ij 1. Detta omvandlar det diskreta optimeringsproblemet till ett som är kontinuerligt. För att hitta den optimala avslappnade X, ta derivatan av följande uttryck med avseende på X: där ί k×k är den diagonala matrisen av Lagrangian multiplikatorer. Ställa in detta lika med 0 och omgruppering termer vi har: där L Q = D −W och vi hänvisar till denna diagonal matris som "Q-Laplacien". Förutom att notera dess likhet i form av standard Laplacian, vi observerar att detta är en standardmatris eigenvärde problem som kan lösas med hjälp av standard eigendecomposition metoder. Dessutom, hade vi normaliserat den ursprungliga matrisen W så att alla rader summan till en och hade vi också lagt tillbaka i normaliseringskonstanten som vi tog ut från ekvation (2.2) då skulle vi ha följande eigen value ekvation: n W där E är en matris av alla och W är matrisen W normaliserad så alla rader summan till en. Den första termen i denna ekvation kan ses som en dämpning term som säkerställer att det finns kanter mellan alla noder av mycket liten vikt och den andra termen är den ursprungliga viktmatrisen efter skalning och normalisering. Som n → ∞, den första termen kommer att närma sig 0 mycket snabbare än den andra termen, och kommer därför att spela en försumbar roll för att bestämma eigenspace av matrisen. Således, för även måttligt stora värden av n, det verkar rimligt att W kommer att ge en nära approximation till L Q, som vi kallar den "normaliserade Q Laplacian." 1 I detta dokument kommer vi att använda den enklaste metoden Copyright © by SIAM. Otillåten reproduktion av denna artikel är förbjuden 276 för normalisering av en matris så dess rader summan till en, nämligen att vänster multiplicera matrisen W med D −1. Fördelen med att använda W = D −1 W som en approximation till L Q är att det är lätt att beräkna, det är väl studerat, särskilt i förhållande till Markov kedjor där det är känt som övergångsmatrisen, och det behåller sparhet så att vi kan använda snabba metoder för eigendecomposing en sparse matris. Det sista steget i detta ramverk är att iterera över olika värden av k, att söka efter de bästa kluster (högsta Q(P k ) poäng). För varje k försöker vi hitta den optimala partitioneringen, d.v.s. en "hård tilldelning" av noderna till k-kluster, baserat på att gruppera raderna i matrisen X. I detta avsnitt föreslår vi två nya algoritmer för att samla grafer som bygger på insikter som utvecklats i föregående avsnitt. Anta att vi söker upp till ett maximum av K-kluster och att vi har en viktmatris W  på nxn. Båda våra föreslagna algoritmer nedan börjar med att beräkna de översta K − 1 eigenvectors (till skillnad från triviala all-ones eigenvector) som motsvarar ekvation 2.6. Specifikt: ] från M med hjälp av en sparse eigenvector decomposition metod såsom en variant av Lanczos metoden eller subrymd iteration. I de experimentella resultaten i denna uppsats beräknar vi K − 1 eigenvektorer med hjälp av Implicitly Restarted Lanczos Method (IRLM) [2]. Om man gör det konservativa antagandet att det finns O(K) extra Lanczos steg, då IRLM har sämre-fall tid komplexitet O(mKh + nK 2 h + K 3 h) där m är antalet kanter i grafen, och h är antalet iterationer som krävs fram till konvergens. För glesa grafer, där m n, och där K n, fann vi IRLM att vara extremt snabb, tar nära linjär tid med avseende på antalet noder n. I algoritmerna nedan, initierade vi k-means så att start centroider valdes att vara så nära ortogonala som möjligt. Initialisera k-medel på detta sätt inte ändra tid-komplexitet men kan avsevärt bidra till att förbättra kvaliteten på kluster, som diskuteras i [11], samtidigt minska behovet av flera slumpmässiga omstarter. Dessutom kan båda algoritmerna nedan köras för alla k-värden mellan en lägre gräns k min och en övre gräns k max. När inget annat anges utgår vi från att vi har k min = 1 och k max = K. I det fall k = 1, Q = 0 och klustret bara är alla hörn i grafen. 3.2 Algoritm Spectral-1 Denna algoritm tar som ingång en Eigenvekor matris U K, och består av följande steg: (a) Forma matrisen U k från den första k − 1 kolumner av U K. (b) Skala raderna av U k med hjälp av l 2 -norm så att de alla har enhetslängd (c) Klustra radvektorer av U k med hjälp av k-medel eller någon annan snabb vektor-baserad kluster algoritm. För k = 1, är klustret bara grafen själv. Denna algoritm liknar i andemening den som utvecklades i [11]. Båda algoritmerna inbäddade inmatningsgrafen i ett Euclidean utrymme genom att eigendecomposing en lämplig matris och sedan kluster inbäddning med hjälp av en geometrisk kluster algoritm. Vi validerade experimentellt påståendet som gjordes i [11] att radnormalisering av matrisen av eigenvekatorer, så att radvektorerna projiceras på enheten hypersfär, ger mycket högre kvalitet resultat. Spectral-1-algoritmen skiljer sig åt i tre viktiga avseenden till detta tidigare arbete (utöver den mindre ontologiska punkten som vårt ramverk är utformat för att samla grafer medan deras är utformad för att samla verkliga värden): 1. Medan i [11] matrisen som är eigendecom-2, var implicit valt att optimera Normalized Cut, vår algoritm är uttryckligen utformad för att optimera modularitet Q. 2. Utgångspunkten är följande: Vår algoritm har en naturlig metod för modellval, Q-måttet, som är samma objektiva funktion som vår inbäddning bygger på. Eftersom Normalized Cut är partisk av storleken på k, kan det inte användas för att välja den bästa k. 3. Vår algoritm kräver inte ett extra steg av modellval för att säkerställa: a) kantvikterna skalas korrekt och b) grafen är sparifierad. Om länkar inte är sparifierade i algoritmen i [11], är tiden komplexitet O(n 3 ). Upphovsrätt © av SIAM. Otillåten reproduktion av denna artikel är förbjuden 277 3.3 Algoritm Spectral-2 Den andra algoritmen vi föreslår är en snabbare version av algoritmen i föregående avsnitt (Spectral-1). Den använder en girig strategi rekursiv bisektion för att söka över olika värden av k. På grund av denna strategi behöver den inte hitta så hög kvalitet en klustering (så högt ett Q-värde) som den andra metoden, men det kommer att vara snabbare eftersom det går från k kluster till k+1 bara en del av data behöver kluster snarare än alla data. Algoritmen tar igen som ingång eigenvektorns matris U K som tidigare och består av följande steg: 1. Initiera k, det nuvarande antalet kluster, till k min. Initialisera P, den bästa klusteruppdrag sett hittills, till kluster som produceras genom att köra k-medel med k satt till k min kluster. Om k min = 1, initiera sedan helt enkelt P att vara en kluster som innehåller alla noder i grafen. 2. Utgångspunkten är följande: Upprepa tills k > K eller inga fler splitar är möjliga: i. Om den inte redan har bildats, forma matrisen U k från den första k − 1 kolumner av U K och skala raderna med hjälp av l 2 - norm så att de alla har enhetslängd ii. Bilda matrisen U k,c från U k genom att bara hålla rader som motsvarar noder i V c iii. Kör k-medel med 2 kluster på U k,c för att få två nya sub-kluster,V c,1 och V c,2. Iv. Forma en ny partition, P genom att ställa in P = P och ersätta motsvarande V c med V c,1 och V c,2 v. Om Q(P ) > Q(P ), acceptera uppdelningen genom att ersätta motsvarande V c i P nya med V c,1 och V c,2, annars avvisa den och lämna P nya oförändrad. Vi. Vad är det? Tilldela k att vara det (eventuellt nya) antalet kluster i P-ny Idén bakom denna algoritm är att börja med k-min-kluster och istället för att köra k-means på hela grafen för efterföljande värden av k som vi gjorde i den tidigare algoritmen, försöker vi istället rekursivt dela varje kluster i två barnkluster om uppdelningen ger ett högre värde av Q. Genom att fortsätta detta förfarande tills inga fler uppdelningar är möjliga eller tills K-kluster har hittats, hamnar vi med en klustering med det högsta värdet av Q som påträffas längs vägen. Den särskilda algoritmen ovan är ordningskänslig i den meningen att cykling genom kluster i en annan ordning kan producera olika resultat-dock har vi inte märkt någon särskild känslighet för ordning i de datamängder som beskrivs senare i tidningen. Till skillnad från många andra rekursiva bisektionsmetoder är modellval här naturligt och enkelt. Vi väljer att acceptera en split om spliten resulterar i ett högre värde på Q. Nackdelen med denna algoritm är naturligtvis att vi byter hastighet med exakthet. Algoritmen använder en girig strategi, där en split aldrig kan återkallas och så ett dåligt val negativt påverkar alla andra val längre ner i samma gren. Således är kvaliteten på resultaten inte nödvändigtvis lika bra som med Spectral-1, även om de fortfarande är generellt konkurrenskraftiga som vi kommer att se nedan. Det finns en subtilitet i denna algoritm i att, om lämnas okontrollerad, varje kluster för vilken ett split försök gjordes men misslyckades skulle upprepas nästa gång genom loopen. Därför tillåter vi bara ett enda försök att dela upp ett visst kluster. O(ndke) där n är antalet datapunkter, d är dimensionaliteten för varje punkt, och e är antalet iterationer som krävs för att k-medelvärden ska konvergera. Elkan [5] föreslog en mycket snabbare version av k-medel. Det ger exakt samma resultat som standard k-medelvärden men använder olika geometriska ojämlikheter för att avsevärt minska antalet distansberäkningar som krävs. Elkan fann att med sin föreslagna algoritm är den totala tids komplexiteten ungefär O (nke) där e är antalet iterationer. Vi använder denna algoritm för vår implementering av k-medel i både Spectral-1 och Spectral-2. Den resulterande komplexiteten för klusterering i Spectral-1, med hjälp av Elkans snabba k-means algoritm, är ungefär O(nK 2 e). För Spectral-2 är beräkningskomplexet inte lika lätt att uppskatta. I värsta fall (helt obalanserade kluster där den största klustret delas vid varje iteration) kommer det att ha samma komplexitet som Spectral-1. Men i praktiken har vi funnit att det är betydligt snabbare än Spectral-1 och kommer att visa experimentella resultat senare i tidningen som illustrerar detta. Dessutom, för båda algoritmerna finns det ytterligare komplexitet av O(mKh + nK 2 h + K 3 h) för att beräkna matrisen av eigenvectors U K, med hjälp av IRLM. Således har Spectral-1 och Spectral-2 en övergripande värsta fall tid komplexitet av O(mKh+nK 2 h+K 3 h+nK 2 e). Således, för glesa grafer, där m n, algoritmerna kommer att skala ungefär linjärt som en funktion av antalet noder n. Detta är i motsats till Newmans algoritm som har komplexitet O(n 2 ) även för glesa grafer, och därmed inte skala upp lika bra till stora värden av n. Experimentella resultat 4.1 Kluster ord från WordNet Vi illustrerar först hur olika val för grafen inbäddning kan påverka kvaliteten på kluster. Vi använder en relativt liten oviktad graf extraherad från WordNet databasen av ordbetydelser och semantiska relationer [8]. Anledningen till att vi valde denna datauppsättning var att man omedelbart kan bedöma kvaliteten på kluster eftersom intuitivt kluster bör innehålla ord som delar vanliga semantiska funktioner som är igenkännliga. Vi skapade en oviktad oriktad graf där noder representerar ord och en kant finns mellan två noder om någon av följande semantiska relationer existerar mellan dem: synonymer, anonymitet, hypernymy, hyponomi, meronymy, troponymy, kausalitet och påbud. Hela grafen innehåller 82670 noder. Vi extraherade en subgraf bestående av alla noder vars kortaste väg avstånd från ordet "vetenskap" är inte mer än 3. Vi tog också bort alla noder med grad 1 så att graf layouten inte skulle vara alltför rörigt. Att lägga till denna begränsning hade liten inverkan på klungornas kvalitet. Den resulterande subgrafen innehåller 230 noder och 389 kanter. Figur 2 visar den bästa klusterbildningen som finns med Spektral-1-algoritmen. För denna klusterbildning fanns 12 kluster och Q = 0,696. Tabell 1 visar tio representativa ord från fem slumpmässiga kluster. Figur 3 visar hur moduläriteten Q varierar med k när var och en av följande tre typer av matriser används i steg 1 av den första algoritmen och eigenvectors beräknas exakt: standard Q Laplacian L Q, normaliserad Q Laplacian L Q, och övergångsmatrisen D −1 W. Vi kan se att med hjälp av övergångsmatrisen i steg 1 ger en mycket bra approximation till den normaliserade Q matrisen. Vi kan också se att standarden Q Laplacian något underformerar båda dessa matriser. Detta stämmer överens med andra författares iakttagelser att den normaliserade Laplacian ger bättre resultat än standarden Laplacian (t.ex. [12], [14] ). Vårt nästa exempel visar förmågan hos båda våra algoritmer att identifiera kända kluster. Det oviktade nätverket drogs från spelplanen som spelades mellan 115 NCAA Division I-A Amerikanska college fotbollslag år 2000. Varje nod i detta nätverk representerar ett college fotbollslag och varje kant representerar det faktum att två lag spelade tillsammans. Eftersom den sanna konferens som varje lag tillhör är känd a-priori, och eftersom inter-konferensspel spelas oftare än intra-konferensspel, de grupper av lag som bildar konferenser motsvarar naturliga kluster som bör identifieras i diagrammet. Figur 4 visar att detta verkligen är fallet när spektral-1-algoritmen identifierade det korrekta antalet kluster och dessutom var varje grupptilldelning till ett kluster som gjorts av algoritmen korrekt. 3 Vår andra algoritm, Spectral-2, gjorde nästan lika bra att göra mycket få misstag. Misstagen var:
White och Smyth (WS) föreslår en snabb spektral kluster algoritm i REF.
A spectral clustering approach to finding communities in graphs
{'venue': 'In SIAM International Conference on Data Mining', 'journal': None, 'mag_field_of_study': ['Computer Science']}