Source-linked AI summary
Graph Neural Networks with Heterophily
Jiong Zhu, Ryan A. Rossi, Anup Rao, Tung Mai, Nedim Lipka, Nesreen K. Ahmed, Danai Koutra
TL;DR
Existing GNNs largely assume homophily and depend heavily on contextual node features, leaving heterophilous graphs insufficiently addressed. CPGNN learns an interpretable class-compatibility matrix for compatibility-guided propagation, and experiments report strong heterophily performance with or without features while retaining comparable homophily performance.
Problem
Existing GNN formulations largely assume homophily and rely heavily on contextual node features, while exact class compatibility is unavailable in semi-supervised classification.
Method
CPGNN estimates prior class beliefs and propagates them through neighborhoods using an end-to-end trainable compatibility matrix H.
Results
CPGNN variants achieve state-of-the-art results in heterophily settings with or without contextual node features and comparable performance in homophily settings.
Takeaways & Limitations
Learning class compatibility extends GNN-based methods to graphs with either homophily or heterophily and supports settings with limited node features.
Takeaways & Limitations
The task is semi-supervised node classification with optional contextual features, using sparse adjacency and feature matrices in the theoretical analysis.
Abstract
from arXiv · showhide
Graph Neural Networks (GNNs) have proven to be useful for many different practical applications. However, many existing GNN models have implicitly assumed homophily among the nodes connected in the graph, and therefore have largely overlooked the important setting of heterophily, where most connected nodes are from different classes. In this work, we propose a novel framework called CPGNN that generalizes GNNs for graphs with either homophily or heterophily. The proposed framework incorporates an interpretable compatibility matrix for modeling the heterophily or homophily level in the graph, which can be learned in an end-to-end fashion, enabling it to go beyond the assumption of strong homophily. Theoretically, we show that replacing the compatibility matrix in our framework with the identity (which represents pure homophily) reduces to GCN. Our extensive experiments demonstrate the effectiveness of our approach in more realistic and challenging experimental settings with significantly less training data compared to previous works: CPGNN variants achieve state-of-the-art results in heterophily settings with or without contextual node features, while maintaining comparable performance in homophily settings.
1 Introduction
Existing GNNs often assume homophily and rely heavily on node features, limiting their effectiveness on heterophilous graphs. CPGNN addresses these limitations with a learned compatibility matrix and is evaluated under more realistic, lower-data settings.
- Many GNNs implicitly assume neighboring nodes belong to the same class, which can cause poor performance when connected nodes are typically from different classes.This limitation matters in applications such as fraudster detection and protein-structure analysis, where heterophilous connections occur.
- CPGNN incorporates a compatibility matrix H that models the likelihood of connections between different classes, capturing both homophily and heterophily.The matrix is learned end-to-end and is interpretable as class-compatibility information.
- The framework is designed to work on graphs with either homophily or heterophily and with missing, incomplete, or absent node features.This extends GNN applicability beyond settings with strong homophily and complete contextual features.
- CPGNN separates prior belief estimation from compatibility-guided propagation, using an off-the-shelf classifier before aggregating neighborhood beliefs.The prior estimator can use node features when available, while propagation is guided by the learned compatibility matrix.
- The evaluation compares CPGNN with baselines using significantly fewer training samples and includes a featureless setup.The experiments are intended to assess effectiveness under more realistic conditions than prior heterophily studies.
2 Framework
CPGNN extends GNNs with a compatibility matrix that models class-dependent connectivity and supports homophilous or heterophilous graphs. Its two-stage framework estimates node beliefs, propagates them using a learned compatibility parameter, and regularizes training for stable estimation.
- Preliminaries: The homophily ratio summarizes within-class connectivity, while compatibility matrix H models connection probabilities between specific class pairs.The ratio approaches 1 for stronger homophily and 0 for stronger heterophily; H captures variability across class pairs.
- Framework Design: CPGNN uses prior belief estimation followed by compatibility-guided propagation of node beliefs.The estimator can use different neural architectures, and propagation updates each node’s belief using neighborhood information and a trainable compatibility matrix.
- Framework Design: MLP and Chebyshev-based estimators provide alternatives for producing prior beliefs from node features.The paper notes that estimators should not themselves be constrained by homophily assumptions, especially for heterophilous graphs.
- Training Procedure: CPGNN pretrains the prior belief estimator, initializes the compatibility parameter from training labels and estimated beliefs, and regularizes it during joint training.The full objective combines output cross-entropy, estimator L2 regularization, and a term keeping the compatibility parameter centered.
- Parameter Interpretation: Unlike a conventional GNN weight matrix, the learned parameter can be transformed into an interpretable estimate of class-pair connection probabilities.The resulting estimate is constructed as a valid stochastic matrix, and the paper reports improved estimation error after training compared with initialization.
3 Theoretical Analysis
The analysis shows that CPGNN contains simplified GCN as the pure-homophily case H = I. Its compatibility-guided propagation adds class-dependent computational and space costs, with complexity depending on graph structure, labels, and the selected prior estimator.
- Theoretical Connections: Setting H = I reduces one-layer CPGNN to simplified GCN, corresponding to a pure homophily assumption.The equivalence follows by fixing the compatibility matrix as the identity and removing the prior estimator’s nonlinearity.
- Time and Space Complexity: CPGNN introduces O(|E||Y|^2) extra time over the selected prior belief estimator during compatibility-guided propagation.The additional cost comes from propagation with the learned compatibility matrix.
- Time and Space Complexity: With an MLP prior estimator, CPGNN-MLP has time complexity O(|E||Y|^2 + |V||Y| + nnz(X)).Here |E| and |V| denote edges and nodes, |Y| the number of labels, and nnz(X) the number of nonzero feature entries.
- Time and Space Complexity: The overall space complexity of CPGNN is O(|E| + |V||Y| + |Y|^2 + nnz(X)).This accounts for the graph, node-level beliefs, compatibility matrix, and sparse node features.
4 Experiments
Experiments evaluate CPGNN variants and baselines on synthetic and real graphs spanning heterophily and homophily, with and without contextual features. CPGNN variants achieve strong heterophily performance, comparable homophily performance, and improved compatibility-matrix estimates through training.
- Experimental Setup: Experiments use synthetic graphs across heterophily levels and real graphs, with 10% of nodes per class for training and validation and 80% for testing.Synthetic evaluation varies heterophily while holding other factors constant; real-graph evaluation uses random splits.
- Node Classification with Contextual Features: CPGNN-Cheby-1 gains up to 7% over GCN-Cheby in heterophily, while CPGNN-MLP-1 is up to 30% better than MLP in heterophily and 50% better in homophily.These results are reported for experiments with contextual node features.
- Node Classification with Contextual Features: CPGNN-Cheby-1 performs best overall on real heterophilous graphs, improving mean accuracy over GNN baselines by 1.68% to 10.64%.The top three methods across the evaluated graphs are CPGNN-based.
- Node Classification without Features: Without contextual features, CPGNN variants are the best-performing methods on each heterophilous dataset, although H2GCN remains competitive overall.CPGNN-MLP-1 has the best overall performance, followed by CPGNN-Cheby-1.
- Node Classification without Features: Under featureless evaluation, CPGNN achieves state-of-the-art performance on heterophilous graphs and comparable performance to the best baselines on homophilous graphs.Considering both settings, CPGNN-Cheby-1 is reported as the best method overall.
- Ablation Study: Removing the compatibility-matrix initializer causes up to a 30% performance drop, removing regularization causes up to a 6% decrease, and end-to-end training contributes up to a 21% gain.The ablation studies support the roles of initialization, regularization, and end-to-end training of H-bar.
- Compatibility Matrix Estimation: For syn-products with h = 0, the estimated compatibility matrix improves over its initialization and its estimation error decreases throughout training epochs.The estimation is compared with the ground-truth empirical compatibility matrix.
5 Related Work
Related work spans semi-supervised learning, belief propagation, and graph neural networks. The paper positions CPGNN against GNN methods that often perform poorly on heterophilous graphs.
- SSL before GNNs: Earlier semi-supervised and collective-classification approaches include iterative methods, graph-based regularization, probabilistic graphical models, and belief propagation.The paper relates its approach to belief propagation as a message-passing method.
- Graph Neural Networks: GNN research generalized convolution from regular grids to graphs, with GCN, Planetoid, and GraphSAGE among prominent models.GCN is described as a simplification of earlier graph-convolution work.
- GNNs for Heterophily: Many GNN methods work well under strong homophily but perform poorly under heterophily, motivating methods such as Geom-GCN, MixHop, and approaches addressing oversmoothing.Recent work also studies theoretical connections between oversmoothing and heterophily.
6 Conclusion
CPGNN models an interpretable class compatibility matrix within GNNs and evaluates the approach under fewer-training-sample and featureless settings. The paper reports theoretical and empirical evidence addressing limitations of existing GNNs, especially for heterophilous graphs without contextual features.
- CPGNN integrates an interpretable class compatibility matrix into the GNN framework.
- The evaluation uses fewer training samples and a featureless setup to examine performance under more realistic conditions.
- Theoretical and empirical analyses address existing GNN limitations, particularly for heterophilous graphs without contextual features.
A Synthetic Graph Generation
The synthetic graph generator modifies preferential attachment so compatibility can be controlled while preserving a power-law degree distribution. The syn-products construction uses ogbn-products as a reference graph and specifies class and compatibility parameters.
- Modified preferential attachment generates synthetic graphs with controllable compatibility matrices and power-law degree distributions.
- For syn-products, ogbn-products serves as the reference graph, with 10 classes and 10,000 total nodes.
- The syn-products classes are balanced at 1,000 nodes each, while diagonal compatibility values share a common parameter h.
B More Experimental Setups
The experimental setup uses official implementations for multiple GNN baselines and provides a released CPGNN implementation. Experiments run on specified workstation hardware and TensorFlow software.
- Baselines include GCN, GCN-Cheby, GraphSAGE, MixHop, GAT, H2GCN, and MLP.
- The MLP baseline uses the H2GCN implementation configured with the M64-R-MO network setup.
- The CPGNN implementation is released at the GemsLab/CPGNN repository.
- Experiments use an AMD Ryzen 9 3900X CPU, 64GB RAM, an Nvidia Quadro P6000 GPU, Ubuntu 20.04.1 LTS, and TensorFlow 2.2.
C Hyperparameter Tuning
The appendix describes hyperparameter selection, synthetic graph-generation inputs, and benchmark evaluation details. It also identifies the table and ablation-study settings used to report accuracy across homophily ratios.
- A Synthetic Graph Generation: Synthetic graph generation takes class sizes, an initial graph size, edge count per added node, a target compatibility matrix, and reference graph mappings as inputs.
- A Synthetic Graph Generation: The generator initializes labels and nodes, creates class-balanced labels, then adds nodes and preferentially selected edges.
- A Synthetic Graph Generation: New nodes select m existing nodes without replacement using degree-weighted probabilities before edges are added.
- C Hyperparameter Tuning: Reported benchmark results use hyperparameters yielding the best average validation accuracy.
- C Hyperparameter Tuning: CPGNN prior-belief estimators share hidden-layer architecture with their corresponding MLP and GCN-Cheby baselines for fair comparison.
- C Hyperparameter Tuning: Tables A.1 and A.2 report mean accuracy and standard deviation across homophily ratios for feature-based classification and CPGNN-MLP-1 ablations.
D Detailed Results
The detailed results report contextual-feature results on syn-products and ablation findings for initialization, regularization, end-to-end training, and pretraining.
- Table A.1 provides detailed node-classification results with contextual features on syn-products.
- Pretraining the prior-belief estimator improves performance by up to 2% under heterophily, although the differences are small.