基于矩阵运算的超网络构建方法研究及特性分析

基于邻接矩阵Khatri-Rao积运算及Khatri-Rao和运算,研究了构建超网络的方法,并通过边际节点度及联合节点度来研究超网络的内在机理。将Khatri-Rao积运算迭代地应用于一个初始图序列组成超网络的邻接矩阵,得到一个分形维数不超过3的自相似超网络。若所有初始图均是连通非二分图,则得到的超网络同时具有小世界特性,其直径不超过所有初始图直径和的两倍。此外,将Khatri-Rao和运算顺次应用于多个初始图序列组成超网络的邻接矩阵,得到一个边际节点度呈一维高斯分布而联合节点度呈高维高斯分布的随机超网络。最后,给出了基于矩阵运算的超网络构建方法的若干性质。     

带权超网络的度量方法及其性质

超网络是较通常意义上的复杂网络更为复杂的网络,该网络的每一条超边能连接任意多个节点的特性使其比复杂网络能更好地描述真实世界中的复杂系统。针对现有超网络研究中对超网络度量方法的缺陷与不足,提出了一种超网络度量方法——超网络维数（HD）,即为所有超边包含的节点权重之和与对应超边权重乘积和的对数值和节点权重之和与超边权重之和乘积对数值的比值的两倍。超网络维数可以应用于节点权重与超边权重为正实数、负实数、纯虚数,乃至复数等多种不同数值类型的带权超网络中。最后给出了超网络维数的若干性质。     

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

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

基于平移约束的异质超网络表示学习

与仅具有节点成对关系的普通网络不同,超网络的节点之间还存在复杂的元组关系,即,超边。而现有的大多数网络表示学习方法不能有效地捕获复杂的元组关系。针对上述问题,该文提出一种基于平移约束的异质超网络表示学习方法(HRTC)。首先,该方法结合团扩展和星型扩展将抽象为超图的异质超网络转换为抽象为2-截图+关联图的异质网络。然后,提出一种感知节点语义相关性的元路径游走方法来捕获节点之间的语义关系。最后,在训练节点成对关系的同时,通过引入知识表示学习中的平移机制来捕获节点之间的元组关系。实验结果表明,对于链接预测任务,该方法的性能接近于其他最优基线方法;对于超网络重建任务,当超边重建比率大于0.6时,该方法在drug数据集上的性能优于其他最优基线方法,同时该方法在GPS数据集上的平均性能超过其他最优基线方法16.24%。     

超网络模型构建及特性分析

关联矩阵是超网络的一种表述形式,节点度、节点超度和超边度是度量超网络的一种方法。从关联矩阵出发对超网络进行研究,重点研究了自相似超网络及随机超网络,并给出了基于矩阵运算的超网络构建方法的若干性质。自相似超网络可通过对一个简单初始超图的关联矩阵进行迭代的Tracy-Singh积运算得到,而随机超网络可通过对多个简单初始超图的关联矩阵进行顺次的Tracy-Singh和运算得到。自相似超网络的分形维数不超过2,且当初始超图是连通的且非二分超图时,自相似超网络的直径不超过初始超图直径的两倍,即同时具有小世界特性。随机超网络的节点度、节点超度和超边度均呈正态分布。仿真实验证实了所构建的超网络的各项特性。     

基于多尺度图匹配核的场景单字识别方法

由于自然场景中的文字具有较大的类内间距, 因此识别场景文字具有很大的挑战性. 本文提出了一种基于多尺度图匹配核的场景单字识别方法. 为了利用字符特有的结构特征, 将每幅图像表示为基于不同网格划分的无向图, 通过计算两个无向图之间图匹配的最优能量值来得到两幅图像的相似度, 由于图匹配在计算每个节点的最佳匹配节点时也考虑了相邻节点之间的空间位置约束, 因此可以应对具有一定形变的文字. 通过图匹配得到的两幅图像之间的相似度很适合用来构造支持向量机的核矩阵. 本文将不同尺度网格划分下得到的核矩阵进行多核融合, 使得最终得到的核矩阵更加地鲁棒. 在国际公开场景文字识别数据集Chars74k和ICDAR03-CH上的实验结果表明, 本方法取得了高于国际上已发表的其他方法的单字识别率.     

基于矢量的无线传感网络能量有效配置算法

无线传感网络的能量消耗决定了网络的使用寿命,如何通过有效节点配置来尽可能地延长网络的生命周期是一个极具挑战性的研究课题.首先提出了一个基于一维网络模型的能量有效节点配置算法,并在将其扩展到二维平面模型的基础上,提出了一个基于矢量的中继节点放置算法.该算法在感应源节点位置和中继节点数给定的情况下,通过计算中继节点的位置得到整个网络的能量有效配置.模拟实验结果表明,在源节点和中继节点数之比为1∶2时,该算法得到的网络能耗比常规配置算法节省50%左右,该结果已在实现的火灾预警系统中得到应用.因为实际应用系统中,基于成本的原因,节点数规模总是受限的,因此该算法对构建低成本的无线传感网络应用系统具有重要意义.     

