Computer Science ›› 2025, Vol. 52 ›› Issue (4): 147-160.doi: 10.11896/jsjkx.240100084

• Database & Big Data & Data Science • Previous Articles     Next Articles

Knowledge Extraction Algorithm Based on Hypergraphs

LIU Chuan1, DU Baocang2, MAO Hua1   

  1. 1 College of Mathematics and Information Science,Hebei University,Baoding,Hebei 071002,China
    2 College of Management,Hebei Finance University,Baoding,Hebei 071051,China
  • Received:2024-01-08 Revised:2024-07-12 Online:2025-04-15 Published:2025-04-14
  • About author:LIU Chuan,born in 1997,master candidate.His main research interests include hypergraph and formal concept analysis.
    MAO Hua,born in 1963,Ph.D,professor.Her main research interests include rough sets,formal concept analysis and hypergraph.
  • Supported by:
    National Natural Science Foundation of China(61572011).

Abstract: Knowledge extraction has always been one of the topics in computer science research.However,some existing know-ledge extraction methods are not sufficient to meet the practical needs in terms of visualization and latent knowledge extraction.It is well known that knowledge consists of definable knowledge and latent knowledge,and definable knowledge can be obtained while the latent knowledge is extracted,but not vice versa.Regarding the extraction of definable knowledge,many achievements have been made,but relatively less attention has been paid to the extraction of latent knowledge,especially how to extract latent knowledge through visualization methods,which is an urgent problem to be solved.Therefore,utilizing the visualization characte-ristics of hypergraphs in the context of information systems,this paper explores the correspondence between information systems and hypergraphs,and proposes methods for their mutual conversion.Using this method,combined with hypergraph theory and rough set theory,a pair of hypergraph-based upper and lower approximation operator is defined.Furthermore,the concept of approximate hypergraphs is proposed,and its properties are explored.The construction of approximate hypergraphs is completed,and an effective method for knowledge extraction under the hypergraph framework is implemented.By comparing with classical and recently proposed approximation theories and knowledge extraction methods,the advantages of the proposed method in terms of approximation and knowledge extraction are demonstrated.For the proposed method,its correctness is verified through practical examples,so that its applicability is indicated.The proposed method is a development and supplement to existing knowledge extraction theories.

Key words: Knowledge extraction, Information system, Hypergraph, Approximate hypergraph, Visualization methods

CLC Number: 

  • TP391
