Graph Belief Propagation Networks

We treat the graph as deterministic but the node attributes randomly as follows: \raisebox{-0.9pt}{1}⃝ Jointly sample the node labels $p(\bm{y})$; \raisebox{-0.9pt}{2}⃝ Given the node labels $\bm{y}$, sample the features from $p(\bm{X}|\bm{y})$. This generation process defines a joint distribution $p(\bm{X},\bm{y})$. Furthermore, we add the following assumptions.

• •

  First, the joint distribution of node labels $p(\bm{y})$ is a pairwise Markov random field,

  $\displaystyle\textstyle p(\bm{y})=\frac{\varphi(\bm{y})}{\sum_{\bm{y}^{\prime}}\varphi(\bm{y}^{\prime})},\quad\varphi(\bm{y})=\prod_{i\in V}h_{i}(y_{i})\prod_{(i,j)\in E}H_{ij}(y_{i},y_{j}),$

  (1)

  and the coupling-potential on every edge is the same and symmetric, i.e. $H_{ij}(y_{i},y_{j})=H_{y_{i},y_{j}}=H_{y_{i},y_{j}}$, where $\bm{H}\in\mathbb{R}_{+}^{c\times c}$. This assumption implies each node is directly coupled only with its neighbors, a condition known as the Markov propriety in probabilistic graph models [31].

• •

  Second, The conditional distribution $p(\bm{X}|\bm{y})$ can be factorized as

  $\displaystyle\textstyle p(\bm{X}|\bm{y})=\prod_{i\in V}p(\bm{x}_{i}|y_{i})=\prod_{i\in V}f(y_{i};\bm{x}_{i}),$

  (2)

  which means the features on each node is independently sampled given its label.

These two assumptions lead to simple and efficient inference algorithms, as we will show next.

Following the generative model defined above, we derive the posterior probability as:

which is a conditional random field [32], where $\cong$ denotes “equality up to a normalization” [33]. We directly parametrize this posterior distribution using a symmetric matrix $\bm{H}$ for the coupling-potential, and a neural network function $g_{\theta}$ to map from a node’s features to its self-potential. Similar modeling assumptions have been considered in collective classification [17, 34], where the models are trained to maximize the joint likelihood. In contrast, our model is trained on the marginal likelihood of individual labels. Next, we introduce the inference algorithm for the marginal probability $p(y_{i}|\bm{X})$. The algorithm only use node features for label prediction, and (once trained) can be used to predict labels in a unseen graph. Later, we consider the inference algorithm for $p(y_{i}|\bm{X},\bm{y}_{L})$, which gives more accurate predictions in the transductive learning setting.

In practice, for numerical stability, we perform belief-propagation updates in the log-space.

where LSE stands for the log-sum-exp function: $\texttt{LSE}_{y_{j}}\left[f(y_{i},y_{j})\right]=\log\left[\sum_{y_{j}}\exp\left(f(y_{i},y_{j})\right)\right].$

Now that our method is fully specified, we comparing it with existing methods in terms of statistical assumption, model parametrization, training/inference objective and optimization algorithm.

One modeling choice we have to make for GBPN is the loss function for training. Although the (unweighted) negative log-likelihood loss is often used for training GNNs, the same choice for GBPN can lead to sub-optimal performance in practice, especially when the degree heterogeneity in a graph is large. The reason is that, unlike GNNs, the predictive confidence of GBPN on a node can grow exponentially with the node degree, as shown in fig. 1. Therefore, the negative log-likelihood loss associated with mis-classifying a node grows linearly with the node degree. This creates a potential misalignment between the loss function and the classification accuracy, as classification accuracy is not weighted based on node degree. We will demonstrate this misalignment empirically in Section 3.3.

We employ a straightforward way to align the loss function to the accuracy measure, which is to reweight the marginal likelihood in the loss function eq. 10 as $\log p_{i}^{\prime}(y)\cong\alpha_{i}\cdot\log p_{i}(y)$. Here, $\alpha_{i}$ reduces the influence of high-degree nodes. In practice, we find that $\alpha_{i}=d(i)^{-1/2}$ gives consistently better performance than $\alpha_{i}=1$ (no reweighting), where $d(i)$ is the degree of node $i$.

