# Drop the mask! GAMM-A Taxonomy for Graph Attributes Missing Mechanisms

Richard Serrano, Baptiste Jeudy, Charlotte Laclau, Christine Largeron

► To cite this version:

Richard Serrano, Baptiste Jeudy, Charlotte Laclau, Christine Largeron. Drop the mask! GAMM-A Taxonomy for Graph Attributes Missing Mechanisms. Advances in Intelligent Data Analysis XXIV, Apr 2026, Leiden (NL), Netherlands. hal-05494967

HAL Id: hal-05494967

https://hal.science/hal-05494967v1

Submitted on 6 Feb 2026

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# Drop the mask! GAMM - A Taxonomy for Graph Attributes Missing Mechanisms

Richard Serrano¹, [0009-0009-4946-896X],
Baptiste Jeudy¹ [0009-0000-8126-2608],
Charlotte Laclau² [0000-0002-7389-3191], and
Christine Largeron¹ [0000-0003-1059-4095]

¹ Laboratoire Hubert Curien, Saint-Étienne 42000, France
{richard.serrano; baptiste.jeudy; christine.largeron}@univ-st-etienne.fr
² Télécom Paris, Institut Polytechnique de Paris, France
charlotte.laclau@telecom-paris.fr

**Abstract.** Exploring missing data in attributed graphs introduces unique challenges beyond those found in tabular datasets. In this work, we extend the taxonomy for missing data mechanisms to attributed graphs by proposing GAMM (Graph Attributes Missing Mechanisms), a framework that systematically links missingness probability to both node attributes and the underlying graph structure. Our taxonomy enriches the conventional definitions of masking mechanisms by introducing graph-specific dependencies.

We empirically demonstrate that state-of-the-art imputation methods, while effective on traditional masks, significantly struggle when confronted with these more realistic graph-aware missingness scenarios.

**Keywords:** Attributed Graph, Missingness Mechanisms, Masking Taxonomy, Missing Values Imputation

## 1 Introduction

Attributed graphs provide a powerful framework for modeling complex systems, from social networks to biological interactions. Unlike tabular data, graph-structured data captures the inherent connections between entities, where a node is defined by both its attributes and its relational context. However, this structure creates unique challenges when dealing with missing data. In practice, node attributes are often partially unobserved, posing a significant problem for methods like Graph Neural Networks (GNNs) that usually require fully observed feature matrices. For instance, in social networks, users may omit sensitive profile information depending not only on their own characteristics but also on their position within the network or the attributes of their friends. A user with many connections might be more cautious about sharing personal data, or missingness may cluster within communities due to shared privacy norms or platform features. Such dependencies between missingness and network structure are not captured by classical missing data models, which assume independence from relational context. Accurately modeling these effects is crucial for fair and effective
inference on graph data. This need has led to substantial research into missing attribute imputation [16, 23, 18]. However, a critical issue is that these methods are often evaluated using simplistic masking mechanisms, e.g., MCAR, MAR, MNAR [7], which provides a crucial foundation, but do not explicitly account for structural dependencies. In real-world graphs, missingness may be influenced by a node's connectivity or the characteristics of its neighborhood.

*Contributions.* We introduce the Graph Attributes Missing Mechanisms (GAMM) taxonomy, which extends traditional missingness frameworks by incorporating structural dependencies and classifying missingness into four sources: (A) node attributes, (S) structural properties, (N) neighbors' attributes, and (G) their combinations. Focusing solely on missing node attributes under a known topology, we show that graph-aware mechanisms substantially degrade the performance of state-of-the-art imputers relative to attribute-only missingness. To structure the investigation, we examine how (Research Question 1) S- and N-based mechanisms affect reconstruction performance across graphs and missing rates, (RQ2) homophily/heterophily modulates the gap between attribute-and neighborhood-based MAR, (RQ3) neighbor-dependent MNAR compares to attribute-based MNAR and in which settings it becomes most severe, and (RQ4) whether imputers preserve feature distributions under these structurally informed conditions. An open-source implementation of all mechanisms and protocols is provided.<fnref n="1" />

This paper is structured as follows. Section 2 outlines existing masking strategies and discusses their limits. Section 3 presents GAMM; Section 4 details experiments and results. Finally, Section 5 concludes.

# 2 Limits of Traditional Missing Data Mechanisms

## 2.1 Traditional Missing Data Mechanisms

The traditional taxonomy identifies three missingness mechanisms [15, 9]: (1) **Missing Completely At Random (MCAR)**, where missingness is independent of all data; (2) **Missing At Random (MAR)**, where it is influenced only by observed data; and (3) **Missing Not At Random (MNAR)**, where it depends on unobserved values. For instance, in a corporate network, missing employee *Salary* data would be MCAR if it resulted from a randomly occurring glitch in the employee database, MAR if junior employees (i.e., observed *Experience* attribute) are less likely to report it, and MNAR if employees with higher salaries (the unobserved feature itself) are the ones who mostly withhold this information. Most imputation methods assume MCAR or MAR conditions [8], while MNAR requires specialized approaches [3]. Existing extensions to this taxonomy, including graphical models [11] and conditional independence approaches [2], enhance the framework for tabular data but fail to address network-specific challenges where structural relationships directly influence missingness patterns.

