Homophily Edge Augment Graph Neural Network for High-Class Homophily Variance Learning

Area of Science:

• Machine Learning
• Graph Theory
• Data Mining

Background:

• Graph Neural Networks (GNNs) excel at learning graph data features.
• Vanilla GNNs show suboptimal performance in graph anomaly detection tasks.
• High Class Homophily Variance (CHV) is identified as the cause of GNNs' poor performance in anomaly detection.

Purpose of the Study:

• To theoretically prove and address the impact of high CHV on GNN performance in anomaly detection.
• To propose a novel GNN model, HEAug, designed to mitigate the effects of CHV.
• To enhance the classification accuracy of GNNs in graph anomaly detection.

Main Methods:

• Proposed and theoretically proved the Class Homophily Variance (CHV) characteristic as a key factor in GNN anomaly detection.
• Developed the Homophily Edge Augment Graph Neural Network (HEAug) model.
• HEAug generates new edges with low CHV using a self-attention mechanism and modifies the loss function to penalize heterophilic edges.

Main Results:

• HEAug achieved state-of-the-art performance across eight benchmark datasets, including anomaly detection, edgeless node classification, and adversarial attack scenarios.
• Demonstrated the effectiveness of the CHV theory and HEAug model in various scenarios, including a novel heterophily attack.
• Showcased HEAug's ability to leverage feature-relevant but unconnected nodes.

Conclusions:

• High CHV is a critical limitation for GNNs in anomaly detection.
• The proposed HEAug model effectively addresses the CHV challenge, leading to superior performance.
• The findings provide a theoretical foundation and a practical solution for improving GNNs in graph anomaly detection and related tasks.