Graph klassificering är ett allt viktigare steg i många tillämpningsområden, såsom funktionsförutsägelse av molekyler och proteiner, datoriserad scenanalys, och anomali upptäckt i programflöden. Bland de olika metoder som föreslås i litteraturen, graf klassificering baserad på frekventa subgrafer är en populär gren: Grafer representeras som (vanligtvis binära) vektorer, med komponenter som anger om en graf innehåller en viss subgraf som är frekvent över datauppsättningen. På stora grafer står man dock inför det enorma problemet att antalet av dessa frekventa subgrafer kan växa exponentiellt med storleken på graferna, men bara ett fåtal av dem har tillräckligt diskriminerande kraft för att göra dem användbara för grafklassificering. Effektivt och diskriminerande funktionsval bland frekventa subgrafer är därför en viktig utmaning för grafbrytning. I den här artikeln föreslår vi ett tillvägagångssätt för att definiera urval på frekventa subgrafer, som kallas Cork, som kombinerar två centrala fördelar. För det första optimerar det ett submodulärt kvalitetskriterium, vilket innebär att vi kan ge en nästan optimal lösning med hjälp av giriga funktionsval. För det andra kan vårt submodulära kvalitetsfunktionskriterium integreras i gSpan, det toppmoderna verktyget för frekvent subgrafbrytning, och bidra till att beskära sökytan för diskriminativa frekventa subgrafer även under frekvent subgrafbrytning.
Cork Ref använder antalet korrespondenser för att mäta diskrimineringskraften i ett subgrafmönster och därigenom uppnå en teoretiskt nära optimal lösning.
Near-optimal supervised feature selection among frequent subgraphs
{'venue': 'IN SDM 2009', 'journal': None, 'mag_field_of_study': ['Computer Science']}