Abstract
Graph Convolutional Networks (GCNs) are highly effective for homophilic graphs but exhibit significant fragility when applied to heterophilic networks—where connected nodes often belong to different classes. This paper identifies structural out-of-distribution (OOD) issues as a primary cause of this vulnerability, characterized by a "right-shift" in node-level heterophily distributions under attack. We propose LHS (Latent Homophilic Structures), a framework that learns a purified, homophilic latent structure to enhance GCN robustness. LHS utilizes a self-expressive generator, dual-view contrastive learning, and a truncated threshold mechanism to filter malicious edges. Experimental results across nine benchmarks demonstrate that LHS significantly outperforms state-of-the-art models under various structural attacks while maintaining competitive performance on clean graphs.
Introduction
The success of Graph Convolutional Networks (GCNs) largely hinges on the homophily assumption: the tendency of similar nodes to be connected. However, many real-world datasets, such as transaction networks or protein-protein interactions, are heterophilic. While recent research has adapted GCNs for heterophily, these models remain susceptible to adversarial structural perturbations.
As shown in Figure 1, structural attacks—whether through training set poisoning or test-time evasion—can lead to a precipitous drop in classification accuracy. The authors identify that these attacks exploit a structural out-of-distribution (OOD) problem, where the distribution of graph properties at test time deviates significantly from the training distribution.
Methodology: The LHS Framework
To address these vulnerabilities, we introduce the Latent Homophilic Structures (LHS) framework. LHS aims to "purify" the input graph by uncovering a hidden homophilic structure that is more resilient to noise and attacks. The framework consists of three core components:
- Self-Expressive Generator: This module captures global structural patterns by representing each node's features as a linear combination of other nodes' features. This global perspective avoids the pitfalls of local k-Nearest Neighbor (kNN) approaches, which are easily manipulated by local edge injections.
- Dual-View Contrastive Learner: To refine the latent structure, LHS employs contrastive learning across two augmented views of the graph. By maximizing the agreement between representations of the same node and applying pairwise constraints to pull nodes of the same class together, the model learns a more discriminative and stable latent space.
- Truncated Threshold GCN: The learned "soft" connections are filtered using a confidence threshold ($\sigma$). This step discards low-confidence edges, effectively removing the malicious or noisy heterophilic relations introduced by an attacker.
Analysis of Structural Vulnerability: The Right-Shift Phenomenon
A key contribution of this work is the identification of the "right-shift" phenomenon. By analyzing the distribution of node-level heterophily ($\mathcal{H}$), the authors found that adversarial attacks consistently shift the distribution toward higher heterophily values.
As illustrated in Figure 2, the magnitude of this shift is directly proportional to the degradation in classification accuracy. By forcing the model to operate on a latent homophilic structure, LHS effectively counteracts this shift, transforming a vulnerable heterophilic problem into a robust homophilic one.
Experimental Results
LHS was evaluated against nine benchmark datasets, including six heterophilic graphs (e.g., Squirrel, Chameleon, Actor) and three homophilic graphs (Cora, Citeseer, Pubmed).
- Robustness to Poisoning: On the Squirrel dataset, LHS maintained significantly higher accuracy than the baseline GPNN, outperforming it by nearly 20 percentage points at high perturbation rates.
- Evasion Attack Resilience: In "Injected" evasion attacks designed to maximize heterophily, LHS achieved an average accuracy of 62.41% across five datasets, compared to 54.89% for the best baseline (BM-GCN).
- General Performance: LHS also set new performance benchmarks on clean heterophilic datasets, such as Wisconsin (88.32%) and Chameleon (72.31%), demonstrating that its structural refinement benefits general classification tasks as well.
Conclusion
LHS provides a robust solution for GCNs on heterophilic graphs by shifting the focus from the noisy, potentially malicious input structure to a learned latent homophilic structure. By addressing the structural OOD problem and the "right-shift" phenomenon, LHS achieves state-of-the-art robustness and performance across diverse graph types. Future work will explore extending this latent structure approach to other graph-based tasks like link prediction and community detection.
Summary updated