Canonical Partition

\emph{Canonical partition} $\mathcal{P}$ crops the index-restricted d-hop neighborhood around the center node from the target graph. $\mathcal{D}(G_t,v_i,v_c)$ means the shortest distance between $v_i$ and $v_c$ on $G_t$. \begin{equation} \mathcal{P}(G_t, v_c, d) = G_c, \operatorname{ s.t. } G_c \subseteq G_t, V_c = { v_i \in V_t|\mathcal{D}(G_t,v_i,v_c) \leq d , v_i \leq v_c} \end{equation}

The graph $G_c$ obtained by canonical partition is called the \emph{canonical neighborhood}. Canonical neighborhoods can correctly substitute the target graph in canonical count. The subgraph count of query in target equals the summation of the canonical count of query in canonical neighborhoods for all target nodes. Canonical neighborhoods are acquired with canonical partition $\mathcal{P}$, given any $d$ greater than the diameter of the query. \begin{equation} \mathcal{C}(G_q,G_t) = \sum_{v_c \in V_t} \mathcal{C}c(G_q, \mathcal{P}(G_t, v_c, d),v_c), d \geq \max{v_i, v_j \in V_q} \mathcal{D}(G_q, v_i, v_j) \end{equation}