大图搜索挑战性与相关技术.pptx

大图搜索：挑战性与相关技术(Big Graph Search:Challenges and Techniques)2024/5/22 周三1无处不在,日常接触很多超大规模图！22024/5/22 周三应用案例传统的软件剽窃检测工具难以检测出一些“深层”剽窃问题基于“图模式匹配”的新工具将程序源代码表示为程序依赖图2.通过图模式匹配检测结构的相似性来判断软件剽窃3软件剽窃检测12024/5/22 周三应用案例由于“基于位置的服务(LBS)”的广泛应用，图搜索大量应用到交通网络.Example:司机Mark想从美国加州的Irvine到Riverside.如果Mark想驾驶car最短的时间到达Riverside,那么这个问题可以看做为图的最短路径问题，然后找到的方案是StateRoute261.4路线规划3如果Mark想驾驶truck运输危险物品，则有的路和桥是不允许通过的，路线的选择是受约束的.这样可以通过正则表达式等方法来表达约束条件来搜索最佳的交通路线.如果考虑的实时交通情况。2024/5/22 周三应用案例推荐系统有着广泛的应用，如socialmatchingsystems.图搜索是一种非常有用的推荐工具.5推荐系统4猎头想找一位生物学家(Bio)来帮助一组软件开发人员(SEs)来分析基因数据.猎头通过专家推荐网(如LinkedIn)搜索图中顶点表示人，标签为专长图中边表示推荐，如HR1推荐Bio1,AI1推荐DM12024/5/22 周三提纲什么是图搜索(Revisited)?大图搜索挑战性大图搜索相关技术总结62024/5/22 周三什么是图搜索？(What is Graph Search？)2024/5/22 周三7图搜索8提出统一的定义5(始叫图匹配):标注：给定模式图Gp和数据图G:检测是否GpmatchG;查找G中所有matchGp的子图两类查询:布尔查询(Yes/No)函数查询，可以调用布尔查询图中顶点或者边常常带有标签模式图通常比较小(如10个顶点),但数据图很大(如上亿个顶点)2024/5/22 周三图搜索9不同的“match”语义表示不同类型的图搜索,包括:最短路径/距离3子图同构11图同态及其扩展9图模拟及其扩展7,8图关键字搜索6紧邻查询10图搜索是一个非常“general”概念!2024/5/22 周三为什么需要图搜索?(Graph Search,Why Bother?)2024/5/22 周三10The need for a Social Search Engine文件系统 1960年代：非常简单的搜索功能数据库-1960中期：SQL查询语言互联网-1990年代：关键字搜索引擎社会网络-1990后期:11文件系统数据库互联络图搜索是一种新型社会搜索模式！社会网络Facebook与2013年1月16日推出“graphsearch”影响到了Google、Yelp和LinkedIn;Yelp股价当天下降7%2024/5/22 周三图搜索 vs.关系数据库 1212Query：查找AlbertoPepe所有朋友名字Step 1:Theperson.nameindex-theidentifierofAlbertoPepe.log2nStep 2:Thefriend.personindex-kfriendidentifiers.log2x:xkfriendnames.klog2n2024/5/22 周三图搜索 vs.关系数据库 1213Step 1:Thevertex.nameindex-thevertexwiththenameAlbertoPepe.log2n)Step 2:Thevertexreturned-thekfriendnames.k+x)Query：查找AlbertoPepe所有朋友名字搜索效率由(k+1)log2n提高到log2n2024/5/22 周三图搜索 vs.Web搜索关键字vs.短语、短句子网页vs.实体(人，社群等)无生命特征vs.人的行为特征历史vs.未来142024/5/22 周三学术界关注15Social computing&Web 2.02024/5/22 周三大图搜索的挑战性(Challenges)2024/5/22 周三16大图数据，如社会网络等17数据量大：高效的图搜索需要在均衡查询性能与准确性数据变化频繁：融合数据的动态性和时间特征数据丢失和不确定性：提高数据的质量，减少负面影响.2024/5/22 周三FAE法则在大量、动态和不确定图数据中：F:如何提供友好的图搜索界面？A:如何搜索“信息”更准?E:如何搜索“信息”更快?18准确性高效性友好性2024/5/22 周三友好性(Friendliness)19如何以友好的方式提供“图搜索”的查询界面？关键字的搜索模式非常友好直接让用户输入模式图非常不友好提供方便的方式隐式表达查询图如，Facebook采用简单化的自然语言Facebook Graph Search2024/5/22 周三如，影响力事件组织者搜索(SIGMOD2014)20以关键字的方式搜索社会网络图中k个事件组织者融合了图上的关键词搜索融合了事件的影响力传播提出了具有性能保障的近似算法-近似比(1/2-)Facebook Graph SearchBob“Psychology”,“Sociology”Tom,“MachineLearning”,“DataMining”Sam,“Database”,“DataMining”Bill,“NLP”,“MachineLearning”查询示例：K=2Q=Psychology,Sociology,Datamining2024/5/22 周三准确性(Accuracy)搜索北航的信息：北航、北京航空航天大学、北京航空航天大學、Beihang、BeihangUniversity、BeijingUniversityofAeronauticsandAstronautics21如何搜索“信息”更准?用户意图理解（融合用户的行为特征）融合知识图谱-KnowledgeGraph基于知识/用户意图的查询转换搜索北航周围的饭店人在美国vs.人在北航人在北航:中午12点vs.半夜12点移动互联网知识图谱2024/5/22 周三高效性(Efficiency)22如何搜索“信息”更快?查询近似技术数据近似技术天下武功天下武功 唯快不破唯快不破Inexact近似性Incremental增量性 Inductive 归纳性大数据的计算特征=3IR=Q(D)2024/5/22 周三大图搜索的查询技术(Query Techniques for Big Graph Search)R=Q(D)2024/5/22 周三23查询近似技术24主要思想：对一类查询复杂性高的查询语言Q，变换为一类查询复杂性低的查询语言Q，并且尽量不影响查询结果的准确性。approximationQ(D)Q(D)挑战:平衡查询的复杂性和查询的准确性!2024/5/22 周三如，强模拟(TODS 201413&VLDB 201214)子图同构11:给定模式图Q,数据图G的子图Gs：Q图同构Gs如果存在一一映射函数f:VQVGs满足：对Q中的任何顶点u，u和f(u)有相同的标签边(u,u)在Q当且仅当(f(u),f(u)在GsQ子图同构G，如果G中存在如上子图Gs25子图同构(NP-Complete)approximation强模拟(O(n3)优点：Q和Gs一模一样缺点：NP完全问题；最坏情况下指数个匹配子图；约束过于严格2024/5/22 周三子图同构26组成一个软件开发团队强模拟：返回F3+F4+F5;子图同构：返回空集！子图同构约束过于严格，并不适合一些新型应用！2024/5/22 周三Terrorist Collaboration Network27“Thosewhoweretrainedtoflydidntknowtheothers.Onegroupofpeopledidnotknowtheothergroup.”(OsamaBinLaden,2001)2024/5/22 周三强模拟28子图同构强模拟双模拟图模拟Topology preservation,bounded matches,and solvable in cubic time查询结果保持70-80%子图同构结构，效率提高100倍2024/5/22 周三大图搜索的数据技术Data Techniques for Big Graph SearchR=Q(D)2024/5/22 周三29数据近似技术30主要思想：对一类查询复杂性高的查询语言Q，将查询数据D变换机器能够高效处理的较小量D，并且尽量不影响查询结果的准确性。approximationQ(D)Q(D)挑战:平衡查询的效率和查询的准确性!D=HARD(D)+SOFT(D)二八定律：在众多现象中，80%的结果取决于20%的原因2024/5/22 周三如，异常检测(ICDM 201315&under review 16)矩阵是图的一种常用表示方式，其存储代价较高数据近似1：将一部分极小的数据项用0替换对计算特征向量的影响有限(理论证明)数据近似2：将n*d维矩阵转换为n*k维矩阵n为图顶点的数量，d为图中社群的数量，kd一个d维向量的第i维的值实际上表示顶点属于该社群的权重31经实验分析，在准确性影响不大的情况下提高了检测效率!2024/5/22 周三如，最短路径/距离(CoRR17)针对无向有权图，提出了概念“proxy”代理代表的区域(DRA)互不重叠将代理代表的区域去掉后，不影响查询结果准确性32使用真实公路图实验，图的大小减少1/3!性质：给定图G中两点u和v，代理分别为up和vp，则有：（1）path(u,v)=path(u,up)+path(up,vp)+path(vp,v)（2）dist(u,v)=dist(u,up)+dist(up,vp)+dist(vp,v)2024/5/22 周三分布式数据处理技术现实中的图通常非常大，使用单机来管理和查询图不现实:Yahoo!Web图有140顶点Facebook:超过10用户现实活中的图通常是分布式的:Google,Yahoo!andFacebook都有大规模的数据中心存储数据ss33Q(D)Q(Di)Q(D1)Q(Dn)2024/5/22 周三如，分布式图模式匹配(TODS 2014&WWW 2012)机群：具有等同计算能力的多台机器(发起查询的指定为协调者);任何一台机器能够直接向其他机器发送任意数量的消息;所有机器通过本地计算和消息传送协同完成任务.3434提出分布式计算模型3:分布式算法复杂性指标:1.机器访问次数:访问一台机器的最大次数(交互复杂性)2.最大完工时间:所有机器中最长的完工时间(效率)3.通讯数据量:不同机器之间的通讯消息的量和(网络带宽的消耗)2024/5/22 周三增量计算技术35Q(D+)Q(D)+Q()Incrementalcomputation已有计算结果2024/5/22 周三增量计算技术将索引系统改为增量的方法：将文档的平均处理时间减少为1%当每天处理的文档数据一样是，将文档的平均老化时间减少50%36从“零”开始是对计算资源的极大浪费!GooglePercolator 18:如，增量模式匹配(VLDB 20108):提高效率，同时也是应对数据动态性的一种有效方法2024/5/22 周三其它数据技术数据索引：空间代价、构建时间代价、查询效率提高37数据抽样：Q(D)Q()samplingQ(D)Q(D)compression数据压缩：数据划分：Q(D)Q(D1)+Q(Dn)partitioningWork in progress！2024/5/22 周三Ring系统：凝聚理论、算法和技术38 Ring典型应用异常事件分析与预警微博图片识别微博心情搜索360度全面事件预警oneringtorulethemall2024/5/22 周三图搜索是一种新型社会搜索模式大图搜索的应用与挑战(FAE法则)解决大图搜索的相关技术小结39Just a start,there is a long way to go for Big Graph Search!2024/5/22 周三Acknowledgements40Collaborators:CharuAggarwal,SouravSBhowmick,YangCao,GaoCong,WenfeiFan,KaiyuFeng,JinpengHuai,JiaLi,JianxinLi,XudongLiu,NanTang,HaixunWang,TianyuWo,YinghuiWu,WeirenYu,They are from:2024/5/22 周三References1ChaoLiu,ChenChen,JiaweiHanandPhilipS.Yu,GPLAG:detectionofsoftwareplagiarismbyprogramdependencegraphanalysis.KDD2006.2J.Ferrante,K.J.Ottenstein,andJ.D.Warren.Theprogramdependencegraphanditsuseinoptimization.ACMTrans.Program.Lang.Syst.,9(3):319349,1987.3Rice,M.andTsotras,V.J.,Graphindexingofroadnetworksforshortestpathquerieswithlabelrestrictions,VLDB2010.4ShuaiMa,YangCao,JinpengHuai,andTianyuWo,DistributedGraphPatternMatching,WWW2012.5ShuaiMa,YangCao,TianyuWo,andJinpengHuai,SocialNetworksandGraphMatching.CommunicationsofCCF,2012(inChinese).6C.C.AggarwalandH.Wang.ManagingandMiningGraphData.Springer,2010.7WenfeiFan,JianzhongLi,ShuaiMa,NanTang,andYinghuiWu,AddingRegularExpressionstoGraphReachabilityandPatternQueries.ICDE2011.8WenfeiFan,JianzhongLi,ShuaiMa,NanTang,andYinghuiWu,GraphPatternMatching:FromIntractabletoPolynomialTime.VLDB2010.9WenfeiFan,JianzhongLi,ShuaiMa,NanTang,andYinghuiWu,GraphHomomorphismRevisitedforGraphMatching.VLDB2010.10HosseinMaserratandJianPei,Neighborqueryfriendlycompressionofsocialnetworks.KDD2010.412024/5/22 周三References11BrianGallaghe,Matchingstructureandsemantics:Asurveyongraph-basedpatternmatching.AAAIFS.2006.12MarkoA.Rodriguez,PeterNeubauer:TheGraphTraversalPattern.GraphDataManagement2011:29-4613ShuaiMa,YangCao,WenfeiFan,JinpengHuai,andTianyuWo.StrongSimulation:CapturingTopologyinGraphPatternMatching.TODS2014.14ShuaiMa,YangCao,WenfeiFan,JinpengHuai,andTianyuWo,CapturingTopologyinGraphPatternMatching.VLDB2012.15WeirenYu,CharuC.Aggarwal,ShuaiMa,HaixunWang:OnAnomalousHotspotDiscoveryinGraphStreams.ICDM201316RenjunHu,CharuC.Aggarwal,ShuaiMa,JinpengHuai:AnEmbeddingApproachtoNetworkAnomalyDetection.underreview.17ShuaiMa,KaiyuFeng,HaixunWang,GaoCong,JianxinLi,JinpengHuai:ProxiesforSpeeding-upShortestPath/DistanceQueries.underreview.18DanielPeng,FrankDabek:Large-scaleIncrementalProcessingUsingDistributedTransactionsandNotifications.OSDI2010.19KaiyuFeng,GaoCong,SouravS.Bhowmick,ShuaiMa:Insearchofinfluentialeventorganizersinonlinesocialnetworks.SIGMOD2014.422024/5/22 周三Thanks!2024/5/22 周三43