Summary
Identifying unknown types of nodes in networks is hard when connected nodes don’t share the same labels, a common situation in real-world graphs. The authors found that existing methods struggle because they assume connected nodes are usually similar, which isn’t true in many cases. They created a new approach called HOPE that better handles these mixed or heterophilic graphs by carefully deciding how to combine information from neighboring nodes and by generating special examples to represent unknown types. Their method helps the system better recognize when it encounters unknown nodes, improving accuracy and reliability. Tests on various datasets showed that HOPE worked better than previous techniques.
open-set classificationnode classificationgraph neural networksheterophilyhomophilymulti-hop structurepseudo-extrapolationneighborhood aggregationunknown-class rejectionlogit margin regularization
Authors
Yumeng Dai, Yue Tan, Yixin Liu, Chenxu Wang, Pinghui Wang, Tao Qin
Abstract
Standard open-set node classification methods rely on the homophily assumption, where connected nodes share labels. However, real-world graphs are often heterophilic, exposing the limitations of current methods and posing new challenges to open-set node classification. On the one hand, cross-class connectivity causes representations from different known or unknown classes to become intertwined after aggregation, undermining their discriminative capacity. On the other hand, structural mixture invalidates threshold-based open-set methods and cross-class feature interpolation, leading to unreliable unknown-class rejection. To address these challenges, we propose HOPE, a Heterophily-aware Open-set node classification method with Pseudo-Extrapolation. To adapt open-set graph neural networks (GNNs) to heterophilic scenarios, HOPE uses a structure-augmented feature initialization layer to capture multi-hop structural patterns. Meanwhile, we design a trustworthy neighborhood aggregation mechanism for standard GNNs to dynamically filter noisy cross-class neighbors. To enhance unknown-class rejection, we introduce a heterophily-guided pseudo-extrapolation strategy. It dynamically maintains known-class centers and extrapolates along cross-class neighborhood displacement directions, synthesizing pseudo-unknown proxies near structurally ambiguous regions. Finally, we optimize the network with joint classification and logit margin regularization, routing synthetic proxies into a dedicated rejection slot without imposing geometric margin constraints in the representation space. Extensive experiments on multiple datasets show that HOPE consistently outperforms state-of-the-art models, validating its effectiveness, robustness, and efficiency.