One limitation of GBPN is that it requires storing all the messages between neighbors during training, which costs $\mathcal{O}(|E|)$ per BP step. In comparison, GCN [5] and GraphSAGE [6] costs $\mathcal{O}(|V|)$ per layer, and GAT [8] costs $\mathcal{O}(|E|)$ per layer due to edge attention weights. To reduce the computational cost on large-scale network, we will introduce a mini-batch training algorithm for GBPN in Section 3.3.

The datasets we consider here fits into three groups: \raisebox{-0.9pt}{1}⃝ small synthetic graphs; \raisebox{-0.9pt}{2}⃝ small real-world graphs; \raisebox{-0.9pt}{3}⃝ large-scale graphs. We first consider \raisebox{-0.9pt}{1}⃝ and \raisebox{-0.9pt}{2}⃝, where training the entire graph can fit into a single GPU. On these datasets, all models take at most 20 minutes to train on a Telsa V100 GPU.

For GBPN, we use a $2$-layer MLP with $256$ hidden units to map the features of each node to its self-potentials. Then we run five steps of BP iterations to compute the predictions. For standard baselines, we consider a $2$-layer MLP, GCN, and GraphSAGE models with the $256$ hidden units, as well as a $2$-layer GAT with four attention heads $\times$ $64$ hidden units per layer. We also compare GBPN with GMNN [20], which is also based on Markov random fields, as well as DeeperGNN [43], which uses several hops of neighborhood information at anode. For both of these baselines, we use the reference implementations¹¹1DeeperGNN is released under GNU General Public License while GMNN is under no license. with default hyperparameters for training and inference.

We randomly split all datasets into 30% training, 20% validation, and 50% testing. All baseline methods are trained by minimizing the negative log-likelihood (NLL), while GBPN is trained with the weighted NLL loss discussed in Section 2.4. For all methods, we use an AdamW optimizer with learning rate $1.0\times 10^{-3}$ and decay rate $2.5\times 10^{-4}$ to perform full-batch training for 500 steps. The testing accuracies are averaged over 30 runs and summarized in Tables 3 and 4.

On the synthetic networks sampled from MRFs, the transductive GBPN outperforms the other methods by large margins (Table 3). The performance gap is due to two reasons. First, the underlying data assumption of our model exactly matches the data. Second, GBPN is able to directly use training labels for inference. On the empirical datasets, inductive and transductive GBPN outperform the baselines in five of seven graphs (Tables 3 and 4). GBPN is more accurate on most of the coauthorship and citation graphs, although the gains over the best baslines are modest. The differences on the Election and Sexual datasets brings additional insights. The node labels in both datasets are binary; however, election outcomes are homophilous, and the sexual interactions are heterophilous (most relationships used to construct the dataset are heterosexual). GBPN is comparable to the best baseline on the Election network (GraphSAGE in this case), it outperforms the baselines by large margins on the Sexual network. This is because GBPN can explicitly learn heterophily with the coupling-potential (Figure 2), while the standard GNN models are designed for homophilous graphs [24, 44]. Finally, although the transductive GBPN consistently outperforms its inductive counterpart, the gap between them is small, as the predictive probabilities on the training nodes are already quite accurate.

A useful aspect of GBPN is that the learned coupling-potentials $\bm{H}$ can be interpreted as between-class affinities. We first confirm that GBPN identifies the true coupling-potentials used to generate the synthetic graphs. Indeed, Figures 2, 2, 2 and 2 shows that the learned $\bm{H}$ is close to the parameters used to generate the data, although the exact numbers have minor differences.

Next, we examine the learned coupling matrices for some empirical datasets (Figures 2, 2 and 2). The learned coupling-potentials are homophilous on the Election network and strongly heterophilous in the Sexual network, which reflect the fact that the election outcome in neighboring counties tend to be the same and that most sexual interactions in the dataset are heterosexual. On the PubMed citation network, node labels 0, 1, 2 correspond to medical publications on experimental diabetes, adult-onset diabetes, and juvenile diabetes respectively. The learned coupling matrix shows that papers citing each other tend to be in the same field, as shown by the large diagonal values. Beyond this, the smallest value is between adult-onset diabetes and juvenile diabetes. This aligns with the fact that those two type of diseases are largely among different age groups.