<footnote n="1">¹ Code and Supplementary Material: github.com/RichardSrn/GAMM</footnote>
Similarly, recent work advocating for explicit measurement process modeling [6] acknowledges the limitations of the rigid MCAR/MAR/MNAR classification in complex dependencies, yet still overlooks how network topology itself can determine whether attributes are observed. While these foundational missingness mechanisms provide a basis for our graph-based taxonomy, they require significant extensions to address the unique complexities of network structure.

## 2.2 Taxonomies and Extensions for Graph-Based Missingness

When translating missingness concepts to graphs, structural relationships between entities add complexity beyond tabular settings. Missingness can depend on node attributes, topological properties, or relational influences [5, 4].

*Limitations.* We claim that traditional definitions of missingness mechanisms are inadequate for graph-structured data, where missingness may depend on structural properties. The following two examples illustrate this argument:

1. **Structurally-Induced Missingness:** Nodes with specific structural properties (e.g., low degree) may exhibit missing attributes due to their position in the network. In social networks, peripheral users may be less likely to report certain attributes, like alcohol consumption [4]. This represents a MAR mechanism dependent on graph topology rather than attributes values; a distinction classical frameworks fail to characterize.

2. **Neighbor-Influenced Missingness:** In social networks, individuals might withhold information (e.g., salary) not based on their own values, but influenced by their friends' values. This creates dependencies unexplainable without incorporating graph structure [5]. This scenario represents a graph-specific form of MNAR because the missingness of a node's attribute is conditioned on the unobserved attributes of its neighbors. Here, traditional MNAR frameworks are inadequate, as they are unable to model dependencies that arise from the underlying graph topology. This concept of leveraging network information can also be applied to the MAR framework, for instance, by conditioning the missingness on the *observed* features of neighboring nodes.

In the following, we propose a new taxonomy for attributed graphs, providing a basis for clear methodology and consistent evaluation of graph-imputation methods under more realistic missingness conditions.

# 3 Taxonomy for Graph Attributes Missing Mechanisms (GAMM)

In this section, we introduce GAMM (Graph Attributes Missing Mechanisms), a novel taxonomy for understanding and generating missing data masks in attributed graphs. GAMM extends traditional missingness definitions by explicitly incorporating the interplay between node attributes and the graph structure.
<figure><img src="image_2.png" /><figcaption>**Fig. 1.** Traditional (a–c) and graph-aware (d–f) missingness mechanisms in GAMM. Each node shows four attribute slots (top-to-down: Hierarchy, Salary, Experience, Age); red shades indicate higher missingness probability, while blue indicates lower probability (white = observed). Consistent with the example description in paragraph *Example*, higher positions in the hierarchy correspond to higher attribute values.</figcaption></figure>

To illustrate these mechanisms, we use a toy example of a corporate email network (Figure 1). Each node represents an employee, and edges denote communication. Node attributes include *Hierarchy*, *Salary*, *Experience*, and *Age*, with some features correlated to aid visual intuition. To ensure consistent interpretation across panels, each node displays four attribute slots in the fixed top-to-down order [*Hierarchy*, *Salary*, *Experience*, *Age*]. We encode the missingness probability $p_{\text{miss}}$ using a color scale: white denotes observed entries ($p_{\text{miss}} = 0$), followed by blue for $p_{\text{miss}} \in (0, 0.25]$, green for $p_{\text{miss}} \in (0.25, 0.50]$, orange for $p_{\text{miss}} \in (0.50, 0.75]$, and red for $p_{\text{miss}} \in (0.75, 1.0]$.

We consider an undirected attributed graph $G = (\mathcal{V}, \mathcal{E}, F)$ with $n$ nodes, edges $\mathcal{E} \subset \mathcal{V} \times \mathcal{V}$, and feature matrix $F \in \mathbb{R}^{n \times d}$ where $F_i$ is the feature vector of node $v_i$ and $S_i$ are its structural properties (degree, ...). Missing entries are indicated by a binary mask $\Omega \in \{0, 1\}^{n \times d}$, with $\Omega_{ij} = 1$ when feature $j$ of $v_i$ is observed. We decompose $F$ into $F^{(\text{OBS})}$ (observed features) and $F^{(\text{MIS})}$ (features subject to missingness).

*Example.* Consider a corporate email network. In a **MAR** scenario, suppose *Experience* is fully observed while *Hierarchy*, *Age* and *Salary* may be missing features. This partitions the features into $F^{(\text{OBS})} = [\text{Experience}]$ and $F^{(\text{MIS})} = [\text{Hierarchy}, \text{Age}, \text{Salary}]$. In contrast, in a **MNAR** scenario, we may have no fully observed features ($F^{(\text{OBS})} = \emptyset$), meaning all attributes fall into $F^{(\text{MIS})}$.