针对有向图的局部扩展的重叠社区发现算法

当前社区发现算法主要是针对无向图研究社区结构,但在实际复杂网络中,链接关系时常表现出非对称性或方向性,比如Twitter的用户关注关系,文献网络的引 用关系,网页之间的超链接关系等应用网络。因此,本文依据信息在复杂网络中的传播规律和流动方向性,提出了k-Path共社区邻近相似性概念及计算方法,用于衡量结点在同一社区的相似性程度,并给出了把有向图转换为带方向权值的无向图的方法。基于带权无向图提出了一种从局部扩展来探测社区的重叠社区发现算法(Local and wave-like extension algorithm of detecting overlapping community, LWS-OCD)。在真实数据集上的实验表明,共社区邻近相似性概念实现了有向到无向的合理转换,而且提高了社区结点的聚集效果,LWS-OCD算法能够有效地发现带权无向图中的重叠社区。     

基于转化策略的异质超网络表示学习

与传统网络相比,超网络结构更加复杂,并对现有网络表示学习方法提出了很大的挑战。为了克服网络表示学习面临的超网络结构的挑战,提出一种基于转化策略的异质超网络表示学习方法MT2vec。首先,结合团扩展和星型扩展将抽象为超图的异质超网络转换为抽象的2-截图+关联图的异质网络;然后提出一种感知节点语义相关性的元路径游走方法来捕获节点之间的成对关系和元组关系;最后,设计一种结合多层感知器的skip-gram优化模型同时训练节点成对相似性和元组相似性来获得节点表示向量。通过在三个不同类型的超网络数据集上进行实验。结果表明MT2vec算法在链接预测和超网络重建任务中,效果优于其他基线方法。     

一种提高3D模型浅浮雕建模质量的方法

顶点数较少的3D模型本身细节不够丰富,浅浮雕建模生成的浮雕效果较差.针对低分辨率3D模型本身细节不够丰富的问题,引入深度学习的方法对3D模型生成的法向图做超分辨率放大,设计出一种基于法向图的超分辨率卷积神经网络,丰富低分辨率法向图的细节,网络的输入是低分辨率3D模型的法向图,输出是高分辨率法向图.实验结果表明:该算法可以有效提升低分辨率法向图的细节,显著提升低分辨率3D模型的浅浮雕建模质量.     

基于0-1规划的并行计算图划分模型

图划分广泛地应用在许多科学与工程领域,但它应用于并行计算任务分配时,使用无向图表示数据依赖关系,这限制了它的应用(例如,无向图不能表示矩形和非对称依赖关系的应用).为了克服图划分的这个缺点,我们对数据间的依赖关系进行区分(即同一条边区分通信的发送方与接收方),然后基于0-1规划模型化这个问题,并通过互联网上求解优化问题常用的NEOS服务器进行求解,在一些数据集上的实验表明,0-1规划方法优于求解图划分流行的多层划分方法.     

利用邻接结构熵确定超网络关键节点

识别网络中的关键节点对研究网络的拓扑结构及功能特性具有重要的实际应用价值.基于超图的超网络拓扑结构为超图,由于超图中的超边可以包含任意数量的节点,使得超网络能够清晰明了地表达出多元、多维、多准则的复杂关系.为了更好地挖掘超网络中的关键节点,基于超图理论及性质,提出超图中的邻接结构熵识别超网络中的关键节点,该方法通过研究...     

图计算加速架构综述

在大数据时代,图被用于各种领域表示具有复杂联系的数据.图计算应用被广泛用于各种领域,以挖掘图数据中潜在的价值.图计算应用特有的不规则执行行为,引发了不规则负载、密集读改写更新操作、不规则访存和不规则通信等挑战.现有通用架构无法有效地应对上述挑战.为了克服加速图计算应用面临的挑战,大量的图计算硬件加速架构设计被提出.它们为图计算应用定制了专用的计算流水线、访存子系统、存储子系统和通信子系统.得益于这些定制的硬件设计,图计算加速架构相比于传统的通用处理器架构,在性能和能效上均取得了显著的提升.为了让相关的研究学者深入了解图计算硬件加速架构,首先基于计算机的金字塔组织结构,从上到下对现有工作进行分类和总结,并以多个完整架构实例分析应用于不同层次的优化技术之间的关系.接着以图神经网络加速架构的具体案例讨论新兴图计算应用的加速架构设计.最后对该领域的前沿研究方向进行了总结,并放眼于未来探讨图计算加速架构的发展趋势.     

