PaperlayerView exact revision on arXiv

Source-linked AI summary

HOPE: Heterophily-Aware Open-Set Node Classification with Pseudo-Extrapolation

Yumeng Dai, Yue Tan, Yixin Liu, Chenxu Wang, Pinghui Wang, Tao Qin

arXiv:2609.08685v1cs.LG

TL;DR

Open-set node classification methods often assume homophily, although cross-class connectivity in heterophilic graphs intertwines known and unknown representations and challenges unknown-class rejection. HOPE combines structural initialization and neighbor filtering with heterophily-guided pseudo-extrapolation and logit-regularized classification. Across multiple benchmarks, the paper reports best or competitive performance against state-of-the-art baselines.

  • Problem

    Existing open-set node classification methods often assume homophily, while heterophilic cross-class connectivity makes known and unknown nodes difficult to distinguish and undermines rejection methods.

    Source: §I · pp. 1–2

  • Method

    HOPE augments features with multi-hop structure, filters untrustworthy neighbors, extrapolates pseudo-unknown proxies along heterophilic directions, and trains a logit-regularized (K + 1)-way classifier.

    Source: §I · p. 2

  • Results

    HOPE achieves the best or competitive performance across evaluated settings against state-of-the-art baselines on multiple benchmarks.

    Source: §VI · p. 10

  • Takeaways & Limitations

    The evaluations support HOPE as a framework for open-set node classification across the heterophilic benchmark settings studied.

    Source: §I · p. 2, §VI · p. 10

Abstract

from arXiv · show

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.

I. INTRODUCTION

Open-set node classification must identify known classes while rejecting unseen classes, but heterophilic connectivity mixes known and unknown nodes and challenges homophily-oriented methods. HOPE combines structural initialization, neighbor filtering, pseudo-unknown generation, and logit-regularized classification; its evaluations report gains over state-of-the-art models.

Motivation

  • Open-set node classification jointly identifies known categories and detects previously unseen categories, rather than forcing unknown nodes into known classes.The introduction describes the risk of conventional closed-set methods assigning unknown nodes to known classes with high confidence.Source: §I · p. 1

Challenges

  • Heterophilic cross-class neighborhoods can overlap known-class representations, while threshold rejection and feature-interpolation proxies can misidentify unknown nodes.The paper identifies representation confusion and unreliable unknown-class rejection as coupled challenges.Source: §I · p. 2

HOPE

  • HOPE combines multi-hop structural initialization, trustworthy neighbor filtering, heterophily-guided pseudo-extrapolation, and a logit-regularized (K + 1)-way classifier.Synthetic proxies are routed to a dedicated rejection slot without explicit geometric margin constraints in representation space.Source: §I · p. 2

Problem

  • HOPE investigates unknown-class topology across homophilic and heterophilic graphs and formalizes open-set node classification under heterophily.The introduction frames whether open-set graph learning can identify unknown nodes in heterophilic graphs.Source: §I · p. 2

Experiments

  • Extensive evaluations on multiple heterophilic benchmarks report that HOPE significantly outperforms state-of-the-art closed-set and open-set models.The reported experiments also characterize its generalizability and robustness as superior.Source: §I · p. 2

II. RELATED WORK

Prior heterophily-aware GNNs address message passing but assume a fixed known label space, while graph open-set methods generally rely on homophily. HOPE instead uses structural extrapolation and a dedicated rejection class for heterophilic open-set graphs.

A. Graph Neural Networks under Heterophily

  • Heterophily-aware GNNs adapt message passing, but the cited approaches assume a fully known label space and therefore do not address unknown test classes.Examples include ego-neighbor separation, geometric mappings, adaptive filtering, and edge discriminators.Source: A. Graph Neural Networks under… · p. 3

B. Open-Set Node Classification on Graphs

  • Existing open-set graph methods use threshold calibration or generative proxies, yet rely on homophily and can blur known and unknown boundaries under severe heterophily.HOPE instead uses structural extrapolation and maps synthetic boundary proxies to a dedicated (K + 1)-th classification slot.Source: B. Open-Set Node Classification on… · p. 3

