G2xy: Generative Open-Set Node Classification on Graphs with Proxy Unknowns

Qin Zhang, Zelin Shi, Xiaolin Zhang, Xiaojun Chen, Philippe Fournier-Viger, Shirui Pan

Standard Graph Neural Networks (GNNs) typically operate under a "closed-set" assumption, where all nodes encountered during testing are assumed to belong to the classes seen during training. However, real-world graphs are dynamic and often contain novel categories. For instance, a citation network model trained on "Physics" and "Biology" might fail when encountering a "Quantum Computing" paper, often misclassifying it into a known category with high confidence. This paper introduces $G^2Pxy$, a generative framework designed for open-set node classification that accurately identifies known classes while rejecting unknown ones.

Methodology

The $G^2Pxy$ framework operates in a strict inductive setting, meaning it has no prior knowledge of unknown classes during training. It addresses the open-set challenge through two primary mechanisms:

  1. Proxy Node Generation via Manifold Mixup: Instead of using computationally expensive Generative Adversarial Networks (GANs), $G^2Pxy$ employs manifold mixup in the latent space of the GNN. It generates "proxy unknowns" by interpolating between hidden representations at a middle layer of the network.
  2. Inter-class Proxies: Created by mixing nodes from different known classes that share an edge, simulating unknowns at the boundaries of known categories.
  3. External Proxies: Generated by mixing "peripheral" nodes (e.g., leaf nodes or unconfident nodes) with "reversed" class centers to represent unknowns at the fringes of the data distribution.
  4. Open-Set Classifier Learning: The model extends a standard $C$-class classifier to a $(C+1)$-class classifier, where the additional class represents "unknown." Training utilizes a combination of standard Cross-Entropy and a Tailored Complement Entropy (CoE) loss. This loss function calibrates the model by ensuring the "unknown" class is the second-most likely prediction for known nodes, effectively sharpening the decision boundaries between known and novel data.
Overview of the $G^2Pxy$ framework, illustrating proxy node generation and the open-set classifier architecture.

Experimental Evaluation

The researchers evaluated $G^2Pxy$ on four standard citation network benchmarks: Cora, Citeseer, DBLP, and PubMed. They tested the model's performance in two specific scenarios:

  • Near Open-Set: One class within the dataset is held out as the "unknown" during training.
  • Far Open-Set: Nodes from entirely different datasets are used as the "unknowns" (e.g., using Cora as known and Citeseer as unknown).

Key Results and Insights

$G^2Pxy$ consistently outperformed state-of-the-art baselines, including PROSER and OpenWGL, across all datasets. In inductive "near open-set" tasks, it achieved an average 3.70% improvement in accuracy and a significant 9.60% improvement in Macro-F1 score over the second-best method.

Performance comparison of $G^2Pxy$ against baseline methods on standard citation datasets, showing Accuracy and F1 scores.

Several key insights emerged from the study:

  • Efficient Generation: The paper demonstrates that manifold mixup provides a lightweight yet effective alternative to heavy generative machinery for synthesizing unknown distributions.
  • Boundary Awareness: By targeting boundary and peripheral nodes for proxy generation, the model learns to define the limits of the "known" space much more effectively than global thresholding methods.
  • Calibration via Complement Entropy: The CoE loss prevents the overconfidence typical of deep networks by forcing a more nuanced relationship between known and unknown classes.

Conclusion

$G^2Pxy$ represents a significant step forward in making GNNs more robust for real-world applications where unknown data is inevitable. While highly effective, future research could address scaling the method to massive graphs with millions of nodes, exploring non-linear proxy synthesis techniques, and adapting the framework for dynamic graphs where new classes emerge continuously over time.

Summary updated

BibTeX
@inproceedings{zhang2023g,
  author = {Qin Zhang and Zelin Shi and Xiaolin Zhang and Xiaojun Chen and Philippe Fournier-Viger and Shirui Pan},
  title = {{G2xy: Generative Open-Set Node Classification on Graphs with Proxy Unknowns}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2023},
  doi = {10.24963/ijcai.2023/509},
}
Figure