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.

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.

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.

A method for improving graph queries processing using positional inverted index (P.I.I) idea in search engines and parallelization techniques

The idea of positional inverted index is exploited for indexing of graph database. The main idea is the use of hashing tables in order to prune a considerable portion of graph database that cannot contain the answer set. These tables are implemented using column-based techniques and are used to store graphs of database, frequent sub-graphs and the neighborhood of nodes. In order to exact checking of remaining graphs, the vertex invariant is used for isomorphism test which can be parallel implemented. The results of evaluation indicate that proposed method outperforms existing methods.

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.

SIHC:一种高效的时态图上k-core查询算法

许多实体之间的关系可以建模为时态图,其中每条边都与表示其发生的时间相关联,k-core是捕获密集子图的基本模型,在近些年得到了广泛研究.给定时间区间I=[s,e]和k值,时态图G上的k-core子图查询从区间I对应的快照图GI中返回相应的k-core子图.针对时态图中的k-core子图查询问题,现有方法是基于PHC索引(Pruned Historical Core-Index)的算法.对任意可能的k值,PHC索引维护了所有可能出现在某个时间区间的k-core子图中的顶点集Sk,且为集合中每个顶点存储了一组时间区间,用于判定该点是否属于给定时间区间的k-core子图.基于PHC索引查询k-core子图时,需要访问Sk集合中的所有顶点,并判断每个顶点的可满足性.由于Sk集合对应于最大区间快照图的k-core子图里的所有顶点,且实际中用户查询区间对应的快照图往往比最大区间快照图小得多,基于PHC索引的查询算法存在许多无效判断,需要对大量不在结果集中的顶点进行检测,且无效检测次数随着查询区间的缩短而增多,从而导致算法效率较低.针对该问题,本文提出一种新的索引,即最短区间历史核索引SIHC(Shortest Interval Historical Core Index).SIHC索引的基本思想是通过维护最短k核区间到顶点的倒排表,查询处理时,可基于用户给定的时间区间定位到SIHC索引中满足条件的区间,进而直接得到满足条件的k-core子图中的顶点,从而避免了基于PHC索引进行查询时所需的大量无效判断.我们从理论上证明了基于SIHC索引处理时态图上k-core子图查询的正确性,并设计了高效的索引构建算法.最后,基于真实世界的时态图进行了实验,实验结果表明本文提出的算法比现有算法快1~2个数量级.

Aunu Integer Sequence as Non-Associative Structure and Their Graph Theoretic Properties

The generating function for generating integer sequence of Aunu numbers of prime cardinality was reported earlier by the author in [1]. This paper assigns an operator on the function for where the operation induces addition or subtraction on the pairs of ai, aj elements which are consecutive pairs of elements obtained from a generating set of some finite order. The paper identifies that the set of the generated pairs of integer sequence is non-associative. The paper also presents the graph theoretic applications of the integers generated in which subgraphs are deduced from the main graph and adjacency matrices and incidence matrices constructed. It was also established that some of the subgraphs were found to be regular graphs. The findings in this paper can further be used in coding theory, Boolean algebra and circuit designs.

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.

一种基于Apriori思想的频繁子图发现算法

如今,关联规则技术应用在许多非传统领域,许多已有的频繁项集搜索方法已经不适用了。一种解决的方法就是用图的形式表示这些领域的事务,然后利用基于图论的数据挖掘技术发现频繁子图。本文提出了一种基于Aproiri思想的频繁子图发现算法SLAGM,它可以有效地挖掘简单图中的频繁子图。实验证明,该算法在性能上优于另一种子图挖掘算法AGM。

基于图重构和子图挖掘的僵尸网络检测方法

针对伪装后僵尸网络主机难以检测的问题,提出一种基于图重构和子图挖掘的僵尸网络检测方法(GR-SGM)。首先,将网络数据转化为图数据,并对其进行重构以此增强主机节点特征表示;其次,基于重构图中拓扑结构、节点的特征和位置变化设计僵尸网络子图评分函数,以此捕捉伪装后的特征,提取出僵尸网络子图,并对原始图和重构图进行预检测,以提高检测的准确率和效率,减少重构误差;最后,对预检测结果和僵尸网络子图进行综合评分,以获取完整的僵尸网络信息。在ISCX2014僵尸网络数据集和CICIDS2017僵尸网络数据集上的实验结果表明:GR-SGM的检测准确率分别达到99.98%和99.91%,F 1分别达到99.94%和99.65%,相较于其他僵尸网络检测模型,GR-SGM能更加高效准确地识别僵尸网络节点,同时具有更低的误报率。

Design Pattern Mining Using Graph Matching

