Vi studerar ett nytt klusterproblem där de parvisa relationerna mellan objekten är kategoriska. Detta problem kan ses som kluster hörn av en graf vars kanter är av olika typer (färger). Vi introducerar en objektiv funktion som säkerställer att kanterna inom varje kluster har, så mycket som möjligt, samma färg. Vi visar att problemet är NP-hård och föreslår en randomiserad algoritm med approximation garanti proportionell mot den maximala graden av inmatningskurvan. Algoritmen iterativt väljer en slumpmässig kant som en pivot, bygger ett kluster runt den, och tar bort kluster från grafen. Även om den är snabb, lätt att implementera och parameterfri, tenderar denna algoritm att producera ett relativt stort antal kluster. För att lösa detta problem introducerar vi en variantalgoritm, som ändrar hur pivoten väljs och hur klustret byggs runt pivoten. Slutligen, för att ta itu med det fall där ett fast antal utdatakluster krävs, utformar vi en tredje algoritm som direkt optimerar den objektiva funktionen baserat på det alternerande minimeringsparadigmet. Vi utökar också vår objektiva funktion för att hantera fall där objektets relationer beskrivs med flera etiketter. Vi ändrar vår randomiserade approximationsalgoritm för att optimera en sådan utökad objektiv funktion och visar att dess approximationsgaranti förblir proportionell mot den maximala graden av grafen. Vi testar våra algoritmer på syntetiska och verkliga data från domänerna sociala medier, protein-interaktionsnätverk och bibliometri. Resultaten visar att våra algoritmer överträffar en basal algoritm både i uppgiften att rekonstruera en mark-sanning kluster och i termer av objektiv-funktionsvärde.
På samma sätt finner REF kluster av kanter sådana att kanterna på ett kluster har samma etiketter.
Chromatic Correlation Clustering
{'venue': 'TKDD', 'journal': None, 'mag_field_of_study': ['Computer Science']}