PaperlayerView exact revision on arXiv

Source-linked AI summary

GBK-GNN: Gated Bi-Kernel Graph Neural Networks for Modeling Both Homophily and Heterophily

Lun Du, Xiaozhou Shi, Qiang Fu, Xiaojun Ma, Hengyu Liu, Shi Han, Dongmei Zhang

arXiv:2110.15777v3cs.LG

TL;DR

GNNs remain limited in modeling heterophily and mixed local neighborhoods because conventional architectures use one feature-transformation kernel. GBK-GNN introduces two relationship-specific kernels and a selection gate, and experiments report consistent gains over baselines across graphs with varied homophily. The paper also identifies a scope boundary for extending the bi-kernel design to multiclass heterophily.

  • Problem

    GNNs model homophily more reliably than heterophily, and conventional single-kernel transformations are limited for mixed local neighborhoods.

  • Method

    GBK-GNN uses separate kernels for homophily and heterophily together with a selection gate that chooses between them for node pairs.

  • Results

    GBK-GNN outperforms most baselines on seven graphs with varied Homophily Ratios, with the largest reported error-rate reduction reaching 32.89%.

  • Takeaways & Limitations

    The approach can balance performance across nodes with different homophily-heterophily properties while improving performance across evaluated graphs.

  • Takeaways & Limitations

    For multiclass node classification, the current bi-kernel design does not yet model each possible heterophilous class-label combination separately.

Abstract

from arXiv · show

Graph Neural Networks (GNNs) are widely used on a variety of graph-based machine learning tasks. For node-level tasks, GNNs have strong power to model the homophily property of graphs (i.e., connected nodes are more similar) while their ability to capture the heterophily property is often doubtful. This is partially caused by the design of the feature transformation with the same kernel for the nodes in the same hop and the followed aggregation operator. One kernel cannot model the similarity and the dissimilarity (i.e., the positive and negative correlation) between node features simultaneously even though we use attention mechanisms like Graph Attention Network (GAT), since the weight calculated by attention is always a positive value. In this paper, we propose a novel GNN model based on a bi-kernel feature transformation and a selection gate. Two kernels capture homophily and heterophily information respectively, and the gate is introduced to select which kernel we should use for the given node pairs. We conduct extensive experiments on various datasets with different homophily-heterophily properties. The experimental results show consistent and significant improvements against state-of-the-art GNN methods.

1 INTRODUCTION

GNNs often handle homophily better than heterophily, while global graph assumptions can overlook substantial local variation. GBK-GNN addresses mixed neighborhoods with two kernels and a learnable selection gate.

  • GNNs commonly perform better on homophilous graphs, whereas their ability to capture heterophily remains doubtful.
  • Existing methods can also under-model homophily because they treat it as globally consistent across the graph.
  • Local homophily varies substantially: Texas contains many mixed-state nodes, and about 30% of Cora nodes are mixed-state.
  • GBK-GNN uses two kernels to model homophily and heterophily separately, with a selection gate choosing the kernel for each node pair.
  • GBK-GNN outperforms most baselines on seven graphs, with the largest reported error-rate reduction reaching 32.89%.

2 PRELIMINARIES AND DEFINITIONS

This section defines graph data, node classification, GNN representation learning, and homophily measures. It distinguishes global Homophily Ratio from node-level measurements of local neighborhoods.

  • A graph is represented as G = (V, E, X, Y), comprising nodes, edges, node features, and node labels.
  • Node classification learns Q(Y|G; Θ) to assign categories to unlabeled nodes in a single graph using partially observed labels.
  • A general GNN transforms node features with a learnable function and aggregates transformed neighbor features through a permutation-invariant operator.
  • Homophily means connected nodes tend to share labels, whereas heterophily means connected nodes tend to have dissimilar labels.
  • Global Homophily Ratio measures the whole graph, while Node-level Homophily Ratio measures same-label edges around an individual center node.

3 GENERALIZATION BOUND OF GCN WITH REGARD TO HOMOPHILY RATIO

