Note on 2-edge-colorings of complete graphs with small monochromatic k-connected subgraphs

Bollobas and Gyarfas conjectured that for n 〉 4（k - 1） every 2-edge-coloring of Kn contains a monochromatic k-connected subgraph with at least n - 2k ＋ 2 vertices. Liu, et al. proved that the conjecture holds when n 〉 13k - 15. In this note, we characterize all the 2-edge-colorings of Kn where each monochromatic k-connected subgraph has at most n - 2k ＋ 2 vertices for n ≥ 13k - 15.

Accurate querying of frequent subgraphs in power grid graph data

With the development of information technology, the amount of power grid topology data has gradually increased. Therefore, accurate querying of this data has become particularly important. Several researchers have chosen different indexing methods in the filtering stage to obtain more optimized query results because currently there is no uniform and efficient indexing mechanism that achieves good query results. In the traditional algorithm, the hash table for index storage is prone to "collision" problems, which decrease the index construction efficiency. Aiming at the problem of quick index entry, based on the construction of frequent subgraph indexes, a method of serialized storage optimization based on multiple hash tables is proposed. This method mainly uses the exploration sequence to make the keywords evenly distributed; it avoids conflicts of the stored procedure and performs a quick search of the index. The proposed algorithm mainly adopts the "filterverify" mechanism; in the filtering stage, the index is first established offline, and then the frequent subgraphs are found using the "contains logic" rule to obtain the candidate set. Experimental results show that this method can reduce the time and scale of candidate set generation and improve query efficiency.

ON THE ASCENDING SUBGRAPH DECOMPOSITIONS OF REGULAR GRAPHS

The definition of the ascending subgraph decomposition was given by Alavi. It has been conjectured that every graph of positive size has an ascending subgraph decomposition. In this paper it is proved that the regular graphs under some conditions do have an ascending subgraph decomposition.

Subgraph Matching Using Graph Neural Network

Subgraph matching problem is identifying a target subgraph in a graph. Graph neural network (GNN) is an artificial neural network model which is capable of processing general types of graph structured data. A graph may contain many subgraphs isomorphic to a given target graph. In this paper GNN is modeled to identify a subgraph that matches the target graph along with its characteristics. The simulation results show that GNN is capable of identifying a target sub-graph in a graph.

k-Factors and Spanning Subgraph in Graphs

In this paper, we discussed k-factors and spanning subgraph, and propose a conjecture which will lead to a series of important conclusion.

On the Ascending Subgraph Decomposition Problem

Alavi and his fellows defined the concept of ascending subgraph decomposition of a graph and conjectured that every graph with positive size has an ascending subgraph decomposition in paper [1]. Paper [2] proved that K n-R n-1 has a star ascending subgraph decomposition,here K n is the complete graph with order n and R n-1 is a subgraph of K n with size at most n-1. In paper [3],Ma Kejie and Chen Huaitang proved that K n-R n has an ascending subgraph decomposition when the size of R n is not greater than n. In this paper we will prove K n-R has an ascending subgraph decomposition when the size of R is less than 3n/2. This paper will also give the concept of comet and prove that K n-R n-1 has a comet ascending subgraph decomposition.

MF-SuP-pK_(a): Multi-fidelity modeling with subgraph pooling mechanism for pK_(a) prediction

Acid-base dissociation constant(pK_(a)) is a key physicochemical parameter in chemical science, especially in organic synthesis and drug discovery. Current methodologies for pK_(a) prediction still suffer from limited applicability domain and lack of chemical insight. Here we present MF-SuP-pK_(a)(multi-fidelity modeling with subgraph pooling for pK_(a) prediction), a novel pK_(a) prediction model that utilizes subgraph pooling, multi-fidelity learning and data augmentation. In our model, a knowledgeaware subgraph pooling strategy was designed to capture the local and global environments around the ionization sites for micro-pK_(a) prediction. To overcome the scarcity of accurate pK_(a) data, lowfidelity data(computational pK_(a)) was used to fit the high-fidelity data(experimental pK_(a)) through transfer learning. The final MF-SuP-pK_(a) model was constructed by pre-training on the augmented ChEMBL data set and fine-tuning on the DataWarrior data set. Extensive evaluation on the DataWarrior data set and three benchmark data sets shows that MF-SuP-pK_(a) achieves superior performances to the state-of-theart pK_(a) prediction models while requires much less high-fidelity training data. Compared with Attentive FP, MF-SuP-pK_(a) achieves 23.83% and 20.12% improvement in terms of mean absolute error(MAE) on the acidic and basic sets, respectively.

