Gruvning täta subgrafer är en viktig operation på grafer; det definieras som att hitta alla subgrafer som ofta visas i en databas enligt en given frekvenströskel. De flesta befintliga arbeten förutsätter en databas med många små grafer, men moderna tillämpningar, såsom sociala nätverk, citeringsgrafer eller proteinproteininteraktioner i bioinformatik, är modellerade som en enda stor graf. I detta papper presenterar vi GRAMI, ett nytt ramverk för frekvent subgrafbrytning i en enda stor graf. GRAMI tillämpar ett nytt tillvägagångssätt där man endast finner den minimala uppsättningen fall för att uppfylla frekvenströskeln och undviker en kostsam uppräkning av alla fall som krävs enligt tidigare tillvägagångssätt. Vi följer vårt tillvägagångssätt med en heuristisk och optimeringar som avsevärt förbättrar prestandan. Dessutom presenterar vi en förlängning av GRAMI som bryter frekventa mönster. Jämfört med subgrafer, mönster erbjuder en mer kraftfull version av matchning som fångar transitiva interaktioner mellan graf noder (som vän till en vän) som är mycket vanliga i moderna applikationer. Slutligen presenterar vi CGRAMI, en version som stöder strukturella och semantiska begränsningar, och AGRAMI, en ungefärlig version som producerar resultat utan falska positiva. Våra experiment på verkliga data visar att vårt ramverk är upp till 2 storleksordningar snabbare och upptäcker mer intressanta mönster än befintliga metoder.
GRAMI REF upptäcker ofta subgrafmönster utan kantetiketter.
GRAMI: Frequent Subgraph and Pattern Mining in a Single Large Graph
{'venue': 'PVLDB', 'journal': 'PVLDB', 'mag_field_of_study': ['Computer Science']}