基于图划分抽样算法的图表示学习

在基于神经网络的图表示算法中,当节点属性维度过高、图的规模过大时,从内存到显存的数据传输会成为训练性能的瓶颈。针对这类问题,该方法将图划分算法应用于图表示学习中,降低了内存访问的I/O开销。该方法根据图节点的度数,将图划分成若干个块,使用显存缓存池存储若干个特征矩阵块。每一轮训练,使用缓存池中的特征矩阵块,以此来减少内存到显存的数据拷贝。针对这一思想,该方法使用基于图划分的抽样算法,设计显存的缓存池来降低内存的访问,运用多级负采样算法,降低训练中负样本采样的时间复杂度。在多个数据集上,与现有方法对比发现,该方法的下游机器学习准确率与原算法基本一致,训练效率可以提高2~ 7倍。实验结果表明,基于图划分的图表示学习能高效训练模型,同时保证节点表示向量的测试效果。今后的课题可以使用严谨的理论证明,阐明图划分模型与原模型的理论误差。     

图数据库系统研究综述

针对图数据管理的新需求,呈现出许多面向特定应用的图数据库系统。本文针对图数据库系统的相关研究进行综述。首先介绍图数据的三种类型。然后根据图数据库功能的不同将图数据库分为查询类和分析类进行介绍。最后对文章进行总结。     

UML及其建模工具的应用

介绍了统一建模语言UML的基本概念及主要内容,并结合UML建模工具Rational Rose给出了UML的建模过程及建模工具的使用方法,结合学校中学生选课信息系统给出了典型的UML视图示例.     

基于缺失信号的图重构

在使用图信号处理工具之前需要知道信号的底层图，即信号的空间结构。但在实际场景中，尤其是对于缺失信号而言，图未必是已知的。对此提出一种缺失信号的图学习模型。利用信号的空间变分和稀疏惩罚项来学习图，同时利用空间变分和时间变分及学到的图重构信号，重复迭代直至目标函数值最小时得到最优解。实验结果表明在信号缺失的情况下，该模型依然能够合理学习到图结构，并且在实测温度数据中聚类和信号重构的效果要优于常用的聚类算法和图信号重构算法。     

图数据库发展综述

随着数据关联关系的发现、管理和应用的深入, 图数据库快速发展. 归纳总结了图数据库概念、图模型、组成架构图和数据库的特点; 详细阐述了图数据库的关键技术; 分析比较了当前主流图数据库产品, 归纳了当前图数据库主要应用场景; 最后提出图数据库未来发展的趋势.     

基于图模型的足球视频语义建模方法

视频低层特征和高层语义之间存在的“语义鸿沟”是视频分析与检索应用研究的一个技术瓶颈问题。通过深入分析,提出了足球视频语义内容的时空关联特性,尝试引入图模型方法来建模这种语义关联,提出了视频语义图（VSU)的语义建模方法和基于DFS的视频语义图匹配算法,并分析了算法的复杂性。实验结果显示,该方法能够有效解决视频语义内容建模和分析匹配问题。     

特殊图的图修正问题研究综述

图修正问题是指在一个图中进行删除点、删除边或加边操作,使这个图转变成另一个具有某种特殊性质的图。图修正问题一直被广泛研究,尤其对弦图、区间图以及单位区间图的图修正问题的研究更是如此。弦图是完美图中最重要的一类图,也是(单位)区间图的父类图,很多经典的NP难问题在弦图上都是多项式可解的。区间图以及单位区间图在生物计算上有着广泛的应用。对这几类图的图修正问题的研究对计算机理论和实践有很大的贡献。首先介绍并总结了关于弦图、区间图以及单位区间图的图修正问题的重要算法和技术,然后对这些问题的研究现状进行分析,并提出了今后研究中值得关注的问题。     

求解连通无向简图的所有连通子图的算法及其应用

讨论了求解连通无向简图的所有连通子图的算法，并将其应用于化学领域：如何将许多具有某种共同属性的物质的分子结构图形分解成子分子结构，进一步地试图找出存在于大多数具有该属性的物质中的子分子结构，并讨论这样的子分子结构导致物质具有该共同属性的概率。     

