Introduction
Standard Graph Neural Networks (GNNs) typically operate under the homophily assumption—the principle that "birds of a feather flock together," where connected nodes share similar attributes or labels. While this assumption holds for citation networks, it fails in many real-world heterophilous graphs. In contexts like fraud detection or certain biological networks, edges often connect nodes of different classes. In these scenarios, traditional Message Passing Neural Networks (MPNNs) act as a "low-pass filter," averaging neighbor features and washing out the distinct signals necessary for accurate classification. Furthermore, standard MPNNs are restricted to local neighborhoods, failing to capture global structural patterns that might define a specific class across the entire graph.
The HP-GMN Framework
To address these limitations, the authors propose HP-GMN (Graph Memory Networks for Heterophilous Graphs). This architecture shifts away from simple neighbor averaging, instead extracting a rich set of local statistics and utilizing a global memory module to recognize neighborhood patterns across the graph.
1. Rich Local Statistics
Instead of treating all neighbors as a single aggregate, HP-GMN extracts four distinct types of information for each node:
- Node Attributes: The raw features of the node itself.
- Label-wise Class Distribution: The model uses an initial MLP to generate "pseudo-labels," then counts the frequency of each class within a node's neighborhood.
- Label-wise Feature Distribution: Neighbor features are grouped and averaged based on their predicted class, preventing the signal-washing effect of traditional GCNs.
- Diffusion Matrix: The model utilizes Personalized PageRank (PPR) to capture higher-order structural information beyond the immediate 1-hop neighborhood.
2. Global Graph Memory Module
The model maintains a memory matrix $M$, where each row represents a "global pattern" or prototype of a neighborhood.
- Querying: A node’s local statistics are used to query this memory via an attention mechanism.
- Global Context: The node receives a global representation based on how closely its local neighborhood matches these learned global prototypes. This allows nodes in different parts of the graph to benefit from shared structural insights even if they are not directly connected.
3. Dual Regularization
To ensure the memory module remains effective, the authors introduce two regularization terms:
- Kpattern Regularization: Forces memory units to stay close to actual local patterns found in the data, ensuring representativeness.
- Entropy Regularization: Encourages the model to utilize all memory units equally, preventing "dead units" and ensuring a diverse set of learned prototypes.
Experimental Results
HP-GMN was evaluated on nine datasets, including heterophilous Wikipedia networks (Chameleon, Squirrel, Crocodile) and traditional homophilous citation networks (Cora, Citeseer, Pubmed).
- Superior Performance on Heterophily: HP-GMN significantly outperformed baselines on heterophilous datasets. On the Squirrel dataset, it achieved 72.3% accuracy, a massive improvement over standard GCN (56.6%) and specialized models like GPRGNN (49.6%).
- Robustness on Homophily: Unlike many models specialized for heterophily, HP-GMN remains highly effective on standard graphs. The HP-GMN-APPNP variant achieved state-of-the-art results on Cora (84.7%) and Citeseer (73.0%).
- Ablation Studies: Removing any of the four local statistics or the regularization terms led to a performance drop, confirming that each component is essential to the model's success.
Key Insights and Discussion
The core innovation of HP-GMN is the recognition of distributional similarity. While a node's neighbors might be different from itself in a heterophilous graph, nodes of the same class often share a similar distribution of diverse neighbors. By capturing this distribution and bridging it with a global memory module, HP-GMN performs a form of "global message passing."
However, the model does introduce higher computational overhead due to the complexity of calculating multiple local statistics and maintaining the attention-based memory matrix. Additionally, the reliance on an initial MLP for pseudo-labels suggests that performance could be sensitive to the quality of initial node features. Future work may explore more efficient ways to summarize local statistics or extend this architecture to dynamic graphs where heterophily patterns evolve over time.
Summary updated