III. PRELIMINARIES

A. Graph Definitions and Heterophily

  • Edge homophily ratio h is the proportion of edges joining same-label nodes; values near 1 indicate homophily, while values near 0 indicate heterophily.The latter corresponds to edges predominantly linking nodes from distinct categories.Source: A. Graph Definitions and Heterophily · p. 3

B. Open-Set Node Detection Formulation

The formulation distinguishes the known training label space from unseen test classes and treats open-set detection as classifying known nodes while assigning unknown nodes to one rejection slot. HOPE frames heterophily-aware structural mappings and a (K + 1)-way classifier as its response to mixed neighborhoods.

B. Open-Set Node Detection Formulation

  • Open-set recognition permits unknown semantic classes at inference, unlike closed-set classification with identical training and test label spaces.The known training classes are YL; deployment may include unseen classes YU, disjoint from YL.Source: B. Open-Set Node Detection Formulation · p. 3
  • Training uses labeled nodes from known classes, while test nodes include both known-class and unknown-class examples.The remaining nodes are partitioned into validation and test sets.Source: B. Open-Set Node Detection Formulation · p. 3
  • The detection objective maps nodes to a known label or a single unified unknown slot, typically the (K + 1)-th class.The unknown slot rejects nodes from any unseen class.Source: B. Open-Set Node Detection Formulation · p. 3

C. Open-Set GNNs under Heterophily

  • Open-set GNNs produce node representations by propagating ego-features over graph structure, rather than assuming independent samples.The described architecture typically places an open-set classifier after a structural encoder.Source: C. Open-Set GNNs under Heterophily · p. 3
  • Uniform low-pass aggregation in heterophilic graphs mixes conflicting neighbor representations and distorts open-set decision boundaries.The mixing can combine known and unknown semantic spaces in a node's neighborhood.Source: C. Open-Set GNNs under Heterophily · p. 3
  • HOPE responds with heterophily-aware structural mappings and a dedicated (K + 1)-way classifier rather than representation-space distance margins.The prediction selects the class with the highest conditional probability given node features and graph structure.Source: C. Open-Set GNNs under Heterophily · p. 4
  • The rejection slot represents pseudo-unknown variations synthetically extrapolated along heterophilic structural directions.This assigns the K + 1 class to synthetic variations generated along those directions.Source: C. Open-Set GNNs under Heterophily · p. 4

IV. METHODOLOGY

HOPE combines four components for semi-supervised open-set node classification on heterophilic graphs. Its feature initialization appends topology-only multi-hop structural information before message passing.

IV. METHODOLOGY

  • HOPE combines structure-augmented initialization, trustworthy neighborhood aggregation, structural pseudo-extrapolation, and joint classification with logit margin regularization.The framework generates out-of-distribution node boundaries without relying on brittle margin-based constraints.Source: §IV · p. 4

A. Structure-Augmented Feature Initialization

  • The initialization augments raw node attributes with structural encodings so the model can recognize open-set boundary structure before feature propagation.The paper motivates this because known and unknown nodes can be structurally mixed in heterophilic graphs.Source: A. Structure-Augmented Feature… · p. 4
  • Each node receives a precomputed 16-dimensional, topology-only encoding of multi-hop structural characteristics.The encoding uses the diagonal propagation values (P)ii through (P^16)ii; each k-step return pattern summarizes local topology over multiple neighborhood ranges.Source: A. Structure-Augmented Feature… · p. 4
  • The structural encoding is concatenated with original node attributes to create the topology-aware initial representation.The encoding depends only on graph structure, requires no node labels, and is shared across backbone choices.Source: A. Structure-Augmented Feature… · p. 4

B. Trustworthy Neighborhood Aggregation

HOPE filters neighborhood messages before aggregation so cross-class and open-set connections do not indiscriminately introduce misleading information. It aggregates over a trusted homophilic subset while retaining the underlying backbone’s propagation rule.