Crucially, missingness in graphs often correlates with structure. For instance, junior employees, often located in peripheral regions of the graph, may be more likely to have missing features. That would be a **MAR** scenario based on struc-
ture, and imputers that ignore this structural pattern may systematically overestimate their roles, yielding distributional distortions that standard attribute-only evaluations fail to capture.

Note that in Figure 1, higher positions in the hierarchy correspond to higher attribute values for visual interpretation.

*Graph Context.* To model this context, we denote by $\mathcal{N}_h(v_i)$ the h-hop neighbors of $v_i$. We define the structural and feature-based neighborhoods as follows:

- **Structure:** $\mathbf{S}_i^{(\text{OBS})}(h) = \{\mathbf{S}_k | v_k \in \mathcal{N}_h(v_i) \text{ and } \mathbf{S}_k \text{ fully observed}\}$ is the set of observed structural properties in the h-hop neighborhood, while $\mathbf{S}_i^{(\text{MIS})}(h) = \{\mathbf{S}_k | v_k \in \mathcal{N}_h(v_i) \text{ and } \mathbf{S}_k \text{ may be missing}\}$ denotes those that may be missing.

- **Features:** Similarly, $\mathbf{N}_i^{(\text{OBS})}(h) = \{F_k^{(\text{OBS})} | v_k \in \mathcal{N}_h(v_i)\}$ represents the observed features of neighbors, and $\mathbf{N}_i^{(\text{MIS})}(h) = \{F_k^{(\text{MIS})} | v_k \in \mathcal{N}_h(v_i)\}$ represents the potentially missing features.

For $h = 0$, $\mathbf{S}_i^{(\text{OBS})}(0)$ and $\mathbf{S}_i^{(\text{MIS})}(0)$ correspond to the properties of $v_i$ itself, abbreviated as $\mathbf{S}_i^{(\text{OBS})}$ and $\mathbf{S}_i^{(\text{MIS})}$. A full notation list is provided in Section A.3 of the Supplementary Material.

## 3.1 Proposed Mechanisms

We are now ready to present GAMM, a Graph-Aware Missingness Mechanism framework, under the assumption that the graph structure $(\mathcal{V}, \mathcal{E})$ is fully observed. The probability that an attribute $F_{ij}$ is missing ($P(\Omega_{ij} = 0)$) is governed by a function $g(\cdot)$ over relevant inputs:

$$P(\Omega_{ij} = 0 | G) = P(\Omega_{ij} = 0 | \cdot) = g(\cdot). \qquad (1)$$

The nature of the inputs to $g(\cdot)$ determines the missingness mechanism. Table 1 summarizes our taxonomy, and illustrative examples are shown in Figure 1. In addition to the MCAR setting, we distinguish four key families of mechanisms that capture different sources of dependency in graphs.

*Missing Completely At Random (MCAR)* Missingness occurs independently of both node attributes and the graph structure: the missingness probability is the same constant for all entries of $F^{(\text{MIS})}$, as shown in Figure 1(a).

*Attribute-based Missingness (A-)* In this setting, missingness for a node $v_i$ depends only on its own attributes, mirroring standard tabular assumptions. **A-MAR** arises when the probability of missingness depends on observed attributes of $v_i$ (e.g., in Figure 1(b), low observed *Experience* correlates with more missing values). Conversely, under **A-MNAR**, missingness is driven by the node's unobserved attributes (Figure 1(c) illustrates higher true *Salary* leading to missing entries).
<table><caption>**Table 1.** GAMM Taxonomy: Characterization of graph-aware missingness mechanisms based on the inputs to the probability function $g(\cdot)$. ✓ indicates an input is potentially used by $g(\cdot)$. A stands for Attribute-based, S for Structure, N for Neighborhood, and G for Generic.</caption><thead><tr><th rowspan="2">Cat. Mech.</th><th rowspan="2">Formal Definition of<br>P(Ω<sub>ij</sub> = 0 | G)</th><th colspan="5">Possible dependencies for g(·)</th></tr><tr><th>F<sub>i.</sub><sup>(OBS)</sup></th><th>F<sub>i.</sub><sup>(MIS)</sup></th><th>S<sub>i</sub><sup>(OBS)</sup>(h)</th><th>S<sub>i</sub><sup>(MIS)</sup>(h)</th><th>N<sub>i</sub><sup>(OBS)</sup>(h)</th><th>N<sub>i</sub><sup>(MIS)</sup>(h)</th></tr></thead><tbody><tr><td>MCAR</td><td>P(Ω<sub>ij</sub> = 0)</td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td rowspan="2">A-</td><td rowspan="2">MAR<br>MNAR</td><td rowspan="2">P(Ω<sub>ij</sub> = 0 | F<sub>i.</sub>)</td><td>✓</td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>✓</td><td>✓</td><td></td><td></td><td></td><td></td></tr><tr><td rowspan="2">S-</td><td rowspan="2">MAR<br>MNAR</td><td rowspan="2">P(Ω<sub>ij</sub> = 0 | S<sub>i</sub>)</td><td></td><td>✓</td><td></td><td></td><td></td><td></td></tr><tr><td></td><td></td><td>✓</td><td>✓</td><td></td><td></td></tr><tr><td rowspan="2">N-</td><td rowspan="2">MAR<br>MNAR</td><td rowspan="2">P(Ω<sub>ij</sub> = 0 | N<sub>i</sub>(h))</td><td></td><td></td><td></td><td>✓</td><td></td><td>✓</td></tr><tr><td></td><td></td><td></td><td></td><td>✓</td><td>✓</td></tr><tr><td rowspan="2">G-</td><td rowspan="2">MAR<br>MNAR</td><td rowspan="2">P(Ω<sub>ij</sub> = 0 | F<sub>i.</sub>, S<sub>i</sub>, N<sub>i</sub>(h))</td><td>✓</td><td></td><td>✓</td><td></td><td></td><td>✓</td></tr><tr><td>✓</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td></tr></tbody></table>

