Generation is better than Modification: Combating High Class Homophily
  Variance in Graph Anomaly Detection
Rui Zhang Dawei Cheng Xin Liu Jie Yang Yi Ouyang Xian Wu Yefeng Zheng
Graph-based anomaly detection is currently an important research topic in the
field of graph neural networks (GNNs). We find that in graph anomaly detection,
the homophily distribution differences between different classes are
significantly greater than those in homophilic and heterophilic graphs. For the
first time, we introduce a new metric called Class Homophily Variance, which
quantitatively describes this phenomenon. To mitigate its impact, we propose a
novel GNN model named Homophily Edge Generation Graph Neural Network (HedGe).
Previous works typically focused on pruning, selecting or connecting on
original relationships, and we refer to these methods as modifications.
Different from these works, our method emphasizes generating new relationships
with low class homophily variance, using the original relationships as an
auxiliary. HedGe samples homophily adjacency matrices from scratch using a
self-attention mechanism, and leverages nodes that are relevant in the feature
space but not directly connected in the original graph. Additionally, we modify
the loss function to punish the generation of unnecessary heterophilic edges by
the model. Extensive comparison experiments demonstrate that HedGe achieved the
best performance across multiple benchmark datasets, including anomaly
detection and edgeless node classification. The proposed model also improves
the robustness under the novel Heterophily Attack with increased class
homophily variance on other graph classification tasks.