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.

Many real-world data are graphs, such as social networks, citation networks, and molecules, where items are connected to each other. Graph Masked Auto-Encoders (GMAEs) are a common self-supervised approach for graph learning. They hide part of a graph and reconstruct the hidden information from the remaining neighborhood context. Existing GMAEs mainly evaluate training by reconstruction results, with limited attention to how the model uses this context. We find that under different random seeds or masking patterns, a GMAE can obtain similar reconstruction results while assigning different weights to neighboring context edges, which can affect later prediction performance. We propose C2-GMAE, which encourages more consistent context weighting and broader training coverage. It uses relative positional distances as a structural reference, density-partitioned masking to cover regions with different local reconstruction support, and heterophilic-edge amplification to preserve useful relations between heterophilic nodes. Experiments on node classification and graph prediction show that C2-GMAE improves over strong self-supervised graph learning baselines.