**Structural Properties-aware Missingness (S-)** Here, missingness depends on the structural characteristics of $v_i$ (degree, centrality, etc.). Under **S-MAR**, it is governed by observed structural features (Figure 1(d) shows low-degree nodes having more missing data). Under **S-MNAR**, missingness depends on missing structural characteristics; for instance, nodes with missing edges in the graph may exhibit more missing values on features too.

**Neighborhood-aware Missingness (N-)** In this case, missingness of $v_i$ depends on attributes of its $h$-hop neighbors (where the neighborhood is defined by the graph topology and not from the feature-space). Under **N-MAR**, it depends only on neighbors' observed attributes (e.g., Figure 1(e), neighbors' observed Experience). Under **N-MNAR**, it depends on neighbors' unobserved attributes, as in Figure 1(f).

**Generic Combination Missingness (G-)** This category captures the most general and realistic forms of missingness. It allows dependencies across a node's own attributes (both observed and unobserved), structural properties, and neighborhood information. Such cases reflect complex real-world patterns where missingness cannot be attributed to a single source but instead arises from intertwined local and structural factors. These scenarios often blur the line between MAR and MNAR, making the masking mechanism particularly hard to disentangle without additional assumptions or annotations.

**Remark On the Identifiability of Missingness Mechanisms** A central challenge in modeling missing data is distinguishing MAR from MNAR mechanisms, a task that is fundamentally unidentifiable without additional assumptions or external supervision. This difficulty arises because the same observed missingness patterns can often be explained by either observed or unobserved variables.
Consider a feature with missing entries, $F_{.j}$, that is correlated with a fully
observed feature $F_{.k}$. If missingness depends on $F_{.k}$, it falls under MAR; but if
it instead depends on the unobserved values of $F_{.j}$, the mechanism is MNAR.
In practice, these explanations are statistically indistinguishable from observa-
tional data alone leading to intrinsic ambiguity in determining the true source
of missingness. In the tabular settings, identifiability is often assumed under the
i.i.d. sampling of rows (i.e., independent individuals) [21], though this assump-
tion is stronger than strictly necessary [2]. For graphs, this assumption breaks
down: nodes are not independent. However, for identifying the masking mecha-
nism, we do not require node-level independence. Instead, it suffices to assume
independence across features, i.e., columns of $F$ are uncorrelated.

While this assumption is rarely satisfied in real-world data (whether graph-
based or tabular), it enables clear identifiability in controlled experiments. By
constructing synthetic data under known and independent feature distributions,
we can isolate and verify the missingness mechanism. This is crucial when bench-
marking models or validating imputation strategies under known ground truth.

*Summary.* GAMM provides a formal framework to characterize and simulate diverse missingness mechanisms in graph data, capturing dependencies on node attributes, structural properties, and neighborhood information. This enables the creation of realistic missing data scenarios and systematic evaluation of their impact on graph learning methods. In the next section, we use GAMM to assess the robustness of state-of-the-art imputer models across these mechanisms. Our results show that performance and reliability vary significantly with the missing data type, highlighting the importance of accounting for these distinctions in graph algorithm design and evaluation.

# 4 Experiments

## 4.1 Experimental Protocol

Our experimental design directly addresses **RQ1–RQ4** by systematically vary-
ing missingness mechanisms (traditional vs. graph-aware), graph homophily, and
missing rates, and evaluating tabular and graph-based imputers using MAE/
RMSE and distributional analysis.

*Datasets.* We select twelve benchmark real-world graph datasets [25, 17, 22, 14,
1] (detailed in Section A.1 of the Supplementary Material) with diverse network
properties, notably varying levels of homophily, which is crucial for evaluating
our proposed mechanisms.