Loop Subgraph-Level Greedy Mapping Algorithm for Grid Coarse-Grained Reconfigurable Array

To solve the problem of grid coarse-grained reconfigurable array task mapping under multiple constraints,we propose a Loop Subgraph-Level Greedy Mapping(LSLGM)algorithm using parallelism and processing element fragmentation.Under the constraint of a reconfigurable array,the LSLGM algorithm schedules node from a ready queue to the current reconfigurable cell array block.After mapping a node,its successor’s indegree value will be dynamically updated.If its successor’s indegree is zero,it will be directly scheduled to the ready queue;otherwise,the predecessor must be dynamically checked.If the predecessor cannot be mapped,it will be scheduled to a blocking queue.To dynamically adjust the ready node scheduling order,the scheduling function is constructed by exploiting factors,such as node number,node level,and node dependency.Compared with the loop subgraph-level mapping algorithm,experimental results show that the total cycles of the LSLGM algorithm decreases by an average of 33.0%(PEA44)and 33.9%(PEA_(7×7)).Compared with the epimorphism map algorithm,the total cycles of the LSLGM algorithm decrease by an average of 38.1%(PEA_(4×4))and 39.0%(PEA_(7×7)).The feasibility of LSLGM is verified.

Simplifying social networks via triangle-based cohesive subgraphs

One main challenge for simplifying node-link diagrams of large-scale social networks lies in that simplified graphs generally contain dense subgroups or cohesive subgraphs.Graph triangles quantify the solid and stable relationships that maintain cohesive subgraphs.Understanding the mechanism of triangles within cohesive subgraphs contributes to illuminating patterns of connections within social networks.However,prior works can hardly handle and visualize triangles in cohesive subgraphs.In this paper,we propose a triangle-based graph simplification approach that can filter and visualize cohesive subgraphs by leveraging a triangle-connectivity called k-truss and a force-directed algorithm.We design and implement TriGraph,a web-based visual interface that provides detailed information for exploring and analyzing social networks.Quantitative comparisons with existing methods,two case studies on real-world datasets,and feedback from domain experts demonstrate the effectiveness of TriGraph.

基于图常量条件函数依赖的图修复规则发现

数据一致性是数据质量管理的一个重要内容。为了提升图数据一致性,大量关系型数据库中的数据依赖理论被引入到图数据库,包括图函数依赖、图关联规则等。图修复规则是最新提出的一种针对图数据的数据依赖规则,具有强大的修复能力,但目前尚无有效的挖掘算法。为了自动生成图修复规则并提高图数据修复的可靠性,提出一种将图常量条件函数依赖转化为图修复规则的方法(GenGRR)。通过图模式在图中匹配同构子图并映射成节点-属性二维表,从表中相应属性域中抽取错误模式把图常量条件函数依赖转化成图属性值修复规则;删去图模式中常量条件函数依赖RHS对应的节点与相连边生成图属性补充规则。基于最大公共同构子图筛选并验证生成图修复规则的一致性。在多个真实数据集上进行测试,验证相比图常量条件函数直接修复图数据,通过转化生成的图修复规则具有更好的修复效果。

航班延误特征可视分析方法

为分析航班延误发生规律,提出一种数学模型联合多视图协同的可视分析方法。对SEIR传染病传播模型进行调整,建立航班延误传播模型分析延误的传播特征,在此基础上,运用频繁子图挖掘算法提取延误频繁模式;设计基于中点分割的地图网络图、矩阵热力图和时序图,分析延误的时空分布特征;设计VA-FDC系统用于方法验证。实验结果表明,VA-FDC能够有效分析航班延误时空分布特征,依据航班延误传播模型准确描述延误传播特征,为相关部门有效措施的制定提供借鉴。

基于PathSim的MOOCs知识概念推荐模型

