基于图连通支配集的子图匹配优化算法

在子图匹配过程中,随着图规模不断增长,匹配时间呈现指数爆炸的趋势.对此,提出一种基于图连通支配集的子图匹配优化算法VF-SMDS.根据贪心算法构建查询图的最小连通支配子图;通过代价模型计算最小连通支配子图节点的匹配代价,构建最优k查询节点匹配序列;通过支配节点的结构特征缩小查询节点搜索空间范围,在数据图中遍历到满足要求的节点,得到最终答案集.实验将VF-SMDS与GADDI、SPath、VF2++、VF3和SubISO方法进行对比.实验结果表明,在处理较大规模子图匹配问题时,VF-SMDS查询效率更高.     

基于三角形子图的复杂网络过滤压缩算法

为高效地挖掘和分析复杂网络,提出一种基于三角形子图的复杂网络过滤压缩算法NIIET。设计一种节点重要性排序算法NRSA选取高、低重要性节点并进行过滤,以降低计算规模并缩短压缩时间。列出边两端的节点及其共同节点集组成三角形子图集合,在此基础上,解析三角形子图集合完成复杂网络压缩。实验结果表明,NRSA算法的排序结果合理且可靠,相对Node_iterator算法,NIIET算法能够缩短压缩时间,提高压缩率,且能保留原网络的大部分结构和信息。     

超边约束的异质超网络表示学习方法

与普通网络相比，超网络具有复杂的元组关系（超边），然而现有的大多数网络表示学习方法并不能捕获元组关系。针对上述问题，提出一种超边约束的异质超网络表示学习方法（HRHC）。首先，引入一种结合团扩展和星型扩展的方法，从而将异质超网络转换为异质网络；其次，引入感知节点语义相关性的元路径游走方法捕获异质节点之间的语义关系；最后，通过超边约束机制捕获节点之间的元组关系，从而获得高质量的节点表示向量。在3个真实世界的超网络数据集上的实验结果表明，对于链接预测任务，所提方法在drug、GPS和MovieLens数据集上都取得了较好的结果；对于超网络重建任务，当超边重建比率大于0.6时，所提方法在drug数据集上的准确性（ACC）优于次优的Hyper2vec(biased 2nd order random walks in Hyper-networks)，同时所提方法在GPS数据集上的ACC超过其他基线方法中次优的基于关联图的超边超边约束的异质超网络表示学习方法（HRHC-关联图）15.6个百分点。     

融合知识图谱和图注意力网络的引文推荐算法

针对传统协同过滤（CF）中的数据稀疏和冷启动问题，以及元路径、随机游走算法没有充分利用节点信息的问题，提出融合知识图谱和图注意力网络的引文推荐算法（C-KGAT）。首先，使用TransR算法将知识图谱信息映射为低维稠密向量，以获取节点的嵌入特征表示；其次，利用图注意力网络通过多通道融合机制聚合邻居节点信息以丰富目标节点的语义，并捕获节点间高阶连通性；接着，在不影响网络的深度或宽度的情况下，引入动态卷积层动态地聚合邻居节点信息以提升模型的表达能力；最后，通过预测层计算用户和引文的交互概率。在公开数据集AAN(ACL Anthology Network)和计算机科学文献库（DBLP）上的实验结果表明，所提算法的效果优于所有对比模型，所提算法的MRR(Mean Reciprocal Rank)相较于次优模型NNSelect分别提升了6.0和3.4个百分点，所提算法的精确率和召回率指标也有不同程度的提升，验证了算法的有效性。     

图数据表示与压缩技术综述

对包含亿万个节点和边的图数据进行高效、紧凑的表示和压缩,是大规模图数据分析处理的基础.图数据压缩技术可以有效地降低图数据的存储空间,同时支持在压缩形式的图数据上进行快速访问.通过深入分析该技术的发展现状,将该技术分为基于传统存储结构的压缩技术、网页图压缩技术、社交网络图压缩技术、面向特定查询的图压缩技术4类.分别对每类技术详细分析了其代表方法并比较了它们之间的性能差异.最后对该技术进行了总结和展望.     

层次序列索引的大规模动态标签图子图查询

