Attraktiv subgraf matchning är ett kraftfullt verktyg för explorativ gruvdrift av stora tilldelad nätverk. I många applikationer (t.ex. nätverk vetenskap team, intelligens analys, nance informatik), användaren kanske inte vet vad exakt s / han letar efter, och därmed kräver användaren att ständigt revidera den ursprungliga frågediagram baserat på vad s / han nds från nuvarande matchande resultat. En stor flaskhals i ett sådant interaktivt matchningsscenario är efficiency, eftersom helt enkelt omkörning av matchningsalgoritmen på den reviderade frågekurvan är beräkningsmässigt oöverkomlig. I detta dokument föreslår vi en familj av eektiva och eektiva algoritmer (FIRST) för att stödja interaktiv tilldelad subgrafmatchning. Det finns två huvudidéer bakom de föreslagna metoderna. Den rst är att omarbeta tillskrivelsen subgraph matchning problem som en cross-network node likhet problem, vars stora beräkning ligger i att lösa en Sylvester ekvation för frågekurvan och den underliggande data grafen. Den andra viktiga idén är att utforska smidigheten mellan de ursprungliga och reviderade frågorna, vilket gör att vi kan lösa den nya/uppdaterade Sylvester ekvation stegvis, utan att lösa det från grunden. Experimentella resultat visar att vår metod kan uppnå (1) upp till 16× speed-up vid tillämpning på nätverk med 6M+ noder; (2) bevara mer än 90% noggrannhet jämfört med befintliga metoder; och (3) skalor linjärt med avseende på storleken på datagrafen.
FÖRSTA algoritmen föreslås i REF för att stödja interaktiv tilldelad subgraph matchning, som omarbetas till en cross-network node likhet problem och beräkningen kan påskyndas genom att undersöka smidigheten mellan inledande och reviderade frågor.
FIRST: Fast Interactive Attributed Subgraph Matching
{'venue': "KDD '17", 'journal': None, 'mag_field_of_study': ['Computer Science']}