Definitions

Mathematical foundations of graphs are rooted in the classical graph theory. Attributed graphs with an unrestricted label alphabet are the most general way to define graphs.

 

Definition 1: Graph

 

An undirected, labeled graph G is defined as a quintuple (V,E, λ, m), where V(G) is the set of nodes, E(G) ⊆ (V×V) is the set of edges and λ: V → L_v(G ) and m: E → L_e(G ) are the labeling functions for nodes and edges respectively, given the alphabets of nodes and edges, L_v(G) and L_e(G). Further, two nodes u ∈V and v ∈V, connected by an edge e, is denoted as e = (u,v), if  (u,v) ∈ E. For undirected graphs, (u,v) = (v,u).

 

Definition 2: Subgraph

 

A subgraph G_s of G, denoted by G_s⊆G, is a graph G_s = (V_s,E_s, λ_s, m_s), where V_s⊆ V, E_s⊆ E, λ_s (v) = λ (v) ∀v ∈ V and m_s (u,v) = m (u,v) ∀(u,v) ∈ E .

 

Definition 3: Subgraph Isomorphism

 

The subgraph G_s is said to be subgraph isomorphic to G, if there exists a bijective mapping  f : V_s→V such that, ∀u ∈V_s, λ_s(u) = λ(f (u)) and, ∀e_s=(u,v) ∈E_s there exist an edge e = (f (u), f (v)) ∈E such that m_s(e_s)= m(e).

 

Definition 4: Occurrence of subgraph

 

A subgraph G_s  occurs in G, if G_s is subgraph isomorphic to G, i.e. G_s⊆G.

 

Definition 5: frequent subgraph

 

Let the graph database D contain a collection of graphs G, then, the support of a subgraph G_s in D is the number of graphs G ∈ D that has a subgraph isomorphism relation with G_s. If the support exceeds a pre-defined value , G_s  is a frequent subgraph in D.