A dynamical systems approach to weighted graph matching

Graph matching is a fundamental problem that arises frequently in the areas of distributed control, computer vision, and facility allocation. In this paper, we consider the optimal graph matching problem for weighted graphs, which is computationally challenging due the combinatorial nature of the set of permutations. Contrary to optimization-based relaxations to this problem, in this paper we develop a novel relaxation by constructing dynamical systems on the manifold of orthogonal matrices. In particular, since permutation matrices are orthogonal matrices with nonnegative elements, we define two gradient flows in the space of orthogonal matrices. The first minimizes the cost of weighted graph matching over orthogonal matrices, whereas the second minimizes the distance of an orthogonal matrix from the finite set of all permutations. The combination of the two dynamical systems converges to a permutation matrix, which provides a suboptimal solution to the weighted graph matching problem. Finally, our approach is shown to be promising by illustrating it on nontrivial problems.     

图文法综述

形式语言理论对计算机科学的发展起了重大的作用,作为对传统字符文法扩展的图文法的形式化研究,其重要意义是不言而喻的.本文在概述图文法的产生、发展和现状的基础上,着重介绍了从一维字符文法扩展到二维图文法所出现的新问题,以及在形式化处理上引出的新方法,其中最主要的是嵌入问题的解决、文法类型的划分和成员问题的判定.文中以目前较为流行的图文法为例,特别是一些典型的上下文无关和上下文相关的图文法,对上述的问题进行了深入的讨论,指出了现有方法中的一些不足之处,并展望了图文法今后值得研究的问题和方向.     

谱聚类算法综述

谱聚类算法是近年来国际上机器学习领域的一个新的研究热点.谱聚类算法建立在谱图理论基础上,与传统的聚类算法相比,它具有能在任意形状的样本空间上聚类且收敛于全局最优解的优点.本文首先介绍了图论方法用于聚类的基本理论,然后根据图划分准则对谱聚类算法进行分类,着重阐述了各类中的典型算法,并对算法进行了比较分析,最后进行总结并提出了几个有价值的研究方向.     

一种基于图的异常入侵检测新算法

根据主机系统异常入侵过程中Windows native API序列的瞬时高频性,提出一种基于图的异常入侵检测算法。该算法首先将每个Native API映射成为图中的一个点,并以其为起点的子序列作为该点的路径、Native API的前后调用关系为边;其次,对图中每个点记录各自的路径,在这些点的路径中找到若干个圈,圈定义为因对同一个Native API重复调用而在图中出现的回路;然后,对组成圈的所有边权值根据一定规则更新;最后利用图的边与其邻边权值差计算出异常指数,判断该序列是否异常。实验结果表明该算法在Windows平台下能实时有效地检测出异常入侵和病毒的Native API序列。     

基于多专业领域的团队协同副本一致性维护模型

本文针对原有协同系统在解决多用户群协同问题中的缺陷以及原有解决方案的弊端,以Chord定位查询[1]和多版本图形设计同一致性算法[2]为基础并改造地副本策略的通用架构,解决了工程设计中多专业领域的团队协同副本一致性问题.     

Edge crossings in drawings of bipartite graphs

Systems engineers have recently shown interest in algorithms for drawing directed graphs so that they are easy to understand and remember. Each of the commonly used methods has a step which aims to adjust the drawing to decrease the number of arc crossings. We show that the most popular strategy involves an NP-complete problem regarding the minimization of the number of arcs in crossings in a bipartite graph. The performance of the commonly employed barycenter heuristic for this problem is analyzed. An alternative method, the median heuristic, is proposed and analyzed. The new method is shown to compare favorably with the old in terms of performance guarantees. As a bonus, we show that the median heuristic performs well with regard to the total length of the arcs in the drawing.     

Feature generation based on relation learning and image partition for occluded person re-identification

In order to solve the challenging tasks of person re-identification(Re-ID) in occluded scenarios, we propose a novel approach which divides local units by forming high-level semantic information of pedestrians and generates features of occluded parts. The approach uses CNN and pose estimation to extract the feature map and key points, and a graph convolutional network to learn the relation of key points. Specifically, we design a Generating Local Part (GLP) module to divide the feature map into different units. Based on different occluded conditions, the partition mode of GLP has high flexibility and variability. The features of the non-occluded parts are clustered into an intermediate node, and then the spatially correlated features of the occluded parts are generated according to the de-clustering operation. We conduct experiments on both the occluded and the holistic datasets to demonstrate its effectiveness.     

基于One-Shot聚合自编码器的图表示学习

自编码器（AE）是一种高效的图数据表示学习模型,但大多数图自编码器（GAE）为浅层模型,其效率会随着隐藏层的增加而降低。针对上述问题,提出基于One-Shot聚合（OSA）和指数线性（ELU）函数的GAE模型OSA-GAE和图变分自编码器模型OSA-VGAE。首先,利用多层图卷积网络（GCN）构建编码器,并引入OSA和ELU函数;然后,在解码阶段使用内积解码器恢复图的拓扑结构;此外,为了防止模型训练过程中的参数过拟合,在损失函数中引入正则化项。实验结果表明,OSA和ELU函数可以有效提高深层GAE的性能,改善模型的梯度信息传递。在使用6层GCN时,基准引文数据集PubMed的链接预测任务中,深层OSA-VGAE相较于原始的VGAE在ROC曲线下的面积（AUC）和平均精度（AP）上分别提升了8.67和6.85个百分点,深层OSA-GAE相较于原始的GAE在AP和AUC上分别提升了6.82和4.39个百分点。