AGM算法

令 G ( V , E , L V , L E , φ ) G(V,E,L_V,L_E,\varphi) G(V,E,LV​,LE​,φ)表示一個帶标簽的圖，其中 V V V和 E E E分别表示頂點集和邊集， L V L_V LV​和 L E L_E LE​分别表示頂點和邊的标簽集， φ \varphi φ是一個标簽函數定義了 V → L V V \to L_V V→LV​和 E → L E E \to L_E E→LE​的映射。

FSM算法根據操作的資料不同，可以分為針對圖資料庫的和針對一個大圖的（現在隻讨論exact match方法）。

根據每個頂點标簽的id對頂點進行排序，然後根據該順序生成鄰接矩陣 X k X_k Xk​， k k k表示頂點個數。鄰接矩陣中每個元素表示該邊标簽的id。

對于

X k = ( x 1 , 1 x 1 , 2 x 1 , 3 ⋯ x 1 , k x 2 , 1 x 2 , 2 x 2 , 3 ⋯ x 2 , k x 3 , 1 x 3 , 2 x 3 , 3 ⋯ x 3 , k ⋮ ⋮ ⋮ ⋱ ⋮ x k , 1 x k , 2 x k , 3 ⋯ x k , k ) X_k=\begin{pmatrix} x_{1,1} & x_{1,2} & x_{1,3} &\cdots &x_{1,k}\\ x_{2,1} & x_{2,2} & x_{2,3} & \cdots &x_{2,k}\\ x_{3,1} & x_{3,2} & x_{3,3} & \cdots &x_{3,k}\\ \vdots & \vdots & \vdots &\ddots &\vdots \\ x_{k,1} & x_{k,2} & x_{k,3} & \cdots &x_{k,k}\\ \end{pmatrix} Xk​=⎝⎜⎜⎜⎜⎜⎛​x1,1​x2,1​x3,1​⋮xk,1​​x1,2​x2,2​x3,2​⋮xk,2​​x1,3​x2,3​x3,3​⋮xk,3​​⋯⋯⋯⋱⋯​x1,k​x2,k​x3,k​⋮xk,k​​⎠⎟⎟⎟⎟⎟⎞​

如果是無向圖，則 c o d e ( X k ) = x 1 , 1 x 1 , 2 x 2 , 2 x 1 , 3 x 2 , 3 x 3 , 3 x 1 , 4 ⋯ x k − 1 , k x k , k code(X_k)=x_{1,1}x_{1,2}x_{2,2}x_{1,3}x_{2,3}x_{3,3}x_{1,4}\cdots x_{k-1,k}x_{k,k} code(Xk​)=x1,1​x1,2​x2,2​x1,3​x2,3​x3,3​x1,4​⋯xk−1,k​xk,k​

如果是有向圖，則 c o d e ( X k ) = x 1 , 1 x 1 , 2 x 2 , 1 x 2 , 2 x 1 , 3 x 3 , 1 x 2 , 3 x 3 , 2 ⋯ x k − 1 , k x k , k − 1 x k , k code(X_k)=x_{1,1}x_{1,2}x_{2,1}x_{2,2}x_{1,3}x_{3,1}x_{2,3}x_{3,2}\cdots x_{k-1,k}x_{k,k-1}x_{k,k} code(Xk​)=x1,1​x1,2​x2,1​x2,2​x1,3​x3,1​x2,3​x3,2​⋯xk−1,k​xk,k−1​xk,k​。

對于一個子圖 G s G_s Gs​，定義它的支援度 s u p ( G s ) sup(G_s) sup(Gs​)為資料庫中包含該子圖的圖的個數與總數的比值。

如果兩個鄰接矩陣 X k X_k Xk​， Y k Y_k Yk​除了第 k k k行和第 k k k列不同外，其餘元素均相同，則将兩個矩陣合并生成 Z k + 1 Z_{k+1} Zk+1​。如下所示：

X k = ( X k − 1 x 1 x 2 T x k k ) X_k = \begin{pmatrix} X_{k-1} & \boldsymbol {x_1}\\ \boldsymbol {x^T_2} & x_{kk}\\ \end{pmatrix} Xk​=(Xk−1​x2T​​x1​xkk​​)， Y k = ( Y k − 1 y 1 y 2 T y k k ) Y_k = \begin{pmatrix} Y_{k-1} & \boldsymbol {y_1}\\ \boldsymbol {y^T_2} & y_{kk}\\ \end{pmatrix} Yk​=(Yk−1​y2T​​y1​ykk​​)

