Selective Feature-Node Transformation for Heterophilic Graph Learning

Graph neural networks (GNNs) can struggle on heterophilic graphs, where neighborhood aggregation mixes information from nodes with different labels. Feature-node transformation addresses this challenge by connecting original nodes through shared discrete features. However, exhaustive transformation includes every active feature, regardless of its predictive relevance or structural cost. This work proposes a selective transformation framework that identifies useful auxiliary structure under a feature-node budget while retaining the original attributes and topology. A relevance score combines normalized mutual information, pairwise label agreement above chance, coverage, and incidence-edge cost. Support-based shrinkage and component standardization balance these signals when labeled observations are limited. The selected incidence graph is integrated with the original topology through signed, feature-aware gated propagation. Analysis establishes exact auxiliary graph sizes and a sufficient condition for above-chance agreement along selected two-hop paths. Evaluation on six node-classification benchmarks shows substantial reductions in auxiliary nodes and edges, accompanied by lower runtime and memory measurements. Predictive outcomes vary across datasets, while matched-budget comparisons and ablations clarify when relevance scoring helps and when simpler criteria remain competitive. These findings establish selective feature-node construction as a practical approach to balancing predictive performance and computational cost in graph learning.