Graph Neural Networks (GNNs) are popular machine learning methods for
modeling graph data. A lot of GNNs perform well on homophily graphs while
having unsatisfactory performance on heterophily graphs. Recently, some
researchers turn their attention to designing GNNs for heterophily graphs by
adjusting the message passing mechanism or enlarging the receptive field of the
message passing. Different from existing works that mitigate the issues of
heterophily from model design perspective, we propose to study heterophily
graphs from an orthogonal perspective by rewiring the graph structure to reduce
heterophily and making the traditional GNNs perform better. Through
comprehensive empirical studies and analysis, we verify the potential of the
rewiring methods. To fully exploit its potential, we propose a method named
Deep Heterophily Graph Rewiring (DHGR) to rewire graphs by adding homophilic
edges and pruning heterophilic edges. The detailed way of rewiring is
determined by comparing the similarity of label/feature-distribution of node
neighbors. Besides, we design a scalable implementation for DHGR to guarantee
high efficiency. DHRG can be easily used as a plug-in module, i.e., a graph
pre-processing step, for any GNNs, including both GNN for homophily and
heterophily, to boost their performance on the node classification task. To the
best of our knowledge, it is the first work studying graph rewiring for
heterophily graphs. Extensive experiments on 11 public graph datasets
demonstrate the superiority of our proposed methods.

通过重新构建异质图的图结构，来提高传统的图神经网络在异质图上的性能，我们提出了 Deep Heterophily Graph Rewiring (DHGR) 的方法，并进行了全面的实证研究和分析，验证了其潜力以及其可用性，可作为任何 GNN 的插件模块，能够提高任何 GNNs，在结点分类任务上的性能。

使异质性图更适合 GNN: 一种图重连方法

Make Heterophily Graphs Better Fit GNN: A Graph Rewiring Approach

Graph neural networks are experiencing a surge of popularity within the
machine learning community due to their ability to adapt to non-Euclidean
domains and instil inductive biases. Despite this, their stability, i.e., their
robustness to small perturbations in the input, is not yet well understood.
Although there exists some results showing the stability of graph neural
networks, most take the form of an upper bound on the magnitude of change due
to a perturbation in the graph topology. However, the change in the graph
topology captured in existing bounds tend not to be expressed in terms of
structural properties, limiting our understanding of the model robustness
properties. In this work, we develop an interpretable upper bound elucidating
that graph neural networks are stable to rewiring between high degree nodes.
This bound and further research in bounds of similar type provide further
understanding of the stability properties of graph neural networks.

本文研究图神经网络 (GNN) 的稳定性，提出一种可解释的上界，表明 GNN 对于高度连通节点之间的重连是稳定的，这为我们进一步了解 GNN 的性质提供了帮助。

图卷积神经网络在边重连下的稳定性研究

On the Stability of Graph Convolutional Neural Networks under Edge  Rewiring

We describe the structure of the graphs with the smallest average distance
and the largest average clustering given their order and size. There is usually
a unique graph with the largest average clustering, which at the same time has
the smallest possible average distance. In contrast, there are many graphs with
the same minimum average distance, ignoring their average clustering. The form
of these graphs is shown with analytical arguments. Finally, we measure the
sensitivity to rewiring of this architecture with respect to the clustering
coefficient, and we devise a method to make these networks more robust with
respect to vertex removal.

描述了在给定序号和规模的情况下，具有最小平均距离和最大平均聚类的图的结构，测量了此结构对于修建顶点的影响以提高其健壮性，并阐述了这些网络的形式和分析论据