Matching spatial relation graphs using a constrained partial permutation strategy

A constrained partial permutation strategy is proposed for matching spatial relation graph (SRG), which is used in our sketch input and recognition system Smart Sketchpad for representing the spatial relationship among the components of a graphic object. Using two kinds of matching constraints dynamically generated in the matching process, the proposed approach can prune most improper mappings between SRGs during the matching process. According to our theoretical analysis in this paper, the time complexity of our approach is O(n 2) in the best case, and O(n!) in the worst case, which occurs infrequently. The spatial complexity is always O(n) for all cases. Implemented in Smart Sketchpad, our proposed strategy is of good performance.

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.

基于潜在语义与图结构的微博语义检索

微博文本短小、特征稀疏、与用户查询之间存在语义鸿沟的特点会降低语义检索效率。针对该问题,结合文本特征和知识库语义,构建基于潜在语义与图结构的语义检索模型。通过Tversky算法计算基于Hashtag的特征相关度;利用隐含狄利克雷分布算法对Wikipedia语料库训练主题模型,基于JSD距离计算映射到该模型的文本主题相关度;抽取DBpedia中实体及其网络关系连接图,使用SimRank算法计算图中实体间的相关度。综合以上3个结果得到最终相关度。通过短文本和长文本检索对Twitter子集进行实验,结果表明,与基于开放关联数据和图论的方法相比,该模型在评估指标MAP,P@30,R-Prec上分别提高了2.98%,6.40%,5.16%,具有较好的检索性能。

一种基于语义关系图的词语语义相关度计算模型

词语的语义计算是自然语言处理领域的重要问题之一,目前的研究主要集中在词语语义的相似度计算方面,对词语语义的相关度计算方法研究不够.为此,本文提出了一种基于语义词典和语料库相结合的词语语义相关度计算模型.首先,以HowNet和大规模语料库为基础,制定了相关的语义关系提取规则,抽取了大量的语义依存关系;然后,以语义关系三元组为存储形式,构建了语义关系图;最后,采用图论的相关理论,对语义关系图中的语义关系进行处理,设计了一个基于语义关系图的词语语义相关度计算模型.实验结果表明,本文提出的模型在词语语义相关度计算方面具有较好的效果,在Word Similarity-353数据集上的斯皮尔曼等级相关系数达到了0.5358,显著地提升了中文词语语义相关度的计算效果.

基于中文维基百科的词语相关度计算

词语相关度的计算是自然语言处理关键技术之一，在信息检索、机器翻译、词义消歧、句法分析等领域有广泛应用。国内现有大部分词语相关度计算方法是基于知网（HowNet）的。本文将中文维基百科作为语义资源，利用其分类层次、概念文档之间的链接来计算汉语词语之间的相关度。在借鉴向量空间模型和谷歌相似度（Google Similarity Distance）计算方法基础上，通过构建分类图和相关语义向量来实现汉语词语相关度的计算。在测试集Word Similarity-353上进行了实验，实验结果的斯皮尔曼等级相关系数显示，本文的方法是可行和有效的。

Graph-Segmenter:graph transformer with boundary-aware attention for semantic segmentation

Thetransformer-based semantic segmentation approaches,which divide the image into different regions by sliding windows and model the relation inside each window,have achieved outstanding success.However,since the relation modeling between windows was not the primary emphasis of previous work,it was not fully utilized.To address this issue,we propose a Graph-Segmenter,including a graph transformer and a boundary-aware attention module,which is an effective network for simultaneously modeling the more profound relation between windows in a global view and various pixels inside each window as a local one,and for substantial low-cost boundary adjustment.Specifically,we treat every window and pixel inside the window as nodes to construct graphs for both views and devise the graph transformer.The introduced boundary-awareattentionmoduleoptimizes theedge information of the target objects by modeling the relationship between the pixel on the object's edge.Extensive experiments on three widely used semantic segmentation datasets(Cityscapes,ADE-20k and PASCAL Context)demonstrate that our proposed network,a Graph Transformer with Boundary-aware Attention,can achieve state-of-the-art segmentation performance.

基于维基语义图的词语语义相关度计算研究

