Grafer är vanliga inom många områden såsom bioinformatik, sociala nätverk, webb- och cybersäkerhet. Grafmönsterbrytning har blivit ett viktigt verktyg i hanteringen och analysen av komplexa strukturerade data, där t.ex. indexering, klusterbildning och klassificering ingår. Befintliga grafbrytningsalgoritmer har uppnått stor framgång genom att utnyttja olika egenskaper i mönsterutrymmet. Tyvärr, på grund av den grundläggande roll subgraph isomorphism spelar i dessa metoder, kan de alla gå in i en fallgrop när kostnaden för att räkna upp en enorm uppsättning isomorphiska inbäddningar exploderar, särskilt i stora grafer. Den lösning vi föreslår för detta problem tillgriper en minskning av datautrymmet. För varje graf, vi bygger en sammanfattning av det och min denna krympta graf istället. Jämfört med andra tekniker för dataminskning som antingen minskar antalet transaktioner eller komprimerar mellan transaktioner, föreslår detta nya ramverk, kallat Summarize-Mine, en tredje väg genom att komprimera inom transaktioner. SummarizeMine är effektiv för att skära ner storleken på grafer, vilket minskar den inbäddade uppräkningskostnaden. Kompression kan dock förlora mönster samtidigt. Vi tar itu med denna fråga genom att generera randomiserade sammanfattningar och upprepa processen för flera rundor, där huvudidén är att sanna mönster sannolikt inte kommer att missa från alla rundor. Vi ger strikta probabilistiska garantier om sannolikheten för förlust av mönster. Experiment på verkliga malware spårdata visar att Summarize-Mine är mycket effektiv, som kan hitta intressanta malware fingeravtryck som inte avslöjades tidigare.
Chen och Al. REF visar att slumpmässiga sammanfattningar kan bidra till att effektivt minska storleken på den ursprungliga grafen och samtidigt kan bryta frekventa grafmönster.
Mining Graph Patterns Efficiently via Randomized Summaries
{'venue': 'PVLDB', 'journal': 'PVLDB', 'mag_field_of_study': ['Computer Science']}