The section analyzes GCN generalization across homophily levels using representation consistency and shows that mixed homophily-heterophily neighborhoods can destroy discriminative ability. Under stated binary-classification assumptions, the complexity measure diverges when homophily and heterophily neighbors are similarly balanced.

  • 3.1 Complexity Measure Based View for Neural Networks Generalization: The analysis uses Consistency of Representations, based on the Davies-Bouldin Index, as a complexity measure for GCN generalization.Lower complexity corresponds to better generalization; the measure compares within-class scatter with between-class separation.
  • 3.2 Generalization Bound Analysis and Failure Reason of GCN: The theoretical analysis assumes binary classification, equal node degree, self-loops, neighbor-label probabilities P0 and P1, and no nonlinear activation.The complexity measure uses the Davies-Bouldin Index with p=2.
  • 3.2 Generalization Bound Analysis and Failure Reason of GCN: When |P0 + P1 − 1| → 0, the Consistency of Representations complexity measure converges to +∞ for GCNs with any nonzero kernel.The theorem concludes that GCN loses generalization ability in this regime.
  • 3.2 Generalization Bound Analysis and Failure Reason of GCN: A similar balance of homophily and heterophily neighbors causes GCN aggregation to smooth outputs from different classes and reduce discrimination despite distinguishable initial features.This inter-class smoothness helps explain why GCN may perform no better than a naive MLP on graphs with varying homophily levels.

4 GATED BI-KERNEL GRAPH NEURAL NETWORKS

GBK-GNN combines two kernels for homophily and heterophily pairs with a learnable gate that selects between them. Its objective jointly trains node classification and gate prediction, while the design targets the distinguishability limitations of single-kernel GCNs.

  • Bi-Kernel Feature Transformation: GBK-GNN uses separate kernels for homophily and heterophily node pairs.The bi-kernel feature transformation is one of the model’s two main differences from vanilla GNNs.
  • Bi-Kernel Feature Transformation: The two kernels can adjust relations between class proportions and provide extra distinguishability when original features are weakly discriminative.The homophily kernel is W_s, the heterophily kernel is W_d, and the second term can help when ||μ_X1 − μ_X0|| → 0.
  • Bi-Kernel Feature Transformation: Unlike GAT’s always-positive attention weights, GBK-GNN can model positive and negative correlations with positive- and negative-definite kernels.This design is intended to represent both similarity and dissimilarity between node features.
  • Kernel Selection Gate: A learnable gate adaptively selects the corresponding kernel for each node pair.The gate discriminates node pairs using a learnable function and produces a gate signal.
  • Loss Design and Optimization: The model jointly optimizes a task loss and a gate prediction loss, with λ balancing the two losses.The gate prediction loss is an additional cross-entropy loss applied at each layer.

5 EXPERIMENTS

The experiments evaluate GBK-GNN on real-world homophily and heterophily graph datasets for node classification against state-of-the-art models.

  • Experimental Setup: GBK-GNN is evaluated on real-world homophily and heterophily graph datasets for node classification.The study compares its empirical performance with other state-of-the-art models.

5.1 Datasets

The evaluation uses seven commonly studied PyTorch-Geometric datasets spanning citation, WebKB, and actor-network graphs. Homophily ratio distinguishes datasets according to the fraction of same-label edges.

  • Dataset Overview: The experiments use seven datasets from PyTorch-Geometric that are commonly used in GNN research.The datasets include Cora, CiteSeer, PubMed, Wisconsin, Cornell, Texas, and Actor.
  • Dataset Overview: Homophily ratio is the fraction of edges connecting nodes with the same label.Ratios near 1 indicate homophily, while ratios near 0 indicate heterophily.
  • Homophily Datasets: Cora, CiteSeer, and PubMed are citation networks whose nodes are papers and whose edges represent citations.Their bag-of-words features and high homophily ratios make them homophily datasets.
  • Heterophily Datasets: Wisconsin, Cornell, and Texas are WebKB subdatasets representing web pages linked by hyperlinks.Their nodes are classified into five categories: student, project, course, staff, and faculty.
  • Heterophily Datasets: Actor is an actor-only subgraph in which edges indicate co-occurrence on the same Wikipedia page.The node-classification task assigns actors to five categories based on words in their Wikipedia pages.
  • Heterophily Datasets: The WebKB and Actor datasets have relatively low homophily ratios and are treated as heterophily datasets.

