Semi-Supervised Learning with Heterophily
This work addresses semi-supervised learning for graph data with heterophily, which is incremental as it builds upon and improves existing label propagation methods.
The authors tackled the problem of semi-supervised learning on graphs with heterophily, where nodes may connect to dissimilar classes, by developing a family of linear inference algorithms that generalize existing methods like Linearized Belief Propagation. The result is a fast algorithm that achieves superior accuracy compared to LinBP, with classification performed in the same time but without prior knowledge of node compatibilities.
We derive a family of linear inference algorithms that generalize existing graph-based label propagation algorithms by allowing them to propagate generalized assumptions about "attraction" or "compatibility" between classes of neighboring nodes (in particular those that involve heterophily between nodes where "opposites attract"). We thus call this formulation Semi-Supervised Learning with Heterophily (SSLH) and show how it generalizes and improves upon a recently proposed approach called Linearized Belief Propagation (LinBP). Importantly, our framework allows us to reduce the problem of estimating the relative compatibility between nodes from partially labeled graph to a simple optimization problem. The result is a very fast algorithm that -- despite its simplicity -- is surprisingly effective: we can classify unlabeled nodes within the same graph in the same time as LinBP but with a superior accuracy and despite our algorithm not knowing the compatibilities.