Canonical Partition

2000년 도입 · 논문 1편에서 사용

\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}

출처: DeSCo: Towards Generalizable and Scalable Deep Subgraph Counting

소개 논문: DeSCo: Towards Generalizable and Scalable Deep Subgraph Counting