# Graph Convolutional Networks Guided by Explicitly Estimated Homophily and Heterophily Degree
## 3 The Proposed Method
### The Pre-Training Module for Estimators  
In order to make full use of the graph information, we pre-train two MLPs by learning from two MLPs which use the node attribute information following [22] and localized structure information independently. We choose Deepwalk [24] to mine localized structure information. Deepwalk [24] applies a group of random walk generators to generate node sequences from a graph. For each node \(v_{i}\) in the graph, the random walk generator takes \(v_{i}\) as the first node to visit, samples uniformly from neighbors of \(v_{i}\) and then designates the sampled neighbor as the next node to visit. The generator repeats the sampling process until the maximum length \(T\) of the sequence is reached and the sampled nodes form a sequence in order. Then, Skip-gram [30] is used to generate embeddings \(\mathbf{x}_{i}^{E}\) for each node \(v_{i}\) from random walk sequences. For each node in a random walk sequence, Skip-gram maximizes the probability of the neighbors that co-occur with the node in a window. It iterates over the random walk set and uses gradient descent to train the embedding of nodes. Let \(\mathbf{X}^{E}\) be the learned matrix generated by Deepwalk in graph \(\mathcal{G}\), and let \(\mathbf{x}_{i}^{E}\) be the \(i\)-th column of \(\mathbf{X}^{E}\). \(\mathbf{X}^{E}\) will be used to train an estimator.  
Then, we define two MLPs, called \(\mathrm{MLP}_{1}\) and \(\mathrm{MLP}_{2}\), respectively. The \(l\)-th layers of the two MLPs can be defined as:  
\[\mathbf{p}_{i}^{(l)} =\sigma\Big{(}\mathbf{W}_{1}^{(l)}\mathbf{p}_{i}^{(l-1)}+\mathbf{ b}_{1}^{(l)}\Big{)} \tag{1}\] \[\mathbf{q}_{i}^{(l)} =\sigma\Big{(}\mathbf{W}_{2}^{(l)}\mathbf{q}_{i}^{(l-1)}+\mathbf{ b}_{2}^{(l)}\Big{)} \tag{2}\]  
where \(\mathbf{p}_{i}^{(0)}=\mathbf{x}_{i}\) and \(\mathbf{q}_{i}^{(0)}=\mathbf{x}_{i}^{E}\) are the original feature vector and embedding vector of node \(v_{i}\) respectively, \(\mathbf{W}_{1}^{(l)}\) and \(\mathbf{W}_{2}^{(l)}\) are the learnable weight matrices, \(\mathbf{b}_{1}^{(l)}\) and \(\mathbf{b}_{2}^{(l)}\) are the learnable bias vectors, and \(\sigma\) is an activation function.  
Through MLP estimators, we can obtain the soft labels of all the nodes:  
\[\mathbf{s}_{i} =\text{softmax}(\mathbf{p}_{i}^{(L)}) \tag{3}\] \[\mathbf{t}_{i} =\text{softmax}(\mathbf{q}_{i}^{(L)}) \tag{4}\]  
where \(\mathbf{p}_{i}^{(L)}\), \(\mathbf{q}_{i}^{(L)}\) are the outputs of the last layers of \(\mathrm{MLP}_{1}\) and \(\mathrm{MLP}_{2}\) for node \(v_{i}\), respectively, and \(\mathbf{s}_{i},\mathbf{t}_{i}\in\mathbb{R}^{C}\), \(\mathbf{s}_{i}|j\), \(\mathbf{t}_{i}|j\) denote the probabilities that node \(v_{i}\) belongs to class \(j\) as estimated by \(\mathrm{MLP}_{1}\) and \(\mathrm{MLP}_{2}\), respectively.  
Figure 2: The schema of GCN-EHHD.  
We pre-train estimators by the nodes with known labels and obtain the optimal parameters of MLP\({}_{1}\) and MLP\({}_{2}\) by minimizing the following two loss functions:  
\[\mathcal{L}_{mlp1} =\sum_{v_{i}\in V_{\mathrm{L}}}\mathcal{J}(\mathbf{s}_{i},y_{i}) \tag{5}\] \[\mathcal{L}_{mlp2} =\sum_{v_{i}\in V_{\mathrm{L}}}\mathcal{J}(\mathbf{t}_{i},y_{i}) \tag{6}\]  
where \(\mathcal{J}\) represents the cross entropy.  
After the above pre-training process, we obtain the estimators MLP\({}_{1}\) and MLP\({}_{2}\), and we will use them to estimate the homophily and heterophily degree of the neighboring nodes.