[1]PAWLAK Z.RoughSets:Theoretical Aspects of Reasoningabout Data[M].Dordrecht:Kluwer Academic Publishers,1991.
[2]PAWLAK Z.Rough Sets[J].International Journal of Computer &Information Sciences,1982,11:341-356.
[3]MAO H,WANG S Y,LIU C,et al.Hypergraph-Based Attribute Reduction of Formal Contexts in Rough Sets[J].Expert Systems with Applications,2023,234:121062.
[4]YAO Y Y,YANG J.Granular Fuzzy Sets and Three-way Approx-imations of Fuzzy Sets[J].International Journal of Appro-ximate Reasoning,2023,161:109003.
[5]JARADEH M Y,SINGH K,STOCKER M,et al.Information Extraction Pipelines for Knowledge Graphs[J].Knowledge and Information Systems,2023,65(5):1989-2016.
[6]BRETTO A.Hypergraph Theory:an Introduction[M].Cham:Springer,2013.
[7]VINAS R,JOSHI C K,GEORGIEV D,et al.Hypergraph Factorization for Multi-tissue Gene Expression Imputation[J].Nature Machine Intelligence,2023,5(7):739-753.
[8]PRAJNANASWAROOPA S,GEETHA J,SOMASUNDARAM K.Total Chromatic Number for Some Classes of Cayley Graphs[J].Soft Computing,2023:1-9.
[9]DALCENGIO S,LECOMTE V,POLETTINI M.Geometry of Nonequilibrium Reaction Networks[J].Physical Review X,2023,13(2):021040.
[10]BERGE C.Graphs and Hypergraphs[M].English translation,Amsterdam:North-Holland Publishing Company,1973.
[11]CHVATAL V.Hypergraphs and Ramseyian Theorems[J].Proceedings of the American Mathematical Society,1971,27(3):434-440.
[12]LOVASZ L.Normal Hypergraphs and The Perfect Graph Conjecture[J].Discrete Mathematics,1972,2(3):253-267.
[13]ERDOS P,LOVASZ L.Problems and Results on 3-ChromaticHypergraphs and Some Related Questions[J].Infinite and Finite Sets,1975,10(2):609-627.
[14]OWRANG O M M,MILLER L L.Query Translation in a He-terogeneous Distributed Database Based on Hypergraph Models[C]//Proceedings of the 1986 ACM Fourteenth Annual Confe-rence on Computer Science.New York:Association for Computing Machinery,1986:412.
[15]GOLDSTEIN A J.Database Systems:A Directed HypergraphDatabase:A Model for The Local Loop Telephone Plant[J].Bell System Technical Journal,1982,61(9):2529-2554.
[16]SACCA D.Closures of Database Hypergraphs[J].Journal of the ACM,1985,32(4):774-803.
[17]LANDE D,FU M,GUO W,et al.Link Prediction of Scientific Collaboration Networks Based on Information Retrieval[J].World Wide Web,2020,23:2239-2257.
[18]ZHANG F,YUAN N J,LIAN D,et al.Collaborative Knowledge Base Embedding for Recommender Systems[C]//Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York:Association for Computing Machinery,2016:353-362.
[19]JI S,FENG Y,JI R,et al.Dual Channel Hypergraph Collaborative Filtering[C]//Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery &Data Mining.New York:Association for Computing Machinery,2020:2020-2029.
[20]YANG B,MITCHELL T.Leveraging Knowledge Bases in LSTMs for Improving Machine Reading[C]//Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics(Volume 1:Long Papers).Vancouver:Association for Computational Linguistics,2017:1436-1446.
[21]RITAL S,CHERIFI H,MIGUET S.Weighted Adaptive Neighborhood Hypergraph Partitioning for Image Segmentation[C]//Pattern Recognition and Image Analysis:Third International Conference on Advances in Pattern Recognition(ICAPR 2005).Berlin Heidelberg:Springer,2005:522-531.
[22]TAN S L,GUAN Z Y,CAI D,et al.Mapping Users AcrossNetworks by Manifold Alignment on Hypergraph[C]//Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence.California:AAAI Press,2014:159-165.
[23]ZHOU H Y,ZHANG D Q.Multi-site Hypergraph Convolu-tional Neural Networks and Application[J].Computer Science,2022,49(3):129-133.
[24]CUI B J,ZHANG Y P,WANG B.Multimodal Data Fusion Algorithm Based on Hypergraph Regularization[J].Computer Science,2023,50(6):167-174.
[25]LIU C,REN G D.Phylogenetic Analysis of Genera of the Tribe Blaptini Based on The Characteristics of Defensive Glands(Coleoptera:Tenebrionidae)[J].Acta Entomologica Sinica,2012,55(10):1205-1220.
[26]GRATZER G.Lattice Theory:First Concepts and DistributiveLattices[M].New York:Dover Publications,2009.
[27]LIANG J Y,QU K S,XU Z B.Reduction of Attribute in Information Systems[J].Systems Engineering-Theory & Practice,2001,21(12):76-80.
[28]GONG X,HIGHAM D J,ZYGALAKIS K.Generative Hypergraph Models and Spectral Embedding[J].Scientific Reports,2023,13(1):540.
[29]YOU L,JIANG H,HU J,et al.GPU-accelerated Faster Mean Shift with Euclidean Distance Metrics[C]//2022 IEEE 46th Annual Computers,Software,and Applications Conference(COMPSAC).Los Alamitos:IEEE,2022:211-216.
[30]ZHAO L.A Theory of Spatial Granular Computing[D].Regina:University of Regina,2023.
[31]GAO Y,FENG Y,JI S,et al.HGNN+:General Hypergraph Neural Networks[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2022,45(3):3181-3199.
[32]HUANG J,HUANG X,YANG J.Residual Enhanced Multi-Hypergraph Neural Network[C]//2021 IEEE International Conference on Image Processing(ICIP).Anchorage:IEEE,2021:3657-3661.
[33]CHEN L H.Research on Modeling and Representation of He-terogeneous Hypergraphs for Academic Recommendations [D].Jilin:Jilin University,2023.
[34]VELDT N.Optimal LP Rounding and Linear-Time Approximation Algorithms for Clustering Edge-Colored Hypergraphs[C]//Proceedings of the 40th International Conference on Machine Learning.New York:PMLR,2023:34924-34951.
[35]ZHAO X,YU Y,ZHOU G,et al.Fast Hypergraph Regularized Nonnegative Tensor Ring Decomposition Based on Low-rank Approximation[J].Applied Intelligence,2022,52(15):17684-17707.
[36]YAO Y Y.Three-way Decision:an Interpretation of Rules inRough Set Theory[C]//Rough Sets and Knowledge Technology:4th International Conference,RSKT 2009,Gold Coast,Australia,July 14-16,2009.Proceedings 4.Berlin Heidelberg:Springer,2009:642-649.
[1] HUANG Qian, SU Xinkai, LI Chang, WU Yirui. Hypergraph Convolutional Network with Multi-perspective Topology Refinement forSkeleton-based Action Recognition [J]. Computer Science, 2025, 52(5): 220-226.
[2] YAO Chang, HAO Yanni, PENG Shenghui, NIU Zhiang, XIE Yong, ZHAO Shizhen. Prospects for the Development of Information System Architecture--Taking the National Natural Science Foundation’s Information Systemfor Example [J]. Computer Science, 2025, 52(4): 14-20.
[3] GU Zhaojun, YANG Wen, SUI He, LI Zhiping. Threat Assessment of Air Traffic Control Information System Based on Knowledge Graph [J]. Computer Science, 2024, 51(11A): 240200052-11.
[4] YANG Dongsheng, WANG Guiling, ZHENG Xin. Hierarchical Hypergraph-based Attention Neural Network for Service Recommendation [J]. Computer Science, 2024, 51(11): 103-111.
[5] XIA Xiaoya, ZHAO Shengyu, HAN Fanyu, BI Fenglin, WANG Wei, ZHOU Xuan, ZHOU Aoying. Data Mining and Information Service for Open Collaboration Digital Ecosystem [J]. Computer Science, 2024, 51(10): 187-195.
[6] YANG Ye, WU Weizhi, ZHANG Jiaru. Optimal Scale Selection and Rule Acquisition in Inconsistent Generalized Decision Multi-scale Ordered Information Systems [J]. Computer Science, 2023, 50(6): 131-141.
[7] DING Hongxin, ZOU Peinie, ZHAO Junfeng, WANG Yasha. Active Learning-based Text Entity and Relation Joint Extraction Method [J]. Computer Science, 2023, 50(10): 126-134.
[8] FANG Lian-hua, LIN Yu-mei, WU Wei-zhi. Optimal Scale Selection in Random Multi-scale Ordered Decision Systems [J]. Computer Science, 2022, 49(6): 172-179.
[9] XUE Zhan-ao, HOU Hao-dong, SUN Bing-xin, YAO Shou-qian. Label-based Approach for Dynamic Updating Approximations in Incomplete Fuzzy Probabilistic Rough Sets over Two Universes [J]. Computer Science, 2022, 49(3): 255-262.
[10] WANG Zhi-qiang, ZHENG Ting-ting, SUN Xin, LI Qing. Attribute Reduction Algorithm Based on a New q-rung orthopair Fuzzy Cross Entropy [J]. Computer Science, 2022, 49(11A): 211200142-6.
[11] WEN Xin, YAN Xin-yi, CHEN Ze-hua. Minimal Optimistic Concept Generation Algorithm Based on Equivalent Relations [J]. Computer Science, 2021, 48(3): 163-167.
[12] HANG Ting-ting, FENG Jun, LU Jia-min. Knowledge Graph Construction Techniques:Taxonomy,Survey and Future Directions [J]. Computer Science, 2021, 48(2): 175-189.
[13] YU Shi-yuan, GUO Shu-ming, HUANG Rui-yang, ZHANG Jian-peng, SU Ke. Overview of Nested Named Entity Recognition [J]. Computer Science, 2021, 48(11A): 1-10.
[14] XUE Zhan-ao, ZHANG Min, ZHAO Li-ping, LI Yong-xiang. Variable Three-way Decision Model of Multi-granulation Decision Rough Sets Under Set-pair Dominance Relation [J]. Computer Science, 2021, 48(1): 157-166.
[15] LI Xiang-li, JIA Meng-xue. Nonnegative Matrix Factorization Algorithm with Hypergraph Based on Per-treatments [J]. Computer Science, 2020, 47(7): 71-77.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!