Table 2 summarizes their characteristics and groups them into Homophilic,
Neutral, and Heterophilic categories based on their adjusted homophily ($H_{adj}$)
[13].
<table><caption>**Table 2.** Presentation of the benchmark datasets, categorized by their adjusted homophily ($H_{adj}$).</caption><thead><tr><th></th><th>Dataset</th><th>#Nodes</th><th>#Edges</th><th>#Classes</th><th>Features</th><th>$H_{adj}$</th></tr></thead><tbody><tr><td rowspan="3">Homophilic</td><td>Cora</td><td>2708</td><td>5278</td><td>7</td><td>{0, 1}<sup>1433</sup></td><td>0.768</td></tr><tr><td>PubMed</td><td>19717</td><td>44324</td><td>3</td><td>[0, 2]<sup>500</sup></td><td>0.693</td></tr><tr><td>CiteSeer</td><td>3327</td><td>4552</td><td>6</td><td>{0, 1}<sup>3702</sup></td><td>0.678</td></tr><tr><td rowspan="6">Neutral</td><td>Chameleon</td><td>2277</td><td>18050</td><td>5</td><td>{0, 1}<sup>2325</sup></td><td>0.042</td></tr><tr><td>Squirrel</td><td>5201</td><td>108536</td><td>5</td><td>{0, 1}<sup>2089</sup></td><td>0.030</td></tr><tr><td>Minesweeper</td><td>10000</td><td>39402</td><td>2</td><td>{0, 1}<sup>7</sup></td><td>0.009</td></tr><tr><td>Actor</td><td>7600</td><td>15009</td><td>5</td><td>{0, 1}<sup>932</sup></td><td>0.007</td></tr><tr><td>Roman-empire</td><td>22662</td><td>32927</td><td>18</td><td>[0, 1]<sup>300</sup></td><td>-0.045</td></tr><tr><td>Tolokers</td><td>11758</td><td>519000</td><td>2</td><td>[0, 1]<sup>10</sup></td><td>-0.188</td></tr><tr><td rowspan="4">Heterophilic</td><td>Wisconsin</td><td>251</td><td>257</td><td>5</td><td>{0, 1}<sup>1702</sup></td><td>-0.189</td></tr><tr><td>Cornell</td><td>183</td><td>149</td><td>5</td><td>{0, 1}<sup>1702</sup></td><td>-0.219</td></tr><tr><td>Texas</td><td>183</td><td>162</td><td>5</td><td>{0, 1}<sup>1702</sup></td><td>-0.425</td></tr></tbody></table>

*Missingness Mask Generation.* We generate masks at overall rates of $p_{miss} \in \{20\%, 50\%, 80\%\}$ using distinct mechanisms from our taxonomy. As introduced in Section 3, we define the function $g(\cdot)$ that maps specific informational inputs to a missingness probability, $P(\Omega_{ij} = 0) = g(\cdot)$. The specific ways in which $g(\cdot)$ is determined, which instantiate mechanisms based on a node's own attributes (A-), its structure (S-), or its neighbors' attributes (N-), are defined as follows:

$$ \text{MCAR: } g() = p_{\text{miss}} $$

$$ \text{A-MAR/MNAR: } g(F_{i.}) = \begin{cases} \sigma(\omega_1 F_i^{(\text{OBS})} + b_1), & \text{A-MAR,} \\ \sigma(\omega_2 F_{ij}^{(\text{MIS})} + b_2), & \text{A-MNAR,} \end{cases} \\ \text{S-MAR/MNAR: } g(\mathbf{S}_i) = \begin{cases} \sigma(\omega_3 \text{deg}(\mathbf{S}_i) + b_3), & \text{S-MAR,} \\ \sigma(\omega_3 \mathbf{S}_i^{(\text{MIS})}(h) + b_3), & \text{S-MNAR,} \end{cases} \quad (2) $$

$$ \text{N-MAR/MNAR: } g(\mathbf{N}_i(h)) = \begin{cases} \sigma(\omega_4 \mathbf{N}_i^{(\text{OBS})}(h) + b_4), & \text{N-MAR,} \\ \sigma(\omega_5 \mathbf{N}_i^{(\text{MIS})}(h) + b_5), & \text{N-MNAR.} \end{cases} $$

Where, $\sigma(\cdot)$ is the sigmoid function, and deg stands for degree. The parameters $\omega_k$ and $b_k$ control the dependency strength and are calibrated to achieve the target probability $p_{miss}$. A detailed description of this calibration is provided in Section A.2 of the Supplementary Material.

*Remark on S-MNAR.* While GAMM defines formally S-MNAR (see Eq. 2), we exclude it from experiments as we assume a fully observed topology. Treating edges as missing shifts the problem to *link prediction*. Furthermore, without edge masks to distinguish unobserved links from non-edges, the structural set $\mathbf{S}_i^{(\text{MIS})}(h)$ remains empty in our setting.
***Imputation Methods.*** We evaluate a suite of state-of-the-art methods, focusing on those that represent current best practices. These methods have been selected because they demonstrate superior performance compared to older or less advanced baselines, thus we do not report standard baselines such as MICE [24].

**Tabular Imputers** process node attributes as a standard feature matrix, inherently ignoring graph structure: *TABULAR AVERAGE* which imputes missing values with the global mean of each feature; *OT-TAB* [12] that leverages optimal transport theory to minimize distributional discrepancies between observed and imputed data.

