Vi fokuserar på stora grafer där noderna har attribut, till exempel ett socialt nätverk där noderna är märkta med varje persons jobbtitel. I en sådan inställning vill vi hitta subgrafer som matchar ett användarsökmönster. Till exempel, en "stjärna" fråga skulle vara, "hitta en VD som har starka interaktioner med en chef, en advokat, och en revisor, eller en annan struktur så nära det som möjligt". På samma sätt skulle en "loop"-fråga kunna hjälpa till att upptäcka en penningtvättsring. Traditionella SQL-baserade metoder, liksom nyare grafindexeringsmetoder, kommer inte att ge något svar när en exakt matchning inte finns. Vår metod kan hitta exakt-, såväl som nära-matcher, och den kommer att presentera dem för användaren i vår föreslagna "godhet" ordning. Till exempel tolererar vår metod indirekta vägar mellan t.ex. "CEO" och "Accountant" i ovanstående urvalsfråga, när direkta vägar inte existerar. Dess andra funktion är skalbarhet. I allmänhet, om frågan har nq noder och datagrafen har n noder, problemet behöver polynom tid komplexitet O(n nq ), vilket är oöverkomlig. Vår G-Ray ("Graph X-Ray") metod finner högkvalitativa subgrafer i tid linjär på storleken på datagrafen. Experimentella resultat på DLBP:s publikationsdiagram (med 356K noder och 1,9M-kanter) illustrerar både effektiviteten och skalbarheten i vårt tillvägagångssätt. Resultaten stämmer överens med vår intuition, och hastigheten är utmärkt. Det tar i genomsnitt 4 sekunder för en 4-node-fråga på DBLP-grafen.
I detta sammanhang fungerar Graph X-Ray (G-Ray) REF på tilldelade grafer för att hitta subgrafer som antingen matchar det önskvärda frågemönstret exakt, eller så nära som möjligt baserat på fördefinierade kriterier.
Fast best-effort pattern matching in large attributed graphs
{'venue': "KDD '07", 'journal': None, 'mag_field_of_study': ['Computer Science']}