M-H_2O系中溶液态物质的优势区域图

M -H2 O系中各溶液态物质在电势 pH平面内的优势区是Pourbaix图的一个重要内容。各物质的优势区大小由溶液态各物质的活性元素 (M)的总浓度T(M)决定 ;只有当各物质均含有相同数目的活性元素 (M)时 ,它们各自的优势区大小才与总浓度T(M)无关。T(M)一定时 ,E -pH平面内各点 (pH ,E)所对应的各物质的浓度可用改进的“二分法”求出。求出了Cu -H2 O系及不同总浓度T(S)和T(Cr)时简化的S -H2 O系和Cr-H2 O系各自的优势区域图。结果表明 ,随着T (S)的增加 ,S -H2 O系中较高级多硫化物的优势区增大 ,且移向低电势区 ;Cr -H2 O系中随T(Cr)的改变而变化最明显的是Cr3 ,Cr(OH) 3,Cr(OH) -4 ,和Cr3(OH) 5 4的优势区。     

一个大规模股市图交互式可视化分析系统

随着物联网、移动互联网、云计算以及各种数据自动采集技术的迅猛发展,许多领域迅速积累了大量具有图结构的可用数据。其中一个重要的图应用是股市图。如何分析股市图达到合理充分的投资决策支持一直是一个重要的课题。其中极大团(Maximal Clique)分析是分析股市图的一个重要方法。股市图的规模庞大,传统的极大团枚举算法仅仅罗列图中所有的极大团。但一个图中可以有指数级数量的极大团,而一支股票对应的点可以参与到任意多的极大团中。因此,传统的极大团枚举算法不能直接有效支持股市图分析。本文提出一个支持快速选择、自动分组及导航浏览三种股市图交互式可视化操作的大规模股市图分析系统。根据用户感兴趣的股市图节点,这三种股市图交互式可视化操作从股市图中快速枚举出与这些特定股票相关的极大团、查看这些特定股票之间的组合关系以及显示与这些特定股票相关的其他股票,是有效支持股市图分析的必要手段。同时基于对某些特定顶点或边相关的极大团枚举的需求,本文提出了从图中枚举出与特定顶点或边相关的极大团算法。我们使用真实数据验证了本文提出的算法的优越性。     

图分类研究综述

图数据广泛存在于现实世界中,可以自然地表示复合对象及其元素之间的复杂关联.对图数据的分类是一个非常重要且极具挑战的问题,在生物/化学信息学等领域有许多关键应用,如分子属性判断,新药发现等.但目前尚缺乏对于图分类研究的完整综述.首先给出图分类问题的定义和该领域的挑战;然后梳理分析了两类图分类方法—基于图相似度计算的图分类...     

一种基于遗传算法思想实现的图匹配算法

针对计算机图数据处理难题中的图数据检索匹配问题。相比传统的基于统计分布、模式识别等理论,该文在研究了遗传算法的智能优化过程的基础上,对照图匹配过程中的对应信息元素的查找难题进行求解。将遗传算法的思想理论与图匹配方法相结合,利用智能优化算法对解决基于内容的图匹配问题探索提供新的解决方法,从智能优化的角度来考虑和快速解决图匹配过程中的结构对应检索难点。通过验证参数和对象得出图匹配问题新解。     

多样性度量的Top-K区分子图挖掘

区分子图可以用来描述复杂的图数据结构和构建高效的图分类模型。提出了多样性度量的Top-K区分子图挖掘问题,避免了挖掘结果之间出现高度相关的子图模式,提高了区分子图模式的可用性。通过组合图结构相似性与支持集相似性约束,给出图模式的多样性度量标准。提出两个高效算法Greedy-TopK和LeapTopK挖掘多样性度量的Top-K区分子图。Greedy-TopK算法采用两阶段的增量式贪婪方法快速挖掘K个区分子图模式。Leap-TopK算法通过在挖掘过程中限制扩展结构相似的图模式,实现了跳跃搜索子图模式空间。实验结果表明,Leap-TopK算法的效率明显优于Greedy-TopK算法;在可用性方面,利用Leap-TopK算法与Greedy-TopK算法挖掘结果构建的图分类器具有相似的分类精度,且都优于传统区分子图挖掘算法产生的结果。     

