A (Sub)graph Isomorphism Identification Theorem

It is generally accepted that graphs are natural representations of the relationships between items in complex systems, such as social networks, chemical compounds, and biological structures. Subgraph isomorphism is a generalisation of the graph isomorphism issue. Graph isomorphism is used to determine if the structures of two graphs are identical, while subgraph isomorphism is an extension of the graph isomorphism problem. A subgraph isomorphism query is an essential technique for discovering geometrical patterns in bigger networks. Given a query network Q (also known as a pattern graph) and a data graph G, this query returns all mappings of nodes in Q to nodes in G that preserve their corresponding edges. Answering subgraph isomorphism queries is important for analysing epidemic transmission patterns in social networks, querying protein interactions in protein networks, etc. Due to the NP-Hard nature of the subgraph isomorphism search issue, several methods have been developed to accelerate the search. All of these techniques are based on the similarity of nodes and subgraphs. Existing enumeration and indexing related subgraph isomorphism methods exploit different representation orders to search potential objects, as well as pruning rules to exclude unprofitable paths, and the use of auxiliary information to eliminate false candidates to speed up the progress. They cannot process matching problems with both large target and query graphs. Therefore, subgraph querying is a knotty problem pressing for a solution. As such, the design objective of our subgraph topological detection technique may result in an appreciable improvement in subgraph detection performance by combining the search space and search time. Exact graph matching produces a binary result when comparing two graphs since they are either identical (match) or dissimilar (mismatch). By assessing the degree of similarity or dissimilarity between the two graphs, inexact graph matching algorithms provide a gradual matching result. Graph distance is also named approximate graph isomorphism, error-tolerant graph matching, it is a measure of similarity (or dissimilarity) between two graphs. The graph distance function is an elusive question remaining a pressing problem in a wide range of fields. In general, graphs are usually enriched with node and edge attributes, namely, heterogeneous graphs, our focus is encapsulating node and edge identities in a graph. Structural and semantic features are both preserved by graphs, so the analysis of row sum and eigenspectra for vertex and edge adjacency matrix has captured the affinity interactions within graphs locally and globally. Therefore, we estimate the geometrical and semantic dissimilarities/distances between graphs extensively and systemically. Several illustrative chemical compound cases implement in practical scenarios, thus, the theory could be easily understood. Our method defines a synopsis quantitative distance (or dissimilarity) measure for approximate matching, it has a good measure of expressiveness and a suited polynomial computation complexity, which paves the way for graph analysis. In this work, our (sub)graph/approximate isomorphism-based method adopts a 3-stage framework for learning and refining structural correspondences. First, an adequate representation of the graph-adjacency matrix can capture the connectivity of the graph structure. Secondly, we employ the permutation theorem to evaluate the row sum of vertex and edge adjacency matrices of two graphs. Lastly, our proposed scheme deploys the well-found equinumerosity theorem to verify the relationship between two graphs. The (sub)graph and approximate graph matching models provide a solid theoretical foundation for practical applications and effective querying. In this thesis, We close this gap by studying the problem via the permutation and equinumerosity theorems, which demonstrates the effectiveness of our method, which can be solved in polynomial time.