Open-World Graph Learning for Emerging Categories

25 concepts23 papers1 proposal

Standard Graph Neural Networks (GNNs) typically operate under a closed-world assumption: they assume that every node or graph encountered during testing belongs to a fixed set of categories seen during training. In reality, graphs are dynamic ecosystems. Social networks sprout new communities, e-commerce platforms add novel product types, and citation indices evolve with emerging research fields.

When a closed-world model encounters a node from a category it has never seen, it suffers from "overconfidence," forcing the new data into an existing, incorrect label. Open-world graph learning seeks to move beyond simple classification to a three-part capability: detecting the unknown, discovering new categories, and adapting to them over time.

Detecting the Unknown Unknowns

The first challenge is distinguishing between "in-distribution" (ID) data and "out-of-distribution" (OOD) data. Traditional models struggle here because they are never exposed to "unknowns" during training.

To solve this, Zhang et al. proposed $G^2Pxy$, which generates "proxy unknowns" by mixing hidden-layer representations of known classes. By training the model to explicitly recognize these simulated outliers, it learns a boundary for what it doesn't know. Guan et al. refined this detection using evidential reasoning. Their framework, EviNet, uses Subjective Logic to distinguish between two types of uncertainty: dissonance (when data is noisy but known) and vacuity (when the model lacks evidence because the category is entirely new).

Structure also plays a role in detection. Song et al. introduced OODGAT, which uses a specialized attention mechanism to model the interactions between ID and OOD nodes, preventing the features of unknown nodes from "polluting" the representations of known ones.

From Rejection to Discovery

Once a model can reject unknown data, the next step is Novel Class Discovery (NCD)—grouping those unknowns into meaningful new categories without human labels.

A recurring mechanism for this is prototype learning. Deng et al. developed ProtoFGW-NCD, which uses learnable "prototype graphs" to capture the structural essence of novel graph categories. Similarly, Hoffmann et al. proposed POWN, which combines self-supervised learning with weighted label propagation to actively discover and name new node classes rather than just rejecting them.

However, discovering new classes is difficult because known classes are often more tightly clustered than new ones. Wang et al. identified this as "variance imbalance." Their framework, OpenIMA, uses contrastive learning and bias-reduced pseudo-labels to ensure that the model doesn't overlook emerging classes that are still sparsely connected or poorly defined.

Learning in an Evolving World

In temporal graphs, categories don't just appear; they emerge in a stream. This leads to the problem of catastrophic forgetting, where a model learns a new category but loses its ability to recognize old ones.

Wang et al. addressed this with N-ForGOT, a framework for open temporal graph learning that uses a regularization module to preserve the relationships between old classes while adapting to distribution shifts. For efficiency, Liu et al. proposed Learning Towards the Future (LTF), which maintains performance by selecting only the most informative subsets of historical data to replay during training, rather than retraining on the entire graph history.

The intuition behind these temporal models is that graphs have a "receptive field." Franke demonstrated that GNNs do not need their entire history to remain accurate; providing data that covers just a portion of the model's receptive field is often sufficient to retain the vast majority of performance on old classes.

Bridging the Semantic Gap

Finally, how do we classify nodes into categories that have zero training examples? Ju et al. tackled this via Zero-shot Node Classification by building a "graph of classes." By mapping the relationships between class metadata, the model can transfer knowledge from a known category (e.g., "Machine Learning") to an unseen but related one (e.g., "Deep Learning").

Luo et al. extended this to graph-level classification with RIGNN. They argue that graphs contain "rationales"—substructures that explain their class. By isolating these rationales and building a "graph-of-graphs" to bridge semantic gaps, their model can classify graphs even when labels are extremely scarce and the test set contains entirely new categories.

Key Foundational Work

Learning to Extrapolate Knowledge: Transductive Few-shot Out-of-Graph Link Prediction (2020) — contributed 1 concept elements to this direction.
Learning cost function for graph classification with open-set methods (2019) — contributed 1 concept elements to this direction.
History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 23 papers
  2. Version 1 · 2026-10-04 · 42 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_closed_world_assumption_open_world_graph_b74274d4,
  title = {closed-world assumption (open-world graph learning)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/closed-world-assumption-open-world-graph-learning/rdr_b74274d4ffab41378bf122f966e18bb5},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 2, frozen text):

@misc{lacuna_closed_world_assumption_open_world_graph_b74274d4_v2,
  title = {closed-world assumption (open-world graph learning)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/closed-world-assumption-open-world-graph-learning/rdr_b74274d4ffab41378bf122f966e18bb5/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake