关于点的度在modulo4下等值的上可嵌入图类

结合 4-边形 2 -因子条件 ,确定了一类点的度在 modulo4下值为 0 ,1的上可嵌入图类 .从而综合已有的结果 。

新的上可嵌入图类

图G的C 划分是指 :G的一个顶点划分 {V1 ,V2 ,… ,Vk}使得每个G[Vi]为多重完全图 (1≤i≤k) .证明了如下结果 :设G为连通图 ,且对任意v∈V(G) ,dG(v)≡ 1 (mod 4) .若G的顶点集存在一个C 划分 {V1 ,V2 ,… ,Vk}使得对每个 1≤i≤k,|Vi|≥ 4 ,且 |Vi|≡ 0 (mod 4) ,则G是上可嵌入的 .另外 ,联系着图的点的度和其它条件 ,推广和深化了目前有关这方面的一些结果 。

较大亏格曲面嵌入图的线性荫度

通过度再分配的方法研究嵌入到曲面上图的线性荫度.给定较大亏格曲面∑上嵌入图G,如果最大度Δ(G)≥((45-45ε)^(1/2)+10)且不含4-圈,则其线性荫度为[Δ/2],其中若∑是亏格为h(h>1)的可定向曲面时ε=2-2h,若∑是亏格为k(k>2)的不可定向曲面时ε=2-k.改进了吴建良的结果,作为应用证明了边数较少图的线形荫度.

与顶点C-划分有关的上可嵌入图类

图的顶点C划分是指 :G的顶点划分 {V1,V2 ,… ,Vk} ,使得每个G[Vi]为多重完全图 (1≤i≤k) .结合图的顶点C划分的条件 ,确定了一类点的度在modulo 4下值为 0或 3的上可嵌入图类 ,综合已有结果 ,较完整地刻画了这类图的上可嵌入情况 .

平面及球面嵌入图α-定向的flip-距离

为研究平面嵌入图的给定出度序列的定向问题,Felsner引入了α-定向及flip变换,并进一步证明了一个平面嵌入图的所有α-定向在flip变换下构成一个分配格.本文中给出平面嵌入图的一个α-定向可由另一个α-定向通过一系列flip变换而得到的一个充分必要条件.与之平行,证明了球面嵌入图的任意两个α-定向均可通过一系列flip变换而相互得到.最后,给出了所需最少flip变换的数目.

一类上可嵌入图

本文主要证明了如下结果 :设G为 3-连通图 ,若G的顶点集存在一个C一划分 {V1,V2 ,… ,Vn} ,使得对每个 1≤i≤n ,|Vi|≡ 0 (mod 2 ) ,且对任意的v∈V(G) ,dG=(v)≡ 1(mod 2 ) ,则G是上可嵌入的 .

Thomassen与曲面嵌入图的着色

曲面嵌入图的着色的研究起源于Heawood地图着色定理.本文在对原始文献进行研究的基础上,论述Thomassen在三色定理与列表着色、曲面嵌入图的着色、色多项式和着色的数目等方面的工作.他的研究受到了Mohar,Thomas和Hutchinson等许多数学家的关注.

上可嵌入图与次上可嵌入图的线性荫度

通过度再分配的方法研究上可嵌入图与次上可嵌入图的线性荫度,证明了最大度△不小于(4-3ε)^(1/3)且欧拉示性数ε≤0的上可嵌入图其线性荫度为「△/2」.对于次上可嵌入图,如果最大度△≥(4-3ε)^(1/3)且ε≤0,则其线性荫度为「△/2」.改进了文献[1]中最大度的的界.作为应用证明了双环面上的三角剖分图的线性荫度.

极大平面图的面嵌入图

定义了极大平面图的面嵌入图的概念,分析了这类极大平面图的结构和性质,给出了一类最小度等于5的四可着色的极大平面图.

曲面嵌入图的圈基

圈基常用于描述图的圈结构.在实际应用算法中,算法的复杂度取决于圈基的选择.圈基的长,即其包含的边数,直接影响算法的速度.2-连通图G圈基长的一个下界是2 |E (G)|-|V (G)|,其中V (G)和E (G)分别是顶点集和边集.若图G包含长为2 |E (G|)-|V (G)|的圈基,则它是平面图.本文应用曲面嵌入图理论将这一结果推广至曲面嵌入图上.

基于相似网络和联合注意力的图嵌入模型

图注意力网络(graph attention network, GAT)将注意力机制与图神经网络融合,但模型只关注节点的一阶邻域节点,缺乏对高阶相似节点的考虑,同时在计算注意力分数时缺乏对节点结构特征的关注.为此提出一种基于相似网络和联合注意力的图嵌入模型.首先计算网络中的节点相似性,并将高相似度且未连接的节点对构建新边以形成相似网络.其次,引入结构相关性和内容相关性的概念,分别用于表征节点之间的结构关系和内容特征.通过融合两种相关性得分计算得到联合注意力分数.最后使用联合注意力分数对节点特征加权聚合,得到最终的节点嵌入表示.将本文所提算法在Cora、Citeseer和Pubmed 3个数据集上进行节点分类任务,准确率分别达到85.70%、74.30%、84.10%,与原始图注意力网络模型相比分别提高了2.70%、3.94%和2.60%.可见,所提出的算法可以得到更好的节点嵌入表示.

基于图嵌入和多标签传播的重叠社区检测算法

为进一步优化重叠社区检测算法,提出了一种新的基于度和节点聚类系数的节点重要性定义,按照节点重要性降序更新节点,固定节点更新策略,提高社区检测的稳定性。在此基础上,提出了一种基于图嵌入和多标签传播的重叠社区检测算法(overlapping community detection based on graph embedding and multi-label propagation algorithm,OCD-GEMPA)。该算法结合node2vec模型对节点进行低维向量表示,构建节点之间的权重值矩阵,根据权重值计算标签归属系数,据此选择标签,避免了随机选择问题。在真实数据集和人工合成数据集上对该算法进行实验验证。实验结果表明,与其他重叠社区检测算法相比,OCD-GEMPA在EQ和NMI这两个指标都有明显提升,具有更好的准确性和稳定性。

基于超图嵌入的行车故障多元关系知识表示方法

鉴于常规知识图谱仅能处理二元关系,而故障知识包含大量“多现象—多原因—多方法”的多元耦合关系,强制转化将会破坏关系的完整性,造成严重的信息失真,为采用知识超图处理此类复杂多元关系以保证数据的完整性,设计了一种基于超图嵌入的行车故障多元关系知识表示方法。通过梳理行车故障单中现象、原因、方法等数据之间的多元关联,构建适用于表征多元耦合关系的行车故障本体模型,以该本体模型为知识超图的模式层建立行车故障知识超图;基于BERT模型和超图卷积网络获取故障知识的嵌入向量表示,并实现了相似故障检索。最后,以上海某钢铁公司收集的行车故障调查单为实例,验证了所提方法的有效性。

基于全局-局部图嵌入的轴承故障诊断

传统基于图的故障诊断框架通常是利用高维数据某种结构关系构造相似图以揭示样本间的几何结构,造成数据其他结构信息丢失,无法准确提取出表征轴承运行状态的低维特征。提出了一种新的基于图的无监督特征提取方法,该方法在构造图的过程中同时考虑了高维数据的全局和局部结构,称为全局–局部图嵌入,该方法首先利用数据的全局结构信息构造一个无向图。然后,通过构造局部结构信息赋予无向图中边相应的权重,得到一个全局–局部图联合表示凸优化问题,并根据得到权重评估样本间的相似性。最后,通过在低维空间中保持样本间的相似性不变计算低维嵌入结果。相较于单一的图结构表示法,构造的全局–局部联合图充分利用了高维数据固有的全局和局部结构信息。此外,通过保持样本间的相似性能有效提取出高维轴承数据的本质特征,实验结果表明,提出的基于全局–局部图嵌入的特征提取方法较现有的方法具有明显优势。

基于图嵌入的多任务用户交互日志分段方法

机器人流程自动化需要借助用户交互日志设计流程模型。然而,真实场景中的用户交互日志往往包含多种任务,同时不同的任务执行过程也很可能存在相互干扰。针对上述问题,本文提出一种基于图嵌入的多任务用户交互日志分段方法。该方法首先将行为上下文信息融入直接跟随图中,然后利用图嵌入算法提取行为的向量表征,最后根据行为前驱、后继相关性对用户交互日志进行切分和聚类,从而达到自动分段的目的。特别地,为了提高行为向量表征的准确性,提出权重增强的方法来优化图嵌入算法中的采样过程。实验结果表明,所提方法可以有效地解决多任务顺序和交错执行场景用户交互日志分段问题。

基于平衡分层K均值的正交无监督大型图嵌入降维算法

为了降低大规模数据集降维的计算代价,提出一种基于平衡分层K均值的正交无监督图嵌入降维方法。该文给出局部保持投影和谱回归等价的充分必要条件;基于平衡分层K-means的锚生成策略,构建加快局部保持投影求解过程的特殊相似矩阵;再结合正交约束,提出正交化无监督大型图嵌入降维方法;在几种公开数据集上进行扩展实验,结果表明提出的方法能够对大规模数据集实现高效快速的降维。

深度学习支持下的自适应学习路径推荐——融合图嵌入与注意力机制的知识追踪模型

自适应学习路径推荐是智能技术在教育服务智能化中的核心应用。知识追踪通过分析学生的历史学习记录,预测其未来知识水平,从而为其提供个性化的学习规划与推荐。然而,现有的知识追踪方法在处理学生在线学习行为的复杂性时存在数据稀疏问题,并且忽略了时间因素和学生的遗忘机制,导致模型不能准确捕捉学生的状态变化,影响推荐效果。因此,在知识追踪模型中融合图嵌入和注意力机制,设计出一种新颖的深度学习支持下的自适应学习路径推荐模型(GE-MAKT)。实验结果表明,相较于传统方法,GE-MAKT模型的AUC和ACC两个评价指标得到显著提升,增强了对学生知识掌握水平的判断能力,可为学生提供更加个性化的学习路径推荐。

基于图嵌入的二进制代码模块划分方法

软件逆向分析作为网络空间安全领域研究的核心支撑技术,在软件漏洞分析、恶意代码行为分析等方面有着广泛应用.二进制代码的模块划分是该领域研究中的关键问题,通过将复杂或者大体量软件合理划分为若干模块,对于帮助分析者快速、准确理解软件结构与功能,提高分析效率起着重要作用.对此,常见方法是将代码中的函数及其调用关系看作复杂网络,通过社区发现算法来进行函数聚类,实现模块划分,该类方法通常只考虑节点之间的连接关系,忽略了节点的属性、节点之间的相似度等信息,且对噪声和异常值比较敏感.为了解决这些问题,提出了一种基于图嵌入的二进制代码模块划分(graph embedding based binary code modularization,GEBCM)方法.该方法首先将软件系统抽象为属性图,然后通过带有注意力机制和排名机制的图嵌入聚类方法对函数节点进行嵌入表示并聚类.通过聚类将二进制文件分组为更具有完整功能的独立部分,揭示了复杂程序结构中分离的模块语义信息.在2个数据集上进行的实验评估,验证了所提出的GEBCM方法的有效性.评估结果表明,相比其他二进制模块化工作,GEBCM的F1值平均提高10.2个百分点.此外,在针对恶意样本的评估实验中,GEBCM能有效地划分出恶意代码的模块,表现出优秀的可扩展性.

自适应图嵌入和非凸正则特征自表达的无监督特征选择

针对传统的无监督特征选择不能充分兼顾样本及特征的局部结构,以及没有考虑非凸正则项带来更稀疏的解并能够选择出更具判别性特征等问题,提出了自适应图嵌入和非凸正则特征自表达的无监督特征选择方法。通过图嵌入降低特征维度,获得样本相似度矩阵,引导特征选择;引入特征自表达策略,用其余特征线性表示每一个特征,考虑特征间的相似性关系,保持特征局部结构;在特征自表达中添加非凸正则项,获得行更稀疏的权重矩阵,实现特征选择;在特征选择过程中执行自适应图嵌入对数据局部结构进行学习,选择最优特征子集;为求解非凸稀疏问题,使用交替迭代方法优化求解模型,设计了一种新的无监督特征选择算法。在6个数据集上与其他算法进行实验对比分析,实验结果表明所提算法是有效的。

异质图嵌入的地理不敏感时空兴趣点推荐方法

基于地理位置的社交网络(LBSN)规模日渐庞大,促进了兴趣点(POI)推荐业务快速发展。现有研究常直接引入POI地理空间距离难以模拟用户高度随机的行为路径,导致兴趣点推荐过程对地点位置距离度量较为敏感。同时,社交网络中用户稀疏的POI签到数据也容易对推荐精度产生巨大影响。针对以上问题,提出一种基于异质图嵌入的地理不敏感时空兴趣点推荐模型(GIPR)。首先,引入用户行为序列,构造行为POI时空拓扑图,使用权重空间路径表示相对位置距离,既符合用户行为特征,也降低了推荐过程对兴趣点间距离的敏感程度,进而增强推荐结果的可解释性。其次,面对异质且高度稀疏的交互数据,提出的GIPR推荐方法可从局部和全局对完整的LBSN异质图进行学习,融合更丰富的用户和POI特征。最后,经过注意力层提取用户的长短期偏好,实现更加个性化的兴趣点推荐。在两个大规模真实数据集Foursquare和Gowalla上的实验表明,GIPR方法具有更高的推荐精度与更强的可解释性。