Approximate subgraph matching based on Chi-squares statistics

XU Zhou-bo; HUANG Wen-wen; LIU Hua-dong; YANG Jian

Chinese

您当前的位置：

首页 >

文章列表页 >

Approximate subgraph matching based on Chi-squares statistics

更新时间：2026-09-04

- Approximate subgraph matching based on Chi-squares statistics
- Vol. 37, Issue 11, Pages: 17-23(2020)
- 作者机构：
  
  1. 桂林电子科技大学广西可信软件重点实验室机构,广西,桂林,541004
  2. 桂林电子科技大学机构机电工程学院,广西,桂林,541004
- 作者简介：
- 基金信息：
- DOI：
  CLC：
- Published：2020
- 稿件说明：
移动端阅览
徐周波, 黄文文, 刘华东, 杨健. 基于卡方统计的近似子图匹配[J]. 微电子学与计算机, 2020, 37(11): 17-23.

XU Zhou-bo, HUANG Wen-wen, LIU Hua-dong, et al. Approximate subgraph matching based on Chi-squares statistics[J]. 2020, 37(11): 17-23.
徐周波, 黄文文, 刘华东, 杨健. 基于卡方统计的近似子图匹配[J]. 微电子学与计算机, 2020, 37(11): 17-23. DOI：

XU Zhou-bo, HUANG Wen-wen, LIU Hua-dong, et al. Approximate subgraph matching based on Chi-squares statistics[J]. 2020, 37(11): 17-23. DOI：

摘要

图查询的应用越来越广泛，其中近似子图匹配是核心技术之一.但是大规模图数据中噪音的存在对近似子图匹配精确度影响较大，为进一步提高近似子图匹配算法的鲁棒性和实时性，提出一种基于卡方统计的近似子图匹配改进算法.在算法预处理阶段，利用统一邻居随机游走距离和高斯影响函数将目标图划分，使得划分后的子图在拓扑结构和标签属性之间达到最佳平衡.在算法匹配阶段，使用卡方统计量捕获的统计显著性来表征近似子图匹配结构相似度，再结合权重系数α调整结构相似度和标签相似度所占比重，其中统计显著性模型能够充分考虑背景结构和顶点邻域中的标签分布，有效处理部分标签和结构失配，从而得到最佳匹配子图.真实数据集中的实验结果表明，该算法效果较好，运算效率较高，可以应用于Top-k近似子图匹配.

Abstract

Graph query is more and more widely used

and approximate subgraph matching is one of the core technologies. However

the existence of noise in large-scale graph data has a great impact on the accuracy of approximate subgraph matching. In order to further improve the robustness and real-time performance of approximate subgraph matching algorithm

an improved algorithm of approximate subgraph matching based on Chi-square statistics is proposed. In the preprocessing stage

the target graph is partitioned by using the Unified Neighborhood Random Walk Distance and Gaussian Influence Function

so that the partitioned subgraph can achieve the best balance between the topological structure and label attributes.In the algorithm matching stage

the statistical significance captured by Chi-square statistics is used to characterize the subgraph similarity of approximate subgraph matching

and then the proportion of structural similarity and label similarity is adjusted by combining the weight coefficient α. The statistical significance model can takes into account the background structure and label distribution in the neighborhood of vertices

and effectively handles partial label and structural mismatches

so as to get the best matching subgraph. The experimental results in real dataset show that the algorithm is effective and efficient

and can be applied to Top-k approximate subgraph matching.

关键词

Keywords

references

TIANYY, PATELJM. TALE: atoolforapproximatelargegraphmatching[C]//Proceedings of the 2008 IEEE 24th International Conference on Data Engineering. Cancun, Mexico: IEEE, 2008: 963-972.

ARORA A, SACHAN M, BHATTACHARYA A. Miningstatis-tically significant connectedsubgraph sinvertexlabeled-graphs[C]//Proceedings of 2014 ACM SIGMOD International Conference on Management of Data. Snowbird: ACM, 2014: 1003-1014.

GLOVER F. Tabusearch-PartI[J]. ORSA Journal on Computing, 1989, 1(3): 135-206. DOI: 135

KHAN A, LI N, YANX F, et al. Neighborhoodbased-fastgraphsearchinlargenetworks[C]//Proceedings of 2011 ACMSIGMO DInternational Conferenceon Management of Data. Athens, ACM, 2011: 901-912.

DUTTA S, NAYEK P, BHATTACHARYA A. Neighbor aware search for approximate labeled graphmatching using the chisquarestatistics[C]//Proceedings of the 26th International Conference on WorldWideWeb.Perth: ACM, 2017: 1281-1290.

SUCHANEK F M, KASNECI G, WEIKUM G. Yago: aco-reofsemantic knowledge[C]//Proceedings of the 16th International Conference on World Wide Web. Banff: ACM, 2007: 679-706.

America READT R C, CRESSIE A C. Goodess of fitstatistics for discrete multivariate data[M]. America: Springer, 1989: 4617-4578. DOI: 4617

ZHU L H, NGW K, CHENG J. Structureandattributeindexfo-rapproximategraphmatchinginlargegraphs[J]. Information-Systems, 2011, 36(6): 958-972. DOI: 958

DUTTA S, BHATTACHARY A A. Most significantsubstringmining based on chisquaremeasure[C]//Proceedings of 14th Pacific-Asia Conference Knowledge Discovery and Data Mining.Hyderabad: Springer, 2010: 21-24.

CHENG H, ZHOU Y, YU J X. Clusteringlargeattributedgraphs: a balance between structural and attribute similarities[J]. ACM Transactionson Knowledge Discovery from Data, 2015: 5(2): 12. DOI: 12

ELMSALLATI A, CLARK C, KALITA J. Globalalignmentof-protein-proteininteractionnetworks: asurvey[J]. IEEE/ACMTransactionsonComputationalBiologyandBioinformatics, 2016, 13(4): 689-705. DOI: 689

KPODJEDO S, GALINIER P, ANTONIOL G. Using loca lsimilarity measures to efficiently address approximate graph matching[J]. Discrete Applied Mathematics, 2014(164): 161-177. DOI: 161

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Lightweight countermeasures against Spectre attacks on the branch prediction unit

Implementation and verification of a dual-chain power gating strategy for low power design

Steganography model guided by attention mechanism and improved dense convolution

A feature-oriented context understanding and slice analysis network for tuberculosis detection

Research on assembly action recognition based on MSS-YOLO-MPHands fusion architecture

Related Author

No data

Related Institution

No data

AI问答

Postal code：100079
Tel：（010）53879206 Email：tmw@bjxintong.com.cn
Technical support is provided by Beijing Founder electronics co., LTD 京ICP备09082226号-64 京公网安备11010602201714号
It is recommended to read the content of this site in Chrome&IE9+. Please switch to extreme mode in browser 360.
Cookies We use cookies to help provide and enhance our service and tailor content. By continuing, you agree to the use of cookies.

⁰