5.2 Baselines

GBK-GNN is compared with heterophily-focused methods and general graph neural network baselines, including models based on compatibility, neighborhood separation, geometric aggregation, and inductive feature use.

  • Baseline Categories: The comparison includes three types of state-of-the-art heterophily methods and six graph neural network-based methods.
  • Heterophily Baselines: CPGNN models class-connection likelihoods with a compatibility matrix, while H2GCN separates ego and neighbor embeddings and uses higher-order neighborhoods.
  • Heterophily Baselines: GEOM-GCN uses geometric aggregation in graph and latent space, and DNN provides a basic fully connected neural network baseline.
  • GNN Baselines: GraphSAGE is an inductive framework that uses node features to generate embeddings for previously unseen data.

5.3 Experimental Setup

Experiments use public data splits and matched optimization settings across models. Each experiment runs with fixed hidden size and training duration, while key hyperparameters are searched over the same space for fairness.

  • Public data splits assign 60% of nodes to training, 20% to validation, and 20% to testing.
  • Experiments use Adam, 16 hidden units, and 500 training epochs for every model.
  • Learning rate, weight decay, and λ are searched over the same-sized hyperparameter space for all models.

5.4 Results

GBK-GNN achieves strong node-classification performance across homophily and heterophily datasets, including under different training splits and homophily-ratio ranges. Its classification gains do not completely depend on perfect gate accuracy.

  • 5.4.1 Results: GBK-GNN achieves state-of-the-art performance on all seven evaluated datasets.Relative error-rate reductions versus second-place models range from 5.25% to 32.89% across the reported datasets.
  • 5.4.1 Results: Relative error-rate reductions versus second-place models reach 32.89% on Wisconsin, 11.37% on Cornell, and 22.20% on Texas.
  • 5.4.2 Results: GBK-GNN has the best performance on most training splits, significantly outperforming baselines on Cornell and Texas.
  • 5.4.3 Results: GBK-GNN performs well for nodes with both low and high homophily ratios, although sparse test proportions can increase variance.The authors attribute the pattern to different contributions from the homophily and heterophily kernels.
  • 5.4.4 Results: Gate effectiveness does not completely depend on gate accuracy, because Cornell and Texas achieve better classification despite lower gate accuracy.

6 RELATED WORK

Related work covers foundational GNN architectures and methods designed for heterophilous graphs. The cited evaluation tables organize comparisons across dataset splits and homophily-ratio or gate-accuracy analyses.

  • Foundational GNNs: Foundational GNN work includes ChebNet, GCN, GraphSAGE, and GAT for graph representation learning.
  • Heterophily methods: Heterophily-focused methods include AMGCN, which uses feature-similarity graphs and separate GCNs, and CPGNN, which models cross-class connection likelihoods.
  • Evaluation tables: Table 3 evaluates GBK-GNN and other GNN models across different splits of Cora and CiteSeer.
  • Evaluation tables: Table 4 evaluates GBK-GNN and other GNN models across different splits of Cornell and Texas.
  • Evaluation tables: Tables 5 and 6 report GBK-GNN accuracy across homophily-ratio ranges and the classification accuracy of its learned gate.

7 CONCLUSION AND FUTURE WORK

The paper identifies locally mixed homophily and heterophily as a limitation of traditional GNNs and addresses it with GBK-GNN’s two kernels and selection gate. Future work extends this idea to finer-grained multi-kernel modeling for multiclass heterophily.

  • Conclusion: Node-level homophily analysis reveals substantial variation across local regions, including mixed neighborhoods within globally homophilous graphs.
  • Conclusion: GBK-GNN uses separate kernels for homophily and heterophily and a selection gate for corresponding kernel selection.
  • Conclusion: Extensive evaluation shows a significant gain, supporting the effectiveness of the proposed approach.
  • Future work: Future work proposes extending the bi-kernel design to multiple kernels for distinct heterophilous class-label combinations in multiclass node classification.
Loading 2110.15777v3…