B. Trustworthy Neighborhood Aggregation

  • Cross-class and open-set connections can introduce misleading messages, so unfiltered averaging may let open-set variants poison known-node representations.HOPE selects reliable, contextually consistent neighbors and aggregates over the resulting trustworthy homophilic subset.Source: B. Trustworthy Neighborhood Aggregation · p. 4
  • An edge discriminator estimates homophily probability, which is combined with hidden-state cosine similarity to score each connection.A strict threshold removes edges with insufficient scores before neighborhood aggregation.Source: B. Trustworthy Neighborhood Aggregation · p. 4
  • HOPE performs normalized aggregation over trusted neighbors and uses a residual connection from the initialization-layer representation.For different backbones, it adds the initialization representation to the backbone’s graph-aware output and applies the same trustworthy aggregation module without changing the backbone’s propagation rule.Source: B. Trustworthy Neighborhood Aggregation · pp. 4–5
  • The module is intended to preserve beneficial homophilic signals while suppressing misleading heterophilic noise for open-set recognition.The architecture also describes multi-hop structural encoding and a unified classifier optimized with known-class, pseudo-unknown, and regularization losses.Source: B. Trustworthy Neighborhood Aggregation · p. 5, Figure 2 · p. 5

C. Pseudo-Unknown Proxy Generation and Classification Loss

HOPE generates pseudo-unknown proxies in structurally ambiguous regions, where heterophilic connections can pull open-set representations into overlaps with known classes. It trains real known nodes and synthetic proxies in a unified classification space with a dedicated unknown slot.

C. Pseudo-Unknown Proxy Generation and Classification Loss

  • Heterophilic connections can pull open-set representations into intersecting zones and ambiguous boundaries of known-class manifolds.HOPE assigns synthetic boundary proxies in these regions to the dedicated (K + 1)-th slot so the classifier can allocate the overlapping regions to unknowns without compacting known clusters.Source: C. Pseudo-Unknown Proxy Generation and… · p. 5
  • During training, HOPE maintains an exponential-moving-average center for each known class and samples structurally ambiguous known nodes as proxy anchors.Anchor selection combines neighborhood entropy and local cross-class connectivity, using statistics from the labeled training-induced subgraph.Source: C. Pseudo-Unknown Proxy Generation and… · pp. 5–6
  • For each anchor, HOPE constructs an outward extrapolation direction from its class center toward heterophilic neighbors and generates a pseudo-unknown representation along that direction.The extrapolation factor is sampled up to a heterophily-adapted bound, while Gaussian perturbations add mild variation for boundary coverage.Source: C. Pseudo-Unknown Proxy Generation and… · p. 6
  • Real labeled nodes are trained with supervised cross-entropy over the first K known-class logits, while generated proxies are trained toward the (K + 1)-th unknown slot.The proxy loss is weighted by the structural sampling weight inherited from its anchor.Source: C. Pseudo-Unknown Proxy Generation and… · p. 6

D. Logit Margin Regularization

HOPE uses a logit margin penalty to keep the unknown rejection logit below the strongest known-class logit for known training nodes. This penalty joins known-node and pseudo-unknown classification losses in the total objective.

D. Logit Margin Regularization

  • The regularization penalty discourages the unknown-slot logit from becoming active for known training nodes by requiring a margin below their strongest known-class logit.The penalty addresses the risk that joint fitting of known nodes and pseudo-unknown proxies pushes the unknown logit excessively high and erodes known-class discrimination.Source: D. Logit Margin Regularization · p. 6
  • Unlike geometric distance constraints in representation space, the soft margin acts directly on logits and preserves the expressiveness of the (K + 1)-way classifier.The paper states that this avoids brittle boundary tuning while preserving known-class representations.Source: D. Logit Margin Regularization · p. 6
  • HOPE’s total objective combines real known-class loss, pseudo-unknown classification loss, and known-class logit regularization.Non-negative hyperparameters scale the pseudo-unknown and regularization terms.Source: D. Logit Margin Regularization · p. 6

A. Experimental Setup

HOPE is evaluated on seven heterophilic graph datasets under an open-set protocol and performs optimally or competitively across almost all evaluation slots. Its design combines structural initialization, selective neighborhood aggregation, pseudo-unknown boundary generation, and logit margin regularization.