The identification of design pattern instances is important for program understanding and software maintenance. Aiming at the mining of design patterns in existing systems, this paper proposes a subgraph isomorphism approach to discover several design patterns in a legacy system at a time. The attributed relational graph is used to describe design patterns and legacy systems. The sub-graph isomorphism approach consists of decomposition and composition process. During the decomposition process, graphs corresponding to the design patterns are decomposed into sub-graphs, some of which are graphs corresponding to the elemental design patterns. The composition process tries to get sub-graph isomorphism of the matched graph if sub-graph isomorphism of each subgraph is obtained. Due to the common structures between design patterns, the proposed approach can reduce the matching times of entities and relations. Compared with the existing methods, the proposed algorithm is not linearly dependent on the number of design pattern graphs. Key words design pattern mining - attributed relational graph - subgraph isomorphism CLC number TP 311.5 Foundation item: Supported by the National Natural Science Foundation of China (60273075) and the Science Foundation of Naval University of Engineering (HGDJJ03019)Biography: LI Qing-hua (1940-), male, Professor, research direction: parallel computing.

Inductive Relation Prediction by Disentangled Subgraph Structure

Currently,most existing inductive relation prediction approaches are based on subgraph structures,with subgraph features extracted using graph neural networks to predict relations.However,subgraphs may contain disconnected regions,which usually represent different semantic ranges.Because not all semantic information about the regions is helpful in relation prediction,we propose a relation prediction model based on a disentangled subgraph structure and implement a feature updating approach based on relevant semantic aggregation.To indirectly achieve the disentangled subgraph structure from a semantic perspective,the mapping of entity features into different semantic spaces and the aggregation of related semantics on each semantic space are updated.The disentangled model can focus on features having higher semantic relevance in the prediction,thus addressing a problem with existing approaches,which ignore the semantic differences in different subgraph structures.Furthermore,using a gated recurrent neural network,this model enhances the features of entities by sorting them by distance and extracting the path information in the subgraphs.Experimentally,it is shown that when there are numerous disconnected regions in the subgraph,our model outperforms existing mainstream models in terms of both Area Under the Curve-Precision-Recall(AUC-PR)and Hits@10.Experiments prove that semantic differences in the knowledge graph can be effectively distinguished and verify the effectiveness of this method.

STABILITY NUMBER IN SUBCLASSES OF P_5^-FREE GRAPHS

Two new hereditary classes of P 5-free graphs where the stability number can be found in polynomial time are proposed.They generalize several known results.

Exact Graph Pattern Matching:Applications,Progress and Prospects

Graph pattern matching(GPM)can be used to mine the key information in graphs.Exact GPM is one of the most commonly used methods among all the GPM-related methods,which aims to exactly find all subgraphs for a given query graph in a data graph.The exact GPM has been widely used in biological data analyses,social network analyses and other fields.In this paper,the applications of the exact GPM were first introduced,and the research progress of the exact GPM was summarized.Then,the related algorithms were introduced in detail,and the experiments on the state-of-the-art exact GPM algorithms were conducted to compare their performance.Based on the experimental results,the applicable scenarios of the algorithms were pointed out.New research opportunities in this area were proposed.

On the Number of Cycles in a Graph

In this paper, we obtain explicit formulae for the number of 7-cycles and the total number of cycles of lengths 6 and 7 which contain a specific vertex vi in a simple graph G, in terms of the adjacency matrix and with the help of combinatorics.

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

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

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

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

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

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

子图匹配和强化学习增强的三维点云配准

针对低质量三维点云数据配准精度不足、效率低的问题,为了实现低质量点云的精确、快速配准,提出一种基于子图匹配和强化学习的点云配准方法.首先将三维点云配准转化为一系列离散的刚性变换连续作用结果,利用强化学习策略训练一个端到端的模型以迭代输出刚性变换动作;然后对于模型架构,采用双流主干网络分别提取源点云与目标点云的局部特征信息,设计交叉图注意力模块将源点云图和目标点云图中的相似节点关联起来,使用带选通向量的加权实现图节点的聚合,分别获取源点云图与目标点云图的全局特征表示;最后融合源点云图与目标点云图的全局特征,基于融合特征预测离散的刚性变换动作.强化学习策略的引入显著提高了点云配准算法的泛化性,在加入交叉图注意力模块后,点云配准的精度及效率也进一步被提升.在ModelNet40和ScanObjectNN这2个公共基准数据集上与最新的点云配准方法 ReAgent进行实验的结果表明,所提方法能够将旋转误差的均方差数值降低至少0.16,各向同性旋转误差数值也降低至少0.16,有效地提升低质量点云配准的精度.