**Graph Imputers** explicitly exploit network topology for enhanced reconstruction. Notably we assess: *GRAPH AVERAGE*, a direct neighborhood average; *FP* [16] that propagates known values as a heat diffusion process along edges; *PCFI* [23] which introduces a novel channel-wise confidence metric for node features and utilizes shortest path distances for feature propagation and refinement; and finally *GRIOT* [18] which combines optimal transport with graph neural networks, to incorporates both node features and graph structure for robust imputation of missing attribute values.

***Evaluation.*** We assess imputation quality using Mean Absolute Error (MAE) and Root Mean Square Error (RMSE). Since our primary contribution is a new missingness-generation taxonomy, these reconstruction metrics provide the most direct and controlled evaluation of how methods respond to the proposed mechanisms, avoiding confounding effects from downstream tasks. The relationship between reconstruction fidelity and downstream performance is known to be complex: downstream models may tolerate substantial missingness [18], and strong downstream accuracy does not necessarily imply reliable interpretability or high-quality imputation [19, 20]. By focusing on reconstruction, we obtain a rigorous and targeted validation of our core contribution. All experiments are repeated eight times, and we use a Wilcoxon-Mann-Whitney U test [10], with a significance level *p* < 0.05 to assess statistical significance, testing the null hypothesis *H*₀ that the performance distributions of the compared methods are identical.

## 4.2 Results and Analysis

We evaluate state-of-the-art imputers under our taxonomy of missingness mechanisms, with a focus on the most challenging MNAR variants (Table 3), and summarise all 2,304 configurations in Table 4.

**RQ1: Impact of Graph-Aware Mechanisms** Across configurations, **graph-aware missingness markedly increases difficulty**. As captured in Table 4, moving from attribute-only to structurally informed masks leads to significant degradation in 46.6% of cases, consistently across tabular and graph-based imputers. These results indicate that conventional attribute-only masks provide
<table><caption>**Table 3.** Percentage degradation in MAE of N-MNAR over A-MNAR ($p_{miss}$ = 20%) across dataset homophily groups. Negative results indicate deterioration in MAE with the N-MNAR mechanism compared to A-MNAR. (*) indicates statistical significance (Mann–Whitney U, *p* < 0.05).</caption><thead><tr><th colspan="4">a) HOMOPHILIC datasets</th><th colspan="4">b) HETEROPHILIC datasets</th></tr><tr><th>Imputer</th><th>CiteSeer</th><th>Cora</th><th>PubMed</th><th>Imputer</th><th>Tolokers</th><th>Cornell</th><th>Texas</th><th>Wisconsin</th></tr></thead><tbody><tr><td>Tabular_Avg</td><td>-50.6*</td><td>-48.7*</td><td>-9.1*</td><td>Tabular_Avg</td><td>-9.0*</td><td>-47.5*</td><td>-46.5*</td><td>-47.2*</td></tr><tr><td>OT-tab</td><td>-10.3*</td><td>-14.0*</td><td>-2.1*</td><td>OT-tab</td><td>-7.6*</td><td>-30.8*</td><td>-25.5*</td><td>-31.2*</td></tr><tr><td>FP</td><td>-72.9*</td><td>-68.9*</td><td>-15.5*</td><td>FP</td><td>-35.3*</td><td>-46.1*</td><td>-67.7*</td><td>-54.4</td></tr><tr><td>GRIOT</td><td>-12.5</td><td>-17.1*</td><td>-5.1*</td><td>GRIOT</td><td>+0.9</td><td>-77.1*</td><td>-72.3*</td><td>-72.4*</td></tr><tr><td>Graph_avg</td><td>-70.1*</td><td>-64.4*</td><td>-12.8*</td><td>Graph_avg</td><td>-5.0*</td><td>-53.1*</td><td>-62.5*</td><td>-54.3*</td></tr><tr><td>PCFI</td><td>-55.6*</td><td>-55.5*</td><td>-13.0*</td><td>PCFI</td><td>-4.0*</td><td>-49.4*</td><td>-38.3*</td><td>-48.9*</td></tr></tbody></table><table><thead><tr><th colspan="6">c) NEUTRAL datasets</th></tr><tr><th>Imputer</th><th>Actor</th><th>Chameleon</th><th>Squirrel</th><th>Minesweeper</th><th>Roman_Empire</th></tr></thead><tbody><tr><td>Tabular_Avg</td><td>-53.1*</td><td>-38.8*</td><td>-34.5*</td><td>-23.1*</td><td>+11.8*</td></tr><tr><td>OT-tab</td><td>-6.4*</td><td>-6.2*</td><td>-7.8*</td><td>-20.1*</td><td>+3.1*</td></tr><tr><td>FP</td><td>-73.3*</td><td>-86.8*</td><td>-78.6*</td><td>-27.4*</td><td>-0.6</td></tr><tr><td>GRIOT</td><td>-14.3*</td><td>-11.2</td><td>-14.1</td><td>-0.0*</td><td>+3.3*</td></tr><tr><td>Graph_avg</td><td>-63.5*</td><td>-38.8*</td><td>-36.0*</td><td>-26.4*</td><td>+6.2*</td></tr><tr><td>PCFI</td><td>-51.6*</td><td>-17.2*</td><td>-17.4*</td><td>-25.5*</td><td>+6.5*</td></tr></tbody></table>