大规模开放在线课程提供大规模开放式在线学习平台,为推进现代教育发挥关键作用。然而,减少用户学习盲区和改善用户体验方面的研究仍具有挑战性:交互数据稀疏;难以扩展到大型推荐任务上;用户需求不单由用户喜好决定,还受到不同教师、课程影响;以统一的方式对课程学习事件中不同类型实体及关系进行建模并不妥靠。基于此,引入相关性度量,依据全图结构信息计算各边权重,提出采用相关性度量算法PathSim进行邻域采样的知识概念推荐模型PathSimSage。各实体间相关性得分可在本地离线计算,将神经网络与传播过程分离,保证神经网络的堆叠层数和传播过程的独立性,大幅减少模型所需训练时间。在公开的MoocCube数据集上进行了综合实验,PathSimSage降低了不相关的信息甚至噪声的影响,解决随机游走采样所引发的高度节点偏差问题,并在一定程度上缓解了过平滑效应。

基于区域路标引导的月面大范围高效行驶导航技术

载人月球探测任务中,受月面环境的复杂性和车载系统配置的限制,仅依靠车载导航系统难以全自主实现精确导航,需要遥操作中心对载人车大范围移动进行智能化支持。针对载人车在复杂月面环境中进行远距离探测时的高效导航问题,提出了基于区域路标引导的月面大范围高效行驶导航方法,通过分析载人车导航相机成像区域,将全路线可视区域中的月坑构建为月面路标图;并利用载人车导航相机图像中的月坑构建导航相机路标图,使用子图匹配的方法确定载人车可视区域内的月坑和环月卫星影像中月坑的对应关系,从而完成载人车位姿的解算。仿真试验结果表明:提出方法可以实现大范围移动过程中的高效导航。

A subgraph matching algorithm based on subgraph index for knowledge graph

The problem of subgraph matching is one fundamental issue in graph search,which is NP-Complete problem.Recently,subgraph matching has become a popular research topic in the field of knowledge graph analysis,which has a wide range of applications including question answering and semantic search.In this paper,we study the problem of subgraph matching on knowledge graph.Specifically,given a query graph q and a data graph G,the problem of subgraph matching is to conduct all possible subgraph isomorphic mappings of q on G.Knowledge graph is formed as a directed labeled multi-graph having multiple edges between a pair of vertices and it has more dense semantic and structural features than general graph.To accelerate subgraph matching on knowledge graph,we propose a novel subgraph matching algorithm based on subgraph index for knowledge graph,called as FGqT-Match.The subgraph matching algorithm consists of two key designs.One design is a subgraph index of matching-driven flow graph(FGqT),which reduces redundant calculations in advance.Another design is a multi-label weight matrix,which evaluates a near-optimal matching tree for minimizing the intermediate candidates.With the aid of these two key designs,all subgraph isomorphic mappings are quickly conducted only by traversing FGqj.Extensive empirical studies on real and synthetic graphs demonstrate that our techniques outperform the state-of-the-art algorithms.

Social Robot Detection Method with Improved Graph Neural Networks

Social robot accounts controlled by artificial intelligence or humans are active in social networks,bringing negative impacts to network security and social life.Existing social robot detection methods based on graph neural networks suffer from the problem of many social network nodes and complex relationships,which makes it difficult to accurately describe the difference between the topological relations of nodes,resulting in low detection accuracy of social robots.This paper proposes a social robot detection method with the use of an improved neural network.First,social relationship subgraphs are constructed by leveraging the user’s social network to disentangle intricate social relationships effectively.Then,a linear modulated graph attention residual network model is devised to extract the node and network topology features of the social relation subgraph,thereby generating comprehensive social relation subgraph features,and the feature-wise linear modulation module of the model can better learn the differences between the nodes.Next,user text content and behavioral gene sequences are extracted to construct social behavioral features combined with the social relationship subgraph features.Finally,social robots can be more accurately identified by combining user behavioral and relationship features.By carrying out experimental studies based on the publicly available datasets TwiBot-20 and Cresci-15,the suggested method’s detection accuracies can achieve 86.73%and 97.86%,respectively.Compared with the existing mainstream approaches,the accuracy of the proposed method is 2.2%and 1.35%higher on the two datasets.The results show that the method proposed in this paper can effectively detect social robots and maintain a healthy ecological environment of social networks.

k阶采样和图注意力网络的知识图谱表示模型

知识图谱表示(KGE)旨在将知识图谱中的实体和关系映射到低维度向量空间而获得其向量表示。现有的KGE模型只考虑一阶近邻,这影响了知识图谱中推理和预测任务的准确性。为了解决这一问题,提出了一种基于k阶采样算法和图注意力网络的KGE模型。k阶采样算法通过聚集剪枝子图中的k阶邻域来获取中心实体的邻居特征。引入图注意力网络来学习中心实体邻居的注意力值,通过邻居特征加权和得到新的实体向量表示。利用ConvKB作为解码器来分析三元组的全局表示特征。在WN18RR、FB15k-237、NELL-995、Kinship数据集上的评价实验表明,该模型在链接预测任务上的性能明显优于最新的模型。此外,还讨论了阶数k和采样系数b的改变对模型命中率的影响。

