Evolving Computation Graphs
This addresses a limitation in GNNs for real-world scenarios with heterophilic data, though it is an incremental improvement building on prior theoretical insights.
The paper tackles the problem of graph neural networks (GNNs) underperforming on heterophilic datasets where connections do not imply similar node classes, by proposing Evolving Computation Graphs (ECGs) to rewire graphs towards adding edges between likely same-class nodes, resulting in improved performance over baselines on diverse heterophilous datasets.
Graph neural networks (GNNs) have demonstrated success in modeling relational data, especially for data that exhibits homophily: when a connection between nodes tends to imply that they belong to the same class. However, while this assumption is true in many relevant situations, there are important real-world scenarios that violate this assumption, and this has spurred research into improving GNNs for these cases. In this work, we propose Evolving Computation Graphs (ECGs), a novel method for enhancing GNNs on heterophilic datasets. Our approach builds on prior theoretical insights linking node degree, high homophily, and inter vs intra-class embedding similarity by rewiring the GNNs' computation graph towards adding edges that connect nodes that are likely to be in the same class. We utilise weaker classifiers to identify these edges, ultimately improving GNN performance on non-homophilic data as a result. We evaluate ECGs on a diverse set of recently-proposed heterophilous datasets and demonstrate improvements over the relevant baselines. ECG presents a simple, intuitive and elegant approach for improving GNN performance on heterophilic datasets without requiring prior domain knowledge.