an overly optimistic view of robustness and that integrating structure in mask generation exposes realistic failure modes.

<table><caption>**Table 4.** Percentage Summary of Statistical Outcomes by mechanism. Total: 100% = 2,304 experiments.</caption><thead><tr><th>Type</th><th>Sign. Degradation</th><th>No Sign. Change</th><th>Sign. Improvement</th><th>Total</th></tr></thead><tbody><tr><td>A-MAR v.s. N-MAR</td><td>8.0%</td><td>32.2%</td><td>2.9%</td><td><strong>43.1%</strong></td></tr><tr><td>A-MNAR v.s. N-MNAR</td><td>38.6%</td><td>9.7%</td><td>8.6%</td><td><strong>56.9%</strong></td></tr><tr><td><strong>Total</strong></td><td><strong>46.6%</strong></td><td><strong>41.9%</strong></td><td><strong>11.5%</strong></td><td><strong>100.0%</strong></td></tr></tbody></table>

**RQ2: Role of Homophily under MAR** Under MAR, the contrast between attribute-based (A-MAR) and neighborhood-based (N-MAR) mechanisms depends strongly on network homophily. In homophilic or neutral graphs, both mechanisms yield similar performance, as neighbors are either similar or redundant (Supplementary Material Section C). In heterophilic graphs, however, switching from A-MAR to N-MAR leads to a significant degradation for most approaches. This degradation arises because aggregating dissimilar neighbors in-
jects misleading signals, highlighting the fragility of methods that implicitly rely
on homophily.

**RQ3: MNAR with Neighborhood Dependence** The MNAR setting amplifies these effects. Missingness that depends on unobserved values interacts with topology in ways that make reconstruction substantially harder.

*Homophilic and Neutral Graphs.* In these graphs, N-MNAR consistently out-
performs A-MNAR in difficulty: Table 3(a,c) shows widespread and significant
degradation when moving from A-MNAR to N-MNAR. For example, on Cora,
GRIOT and FP incur a deterioration of 17.1% and 68.9%, respectively, for the
MAE (both significant). Although the homophilic structure typically helps im-
putation, N-MNAR introduces dependencies between a node’s missingness and
its neighbors’ unobserved values, making the reconstruction problem inherently
more entangled than in A-MNAR.

*Heterophilic Graphs.* The effect is strongest in heterophilic graphs (Table 3(b)). For instance, FP presents a decrease of 35.3% in MAE on Tolokers, and GRIOT’s performance decrease by 77.1% on Cornell ($p < 0.05$). Here, dependence on unobserved values compounds with misleading neighbor information, creating a worst-case regime where all core assumptions of existing imputers are violated. This heterophilic N-MNAR combination emerges as a universal Achilles’ heel across methods and datasets.

**RQ4: Distributional Fidelity** Pointwise errors do not guarantee correct distributional reconstruction. Figure 2 illustrates distortions in binary attribute distributions on Tolokers (heterophilic) with 20% missing values: imputers underestimate the mass at 0 in N-MNAR, and at 1 in A-MNAR, flattening the bimodal structure. This skew is visible under A-MAR but intensifies under N-MAR and becomes severe under N-MNAR. In these conditions, imputers face biased supervision (missingness depends on unobserved values) and misleading structural cues (dissimilar neighbors), jointly causing systematic underestimation and flattening.

*Summary of Findings.* We synthesise the main insights across RQs:

1. Graph-aware missingness markedly degrades imputation performance in nearly half of all configurations.

2. Heterophily drives the MAR gap, with significant drops from A-MAR to N-MAR.

3. Under MNAR, N-MNAR is consistently the hardest regime, especially on heterophilic graphs.

4. Graph-aware mechanisms break distributional fidelity, introducing biases even when MAE/RMSE appear acceptable.
<figure><img src="image_3.png" /><figcaption>**Fig. 2.** Density (KDE) plots of imputed features on Tolokers with 20% of missing values. MNAR (left); MAR (right)</figcaption></figure>

# 5 Conclusion and Future Directions

We introduced **GAMM**, a taxonomy extending traditional missing-data definitions to account for graph structure. Our experiments show that graph-aware missingness, especially neighbor-aware MNAR in heterophilic networks, can severely degrade imputation performance, and current state-of-the-art methods, designed for classical settings, struggle under these conditions. Although some downstream tasks remain robust, many rely on accurate feature reconstruction. We highlight the need for imputation methods resilient to these challenges, and for future work on missing structural data. By providing a theoretical framework, empirical evidence, and open-source code¹, we aim to support more rigorous evaluation and development of imputation approaches for graphs.

# 6 Acknowledgment