B. Performance Comparison

  • 40.05% to 50.04% accuracy and 33.81% to 51.04% Macro-F1 on Roman-Empire with GPR-GNN; HOPE reports the best values for both metrics.Across almost all evaluation slots, HOPE achieves optimal or competitive second-best performance under both metrics.Source: Table II · p. 7, B. Performance Comparison · p. 7

A. Experimental Setup

  • Evaluation covers seven heterophilic datasets, with each dataset’s least-represented class held out as unknown during optimization.The remaining classes form the observed known label space.Source: A. Experimental Setup · pp. 6–7
  • The comparison includes graph encoders and open-set detection frameworks, with GCN used as the default backbone for most open-set methods.GCNII, GPR-GNN, and EG-GCN retain their specialized encoders in the specified analyses.Source: A. Experimental Setup · p. 7
  • Overall Accuracy and Macro-F1 are the evaluation metrics; the default settings are γ1 = 0.5, γ2 = 0.1, and m = 0.3.The random seed is fixed at 42 for randomized operations and dataset splits.Source: A. Experimental Setup · p. 7

B. Performance Comparison

  • HOPE enriches raw features with multi-hop structural patterns, filters semantically inconsistent messages, and synthesizes pseudo-unknown boundaries through structural extrapolation.Joint classification and logit margin regularization are used to maintain a balanced decision space.Source: B. Performance Comparison · pp. 7–8

C. Ablation Study

HOPE preserves known-class accuracy while detecting unknown nodes, and its performance remains optimal as the open-set class space expands. Ablations report that each key module contributes to the full model’s performance.

C. Ablation Study

  • The full model performs best overall in ablations, while removing structural initialization, trustworthy aggregation, or logit margin regularization degrades performance.Without margin regularization, the model collapses toward classifying almost all nodes as open-set; without filtering, cross-class neighbors can poison ego-node features.Source: C. Ablation Study · p. 8

E. Robustness Analysis

  • As unseen classes increase from one to eight, HOPE maintains optimal performance across the reported phases.The authors attribute this robustness to proxies shifted outward along heterophilic neighborhood displacement vectors.Source: Figure 4 · p. 8, E. Robustness Analysis · p. 9

D. Open-set and Closed-set Performance

  • HOPE maintains high precision on known classes and strong detection of unknown nodes; G2Pxy’s higher unknown accuracy on Roman-Empire comes with lower known-class accuracy.The comparison highlights the trade-off between unknown detection and false-positive rejection of known nodes.Source: D. Open-set and Closed-set Performance · p. 8, Figure 3 · p. 8

F. Latent Space Topology Visualization

HOPE’s proxies appear near real unknown nodes in a Chameleon visualization, while its reported computational footprint remains small. The paper also reports low sensitivity to hyperparameter settings and strong performance across evaluated benchmarks.

F. Latent Space Topology Visualization

  • On Chameleon, synthesized proxies tend to lie near known-class boundaries and overlap regions containing real unknown nodes.The t-SNE visualization provides qualitative evidence about proxy locations.Source: F. Latent Space Topology Visualization · p. 9

G. Efficiency Analysis

  • For fixed hidden dimension d and proxy count S, per-epoch complexity scales linearly with N + M, with memory complexity O(Nd+Md).Trustworthy edge scoring and aggregation require O(Md), and proxy construction requires O(Md + Sd).Source: G. Efficiency Analysis · p. 9
  • HOPE combines a substantial performance margin over competitors with lower time and memory expenditures than heavy paradigms such as EGonc.The Chameleon comparison plots accuracy versus time and memory usage.Source: Figure 6 · p. 9, G. Efficiency Analysis · p. 9

H. Parameter Sensitivity Analysis

VI. CONCLUSION

  • HOPE achieves best or competitive performance across the evaluated settings against state-of-the-art baselines.The conclusion characterizes the method as effective, efficient, and robust in entangled-label environments.Source: §VI · p. 10

Related papers

Loading 2609.08685v1…