标签图常用于智能交通网、生物信息网等新兴领域的建模。子图查询作为图数据分析的关键问题，引起了研究者的广泛关注。对现有子图查询算法的研究发现，随着图数据规模增大且频繁更新，传统子图查询算法普遍存在查询效率低，存储开销大，忽略顶点标签信息等问题。为此，提出了一种支持大规模动态标签图子图查询的层次序列索引（Dynamic Hierarchical Sequence，DHS），该索引提取数据图中带有顶点编号的层次拓扑序列关系以实现子图查询；针对图的动态变化，提出了更新点拓扑扩展式索引维护策略，仅从局部变化顶点及边开始进行增量式更新，大大降低了重建索引造成的巨大开销；提出了基于DHS索引的子图查询方法，仅需将查询图与数据图的层次序列进行匹配即可获得候选集，并在其上利用关系匹配策略获得最终查询结果。实验证明提出的方法在保证高效查询的同时降低了索引的创建及维护时间，提高了子图查询效率。     

图的有损摘要问题的两阶段算法

问题如下:给定图G=(V, E)和正整数k,要求将图G中所有节点合并成为k个超节点,满足由这些超节点组成的摘要图能够在一定误差范围内表示原图G.这是一个基于图划分的组合优化问题,一个主要求解思路是逐次地随机抽取节点对集并用启发式方法从中选取节点对进行合并.本文提出一个有效的两阶段求解算法TS＿LGS.算法根据图G的平均点度特征设置阶段阈值:当前超节点数大于阶段阈值为第1阶段,期间算法在采样节点对中基于当前最佳合并分数批量选择节点对合并,旨在有效减少迭代次数;否则为第2阶段,期间算法在加权采样的基础上优先挑选相邻的节点对,旨在找到重构误差增量较小的节点对合并,直至超节点的个数为k.在典型的真实网络实例图上与现有最好算法SAA进行了实验对比,结果表明,算法TS＿LGS以较低时间复杂度提取到的图摘要具有更低的重构误差和查询误差.     

基于贪婪策略的紧密k核子图查询

k核查询是一种社团查询,由于其可以在线性时间内被有效计算,因此在社团检测中具有较广泛的应用。图中边的权值在很多场景下具有较强的语义关系,但现有研究较少考虑图中边的权值。为提升k核查询的效率,在k核的基础上定义加权图中的紧密k核子图查询（CRKSQ）问题,并使用归约方法证明该问题是NP-难的。基于贪婪策略设计启发式算法CRK-G,通过迭代删除节点为CRKSQ问题找到一个近似解。在此基础上,从降低图规模和减少迭代次数两方面研究CRK-G算法的优化策略,分别提出使用图压缩策略的算法CRK-C及使用单次多节点删除策略的算法CRK-F。在Bio-GRID、Email-Enron、DBLP 3个数据集上的实验结果表明,相对于CRK-G算法,CRK-C、CRK-F算法在查询速度上有较大的提升,且平均误差均在8%以内。     

融合语料库特征与图注意力网络的短文本分类方法

短文本分类是自然语言处理（NLP）中的重要研究问题,广泛应用于新闻分类、情感分析、评论分析等领域。针对短文本分类中存在的数据稀疏性问题,通过引入语料库的节点和边权值特征,基于图注意力网络（GAT）,提出了一个融合节点和边权值特征的图注意力网络NE-GAT。首先,针对每个语料库构建异构图,利用引力模型（GM）评估单词节点的重要性,并通过节点间的点互信息（PMI）获得边权重;其次,为每个句子构建文本级别图,并将节点重要性和边权重融入节点更新过程。实验结果表明,所提模型在测试集上的平均准确率达到了75.48%,优于用于文本分类的图卷积网络（Text-GCN）、TL-GNN、Text-ING等模型;相较原始GAT,所提模型的平均准确率提升了2.32个百分点,验证了其有效性。     

基于图信号处理的无线传感器网络异常节点检测算法

针对无线传感器网络（WSN）中传感器自身安全性低、检测区域恶劣及资源受限造成节点采集数据异常的问题,提出一种基于图信号处理的WSN异常节点检测算法。首先,依据传感器位置特征建立K-近邻（KNN）图信号模型;然后,基于图信号在低通滤波前后的平滑度之比构建统计检验量;最后,通过统计检验量与判决门限实现异常节点存在性的判断。通过在公开的气温数据集与PM2.5数据集上的仿真验证,实验结果表明,与基于图频域异常检测算法相比,在单个节点异常情况相同条件下,所提算法检测率提升7个百分点;在多个节点异常情况相同条件下,其检测率均达到98%,并且在网络节点异常偏离值较小时仍具有较高的检测率。     

基于图割和局部算子的图子集选取

