Querying Big Graphs within Bounded Resources查询有界资源中的大图

QueryingBigGraphswithinBoundedResources1YinghuiWuUCSantaBarbaraWenfeiFanUniversityofEdinburghSouthwestJiaotongUniversityXinWangBigreal-lifegraphs2socialscale100B(1011)Webscale1T(1012)brainscale,100T(1014)Real-lifescope100M(108)USroadHumanConnectome,(TheHumanConnectomeProject,NIH)knowledgegraphBTCSemanticWebWebgraph(Google)Internet(Opteproject)AnNSABigGraphexperiment,P.Burkhardt,etal,US.NationalSecurityAgency,May2013Socialgraph(300PBuserdata)Queryingbiggraphs3GivenaqueryQandadatagraphG,findanswersQ(G)Graphpatternmatching:knowledgediscovery,socialrecommendation,drugdesigning…Reachability:cybersecurity,metabolicanalysis,softwareengineering,Internetofthings…ChallengesGraphsaretoobigHardtoreducecomputationcomplexityLimitedresourceState-of-the-artTractableapproachesSSDlinearscanfornodesearch:1PB->1.9days,1EB->5.28yrsIndexing&CompressionCanwestillanswerQwithlimitedresource?Outline4ResourceboundedqueryansweringLocalized:GraphPatternQueriesResourceboundedsimulationqueriesResourceboundedsubgraphisomorphismNon-localized:ReachabilityResourceboundedreachabilityExperimentalstudyConclusion&FutureworkQueriesanddatagraph5Localizedqueries:canbeansweredlocallyGraphpatternqueries:simulationqueries(personalizedsocialsearch,egonetworkanalysis…)matchingrelationoverdQ-neighborhood

ofapersonalizednodeNon-localizedqueriesReachabilityqueriesMichael(Personalizednode)hikinggroupcyclingclub

member?cyclingloversMichael(uniquematch)hikinggroup………cycling

club

membercyclingfanshgmhg1hg2cc1cc2cc3cl1cl2cln-1clnMichael:“findcyclingfanswhoknowbothmyfriendsincyclingclubandmyfriendsinhikinggroups”(IBMWatson,FacebookGraphSearch,AppleSiri,WolframAlphaSearch…)Michaelcc1cl3cl7cln-1cl4cl9cl5……cl6cl16Eric…CanwestillanswerQwithlimitedresource?Makingbiggraph“small”6Idea:usingasmallgraphinsteadofGtomakeitfeasibletoanswerexpensivequeriesinbiggraphs.

Reduction(boundedresources:time,space,energy…)queryexactresultsqueryapproximate

resultsApproximation(guaranteedquality:

accuracy,errorrate,…)biggraphsmallgraphexpensive!Resource-boundedqueryanswering7onlinereductionsize|GQ|<=α|G|visitα*c|G|amountofdata(α*c<1)queryresultsqueryresultsApproximationAccuracy>=ηbiggraphGsmallgraphGQexpensive!Resource-boundedalgorithmAforqueryclassL

andanyG:withresourceboundαhasaccuracyguaranteeη

Hardnessresults8Exactresource-boundedquerying:η=100%IntractabilityNP-hardforsimulationqueries(evenwhenQisapathandGisaDAG)ReductionfromSetCoverNP-hardforsubgraphqueriesImpossibilityForanyα,thereexistsNOalgorithmforreachabilityquerieswithresource-boundαand100%accuracybound

Resource-boundedsimulation9

Reductionsize|GQ|<=α|G|inO(dG|Q||GQ|)timeSimulationqueryresultsqueryresultsApproximation100%forα>=biggraphGsmallgraphGQO(|Q||G|+|G|2)dG:maximumdegreeofdQ-neighborhoodgraphofp-node;d:diameterofQ;l:distinctlabelsizeinQf:maxnumberofnodeswithasamelabel&neighborinQResource-boundedsimulation:dynamicreduction10Preprocessing(auxiliaryinformation)dynamicreduction(computereducedsubgraph)ApproximatequeryevaluationoverreducedsubgraphlocalauxiliaryinformationGBooleanguardedcondition:labelmatchingCostfunctionc(u,v)Potentialfunctionp(u,v),estimatedprobabilitythatvmatchesuboundb,determinesanupperboundofthenumberofnodestobevisitedQdegree|neighbor|<label,frequency>…uvuvlabelmatchDynamicallyupdatedauxiliaryinformationuv？Resource-boundedsimulation:dynamicreduction11preprocessingdynamicreduction(computereducedsubgraph)ApproximatequeryevaluationoverreducedsubgraphMichaelhikinggroupcyclingclub?cyclingloversMichaelhikinggroup…cycling

