Viet-Anh on Software Logo

What is: Canonical Partition?

SourceDeSCo: Towards Generalizable and Scalable Deep Subgraph Counting
Year2000
Data SourceCC BY-SA - https://paperswithcode.com

\emph{Canonical partition} P\mathcal{P} crops the index-restricted d-hop neighborhood around the center node from the target graph. D(Gt,vi,vc)\mathcal{D}(G_t,v_i,v_c) means the shortest distance between viv_i and vcv_c on GtG_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 GcG_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 P\mathcal{P}, given any dd 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}