This work has been partly funded by a public grant from the French National Research Agency (ANR) under the "France 2030" investment plan, which has the reference EUR MANUTECH SLEIGHT - ANR-17-EURE-0026.

# References

1. Craven, M., DiPasquo, D., Freitag, D., McCallum, A., Mitchell, T., Nigam, K., Slattery, S.: Learning to extract symbolic knowledge from the World Wide Web. AAAI/IAAI **3**(3.6), 2 (1998)

2. Doretti, M., Geneletti, S., Stanghellini, E.: Missing data: a unified taxonomy guided by conditional independence. International Stat. Review **86**(2), 189-204 (2018)

3. Hsu, C.H., He, Y., Hu, C., Zhou, W.: A multiple imputation-based sensitivity analysis approach for data subject to missing not at random. Statistics in medicine **39**(26), 3756-3771 (2020)

4. Huisman, M.: Imputation of Missing Network Data: Some Simple Procedures. In: Encyclopedia of Social Network Analysis and Mining, pp. 707-715 (2014)
5. Kossinets, G.: Effects of missing data in social networks. Social Networks **28**(3), 247-268 (2006)

6. Lee, K.J., Carlin, J.B., Simpson, J.A., Moreno-Betancur, M.: Assumptions and analysis planning in studies with missing data in multiple variables: moving beyond the mcar/mar/mnar classification. International Journal of Epidemiology **52**(4), 1268-1275 (2023)

7. Li, C.: Little's Test of Missing Completely at Random. The Stata Journal (2013)

8. Little, R.J., Carpenter, J.R., Lee, K.J.: A comparison of three popular methods for handling missing data: complete-case analysis, inverse probability weighting, and multiple imputation. Sociological Methods & Research **53**(3), 1105-1135 (2024)

9. Little, R.J.A.: A Test of Missing Completely at Random for Multivariate Data with Missing Values. Journal of the Am. Stat. Association **83**(404), 1198-1202 (1988)

10. Mann, H.B., Whitney, D.R.: On a test of whether one of two random variables is stochastically larger than the other. The Annals of math. stat. pp. 50-60 (1947)

11. Mohan, K., Pearl, J.: Graphical models for processing missing data. Journal of the American Statistical Association **116**(534), 1023-1037 (2021)

12. Muzellec, B., Josse, J., Boyer, C., Cuturi, M.: Missing data imputation using optimal transport. In: ICML. pp. 7130-7140 (2020)

13. Pei, H., Wei, B., Chang, K.C.C., Lei, Y., Yang, B.: Geom-gcn: Geometric graph convolutional networks. In: ICLR (2020)

14. Platonov, O., Kuznedelev, D., Diskin, M., Babenko, A., Prokhorenkova, L.: A critical look at evaluation of gnns under heterophily: Are we really making progress? In: The Eleventh International Conference on Learning Representations (2023)

15. Rebin, D.B.: Inference and missing data. Biometrika **63**(3), 581-592 (1976)

16. Rossi, E., Kenlay, H., Gorinova, M.I., Chamberlain, B.P., Dong, X., Bronstein, M.M.: On the unreasonable effectiveness of feature propagation in learning on graphs with missing node features. In: Learning on Graphs Conference (2022)

17. Rozemberczki, B., Allen, C., Sarkar, R.: Multi-scale attributed node embedding. Journal of Complex Networks **9**(2) (05 2021)

18. Serrano, R., Laclau, C., Jeudy, B., Largeron, C.: Reconstructing the unseen: Griot for attributed graph imputation with optimal transport. In: ECML-PKDD. pp. 269-286. Springer (2024)

19. Shadbahr, T., Roberts, M., Stanczuk, J., Gilbey, J., Teare, P., Dittmer, S., Thorpe, M., Torne, R.V., Sala, E., Lio, P., et al.: Classification of datasets with imputed missing values: Does imputation quality matter? arXiv:2206.08478 (2022)

20. Shadbahr, T., Roberts, M., Stanczuk, J., Gilbey, J., Teare, P., Dittmer, S., Thorpe, M., Torné, R.V., Sala, E., Lió, P., et al.: The impact of imputation quality on machine learning classifiers for datasets with missing values. Communications medicine **3**(1), 139 (2023)

21. Sportisse, A.: Handling heterogeneous and MNAR missing data in statistical learning frameworks: imputation based on low-rank models, online linear regression with SGD, and model-based clustering. Ph.D. thesis, Sorbonne Université (2021)

22. Tang, J., Sun, J., Wang, C., Yang, Z.: Social influence analysis in large-scale networks. In: Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining. pp. 807-816 (2009)

23. Um, D., Park, J., Park, S., young Choi, J.: Confidence-based feature imputation for graphs with partially known features. In: ICLR (2023)

24. Van Buuren, S., Groothuis-Oudshoorn, K.: mice: Multivariate imputation by chained equations in r. Journal of statistical software **45**, 1-67 (2011)

25. Yang, Z., Cohen, W., Salakhudinov, R.: Revisiting semi-supervised learning with graph embeddings. In: ICML. pp. 40-48 (2016)