基于频繁闭图的图包含查询算法

 交通网络可利用图数据进行描述与分析,常用的方法包括挖掘、查询、分类等.提高大规模图集上查询算法效率的问题是当前图数据分析领域中一个重要的研究方向.给定图集,图包含查询返回图集中所有查询图的子图.本文提出一种基于频繁闭图的包含查询算法.算法首先通过选择比消除频繁闭图之间的冗余,然后将具有强选择性的频繁闭图通过树的结构组织起来建立索引,并在此索引基础上实现图包含查询.在文章的最后,给出了理论与实验的分析结果.结果表明,该算法不但能高效的进行索引筛选,而且能显著的减小候选集尺寸,进而大大的降低了查询图与索引模式之间以及与候选集之间的子图同构测试次数,提高了查询效率.     

ERSearch:一种高效的子图查询算法

子图查询是图数据库研究中的一个重要问题,许多方法基于“过滤-验证”策略进行子图查询,算法研究的重点为快速找到有效的特征集.通过对特征模式在数据图集中的嵌入信息进行分析,离线建立基于重叠关系、邻接关系和近邻关系的嵌入关系索引,提出基于嵌入关系的子图查询算法ERSearch.在给定查询图后,利用特征共现关系与特征嵌入关系联合进行过滤操作,并将过滤阶段的嵌入关系比对结果用于验证过程,提高验证效率.在真实及模拟数据上的实验表明,通过与PathIndex等方法的对比,ERSearch算法有效缩减了候选集的规模,能有效提高过滤与验证阶段的执行效率.     

DisHAP:基于层次亲和聚类的分布式大图划分算法

平衡图划分是改善并行图计算性能的关键.一个良好的划分算法应保证划分后的子图在负载均衡的前提下,减少子图之间的交互边(切割边)规模,从而减少网络通信.对此,本文设计一种基于层次亲和聚类的分布式大图划分算法(DisHAP).该算法采用亲和聚类的思想,将图初始划分为规模相等的k个子图;再将结果映射成顶点序列,以线性嵌入顺序处理节点,通过局部交换策略优化割边率;最后将DisHAP应用在MapReduce框架中,使用多种真实及理论图数据,与现有的大图划分算法做比较分析.以Twitter图为例,划分2,4,8,16,32个子区,相较于现有的大图划分算法(LDG,BLP,Spinner,Fennel,ParMetis及PSA-MIR算法),割边率减少1.7％～30.2％,说明了该算法的优越性.同时该算法具有良好的可扩展性,划分的子区数量及图的规模对划分时间具有较低的影响.     

面向距离查询的属性加权图聚集算法

图聚集技术是在保留原始图的结构和属性信息的同时,将一个大规模图聚集成简洁的小规模图的技术.随着图的规模不断增加使得图数据变得难以查询和存储,而基于距离的查询,例如最短路径查询,非常依赖图的规模大小.本文提出了面向距离查询的属性加权图聚集算法,在保证节点之间结构和属性相似的同时,保护了节点之间的距离,并有效地减小了图规模...     

基于约束的局部-全局LWF链图结构学习算法

LWF链图结构学习旨在发现链图中所有节点的父节点、子节点、邻居节点以及配偶节点.然而,目前最新的LWF链图结构学习算法是基于Growing-Shrinking(GS)思想得到节点的局部结构（即节点的马尔科夫毯）来学习全局网络结构,该类算法的条件独立测试是以整个马尔科夫毯为条件集的,为了保证条件独立测试的可靠性,算法要求样本数量是马尔科夫毯大小的指数级,从而使得算法的数据效率较差.针对该问题,本文提出了一种基于约束的局部-全局LWF链图结构学习算法.该算法通过迭代的学习邻接集和配偶集来降低对数据样本量的要求;与此同时,在学习邻接集时采用后向策略保障了条件独立测试的正确性.算法的基本思想如下：首先学习网络中每个节点的马尔科夫毯,将节点马尔科夫毯学习拆分为学习邻接集和学习配偶集;然后利用节点的马尔科夫毯信息恢复网络骨架,根据链图复合体有向边的特点,利用条件独立测试确定网络复合体有向边,从而恢复链图结构.理论分析证明了该算法的正确性,在仿真数据集和标准数据集上的实验测试验证了算法的有效性.     