图子集选取问题旨在从图节点集中采样少部分代表性节点,利用观测的节点信号值去重构原始图信号。在资源有限的情况下,可以降低数据维度和计算复杂度,提高对复杂多变图结构的适应性,从而为网络数据的传输处理提供高效的技术支撑。现有的确定性算法大多采用贪心优化,后序采样点的选择依赖于前序已采样节点,对初始值敏感,且可能陷入局部最优;同时,大多数频域算法没有考虑顶点域内采样集节点的空间关系。该文提出基于局部算子的两步采样算法,通过构建节点局部算子的内积完全图来度量采样节点的距离,首先求解标准图割,将节点集按距离划分指定个数簇;其次,在各个簇内依据稀疏性度量选择最优点,从而生成最终的采样集。该算法同时结合了频域与节点域的信息,并使得采样可并行执行。在多种图场景下与多种代表性算法相比,该算法都可以取得最优或相近的重构效果。     

基于变迁图编辑距离的流程相似性算法

为了提高从企业模型库中查询检索模型的效率,提出一种基于变迁图编辑距离的流程相似性算法。首先,给出了变迁图的概念及其生成方法;其次,提出边的长度概念,且删除和插入边的代价由该边的长度决定,基于此定义出图编辑操作及其代价,并用节点匹配算法计算最小图编辑距离;然后,给出两个过程模型的相似性概念和计算方法;最后,通过实验验证了算法的正确性且满足七条相似性性质,并验证了变迁图编辑距离满足四条距离性质。     

基于增强加权共现图和图核相似性的文本分类方法

为有效表示文本结构信息，提高文本分类性能，提出一种增强加权共现图的文本分类方法。利用加权共现图表征文本，基于术语与文本分类的相关性对术语及其相依性进行加权；通过词相似性矩阵对加权图进行增强，增强图的节点和边。采用基于边匹配的图核，计算文本之间的相似性。实验在3个公开数据集上进行，在标准设置情况下，相比于其它优秀方法，所提方法在精度、召回率和F1得分提高约5%。在少量标注样本情况下，所提方法Micro-F1的增益在3%到8%之间。     

基于OAN的知识图谱查询研究

知识图谱查询是目前知识图谱研究中最广泛的应用,能够有效提高搜索引擎查询效率。然而,现有的知识图谱的查询研究多是基于节点标签的子图匹配。由于节点标签不能体现节点间的语义信息,导致查询结果的语义相关性不高。针对此问题,本文提出了一种基于本体和邻居信息的查询算法OAN(Ontology and Neighborhood)。首先,结合本体相似度和邻居相似度来确定查询节点的候选集,以此提高候选节点的语义相似度;其次,通过边检测算法移除那些不满足条件的查询节点候选集,以此减少查询规模;然后,在目标图上查找满足边标签同构的查询子图,并计算节点的标签相似度和结构相似度总和,给每个结果集打分后排序,获得最终排序后的结果集;最后,通过在真实数据集上与已有查询算法进行对比实验,实验结果表明:本文所提出的方法无论是在精确度上,还是在查询效率方面都有所提高。     

基于图结构特征采样数据摘要的联邦知识图谱查询

联邦SPARQL查询是通过构建查询计划来指导查询执行,数据摘要索引文件捕获了RDF数据集的结构和语义信息,对查询计划生成过程中子查询基数评估至关重要。现有的数据摘要生成方法需要远程遍历每个数据源的完整数据,该过程成本消耗较高,且在大部分环境中联邦查询无法完成对大数据集的统计工作。为在减少数据摘要索引文件生成时间和内存开销的同时捕获尽可能真实的计数信息,考虑主语和谓语的分布偏差,提出利用样图生成原始图近似数据摘要的方法。使用对RDF图出度特征加权的采样方法获取原始图的典型样图,通过改进的映射函数将样图中的信息映射到原始图上,从而生成原始图的近似数据摘要。实验结果表明,该方法相比于基线方法至少节省了70%的数据摘要索引文件生成时间,并且仅采样0.5%的原始图生成的近似数据摘要即可在查询正确率上与基线方法保持高度一致。     

大规模标签图中的动态Top-K兴趣子图查询