club

membercyclingfanshgmhg1hg2cc1cc2cc3cl1cl2cln-1clncyclingclub

cc1cc2cc3cycling

club

member?cyclingloverscln-1clncyclingfanshgmhikinggrouphikinggroupFALSE---TRUECost=1Potential=3Bound=2TRUECost=1Potential=2Bound=2bound=14visited=16Matchrelation:(Michael,Michael),(hikinggroup,hgm),(cyclingclub,cc1),(cyclingclub,cc3),(cyclinglover,cln-1),(cyclinglover,cln)Resource-boundedreachability12

Reductionsize|GQ|<=α|G|ReachabilityqueryresultsReachabilityqueryresultsApproximation(experimentallyVerified;nofalsepositive,intimeO(α|G|)biggraphGsmalltreeindexGQO(|G|)Preprocessing:landmarks13Preprocessingdynamicreduction(computelandmarkindex)ApproximatequeryevaluationoverlandmarkindexMichaelcc1cl3cl7cln-1cl4cl9cl5……cl6cl16Eric…LandmarksalandmarknodecoverscertainnumberofnodepairsReachabilityofthepairsitcoverscanbecomputedbylandmarklabelscc1“Icanreachcl3”cl3cln-1,“cl3canreachme”cl4…cl6cl16HierarchicallandmarkIndex14LandmarkIndexlandmarknodesareselectedtoencodepairwisereachabilityHierarchicalindexing:applymultipleroundsoflandmarkselectiontoconstructatreeoflandmarkscc1cl7cln-1Michaelcc1cl3cl7cln-1cl4cl9cl5……cl6cl16Eric……cl16cl3cl5cl6cl4cl9…Booleanguardedcondition(v,source,dst)Costfunctionc(v):sizeofunvisitedlandmarksinthesubtreerootedatvPotentialP(v),totalcoversizeofunvisitedlandmarksasthechildrenofvCoversizeLandmarklabels/encodingTopologicalrank/rangeResource-boundedreachability15Michaelcc1cl3cl7cln-1cl4cl9cl5……cl6cl16Ericcc1…cl7cln-1…cl16cl3cl5cl6cl4MichaelEric“drilldown”?cl9…localauxiliaryinformation“rollup”Preprocessingdynamicreduction(computelandmarkindex)Approximatequeryevaluationoverlandmarkindexbi-directedguidedtraversalCondition=FALSE--Condition=?Cost=9Potential=46Condition=?Cost=2Potential=9Condition=TRUE……ExperimentalStudy16DatasetYoutube(1.61millionnodes,4.51millionedges)

(http://netsg.cs.sfu.ca/youtubedata)

YahooWebgraph(3millionnodes,14.98millionedges)(/catalog.php?datatype=g)AlgorithmsGraphpatternmatching:ResourceboundedsimulationalgorithmRBSimOptimizedstrongsimulationpatternmatchingMatchOptResourceboundedsubgraphisomorphismRBSubOptimizedVF2Reachability:ResourceboundedreachabilityRBReachBFSandoptimizedBFSovercompressedgraphsLM:applyinglandmarkvectors(4*Log|V|landmarks)Efficiencyofresourceboundedsimulation17Varyingα(10-5),YahooRbsimis5.5timesfasterthanMatch-OPT;RBSubis6.25timesfasterthanVF2-OPTonaverageVaryingα(10-5),YoutubeAccuracy18Varyingα(10-5),accuracy,Yahoo89%-100%forsimulationqueriesbothachieves100%accuracywhenα>0.0015%,Efficiencyofresourceboundedreachability19RBreachis62.5timesfasterthanBFSand5.7timesfasterthanBFS-OPT

Varyingα(10-4),YahooVaryingα(10-4),YoutubeAccuracy20Varyingα(10-4),accuracy,Yahoo>=96%achieves100%accuracywhenα>0.05%,Conclusion21ResourceboundedqueryingforbiggraphprocessingDynamicreduction+approximatequeryansweringLocalqueries:strongsimulation,subgraphisomorphismNon-localqueries:reachabilitytunableperformance,abalanceofresourceandanswerqualityMoretobedone…Maximumaccuracyratioη

resourceboundedalgorithmscanguarantee?Graphquerypatternswithoutpersonalizednodes,moregraphqueryclasses…Distributeddeployment(MapReduce,GraphLab)Deploymentinemergingapplications(knowledgegraph,cyber