SCARCE: How Label-Free Graph Generalization Achieves Implicit Feature Reweighting

Graph neural networks often face distribution shift (OOD) problems in real-world scenarios, and improving graph-level generalization capability is key to deployment. Traditional methods rely on class labels during representation learning to identify predictive substructures, which limits their applicability to label-free settings. A recent paper proposes the SCARCE framework, which can learn distributionally robust graph representations using only environment partitions of training graphs (from metadata or unsupervised clustering), offering a new approach for label-free graph generalization.

The Label Dependency Dilemma of Existing Methods

Graph-level OOD generalization aims to keep models robust outside the training distribution. Existing work typically assumes access to class labels during training, using supervised signals to determine which substructures are predictive, thereby suppressing spurious correlations in representation learning. However, in reality labels are often scarce or expensive to obtain, making this dependency a bottleneck. SCARCE's starting point is precisely to remove label dependency: it only requires environment partitions of training graphs, which can come from dataset-provided metadata or, in the absence of metadata, from clustering self-supervised embeddings. Environment partitions provide coarse-grained information about distribution shift but do not involve class semantics.

Two-Stage Training: Reconstruction and Adversarial Confusion

SCARCE adopts a two-stage pipeline. In the first stage, a variational graph autoencoder (VGAE) is warm-started via a graph reconstruction task, enabling the encoder to initially capture graph structural information. The second stage introduces an adversarial confusion mechanism: a discriminator attempts to distinguish environments from the representations output by the encoder, while the encoder is trained to produce representations that the discriminator cannot use to tell environments apart. Meanwhile, graph reconstruction fidelity is retained as a constraint to prevent excessive information loss. This adversarial game encourages the encoder to discard environment-discriminative directions while preserving task-relevant structural information.

A variational graph autoencoder (VGAE) is a generative model based on graph structure. Its encoder maps node features and an adjacency matrix to distribution parameters in latent space (mean and log-variance), and the decoder reconstructs the adjacency matrix from the latent representation. The training objective includes a reconstruction loss and a KL divergence regularization term, bringing the latent representation close to a prior distribution. VGAE is commonly used for unsupervised graph representation learning and can capture graph topology and attribute information. In SCARCE, the VGAE warm-start stage pretrains the encoder through the reconstruction task, providing a stable initialization for subsequent adversarial training and avoiding the instability caused by starting the adversarial game from random noise.

Theoretical Perspective: Implicit Feature Reweighting

The paper provides a theoretical analysis showing that environment confusion contracts the directions in representation space that are relevant to environment discrimination. Under a regularized downstream classifier, this is equivalent to imposing a stronger directional penalty on environment-associated features. In other words, SCARCE implements an implicit form of feature reweighting: unlike last-layer reweighting methods that explicitly adjust weights, it continuously reduces reliance on spurious correlations through representation learning without erasing information. This label-free continuous relaxation offers a scalable alternative to traditional reweighting methods.

Feature reweighting is a classic strategy for handling distribution shift. Its core idea is to assign different weights to different feature dimensions to reduce the influence of spuriously correlated features. Last-layer reweighting methods typically adjust weights explicitly in the final layer of the model, for example by learning sample weights or feature penalties through environment labels. Such methods require environment labels or additional optimization steps, and the weight adjustments are discrete. SCARCE's implicit reweighting occurs during representation learning, continuously contracting environment-discriminative directions through adversarial confusion, which is equivalent to imposing directional penalties on all downstream classifiers. This continuous relaxation avoids the two-stage optimization of explicit reweighting and is easier to train end-to-end, but the theoretical guarantees depend on the convergence of adversarial training.

Experimental Validation: Synthetic Data and DrugOOD

On controlled synthetic datasets and the DrugOOD dataset, SCARCE achieves state-of-the-art OOD generalization performance among label-free methods. Interestingly, the entire representation learning process uses no class labels and relies solely on environment partitions. This validates the effectiveness of the environment confusion mechanism and also shows that unsupervised environment clustering can serve as a practical substitute for metadata. Experiments cover different types of distribution shift, and results consistently show that SCARCE outperforms existing label-free baselines.

DrugOOD is a graph-level distribution shift benchmark dataset in the drug discovery domain, containing multiple sub-datasets that cover different shift types (e.g., scaffold shift, molecular size shift, etc.). Each molecule is represented as a graph, with atoms as nodes and chemical bonds as edges, and the task is to predict molecular properties (e.g., toxicity). DrugOOD provides environment partitions (based on metadata), facilitating evaluation of OOD generalization methods. SCARCE does not use class labels on DrugOOD and trains only with environment partitions, achieving the best performance compared with label-free baselines, validating its effectiveness in real drug discovery scenarios.

Significance and Limitations

SCARCE's core contribution is to free graph OOD generalization from label dependence, providing a feasible path for graph learning scenarios with scarce labels. Its theoretical connection reveals the equivalence between adversarial confusion and feature reweighting, offering a new perspective for understanding label-free generalization. Potential limitations include dependence on the quality of environment partitions: when self-supervised clustering performs poorly, performance may degrade; in addition, the computational overhead and stability of adversarial training are factors to consider in practical deployment. Future work could explore more robust environment discovery methods and extend the framework to node-level tasks.

One-line Summary

SCARCE achieves label-free graph-level OOD generalization using only environment partitions.

Paragraph Summary

SCARCE is a label-free generalization framework for distribution shift (OOD) problems in graph neural networks. Traditional methods rely on class labels to identify predictive substructures, limiting their applicability in label-free settings. SCARCE requires only environment partitions of training graphs (from metadata or unsupervised clustering) and adopts two-stage training: first warm-starting with a variational graph autoencoder (VGAE), then using an adversarial confusion mechanism to force the encoder to discard environment-discriminative information. Theoretical analysis shows that environment confusion contracts environment-discriminative directions, equivalent to implicit feature reweighting. On synthetic datasets and DrugOOD, SCARCE achieves state-of-the-art OOD generalization performance among label-free methods, providing a feasible path for label-scarce scenarios, though environment partition quality and adversarial training overhead are potential limitations.