不确定图间α-β子图同构匹配算法

子图查询返回图数据集合中所有包含查询图的数据图.在查询图和数据图同时为不确定性图的前提下,提出了不确定图间的期望子图同构定义和α-β子图同构匹配定义.不确定图间的期望子图同构是确定图上子图同构在概率图模型上的直接推广,不确定图间α-β子图同构利用两个限制阈值来衡量查询图和数据图间的匹配质量.文章详细阐述了α-β子图同构...     

SCBT-index:基于谱编码的子图索引算法

随着图模型规模的扩大,单机算法难以适应大规模数据集下的子图查询.而现有的分布式算法基于无索引的简单遍历,join过程容易出现内存溢出,而且查询图分布异常时易出现负载不均衡.提出了一种基于谱编码的二叉索引树（SCBT-index）,首先对数据图中的顶点谱编码,根据编码信息构建二叉索引树.然后对查询图使用最小查询计划进行分解,最后join过程使用3个剪枝策略：基于拓扑结构的预剪枝、序列化join和基于分布式下的join优化.实验结果表明,SCBT-index在图集下的综合性能优于现有主流算法,单图下的查询时间为现有算法的1/2到1/4.     

基于图匹配网络的小样本违禁物品分割算法

自动化安检技术是维护公共安全、提升安检效率的一项有效措施。在实际场景中很难获得充足的违禁品标注样本用于神经网络的训练,并且在不同场景和安全级别下违禁品的类别也有所不同。为解决基于神经网络的违禁品检测方法所面临的样本不均衡问题,以及避免模型在分割新的违禁品类别时需重新训练的现象,文中提出一种基于图匹配网络的小样本违禁物品分割算法。文中模型将测试图像与参考图像并行输入到图匹配网络中,并根据匹配结果从测试图像中分割出违禁品。所设计的图匹配模块不仅从图间节点的相似性考虑匹配问题,并利用DeepEMD算法建立全局概念,进一步提高测试图和参考图的匹配结果。在SIXray数据集和Xray-PI数据集上的实验表明:本模型在单样本分割任务中得到36.4%和51.2%的类平均交并比,分别比目前先进的单样本分割方法提高2.5%和2.3%。由此表明所设计的算法能有效提升小样本X光图像分割算法的精确度。     

Beta在线匹配

二部图的在线匹配问题最早由Karp等人在1990年提出,该问题在近年得到了广泛的关注,在日常生活中有大量的应用.本文引入了Beta分布作为二部图节点间的邻接关系的统计先验,提出了最大化节点的预留匹配能力准则作为在线匹配策略的评价度量,设计了在线匹配算法BetaOM,并证明了该算法的正确性.本文把BetaOM分别应用于基于人造数据和真实数据的在线匹配问题,实验的结果显示该算法优于经典的Greedy算法和Ranking算法.     

求二部图的最大匹配图的一种算法

 一个图的最大匹配图是以这个图的最大匹配集作为顶点集,两个顶点相邻当且仅当这两个最大匹配恰有一条边不同.本文首先对Gallai Edmonds结构定理中的三部分顶点在二部图中进行了详细刻画.然后讨论了构造最大匹配图问题的计算复杂性.最后深入研究了二部图最大匹配图的结构性质并给出了构造二部图的最大匹配图的一种算法.     

The augmentation of undirected weighted graph to aK-edge-connected graph

An approximation algorithm is presented for augmenting an undirected weighted graph to aK-edge-connected graph. The algorithm is useful for designing a reliable network.     

游程DSGM-SC同步波形压缩

该文研究了一维局域急变,广域缓变信号的游程DSGM-SC同步高效压缩。该压缩技术采用游程差分样条梯度均值检测,标记信号的高频分量,再通过优化插值进行谱压缩,提高数据序列的整体相关性,同步压缩相关变换后的高低频数据文件,获得高压缩效率。记录高低频数据分段定位信息,实现无损时间解压缩。对NEC的BSM8300多功能床旁监护仪ECG记录的压缩实验表明,在医疗特征保真度很高的情况下,压缩比可达32.4。此项研究适用于一维数据分析,记录,传输和综合应用。     