Intelligent fault diagnosis for rolling bearings based on graph shift regularization with directed graphs

Graph shift regularization is a new and effective graph-based semi-supervised classification method, but its performance is closely related to the representation graphs. Since directed graphs can convey more information about the relationship between vertices than undirected graphs, an intelligent method called graph shift regularization with directed graphs (GSR-D) is presented for fault diagnosis of rolling bearings. For greatly improving the diagnosis performance of GSR-D, a directed and weighted k-nearest neighbor graph is first constructed by treating each sample (i.e., each vibration signal segment) as a vertex, in which the similarity between samples is measured by cosine distance instead of the commonly used Euclidean distance, and the edge weights are also defined by cosine distance instead of the commonly used heat kernel. Then, the labels of samples are considered as the graph signals indexed by the vertices of the representation graph. Finally, the states of unlabeled samples are predicted by finding a graph signal that has minimal total variation and satisfies the constraint given by labeled samples as much as possible. Experimental results indicate that GSR-D is better and more stable than the standard convolutional neural network and support vector machine in rolling bearing fault diagnosis, and GSR-D only has two tuning parameters with certain robustness.     

图神经网络推荐研究进展

图神经网络(graph neural network, GNN)具有从图的领域对数据进行特征提取和表示的优势,近年来成为人工智能研究的热点,图神经网络推荐也是推荐系统研究的一个新方向。本文对GNN模型进行深入研究的基础上,分析了GNN推荐过程,并从无向单元图推荐、无向二元图推荐、无向多元图推荐3个方面详细讨论了现有GNN推荐研究取得的主要进展及不足,阐明了现有GNN推荐研究中存在的主要难点,最后提出了GNN上下文推荐、GNN跨领域推荐、GNN群组推荐、GNN推荐的可解释性等未来GNN推荐的研究方向。     

图神经网络在复杂图挖掘上的研究进展

图神经网络对非欧式空间数据建立了深度学习框架,相比传统网络表示学习模型,它对图结构能够实施更加深层的信息聚合操作.近年来,图神经网络完成了向复杂图结构的迁移,诞生了一系列基于复杂图的图神经网络模型.然而,现有综述文章缺乏对复杂图神经网络全面、系统的归纳和总结工作.将复杂图分为异质图、动态图和超图3种类型.将异质图神经网络按照信息聚合方式划分为关系类型感知和元路径感知两大类,在此基础上,分别介绍普通异质图和知识图谱.将动态图神经网络按照处理时序信息的方式划分成基于循环神经网络、基于自编码器以及时空图神经网络三大类.将超图神经网络按照是否将超图展开成成对图划分为展开型和非展开型两大类,进一步按照展开方式将展开型划分成星形展开、团式展开和线形展开3种类型.详细阐述了每种算法的核心思想,比较了不同算法间的优缺点,系统列举了各类复杂图神经网络的关键算法、(交叉)应用领域和常用数据集,并对未来可能的研究方向进行了展望.     

基于复杂结构信息的图神经网络序列推荐算法

图结构因其在序列推荐场景中的自然适应性而备受关注,而现有的基于图神经网络的会话序列推荐算法虽然能够利用图结构信息达到较好的推荐效果,但是没有考虑用户在会话序列中的重复点击行为和项目之间的复杂转换,且未很好地利用图中复杂的结构信息,导致推荐的效果受到一定程度的限制。提出有向与无向信息同注意力相融合的图神经网络序列推荐算法,并基于推荐算法给出项目隐含向量建模算法,结合会话序列图中的有向结构信息与无向结构信息,通过考虑用户的重复点击行为和引入注意力机制建立会话中点击项目的复杂转换模型。图节点在特征传播的过程中平衡邻居节点信息与自身信息的比例,以更准确地预测推荐过程中生成的会话向量。在Diginetica、Yoochoose 1/64、Yoochoose 1/4 3个数据集上的实验结果表明,与SR-GNN、TAGNN算法相比,该算法精度最高提升4.34%,能够更好地预测用户在会话中的下一次点击精度。     

超网络的全终端可靠性分析

网络的可靠性是复杂网络研究的一个重要领域,能有效刻画某些复杂系统的超网络属于复杂网络的研究范畴。基于超网络的拓扑结构——超图,提出了超网络在边失效下的全终端可靠度的定义,并给出了计算可靠度的两种基本方法,即状态枚举法和因式分解法,依据因式分解法对一些具有特殊结构的超网络进行化简。作为超网络可靠性的应用,研究了连通生成子网络的数目;在与普通复杂网络的对比中可以得知,超网络的可靠性研究不能用其转换后的普通复杂网络可靠性作替代研究,该研究是对超网络可靠性研究的初步探索,有着广阔的研究空间和应用前景。