SPMiner

Definition

Subgraph pattern miner (SPMiner) is a model for identifying frequent subgraphs (network motifs) in a graph.

Architecture

The frequent subsampling counting problem consists of two stages: searching over all possible motifs, and counting the frequency of each motif in graph. SPMiner consists of two steps: Embedding candidate subgraphs, and motif search procedure.

Embedding candidate subgraphs

SPMiner decomposes the input Graph into many overlapping node-anchored neighborhoods around each node. Then encodes each subgraph into an order embedding space.

Motif Search Procedure

SPMiner then directly reasons in the embedding space to identify frequent motifs. It searches for a $k$-step walk in the embedding space that stays to the lower left of as many neighborhoods as possible. The walk is performed by iteratively adding nodes and edges to the current motif candidate, and tracking its embedding.

Given an order embedding encoder $\varphi$, let a Graph generation procedure be $\{G_0,G_1,\dots ,G_{k-1}\}$, where at any step $i$, $G_i$ is generated by adding $1$ node to $G_{i-1}$. Then the sequence of embeddings $\{\varphi (G_0),\varphi (G_1),\dots ,\varphi (G_{k-1})\}$ is a monotonic walk in the order embedding space. Finding the frequent motif is the same as finding a walk that $\underset{G_{k-1}}{\mathrm{argmax}}|\{G_v|\forall G_v\subset G_T,\varphi (G_{k-1})⪯\varphi (G_v)\}|$

SPMiner can quickly count the number of occurrences of a given motif by simply checking the number of neighborhoods that are embedded to the top-right of it in the embedding space