Flow graph development method

The present paper demonstrates the use of graph theory to find the steady state behaviour of multi-state systems described by Markov models.Two applications are demonstrated and compared with results obtained by Laplace Transform technique. The agreement between the two techniques appears to be excellent.The developed method is also compared with another method which uses the graph theory to calculate the steady state probabilities.     

Choosing the right graph

When it comes to graphing data, most professionals show little method or creativity. They typically limit themselves to a small repertoire of graph types and select from it on the basis of habit, if not sheer ease of production. Similarly, the many books on graphing devote much attention to graphical integrity and readability, but little or none to graph selection. We developed a methodology to help engineers, scientists, and managers choose the "right graph" on the basis of three criteria: the structure of the data set in terms of number and type of variables, the intended use of the graph, and the research question or intended message. The first and third criteria allow one to construct an effective two-entry selection table     

基于图割框架的改进多层图彩色图像分割方法

彩色图像中所含有的颜色信息和纹理信息量很大且非常复杂,伴随着多个目标区域的出现,当前图像分割法很难整合纹理特征与颜色特征,图像分割效果不佳,因此,提出一种基于图割框架的改进多层图彩色图像分割方法,将多层图彩色图像分割问题看作是计算机视觉中的二元标识问题,转换成能量函数最小化问题,给出多标签MRF马尔科夫随机场能量函数,将颜色信息与纹理信息进行融合,通过建立多层图割模型对多类彩色图像能量函数的最小化问题进行求解。为了得到多类分割结果,采用一种自适应迭代收敛准则进行修改,在图割框架下进行多次迭代分割。实验结果表明,所提方法不仅分割效果良好,而且性能优越。     

Source coding and graph entropies

A sender wants to accurately convey information to a receiver who has some, possibly related, data. We study the expected number of bits the sender must transmit for one and for multiple instances in two communication scenarios and relate this number to the chromatic and Korner (1973) entropies of a naturally defined graph     

Techniques for content-based graph authentication

In addition to images and text, more and more documents use graphs for system and idea illustration. Compared to grayscale images, graphs are more difficult to watermark because of their binary nature. We propose two methodologies for digital graph authentication, at the object and pixel levels, that detect and localize alterations     

The Z specification dependence graph

The lack of existing solutions makes it really hard to understand formal specification languages since the application domain for representations is useful for the purpose of carrying out certain software engineering operations such as slicing and the computation of program metrics.A Z specification dependence graph is presented in this letter. It draws on the strengths of a range of earlier works and adapts them, if necessary, to the Z language.     

Minimum-distance bounds by graph analysis

The parity-check matrix of a linear code is used to define a bipartite code constraint (Tanner) graph in which bit nodes are connected to parity-check nodes. The connectivity properties of this graph are analyzed using both local connectivity and the eigenvalues of the associated adjacency matrix. A simple lower bound on the minimum distance of the code is expressed in terms of the two largest eigenvalues. For a more powerful bound, local properties of the subgraph corresponding to a minimum-weight word in the code are used to create an optimization problem whose solution is a lower bound on the code's minimum distance. Linear programming gives one bound. The technique is illustrated by applying it to sparse block codes with parameters [7,3,4] and [42,23,6]     

二值化身份感知图卷积神经网络北大核心CSCD

针对有限的内存资源导致图神经网络(graph neural network, GNN)无法完全加载属性图的问题,文中提出了二值化身份感知图卷积神经网络(binary identify-aware graph convolutional network, BID-GCN)。该网络通过在消息传递过程中递归地考虑节点的信息,为了获得一个给定的节点的嵌入,BID-GCN将提取以该节点为中心的自我网络,并进行多轮的异构消息传递,在自我网络的中心节点上应用与其他节点不同的参数。在消息传递过程中,对网络参数和输入节点特征进行二值化,并将原始的矩阵乘法修改为二值化以加速运算。通过理论分析和实验评估,BID-GCN可以减少网络参数和输入数据的平均约36倍的内存消耗,并加快引文网络上平均约49倍的推理速度,可以提供与全精度基线相当的性能,较好地解决内存资源有限的问题。