针对词语语义相关度计算缺乏统一模型框架与典型随机游走模型PPR（ Personalized PageRank）中的问题，提出基于维基语义图的词语语义相关度算法P3R（ Penalized-Personalized PageRank ） 。P3R强调词语相关关系的相对性，能够减小PPR“马太效应”对相关度计算产生的影响，同时集成多种语义特征于一个统一的维基多关系语义图模型，使不同语义关系得到互相增强。实验中，比对典型方法验证了P3R的有效性与准确性。

Architecture and algorithm for web phishing detection

A phishing detection system, which comprises client-side filtering plug-in, analysis center and protected sites, is proposed. An image-based similarity detection algorithm is conceived to calculate the similarity of two web pages. The web pages are first converted into images, and then divided into sub-images with iterated dividing and shrinking. After that, the attributes of sub-images including color histograms, gray histograms and size parameters are computed to construct the attributed relational graph（ARG）of each page. In order to match two ARGs, the inner earth mover＇s distances（EMD）between every two nodes coming from each ARG respectively are first computed, and then the similarity of web pages by the outer EMD between two ARGs is worked out to detect phishing web pages. The experimental results show that the proposed architecture and algorithm has good robustness along with scalability, and can effectively detect phishing.

社会化标签系统语义相关度的拓扑图法计算

针对Web2.0社会化标签系统中标签组织混乱和标签语义模糊的问题,围绕标签共现网络的拓扑图,建立了一种形式化的标签语义相关度计算模型.该模型利用基于统计的标签语义相关度计算结果,为标签共现网络的拓扑图扩展以语义相关度权值,并定义算子围绕标签共现网络的拓扑图来计算权值的综合效应,从而可以显式地描述标签语义关联的交叉影响,并在标签语义相关度的计算中融入这些影响因素.从照片共享网站Flickr中抓取热门标签数据,通过实验对该模型的计算过程、计算结果的有效性和实用性等进行了分析评价.实验表明,该模型的标签语义相关度计算结果更为准确,可以更好地引导和约束Web2.0用户的标签使用行为.

Development of efficient and accurate skeletal mechanisms for hydrocarbon fuels and kerosene surrogate

In this paper,the methodology of the directed relation graph with error propagation and sensitivity analysis（DRGEPSA）,proposed by Niemeyer et al.（Combust Flame 157：1760-1770.2010）.and its differences to the original directed relation graph method are described.Using DRGEPSA,the detailed mechanism of ethylene containing 71 species and 395 reaction steps is reduced to several skeletal mechanisms with different error thresholds.The 25-species and 131-step mechanism and the 24-species and115-step mechanism are found to be accurate for the predictions of ignition delay time and laminar flame speed.Although further reduction leads to a smaller skeletal mechanism with 19 species and 68 steps,it is no longer able to represent the correct reaction processes.With the DRGEPSA method,a detailed mechanism for n-dodecane considering low-temperature chemistry and containing 2115 species and8157 steps is reduced to a much smaller mechanism with249 species and 910 steps while retaining good accuracy.If considering only high-temperature（higher than 1000 K）applications,the detailed mechanism can be simplified to even smaller mechanisms with 65 species and 340 steps or48 species and 220 steps.Furthermore,a detailed mechanism for a kerosene surrogate having 207 species and 1592 steps is reduced with various error thresholds and the results show that the 72-species and 429-step mechanism and the66-species and 392-step mechanism are capable of predicting correct combustion properties compared to those of the detailed mechanism.It is well recognized that kinetic mechanisms can be effectively used in computations only after they are reduced to an acceptable size level for computation capacity and at the same time retaining accuracy.Thus,the skeletal mechanisms generated from the present work are expected to be useful for the application of kinetic mechanisms of hydrocarbons to numerical simulations of turbulent or supersonic combustion.

利用词项语义共现和社团划分发现微博热点事件

针对传统词项之间语义关系抽取难以适用于微博,导致发现微博热点事件不敏感的问题,提出一种基于词项语义共现和社团划分的方法发现热点事件。首先利用热度定义对微博数据进行初次筛选,通过构建共现词项图来模拟词项间的语义相关性,并结合修改的TF-IDF公式计算词项间的语义相关度;借助社区划分和模块度的概念对词项图进行划分,完成词项聚类,进而获得热点事件。实验结果表明,与同类方法相比,该方法的准确率较高,发现的热点事件与实时事件基本保持一致,具有较好的热点识别效果。