Z k + 1 = ( X k − 1 x 1 y 1 x 2 T x k k z k , k + 1 y 2 T z k + 1 , k y k k ) Z_{k+1} = \begin{pmatrix} X_{k-1} & \boldsymbol {x_1} & \boldsymbol {y_1}\\ \boldsymbol {x^T_2} & x_{kk}& z_{k,k+1}\\ \boldsymbol {y^T_2} &z_{k+1,k}& y_{kk}\\ \end{pmatrix} Zk+1​=⎝⎛​Xk−1​x2T​y2T​​x1​xkk​zk+1,k​​y1​zk,k+1​ykk​​⎠⎞​，也可寫成

其中，新矩陣中的元素滿足下列關系：

如果是無向圖，那麼 z k + 1 , k z_{k+1,k} zk+1,k​和 z k , k + 1 z_{k,k+1} zk,k+1​相同。該合并操作可以産生多個 Z k + 1 Z_{k+1} Zk+1​矩陣，這是因為 v k v_k vk​和 v k + 1 v_{k+1} vk+1​的構成的邊的label可以有多種選擇，因為圖資料庫中不同的圖中這兩個點之間的邊的不同，也就造成了該邊的label的不同，是以 z k + 1 , k z_{k+1,k} zk+1,k​和 z k , k + 1 z_{k,k+1} zk,k+1​有多個選擇，還有一種選擇是沒有邊，既0。

當 X k X_k Xk​和 Y k Y_k Yk​中的 v k v_k vk​的label相同時，交換 X k X_k Xk​和 Y k Y_k Yk​後生成的矩陣是一樣的，為了避免這種情況，隻有當 c o d e ( t h e   f i r s t   m a t r i x ) < = c o d e ( t h e   s e c o n d   m a t r i x ) code(the\ first\ matrix)<=code(the\ second\ matrix) code(the first matrix)<=code(the second matrix)時才生成矩陣，生成的矩陣也被稱為normal form。隻有當大小為 k + 1 k+1 k+1的圖 G G G的所有 k k k子圖都是頻繁子圖時， G G G才是頻繁子圖候選項。

如果通過删除一個節點得到的子圖不是normal form，必須将其轉換成normal form之後才能判斷該子圖是否已經生成過。通過以下步驟，可以将一個non-normal form 的矩陣 X k X_k Xk​轉換成normal form的矩陣 X k ′ X'_k Xk′​：（1）對 X k X_k Xk​中的每個節點生成一個 1 × 1 1 \times 1 1×1的鄰接矩陣；（2）對于點 v i , v j ∈ G ( X k ) v_i,v_j \in G(X_k) vi​,vj​∈G(Xk​)，如果其鄰接矩陣符合合并條件，則合并；（3）不斷地合并新生成的矩陣，知道獲得了一個 k × k k \times k k×k的矩陣 X k ′ X'_k Xk′​。該過程涉及到的是行列式的操作，是以可以表示成 X k ′ = ( T k ) T X k T k X'_k=(T_k)^T X_k T_k Xk′​=(Tk​)TXk​Tk​。

當所有候選子圖生成後，需要統計每個子圖的支援度。但是每個圖的normal form并不是唯一的。是以需要将代表同一個子圖的不同的normal form的支援度加在一起。為了索引代表同一個子圖的不同normal form，定義了normal form的canonical form。定義 G G G的canonical form是 G G G的normal form中 c o d e code code最小的。令 X k − 1 m X^m_{k-1} Xk−1m​表示 G ( X k ) G(X_k) G(Xk​)移除點 v m v_m vm​後得到的圖。 X k − 1 ′ m X^{'m}_{k-1} Xk−1′m​表示 X k − 1 m X^m_{k-1} Xk−1m​經過 T k − 1 m T^m_{k-1} Tk−1m​變換後得到的normal form。 X k − 1 ′ m X^{'m}_{k-1} Xk−1′m​經過 S k − 1 m S^m_{k-1} Sk−1m​變換後得到canonical form。整體過程可表示為 ( T k − 1 m S k − 1 m ) T X k − 1 m T k − 1 m S k − 1 m (T^m_{k-1}S^m_{k-1})^TX^m_{k-1}T^m_{k-1}S^m_{k-1} (Tk−1m​Sk−1m​)TXk−1m​Tk−1m​Sk−1m​。

那麼我們可以用 S k m S^m_k Skm​和 T k m T^m_k Tkm​将 X k X_k Xk​轉換成canonical form X c k X_{ck} Xck​。而 S k m S^m_k Skm​和 T k m T^m_k Tkm​又可以通過 S k − 1 m S^m_{k-1} Sk−1m​和 T k − 1 m T^m_{k-1} Tk−1m​獲得。具體過程如下所示：

尋找頻繁子圖時，對資料庫中的每個圖從1到k的構造子圖，并計算每個子圖的支援度。