How do Probabilistic Graphical Models and Graph Neural Networks Look at Network Data?

Graphs are powerful data structures for representing relational data, and this paper compares Probabilistic Graphical Models (PGMs) and Graph Neural Networks (GNNs) to determine how they capture information in networked datasets. The core finding is that PGMs outperform GNNs when input features are low-dimensional or noisy, while PGMs demonstrate greater robustness to increasing graph heterophily.

Comparison of Frameworks and Input Features

The fundamental difference between the two frameworks lies in their handling of input features: PGMs do not necessarily require node attributes, as they can rely solely on the graph’s edge list, allowing them to function even when node attributes are sparse. In contrast, GNNs explicitly require an input matrix X to train the model, and their message-passing algorithm explicitly requires in input node features. The authors evaluate how performance is affected by tuning feature informativeness, dimensionality, and availability. They find that GNNs are outperformed by PGMs when input features are low-dimensional or noisy, mimicking many real scenarios where node attributes might be scalar or noisy. Furthermore, the study shows that there are no clear advantages in utilizing an extra input feature X for link prediction, suggesting one must be careful in using all the information available.

Robustness to Graph Structure and Noise

The investigation explores model robustness under changing network properties. First, they examine robustness to noise by systematically randomizing features of randomly selected nodes in real datasets. They find that PGMs are more robust when increasing the percentage of nodes whose features are randomized, highlighting the stronger reliance of GNNs on input feature information. Second, they assess performance when increasing graph heterophily, defined as a structural measure where heterophilic have larger off-diagonal elements of the affinity matrix. The results indicate that PGMs generally outperform GNNs when increasing the heterophily of the graph (both synthetic and real), when given the full input feature. However, they note that for GNNs, performance can be improved by a better choice of input features rather than architectural changes alone.

Model Variants and Architectures

The paper analyzes specific model variants within each family. For PGMs, they consider three variants of the Stochastic Block Model (SBM): MULTITENSOR and MTCOV, which use tensor factorization; BNP, a Bayesian model using Markov chain Monte Carlo sampling. Among these, MTCOV is the only model that can also take node attributes in input. For GNNs, four distinct architectures are employed: Graph Attention Networks (GAT), Graph Autoencoders (GAE) and Graph Variational Autoencoders (VGAE), and H2GCN, which is specifically designed to handle heterophily.

Interpretability and Complexity

The two frameworks differ significantly in interpretability. PGMs are inherently interpretable because they learn community membership vectors on each node, which are quantities directly interpretable as they provide clear insights into the community structure of the network. GNNs, conversely, learn embeddings that are not directly interpretable, requiring ad-hoc processing a posteriori to allow for interpretability. The authors compare these by visualizing memberships and embeddings using t-SNE. They find that both MULTITENSOR and GAT are able to place more mixed nodes closer to the border of their main community, similar to ground truth, but PGMs offer a direct estimation of the mixed-membership as their natural output. Regarding computational complexity, PGMs are generally linear in system size (the number of nodes or edges), while GNNs have complexities that depend on factors like the number of layers L and embedding dimensions F'.

Conclusion

In summary, PGMs outperform GNNs when input features are low-dimensional or noisy, and they exhibit greater robustness to increasing graph heterophily. While GNNs offer flexibility in processing heterogeneous features without requiring ad-hoc design choices, the authors suggest that linear models can outperform GNNs in link prediction tasks, implying that GNNs should ideally be designed to learn automatically whether to discard irrelevant features or to select what features to use.

The gist

PGMs outperform GNNs when input features are either low-dimensional or noisy, a common scenario in real-world networks where node attributes may be minimal or unreliable. The core finding is that PGMs demonstrate greater robustness to increasing graph heterophily compared to GNNs.

Figure 1: Structure-based vs. attribute-based features.

The performance of GNNs is generally comparable in the two cases, except for Peptides, where AUC is much higher in the structure-based case. Feeding the high-dimensional adjacency matrix row improves performance, which is generally comparable to that of PGMs.

**Figure 2: High vs. low dimensional features.

As a fastidious researcher, I have analyzed this comparative study between Probabilistic Graphical Models (PGMs) and Graph Neural Networks (GNNs). The core findings suggest distinct advantages for each framework depending on the network characteristics.

Here are the specific improvements that can be made to AI systems by synthesizing these findings:

1. // Feature-Aware Model Selection for Low-Information/Noisy Data

2. // Robustness Enhancement via Feature Engineering

3. // Heterophily-Adaptive Network Architectures

4. // Interpretable Structure Discovery (Hybrid Modeling)

5. The improved system should implement a dynamic model selection layer based on input feature quality and dimensionality:

5.1 The system will first assess the nature of available node features (attribute-based vs. structure-based). If features are low-dimensional or noisy, the system should default to a PGM framework (e.g., MTCOV) for link prediction tasks, as PGMs outperform GNNs in these scenarios (as seen in Figure 1 and Text Section 6).

5.2 When using GNNs on real-world data where features are available, the system must employ structure-based features (the adjacency matrix row) rather than relying on attribute-based features, as this yields comparable or superior performance across most datasets (as seen in Figure 7 and Text Section 6).

3. The system will integrate mechanisms to explicitly handle network structural properties during training:

3.1 For heterophilic networks, the system should utilize GNN architectures specifically designed for it, such as H2GCN, which incorporates separate embeddings for self and neighbor nodes (as noted in Section 4.2).

3.2 When performance degradation due to heterophily is observed even with specialized architectures (like H2GCN), the system must dynamically adjust weight initialization variance to mitigate oversmoothing effects (as suggested in Section 8).

4. The system will incorporate a hybrid interpretability module:

4.1 For PGM-based tasks, the model's latent community membership vectors should be extracted directly as interpretable parameters, allowing for clear insights into cluster structure.

4.2 For GNN-based tasks, the system must employ post-hoc interpretability techniques (like t-SNE visualization of embeddings) to attempt to extract meaningful mixed-membership information from the learned node representations, bridging the gap between GNN black-box outputs and PGM interpretability.

The resulting AI system will be a more resilient and context-aware graph learning engine capable of:

1. Accurately predicting missing links in low-feature/noisy environments by leveraging the structured knowledge encoded in PGMs.

2. Maximizing the utility of available features by intelligently prioritizing structural information over potentially misleading attribute data when training GNNs.

3. Maintaining high predictive accuracy on complex, real-world networks characterized by varying degrees of heterophily, even when structural modifications are insufficient to prevent oversmoothing.

4. Providing dual interpretability outputs: direct probabilistic community structure for PGMs and visualization-based embedding analysis for GNNs, enabling researchers to understand both the latent structure (PGM) and the learned representations (GNN).

Graphs are a powerful data structure for representing relational data and are widely used to describe complex real-world systems. Probabilistic Graphical Models (PGMs) and Graph Neural Networks (GNNs) can both leverage graph-structured data, but their inherent functioning is different. The question is how do they compare in capturing the information contained in networked datasets? We address this objective by solving a link prediction task and we conduct three main experiments, on both synthetic and real networks: one focuses on how PGMs and GNNs handle input features, while the other two investigate their robustness to noisy features and increasing heterophily of the graph. PGMs do not necessarily require features on nodes, while GNNs cannot exploit the network edges alone, and the choice of input features matters. We find that GNNs are outperformed by PGMs when input features are low-dimensional or noisy, mimicking many real scenarios where node attributes might be scalar or noisy. Then, we find that PGMs are more robust than GNNs when the heterophily of the graph is increased. Finally, to assess performance beyond prediction tasks, we also compare the two frameworks in terms of their computational complexity and interpretability.