Refining Latent Homophilic Structures over Heterophilic Graphs for Robust Graph Convolution Networks

Chenyang Qiu, Guoshun Nan, Tianyu Xiong, Wendi Deng, Di Wang, Zhiyang Teng, Lijuan Sun, Qimei Cui, Xiaofeng Tao

Introduction

Graph Convolutional Networks (GCNs) have become a cornerstone of graph-based machine learning. While initial designs focused on homophilic graphs—where connected nodes share similar features or labels—recent research has expanded into heterophilic graphs, such as dating networks or predator-prey systems, where neighbors are often dissimilar. However, these specialized heterophilic GCNs exhibit a critical vulnerability: they are remarkably fragile under structural attacks. This paper introduces LHS (Latent Homophilic Structures), a framework designed to uncover hidden homophilic patterns within heterophilic data to provide a robust defense against malicious edge perturbations.

The Structural OOD Problem

The primary challenge identified by the authors is a phenomenon termed the "right-shift" in node-level heterophily distribution. In a standard setting, a model is trained on a graph with a specific distribution of heterophily. During a structural attack, an adversary adds or removes edges, causing the test-time graph to deviate significantly from the training distribution.

The "right-shift" phenomenon: structural attacks cause the heterophily distribution of the graph to shift, creating an out-of-distribution (OOD) scenario that degrades GCN performance.

This shift creates a structural Out-of-Distribution (OOD) issue. As the distribution of heterophily shifts, the assumptions made by heterophilic GCNs during training no longer hold, leading to a collapse in classification accuracy. The authors quantitatively demonstrate that performance degradation is directly proportional to the magnitude of this distributional shift.

The LHS Framework

To counter this vulnerability, the LHS framework shifts the focus from the noisy, potentially compromised input graph to a learned latent homophilic structure. The framework operates through four key stages:

  1. Self-Expressive Generator: Utilizing a self-expressive technique, the model represents each node's features as a linear combination of others. This allows the discovery of global structural information in a low-dimensional subspace, forming an initial latent structure ($S^*$).
  2. Dual-view Contrastive Learner: To filter noise from $S^*$, the model employs contrastive learning across two corrupted views of the graph. A pairwise constraint is integrated to explicitly pull nodes of the same class closer in the embedding space.
  3. Iterative Refinement: The latent structure is iteratively updated, bootstrapping the learned connections with the original graph data to maintain a balance between raw observations and discovered homophilic patterns.
  4. Truncated Threshold GCN: A thresholding mechanism is applied to prune weak connections, ensuring the resulting graph remains sparse and computationally efficient.

Adversarial Scenarios and Evaluation

The robustness of LHS was evaluated against several attack vectors across nine benchmark datasets, including both heterophilic (e.g., Squirrel, Chameleon) and homophilic (e.g., Cora) graphs.

Visualizing structural attacks: (a) Poisoning attacks perturb edges via a meta-adversarial module before training; (c) Injected evasion attacks lower the homophily ratio by injecting heterophilic relations during testing.

The researchers focused on two primary threat models:

  • Poisoning Attacks: Modifying the graph structure prior to the training phase to degrade the model's learned parameters.
  • Evasion Attacks: Perturbing the graph during the inference phase, specifically targeting the OOD shift to fool a pre-trained model.

Key Results and Insights

Experimental results demonstrate that LHS significantly outperforms state-of-the-art robust GCNs. On the Squirrel dataset under poisoning attacks, LHS achieved a performance lead of up to 20 percentage points over baselines like ProGNN. In OOD evasion scenarios, LHS maintained an accuracy of 68.76% on Squirrel, while the strongest baseline trailed at 57.30%.

A crucial insight from the study is that homophily acts as a natural defense. Models that successfully find homophilic patterns—even within heterophilic graphs—are inherently more resilient to local edge perturbations. By prioritizing global structural properties over local neighborhood relationships, LHS makes it significantly harder for attackers to deceive the model.

Conclusion and Future Work

LHS provides a robust path forward for GCNs operating on heterophilic graphs. By refining a latent homophilic structure, it effectively mitigates the performance degradation caused by structural OOD shifts. While the framework shows excellent generalization and robustness, future work will focus on improving scalability for billion-scale graphs and further automating hyperparameter tuning. Combining LHS with advanced adversarial training could lead to even more resilient graph neural architectures.

Summary updated

Abstract

Graph convolution networks (GCNs) are extensively utilized in various graph tasks to mine knowledge from spatial data. Our study marks the pioneering attempt to quantitatively investigate the GCN robustness over omnipresent heterophilic graphs for node classification. We uncover that the predominant vulnerability is caused by the structural out-of-distribution (OOD) issue. This finding motivates us to present a novel method that aims to harden GCNs by automatically learning Latent Homophilic Structures over heterophilic graphs. We term such a methodology as LHS. To elaborate, our initial step involves learning a latent structure by employing a novel self-expressive technique based on multi-node interactions. Subsequently, the structure is refined using a pairwisely constrained dual-view contrastive learning approach. We iteratively perform the above procedure, enabling a GCN model to aggregate information in a homophilic way on heterophilic graphs. Armed with such an adaptable structure, we can properly mitigate the structural OOD threats over heterophilic graphs. Experiments on various benchmarks show the effectiveness of the proposed LHS approach for robust GCNs.
BibTeX
@inproceedings{qiu2024refining,
  author = {Chenyang Qiu and Guoshun Nan and Tianyu Xiong and Wendi Deng and Di Wang and Zhiyang Teng and Lijuan Sun and Qimei Cui and Xiaofeng Tao},
  title = {{Refining Latent Homophilic Structures over Heterophilic Graphs for Robust Graph Convolution Networks}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2024},
  doi = {10.1609/aaai.v38i8.28741},
}
Figure