基于图粗化的层次图池化方法研究

图神经网络(Graph Neural Networks, GNNs)已被证明能有效对图结构数据进行建模，池化机制在使用GNN模型提取图层次特征过程中至关重要，近年来已经引起了越来越多研究者们的关注.现有基于聚类的层次图池化方法要么需要增加额外的神经网络层以实现特征图的粗化；要么不能从全局角度捕获节点在图中的重要性大小.针对以上问题，本文提出一种基于图粗化的层次图池化方法(Hierarchical Graph Pooling Based on Graph Coarsening, HGP-GC),用于学习图的层次特征表示.该方法主要包括图结构粗化和图属性粗化两个部分.利用结构粗化实现特征图尺寸的缩减；利用属性粗化突显图中重要节点对图级表示的关键作用.通过将HGP-GC池化策略与现有神经网络相结合，在不同规模公共数据集上的图分类实验结果证明了HGP-GC的有效性.     

结点可同名的连通无向图的子图研究

给出了求解结点可同名的连通无向图的所有边极大连通子图的算法,并将其应用于化学领域: 将许多具有某种共同属性的物质的分子结构图形分解成子分子结构,进一步地试图找出存在于大多数具有该属性的物质中的子分子结构,并讨论这样的子分子结构导致物质具有该共同属性的可能性.     

结点可同名的连通无向图的子图研究

给出了求解结点可同名的连通无向图的所有边极大连通子图的算法,并将其应用于化学领域:将许多具有某种共同属性的物质的分子结构图形分解成子分子结构,进一步地试图找出存在于大多数具有该属性的物质中的子分子结构,并讨论这样的子分子结构导致物质具有该共同属性的可能性。     

基于最小生成树的图数据库索引算法

对复杂数据进行图模式建模近几年越来越流行,因此,在查询执行的优化过程中图索引技术变得至关重要.研究了图模式的索引问题,并且提出了一种近似的索引方法,称为MSTA方法.MSTA方法利用最小生成树结构作为索引特征,依据最小生成树边序列的包含关系和基于最大公共子图的图距离度量,将最小生成树组织到一个称为MST树的索引结构中.MST树索引结构可以高效地支持多种查询,例如子图查询.MSTA方法具备高效的索引性能.在索引大小和索引建立时间方面,传统方法是MSTA方法的数十倍,甚至上百倍.MSTA方法虽然不能返回完整结果,但是可以返回经图距离度量排序最好的部分结果.     

动态图划分算法研究综述

图划分是大规模分布式图处理的首要工作,对图应用的存储、查询、处理和挖掘起基础支撑作用.随着图数据规模的不断扩大,真实世界中的图表现出动态性.如何对动态图进行划分,已成为目前图划分研究的热点问题.从不同动态图划分算法的关注点和特点出发,系统性地介绍当前可用于解决动态图划分问题的各类算法,包括流式图划分算法、增量式图划分算法和图重划分算法.首先介绍图划分的3种不同的划分策略及问题定义、图的两种不同的动态性来源以及动态图划分问题;然后介绍3种不同的流式图划分算法,包括基于Hash的划分算法、基于邻居分布的划分算法以及基于流的优化划分算法;其次介绍单元素增量式划分和批量增量式划分这两种不同的增量式图划分算法;再次,分别介绍针对图结构动态的重划分算法和针对图计算动态的重划分算法;最后,在对已有方法分析和比较的基础上,总结目前动态图划分面临的主要挑战,提出相应的研究问题.     

一个任意图的输出和编辑系统

本文给出了一个对任意图的输出算法，这个算法同其它的同类算法相比，具有更小的时间复杂性，并且由于此算法的参数是可控制的，所以对图的输出也是可控制的．另外，本文描述了一个图的显示和编辑系统ＧＬＥＡＭ，这个系统是基于所给出的新算法的，并且在本系统中使用了约束技术，使图的输出更美观、合理．ＧＬＥＡＭ是一个通用且可以扩充的系统，用户只要加入相应的具体领域知识，就可把其变为一个专用的系统.