I en mängd nya tillämpningar måste man avgöra om en graf G matchar en annan Gp, dvs. om G har en topologisk struktur som liknar Gp. De traditionella begreppen graf homomorfism och isomorfism misslyckas ofta med att fånga den strukturella likheten i dessa tillämpningar. I detta dokument studeras revideringar av dessa begrepp, vilket ger en fullständig behandling från komplexitet till algoritmer. (1) Vi föreslår p-homomorfism (p-hom) och 1-1 p-hom, som utvidgar graf homomorfism och subgraph isomorfism, respektive genom att kartlägga kanter från en graf till stigar i en annan, och genom att mäta likheten av noder. (2) Vi introducerar mätvärden för att mäta graf likhet, och flera optimeringsproblem för p-hom och 1-1 p-hom. (3) Vi visar att beslutsproblemen för p-hom och 1-1 p-hom är NP-komplett även för DAGs, och att optimeringsproblemen är approximativa-hårda. (4) Trots detta tillhandahåller vi approximativa algoritmer med påvisbara garantier för matchkvalitet. Vi verifierar experimentellt effektiviteten av de reviderade begreppen och effektiviteten av våra algoritmer i webbplats matchning, med hjälp av verkliga och syntetiska data.
Nyligen, Fan et al. REF studerade 1-1 p-homomorphisms som utvidgar injicerande graf homomorphisms genom att slappna av kanten bevarande tillstånd.
Graph Homomorphism Revisited for Graph Matching
{'venue': 'PVLDB', 'journal': 'PVLDB', 'mag_field_of_study': ['Computer Science']}