# A Noval Weighted Meta Graph Method for Classification in Heterogeneous Information Networks
## 3 Problem Formalization  
The related concepts and definitions are introduced as follow. We define a HIN as a graph denoted by G = (V, E, A, R), where \(V\) and \(E\) represent the set of nodes and edges of the graph respectively, \(A\) and \(R\) represent the set of types of nodes and edges, respectively. Definition 1 represents network's meta-level structure, as shown in Figures 1(a) and 2(a). **Definition 1**. : _Network schema [2; 23]. The network schema is defined as \(T_{G}\) = (A,R). \(T_{G}\) is a meta template for network G = (V, E, A, R) with the object type mapping \(\phi:V\to A\) and the link type mapping \(\psi:E\to R\)._In homogeneous networks, different paths connect two objects of the same type. However, in heterogeneous information networks, different paths can connect objects of different types. These connecting paths imply different semantics. Formally, we call these paths as meta paths. **Definition 2**. : _Meta path [1]. A meta path \(P\) is a composite relation \(A_{1}\xrightarrow{R_{1}}A_{2}\xrightarrow{R_{2}}\dots\xrightarrow{R_{l}}A_{l+1}\), which represents a composite relation \(R=R_{1}\circ R_{2}\circ\dots\circ R_{l}\), between object types \(A_{1},A_{2},\dots,A_{l+1}\), where \(\circ\) denotes the composition operator on relations._  
Meta paths can express semantics between different objects. Obviously, different meta paths demonstrate different semantic meanings. In Figure 1b, meta path APA (Author-Paper-Author) shows that authors are co-writing a paper and the links between authors and papers denote co-author relationships. **Definition 3**. : _Classification in HINs. Given a class \(C=\{c_{1},c_{2},\cdots,c_{|c|}\}\) and object set \(V=\{v_{1},v_{2},\cdots,v_{|v|}\}\) in a HIN, where \(|c|\) and \(|v|\) denote the cardinality of these sets, respectively, then classification of HINs aims to map the object set \(V\) into the class set \(C\) through \(f:V\to C\)._  
Figure 3: Network Schema and Meta Graphs of Yelp Dataset. Figure 2: Network Schema and Meta Graphs of DBLP (Digital Bibliography & Library Project) Dataset. **Definition 4**. : _Meta graph [24]. A meta graph is denoted by \(S\) = (\(A\), \(L\), \(n_{t}\), \(n_{s}\) ), where \(A\subseteq V\) is a subset of nodes and \(L\subseteq E\) is a subset of edges. The meta graph \(S\) is a directed acyclic graph (DAG), and \(n_{t}\), \(n_{s}\) are a single source and target node, respectively._  
Figure 2b shows the meta graphs of Figure 1b. In Figure 4a, we can consider three meta paths \"_APA_, _APAPA_, _APVPA_\" and a meta graph \"_APA_\(\bigcup AP(A;V)PA\)\". Tables 1 and 2 show respectively the connecting author neighbors of \(A_{1}\) based on these meta paths and meta graph. **Definition 5**. : _Meta graph matrix. A meta graph matrix \(M\) for a meta graph \(S=(A_{1}A_{2}\cdots A_{l+1})\) is defined as \(M_{1l+1}=W_{A_{1}A_{2}}\times W_{A_{2}A_{3}}\times\ldots\times W_{A_{l}A_{l+1}}\), where \(W_{A_{l}A_{j}}\) is the adjacency matrix created for objects of type \(A_{i}\) and \(A_{j}\). \(M[x_{i},y_{j}]\) represents the number of graphs between objects \(x_{i}\in A_{l}\) and \(y_{j}\in A_{l+1}\) following meta graph \(S\), and \(M[x_{i},y_{j}]=M[y_{j},x_{i}]\)._  
Obviously, meta graphs are composed of various meta paths in this paper. We take Figure 2b as the running example to better comprehend the computation of meta graph matrix. For meta graph \(D_{1}\), it is computed as \(M_{D_{1}}=W_{AP}\cdot W_{PA}\); the computing matrix of meta graph \(D_{2}\) is computed as \(M_{D_{2}}=W_{AP}\cdot\{(W_{PT}\cdot W_{TP})\odot(W_{PA}\cdot W_{AP})\odot(W_{ PC}\cdot W_{CP})\}\cdot W_{PA}\), where \"\(\odot\)\" represents Hadamard product. \begin{table}
\begin{tabular}{c c c} \hline \hline
**Object** & **Meta Paths** & **Neighbors** \\ \hline \multirow{3}{*}{\(A_{1}\)} & APA & \(A_{2}\) \\  & APAPA & \(A_{4},A_{5}\) \\ \cline{1-1}  & APVPA & \(A_{3},A_{5}\) \\ \hline \hline \end{tabular}
\end{table} 
Table 1: The neighbors of \(A_{1}\) based on three meta paths.