Measuring Semantic-Based Structural Similarity in Multi-Relational Networks

Measuring Semantic-Based Structural Similarity in Multi-Relational Networks

Yunchuan Sun (Beijing Normal University, Beijing, China), Rongfang Bie (Beijing Normal University, Beijing, China) and Junsheng Zhang (IT Support Center, Institute of Scientific and Technical Information of China, Beijing, China)
Copyright: © 2016 |Pages: 14
DOI: 10.4018/IJDWM.2016010102
OnDemand PDF Download:
No Current Special Offers


Measuring graph similarity is a primary issue for graph-related applications. Many works have been proposed on simple topology-based structural similarity measuring for networks. It is not enough for semantic-rich networks like semantic networks, semantic link networks, and event-linked networks where semantic-based structural similarity measuring is more important than topology-based structure similarity measuring. In this paper, the authors introduce a semantic-based structural similarity for the first time and then propose an approach to measure the semantic-based structural similarity between networks with the computing theory for semantic relations as the foundation. A case study in semantic link network of the scientific research is also presented to show the feasibility of the proposed approach.
Article Preview


Graph similarity is a primary issue for graph-related applications. Many intelligent applications are related to graphs. For examples, transportation control needs to manipulate the road networks; computer-aided design (CAD) needs to organize the electronic components; pattern recognition such as face recognition needs to represent the complex objects; chemical and biological databases need to represent the complex molecules; objects in IoT formulate large-scaled graph, knowledge formulates knowledge graph, and so on. In these graph-related applications, complex objects and their relations could be represented as multi-relational networks, which are essentially graphs in the mathematical perspective.

With the rapid increase of various graph databases, especially in the big data age, it becomes more and more important to query the graph databases. Exact matching is too restrictive to find reasonable results, so approximate search becomes a vital operation for graph database query (Yan, Yu & Han, 2005). Furthermore, graph similarity measuring is the key technique for approximate searching.

Structural similarity measuring is essential for similarity computing between two graphical structures. Structure distance can be used to measure the similarity between structures and there are two categories, that is, feature-based distance and cost-based distance (Sanfeliu & Fu, 1983). For feature-based distance, a set of features is extracted from the structural representation, and these features are used as an n-dimensioned vector where the Euclidean distance can be applied. For cost-based distance, the distance between two objects measures the number of modifications required in order to transform the first object to the second. Tsai and Fu focused on exploiting error-correcting codes of attributed relational graphs to express similarities (Tsai & Fu, 1979; Tsai & Fu, 1983), in order to perform pattern analysis and syntactic pattern recognition. The concept of inexact graph matching has been also used and applied to structural pattern recognition (Bunke & Allermann, 1983). Sanfeliu and Fu (1983) defined a distance between attributed relational graphs (ARGs), based on a descriptive graph grammar. A recent discussion on discovering structural similarities can be found in (Djoko, Cook & Holder, 1997).

Many works focus on graph pattern matching, and subgraph isomorphism is most widely discussed (Lü& Zhou, 2011; Ullmann, 1976). Some recent work on the graph pattern matching such as tree pattern queries on graph-structured data usually opts to avoid queries with semantic information (Spiegel, Clausen, Albayrak& Kunegis, 2012).

To the best of our knowledge, most researches on subgraph isomorphism only concentrate on simple topology-based structure matching and similarity measuring (Ullmann, 1976). However, it is not enough for semantic–rich networks like semantic networks, semantic link networks, and event-linked networks where semantic-based structural similarity measuring is more important than topology-based structural similarity measuring. Semantic links or semantic relations are the main feature for such a semantic-rich network. Many efforts have been put into this area, and there are various models for representing multi-relational networks:

Complete Article List

Search this Journal:
Open Access Articles
Volume 18: 4 Issues (2022): Forthcoming, Available for Pre-Order
Volume 17: 4 Issues (2021): 2 Released, 2 Forthcoming
Volume 16: 4 Issues (2020)
Volume 15: 4 Issues (2019)
Volume 14: 4 Issues (2018)
Volume 13: 4 Issues (2017)
Volume 12: 4 Issues (2016)
Volume 11: 4 Issues (2015)
Volume 10: 4 Issues (2014)
Volume 9: 4 Issues (2013)
Volume 8: 4 Issues (2012)
Volume 7: 4 Issues (2011)
Volume 6: 4 Issues (2010)
Volume 5: 4 Issues (2009)
Volume 4: 4 Issues (2008)
Volume 3: 4 Issues (2007)
Volume 2: 4 Issues (2006)
Volume 1: 4 Issues (2005)
View Complete Journal Contents Listing