Another interesting component of the GBPN model is that we can examine intermediate predictions computed during belief propagation. Although belief propagation is not guaranteed to converge on graphs with cycles, GBPN converged quickly on all real-world graphs, oftentimes in a handful of iterations. Here, we consider the PubMed dataset in detail, using the setup in section 3.1. After training, we run belief propagation to compute the belief probability $\{p_{i}^{(t)}\}_{i\in V}$ for all nodes for up to $T=20$ steps. To evaluate BP convergence, we measure the norm of the difference between the belief at step $t$ and the converged belief, $\|p_{i}^{(t)}-p_{i}^{(\infty)}\|\approx\|p_{i}^{(t)}-p_{i}^{(20)}\|$, along with the train and test accuracies (Figure 3). The result shows that GBPN converges linearly with the number of belief-propagation steps, and the train and test accuracies change little after a handful of iterations.

To help understand BP convergence and the algorithm in general, we also visualize how each BP step refines the final prediction (Figure 3). We plot the nodes that are correctly predicted by GBPN at step $5$, where the coordinate of each node is computed by compressing its spectral embeddings [45] and features together with UMAP [46], and the color indicates the step after which the prediction is always correct. Nodes corrected at later steps (e.g., $t=5$ in dark red) are typically surrounded by others examples that are already corrected earlier. This behavior reflects the mechanism of the GBPN model: start with easy data points and iteratively correct harder examples with neighbor information.

In Section 2.4, we identified the misalignment between the unweighted NLL loss function and the classification accuracy on graphs with high degree heterogeneity, which prompts us to down-weight the high degree nodes. Here, we consider neighborhood sub-sampling as an alternative solution to the misalignment problem, which also reduces computation and enables efficient mini-batch training.

To demonstrate how degree heterogeneity causes the misalignment and consequently hurts accuracy, we manually reduced the degree heterogeneity by regularizing the high degree nodes during training. In particular, we train a 1-hop GBPN on the OGBN-arXiv dataset with the unweighted NLL loss, uniformly sub-sampling a maximum number of neighbors during the aggregation step in eq. 8 (or all neighbors if the degree is below the threshold). At inference, we run GBPN with all neighbors to predict the testing labels. Figure 4 shows the average log-likelihood and accuracy on the testing nodes as a function of the maximum number of neighbors, and reducing this number improves the testing accuracy. At the same time, the log-likelihood of the testing node decreases, showing the misalignment. We further split the testing nodes into the $30\%$ lowest degree nodes and the rest $70\%$, and find that the log-likelihood and accuracy aligns on the low-degree nodes (Figure 4) but not on the high-degree nodes (Figure 4). This justifies our heuristic of down-weighting high degree nodes.

For large-scale graphs where mini-batch training is necessary, neighborhood sub-sampling improves the classification accuracy and also reduces computational costs. In particular, computing the $T$-step belief of a node $i$ requires unrolling a computation tree [47] that includes all $T$-hop neighbors of $i$, which can quickly grow to the entire graph. With neighborhood sub-sampling, we randomly select a maximum of $d$ neighbors per node when unrolling the tree, and the sub-sampled tree has $\mathcal{O}(d^{T})$ nodes (Figure 5). This is similar to sub-sampling in GNNs to address scalability [6], although our sample is a tree and also explicitly down-weights high-degree nodes.

We test the performance of GBPN with mini-batch training on four large-scale real-world datasets. The experimental setup is the same as in Section 3.1, except we only train for $100$ epochs, as the model parameters are updated multiple times per epoch. We repeat each experiment only $10$ times because accuracy has smaller variance. During GBPN training, we use $T=2$ BP steps and a maximum of $5$ sampled neighbors. Training on the largest dataset (Products) takes about one minute per epoch and less than two hours overall on a Telsa V100 GPU. For a fair comparison, we use a similar neighborhood expansion method for mini-batch training of GraphSAGE and GAT, with the branching factor set to $5$. We replace the GCN baseline with ClusterGCN [48], where we set the average size per cluster to be $256$ and the number of clusters per mini-batch to be $3$; other hyperparameters are kept the same. We do not include GMNN and DeeperGNN as baselines since neither of the reference repositories implemented mini-batch training. The labels in the Elliptic and Payments datasets are highly imbalanced as most transactions are licit, so we measure the prediction performance with the F1 score ($\times 100$) on the illicit class. Performance on the arXiv and Products datasets is measured by the classification accuracy. We find that GBPN-I outperforms the baselines on all four datasets (Table 5), and GBPN provides additional gains on the Payments and arXiv datasets.

In addition to uniform sampling, we also experimented with importance sampling, which has proven useful for training certain graph neural networks [49, 50]. The results are summarized in Appendix B.