针对传统算法由于时间或空间复杂度过高而难以实现规模大且动态变化情况下标签图的Top-K子图查询问题,提出一种适用于大规模标签图的动态Top-K兴趣子图查询方法DISQtop-K。该方法建立了包括节点拓扑结构特性（NTF）索引和边特性（EF）索引的图拓扑结构特性（GTSF）索引,利用该索引可有效剪枝过滤不满足限制条件的无效节点及边;基于GTSF索引提出了多因素候选集过滤策略,通过对查询图候选集进一步剪枝以获得较少的候选集;考虑到图的动态变化可能对匹配结果产生影响,提出了Top-K兴趣子图匹配验证方法——DISQtop-K,将匹配验证过程分为初始匹配和动态修正两个阶段,以尽可能保证查询结果的实时、准确。大量实验结果表明,相比RAM、RWM算法,DISQtop-K方法的索引创建时间较短且占用空间较少,能有效处理大规模标签图中的动态Top-K兴趣子图查询。     

基于参考节点嵌入的图可达性查询

针对k步可达性查询算法无法解决带距离约束的图可达性查询问题,提出基于参考节点嵌入的图可达性查询算法。首先,从所有节点中选出极少数有代表性的全局参考节点,预先计算所有节点与全局参考节点之间的最短路径距离;然后,采用最短路径树和范围最小值查询技术求得局部参考节点;接着,利用三角不等式关系得到查询点对距离范围;最后,根据查询条件中的距离值与查询点对距离范围上、下限值的大小关系,可快速得出可达性结论。针对社会关系网络和公路网络数据,将所提算法与Dijkstra算法、K-Reach算法进行实验对比测试。相较于K-Reach算法,其索引建立时间小4个数量级,其索引规模小2个数量级;相较于Dijkstra算法,在公路网络和社会关系网络中,直接得出可达性结论的比例分别为92%和78.6%,其查询时间大大缩短,分别降低了95.5%和92%。实验结果表明：所提算法能够通过使用较小的索引开销,实现在线查询计算复杂度的降低,可很好地解决既适用于有权图又适用于无权图带距离约束的可达性查询问题。     

基于最小描述长度原则的属性图概要方法

图概要技术是管理、分析和可视化大规模图的关键技术之一。如何综合结构和属性信息进行图概要是一个挑战。大部分现有的图概要方法或者只考虑结构或属性某一方面的信息,或者要求属性的表现形式是一致的。结合信息论中最小描述长度原则,对属性图概要问题建模,将其转化为求解最小表示代价问题,以实现图压缩和图概要的双重目标。提出了一种计算节点属性相似性的方法,该属性度量方法对节点属性的限制较小,并且将节点间的相似性统一为存储代价,实现了节点结构相似和属性相似的协同考虑。提出了两种求解最小代价表示的图概要算法。在真实和合成的数据集上实验,验证了提出算法的有效性。     

基于对比学习的多关系属性图聚类方法

现实世界包含复杂的图数据，其节点之间通常包含多种关系，这种图被称为多关系属性图。图聚类是挖掘图数据相似信息的技术之一，然而现有的图聚类的方法大多只适用于单关系图。即使有的方法考虑到了多关系图，也往往是将图表示学习与聚类看作两个单独的过程。受Deep Graph Infomax(DGI)算法的启发，文中设计了一种基于对比学习的多关系属性图的聚类方法(CCLMAG),用于解决上述问题：1)通过引入社区级互信息机制，弥补了DGI算法无法融合簇信息的缺点；2)引入嵌入融合模块来聚合不同关系上的节点嵌入；3)引入聚类优化模块将图表示学习与聚类两个过程联系起来，使得学习到的节点表示更适合聚类任务。在3个公开数据集和1个构建的期货数据集上的大量实验表明，所提方法优于目前最先进的基线方法，且具有实际应用价值。     

基于密集子图的银行电信诈骗检测方法

目前银行对电信诈骗的标记数据积累少，人工标记数据的代价大，导致电信诈骗检测的有监督学习方法可使用的标记数据不足。针对这个问题，提出一种基于密集子图的无监督学习方法用于电信诈骗的检测。首先，通过在账户-资源（IP地址和MAC地址统称为资源）网络搜索可疑度较高的子图来识别欺诈账户；然后，设计了一种符合电信诈骗特性的子图可疑度量；最后，提出一种磁盘驻留、线性内存消耗且有理论保障的可疑子图搜索算法。在两组模拟数据集上，所提方法的F1-score分别达到0.921和0.861，高于CrossSpot、fBox和EvilCohort算法，与M-Zoom算法的0.899和0.898相近，但是所提方法的平均运行时间和内存消耗峰值均小于M-Zoom算法；在真实数据集上，所提方法的F1-score达到0.550，高于fBox和EvilCohort算法，与M-Zoom算法的0.529相近。实验结果表明，所提方法能较好地应用于现阶段的银行反电信诈骗业务，且非常适合于实际应用中的大规模数据集。