# StructSim: Meta-Structure-Based Similarity Measure in Heterogeneous Information Networks
## 3 The Proposed Method
### Subgraph Expansion with Bias  
In HINs, similarity measures based on the meta structure employ the subgraph expansion to model the complex semantic meanings between objects. The subgraph expansion strategy claims that the expansion probability is the same when expanding to a different node of the same type from the same layer of the meta structure in each step. In fact, the expansion probability may be different due to the difference between objects. Therefore, we propose a novel strategy of subgraph expansion with bias in this paper, which has an essential difference from current subgraph expansion. Based on the subgraph expansion with bias, we can easily calculate the subgraph expansion probability with bias. We firstly describe the process of subgraph expansion and then focus on the bias factor in subgraph expansion. Similar to random walk based on the meta path, the subgraph \begin{table}
\begin{tabular}{c c c c c} \hline \hline
**Category** & **Method** & **Model** & **Characteristic** & **Formula** \\ \hline \multirow{6}{*}{Meta-path-based} & PathSim [9] & PathCount & Peer objects similarity & \(\text{s}(\text{x},\text{y})=\frac{2\times|\{|\{\text{P}\}\cup\text{x}\rangle \geqslant\text{P}\}|\in\mathcal{P}\}|\)\(|\{|\{\text{P}\}\cup\text{y}\rangle\geqslant\text{P}\}|\) \\ \cline{2-5}  & PCRW [10] & RW & Query node proximity & \(\text{s}(\text{x},\text{y}|P)=\sum_{\text{P}\in\mathcal{P}}\text{RW}(\text{p})\) \\ \cline{2-5}  & HeteSim & \multirow{2}{*}{PRW} & Heterogeneous objects & \(s(\text{x},\text{y}\;|R_{1}\cdots R_{l})=\frac{1}{|\text{C}\cdot(x_{1}R_{1})| \prod_{j=1}^{l}|\sum_{j=1}^{l}|S(O\cdot(x_{1}|R_{1})|R_{2}\cdots R_{l-1})}\) \\  & & & & \(\frac{1}{|\text{C}\cdot(x_{1}R_{1})|\prod_{j=1}^{l}|\sum_{j=1}^{l}|S(O\cdot(x_{1} |R_{1})|R_{2}\cdots R_{l-1})}\) \\ \cline{2-5}  & HowSim [23] & PRW & Structure and & \(\text{S}_{\text{A}}=\left(\sum_{\text{R}\in\mathcal{B}\cap\text{A}}(\text{C} )\text{R}\right)\text{W}_{\text{S}}\text{E}_{\text{T}}\text{W}_{\text{R}}^{ \text{T}}\)\(\bigvee I\) \\ \cline{2-5}  & RelSim [25] & PathCount & Relation instances similarity & \(\text{s}(\text{<}\text{x},\text{y}\text{>},\text{<}\text{x}^{\prime},\text{y} \text{>})=\frac{2\times\sum_{\text{P}\in\text{An}}\text{min}\left(\text{P}_{ \text{An}}\text{P}_{\text{An}}^{\prime}\right)}{\sum_{\text{An}}\omega_{\text{ PAn}}+\sum_{\text{An}}\omega_{\text{P}}\text{min}^{\prime}\text{P}_{\text{An}}}\) \\ \hline \multirow{3}{*}{Meta-structure-based} & BSCSE [14] & Subgraph Expansion & Complex semantic relevance & \(\text{s}\big{(}\text{g},\text{i}\text{|S},\text{o}_{\text{y}}\big{)}=\frac{\sum_{ \text{P}\in\text{g}\text{|S}\cap\text{g}}\big{(}\text{g}^{\prime}+1|\text{ S}\circ_{\text{y}}\big{)}}{|\sigma(\text{g}|\text{S}\cap\text{C})|^{\alpha}}\) \\ \cline{2-5}  & MGP [21] & Graphcount & Distinct proximity semantic classes & \(\text{s}(\text{x},\text{y};\omega)=\frac{2\omega\cdot\text{m}_{\text{xy}}}{ \text{m}_{\text{xx}}\cdot\text{m}_{\text{xy}}\cdot\text{m}}\) \\ \hline \multirow{2}{*}{Integrating meta path and meta structure} & \multirow{2}{*}{RMSS [26]} & \multirow{2}{*}{RecurMS} & Robust semantic rich similarity & \(\text{s}\left(\text{x},\text{y}\right)=\frac{U(\text{x}\text{y})}{U(\text{x})}\) \\ \hline \hline \end{tabular}
\end{table} 
Table 1: A comparison of measures based on the meta path and meta structure in HINs. expansion based on the meta structure means that we traverse the network starting from a given source node until the target node along the given meta structure is reached to. Owing to the complexity of the meta structure, the traversing result refers to the subgraph rather than the path. We will describe the process with an example. Figure 2 shows an example of the detailed process of subgraph expansion.