Reconstruction Outcomes Look Similar but Processes Differ: Improving Context Consistency and Coverage in Graph Masked Auto-Encoder

Graph Masked Auto-Encoder (GMAE) has emerged as a prevalent self-supervised paradigm, showing superior performance in graph learning. However, existing methods mainly emphasize reconstruction outcomes and give limited specification to how neighborhood context is used for reconstruction. Our experimental investigation shows that, even when reconstruction outcomes are similar, the ways of using neighborhood context differ substantially, resulting in performance shifts. To address this issue, we propose Consistency-and Coverage-aware Graph Masked Auto-Encoder (C2-GMAE), which encourages more consistent use of neighborhood context and promotes broader training coverage in the graph. Specifically, C2-GMAE leverages positional encoding as an observable structural reference, introduces density-partitioned masking to improve coverage across regions, and amplifies heterophilic edges to reduce the attenuation of discriminative relational information during reconstruction. Extensive experiments on multiple benchmarks demonstrate that C2-GMAE improves downstream performance against GMAE baselines.

Improving Context Consistency and Coverage in Graph Masked Auto-Encoder (a) Similar outcomes, different usage of context (b) Similar outcomes, different masks (c) Limited coverage in hard regions Easy region Hard region Loss reduction Mask Higher weight Context edge