基于复杂网络的突发事件下汽车产业供应链韧性研究

汽车产业供应链中,各企业间由于合作伙伴关系或者竞争关系而产生的交互作用影响整个供应链网络,加之其参与主体众多,更易受到各种突发事件的干扰影响网络韧性。文章以复杂网络模型为基础,收集中国经济金融研究数据库数据库汽车供应链板块中141家车企数据构建复杂网络关系矩阵模型,通过复杂网络特性分析对所构建的网络模型进行检验。采用目标干扰和随机干扰两种方式来模拟突发事件产生的供应链中断情景,由矩阵工厂和大型复杂网络分析工具对网络进行仿真实验,通过最大连通子图所表示的弹性性能和效率性能两项数据来观测网络稳定性,得出提升汽车产业供应链韧性的方法。

以子图融合为最小单位的混合精度推理

近几年卷积神经网络作为深度学习最重要的技术,在图像分类、物体检测、语音识别等领域均有所建树。在此期间,由多层卷积神经网络组成的深度神经网络横空出世,在各种任务准确性方面具有显著提升。然而,神经网络的权重往往被限定在单精度类型,使网络体积相较于特定硬件平台上的内存空间更大,且floating point 16、INT 8等单精度类型已无法满足现在一些模型推理的现实需求。为此,提出一种以子图为最小单位,通过判断相邻结点之间的融合关系,添加了丰富比特位的混合精度推理算法。首先,在原有单精度量化设计的搜索空间中增加floating point 16半精度的比特配置,使最终搜索空间变大,为寻找最优解提供更多机会。其次,使用子图融合的思想,通过整数线性规划将融合后的不同子图精度配置,根据模型大小、推理延迟和位宽操作数3个约束对计算图进行划分,使最后累积的扰动误差减少。最终,在ResNet系列网络上验证发现,所提模型精度相较于HAWQ V3的损失没超过1%的同时,相较于其他混合精度量化方法在推理速度方面得到了提升,在ResNet18网络中推理速度分别提升18.15%、19.21%,在ResNet50网络中推理速度分别提升13.15%、13.70%。

基于图挖掘的黑灰产运作模式可视分析

为分析黑灰产网络资产图谱数据中黑灰产团伙掌握的网络资产及其关联关系,提出一种基于图挖掘的黑灰产运作模式可视分析方法.首先,在网络资产图谱数据中锁定潜在团伙线索;其次,根据潜在线索、黑灰产业务规则挖掘由同一黑灰产团伙掌握的网络资产子图,并识别子图中的核心资产与关键链路;最后,基于标记核心资产和关键链路的黑灰产子图实现可视分析系统,从而直观发现黑灰产团伙掌握的网络资产及其关联关系,帮助分析人员制定黑灰产网络资产打击策略.经实验验证,该方法能有效、直观地分析和发现黑灰产团伙及其网络资产关联关系,为更好监测黑灰产网络运作态势提供必要的技术支持.

采用局部子图嵌入的MOOCs知识概念推荐模型

大规模开放在线课程(MOOCs)在减少用户学习盲区和改善用户体验方面已经有大量的研究,尤其是基于图神经网络的个性化课程资源推荐,但现有工作主要集中在固定或同质图上,容易受到数据稀疏问题的影响且难以扩展。在局部子图上使用图卷积,并结合扩展的矩阵分解(MF)模型来解决这一问题。首先,将异构图分解为多个基于元路径的子图,结合随机游走采样方法实现在采样节点富有影响力邻域的同时捕获实体之间复杂的语义关系,并在局部邻域上进行图卷积平滑各节点表示,实现高可扩展性;然后,使用注意力机制适应性地融合不同子图的上下文信息,更全面地构建用户偏好;最后,通过扩展矩阵分解优化模型参数,获得推荐列表。为了验证提出模型的性能,在公开的MOOCs数据集上进行对比实验,相较于最优基线,性能提升了2%,内存计算需求降低了近500%,缓解数据稀疏问题的同时仍具有较强的可扩展性。