Measuring Semantic-Based Structural Similarity in Multi-Relational Networks

Introduction

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: