Abstract-Detection av intressanta (t.ex. sammanhängande eller avvikande) kluster har studerats i stor utsträckning på enkla eller univariata nätverk, med olika tillämpningar. Nyligen har algoritmer utvidgats till nätverk med flera attribut för varje nod i den verkliga världen. I ett multiattribuerat nätverk är ofta ett kluster av noder bara intressant för en delmängd (subrymd) av attribut, och denna typ av kluster kallas subrymdskluster. I den nuvarande litteraturen är det dock få metoder som kan upptäcka subrymdskluster, vilket innebär samtidig urval av funktioner och upptäckt av nätverkskluster. Dessa relevanta metoder är mestadels heuristiska och anpassade för specifika tillämpningsscenarier. I detta arbete presenterar vi en allmän och teoretisk ram för upptäckt av intressanta subrymdskluster i stora multiattribuerade nätverk. Specifikt föreslår vi en subrymdsgrafstrukturerad matchande jaktalgoritm, nämligen SG-Pursuit, för att ta itu med en bred klass av sådana problem för olika poängfunktioner (t.ex. sammanhängande eller avvikande funktioner) och topologiska begränsningar (t.ex. anslutna subgrafer och täta subgrafer). Vi bevisar att vår algoritm 1) körs i nästan linjär tid på nätverksstorleken och det totala antalet attribut och 2) har rigorösa garantier (geometrisk konvergensgrad och snäv felbindning) i likhet med de senaste algoritmerna för glesa problem med urval av funktioner och problem med att upptäcka subgrafer. Som fallstudie specialiserar vi oss på SG-Pursuit för att optimera ett antal välkända poängfunktioner för två typiska uppgifter, inklusive upptäckt av sammanhängande täta och avvikande anslutna subrymdskluster i verkliga nätverk. Empiriska bevis visar att vår föreslagna generiska algoritm SG-Pursuit är överlägsen state-of-the-art metoder som är utformade specifikt för dessa två uppgifter.
I REF föreslås ett generiskt ramverk för att upptäcka subrymdskluster i tilldelade grafer.
A Generic Framework for Interesting Subspace Cluster Detection in Multi-attributed Networks
{'venue': '2017 IEEE International Conference on Data Mining (ICDM)', 'journal': '2017 IEEE International Conference on Data Mining (ICDM)', 'mag_field_of_study': ['Computer Science', 'Mathematics']}