Universally Robust Graph Neural Networks by Preserving Neighbor
  Similarity
Yulin Zhu Yuni Lai Xing Ai Kai Zhou
Despite the tremendous success of graph neural networks in learning
relational data, it has been widely investigated that graph neural networks are
vulnerable to structural attacks on homophilic graphs. Motivated by this, a
surge of robust models is crafted to enhance the adversarial robustness of
graph neural networks on homophilic graphs. However, the vulnerability based on
heterophilic graphs remains a mystery to us. To bridge this gap, in this paper,
we start to explore the vulnerability of graph neural networks on heterophilic
graphs and theoretically prove that the update of the negative classification
loss is negatively correlated with the pairwise similarities based on the
powered aggregated neighbor features. This theoretical proof explains the
empirical observations that the graph attacker tends to connect dissimilar node
pairs based on the similarities of neighbor features instead of ego features
both on homophilic and heterophilic graphs. In this way, we novelly introduce a
novel robust model termed NSPGNN which incorporates a dual-kNN graphs pipeline
to supervise the neighbor similarity-guided propagation. This propagation
utilizes the low-pass filter to smooth the features of node pairs along the
positive kNN graphs and the high-pass filter to discriminate the features of
node pairs along the negative kNN graphs. Extensive experiments on both
homophilic and heterophilic graphs validate the universal robustness of NSPGNN
compared to the state-of-the-art methods.