Parametric message passing-based relative navigation in joint tactical information distribution system

Relative navigation is a key feature in the joint tactical information distribution system（JTIDS）.A parametric message passing algorithm based on factor graph is proposed to perform relative navigation in JTIDS.First of all,the joint posterior distribution of all the terminals＇ positions is represented by factor graph.Because of the nonlinearity between the positions and time-of-arrival（TOA） measurement,messages cannot be obtained in closed forms by directly using the sum-product algorithm on factor graph.To this end,the Euclidean norm is approximated by Taylor expansion.Then,all the messages on the factor graph can be derived in Gaussian forms,which enables the terminals to transmit means and covariances.Finally,the impact of major error sources on the navigation performance are evaluated by Monte Carlo simulations,e.g.,range measurement noise,priors of position uncertainty and velocity noise.Results show that the proposed algorithm outperforms the extended Kalman filter and cooperative extended Kalman filter in both static and mobile scenarios of the JTIDS.

Graph reasoning over explicit semantic relation

Multi-hop reasoning over language or graphs represents a significant challenge in contemporary research,particularly with the reliance on deep neural networks.These networks are integral to text reasoning processes,yet they present challenges in extracting and representing domain or commonsense knowledge,and they often lack robust logical reasoning capabilities.To address these issues,we introduce an innovative text reasoning framework.This framework is grounded in the use of a semantic relation graph and a graph neural network,designed to enhance the model’s ability to encapsulate knowledge and facilitate complex multi-hop reasoning.Our framework operates by extracting knowledge from a broad range of texts.It constructs a semantic relationship graph based on the logical relationships inherent in the reasoning process.Beginning with the core question,the framework methodically deduces key knowledge,using it as a guide to iteratively establish a complete evidence chain,thereby determining the final answer.Leveraging the advanced reasoning capabilities of the graph neural network,this approach is adept at multi-hop logical reasoning.It demonstrates strong performance in tasks like machine reading comprehension and question answering,while also clearly delineating the path of logical reasoning.

Multi-Robot Cooperative Localization:Time-Varying Unobservable Subspace Analysis and Consistent Algorithm Design

This paper investigates the problem of cooperative localization(CL)for a multi-robot system(MRS)under dynamic measurement topology,which involves a group of robots collectively estimating their poses with respect to a common reference frame using ego-motion measurements and robot-to-robot relative measurements.The authors provide a theoretical analysis of the time-varying unobservable subspace and propose a consistent cooperative localization algorithm.First,the authors introduce the relative measurement graph(RMG)to represent the relative pose measurements obtained by the MRS at each instant.Then,the authors derive the local observability matrix over a time interval.An equivalent relationship is established between the local observability matrix and the spectral matrices of the RMG.Moreover,the authors present a method for constructing the unobservable subspace based on the RMG under different topology conditions.Based on this analysis,the authors design a consistent cooperative localization algorithm that satisfies the constraints of the time-varying unobservable subspace.An analytical optimal solution is derived for the constrained optimization problem.Monte Carlo numerical simulations are conducted to demonstrate the consistency and accuracy of the proposed method.

Reduced Methane Combustion Mechanism and Verification,Validation,and Accreditation(VV&A)in CFD for NO Emission Prediction

In order to obtain a reduced methane combustion mechanism for predicting combustion field and pollutants accurately in CFD simulations with a lower computational cost,a reduced mechanism with 22 species and 65 steps of reactions from GRI-Mech 3.0 was obtained by direct relation graph method and sensitivity analysis.The ideal reactor calculation and VV&A(Verification,Validation,and Accreditation)in CFD were carried out using the proposed mechanism.The results showed that the proposed mechanism agrees well with the detailed mechanism in a wide range of operating conditions;the temperature field and species can be predicted accurately in CFD simulations(RANS and LES models),and the NO prediction error of an industrial gas turbine combustor outlet is less than 2×10-6.The proposed mechanism has high engineering values.

A Class of Association Schemes and Their Automorphisms

In this paper,we construct a class of association schemes by using pairs of subspaces of vector spaces and determine their full automorphism groups.