Causally Fair Node Classification on Non-IID Graph Data

Technical Summary: Causally Fair Node Classification on Non-IID Graph Data

Problem Statement

Existing fair machine learning research predominantly assumes that data instances are independent and identically distributed (IID). However, real-world graph data (e.g., social networks, credit systems) inherently violates this assumption, as node outcomes are influenced by the attributes and behaviors of neighboring nodes (non-IID settings). While fairness notions have been extended to graph settings, a significant gap remains in applying causality-based fairness to these environments.

The core challenge addressed in this work is the heterogeneity of causal mechanisms across nodes in a graph. In networked data, a node's outcome depends on its own attributes and the aggregated attributes of its neighbors. Consequently, nodes with different neighborhood structures follow different effective causal mechanisms. This variability violates the invariance assumptions required for classical Structural Causal Models (SCMs) and the application of do-calculus, rendering standard causal inference techniques (such as computing interventional distributions $P(x|do(s))$) inapplicable or biased in non-IID settings.

Methodology

The authors propose a framework grounded in the Network Structural Causal Model (NSCM) to address causal inference and fairness in graph data. The methodology proceeds through three main stages:

1. Theoretical Foundation: Restoring Invariance
The paper establishes that causal mechanisms can be rendered invariant across nodes by encoding local structural information.

• Network Structural Causal Model (NSCM): The authors define an NSCM as a tuple $\langle G, U, V, F \rangle$, combining a network $G$ (representing interference between individuals) and a causal diagram $C$ (representing feature relationships).
• Weisfeiler-Lehman (WL) Encoding: To handle structural heterogeneity, the authors utilize node colors derived from the WL graph isomorphism test. Nodes with identical computation trees receive the same color $c(i)$, serving as a structural representation.
• Key Conditions: The authors introduce two conditions under which the heterogeneous networked process can be reduced to a shared causal model:
  • Decomposability: The structural equation can be decomposed into a message-passing mechanism $f^{MP}$ (aggregating neighborhood info) and an internal mechanism $f^{INT}$ (governing node-level effects). This allows the aggregation of neighborhood effects into an intermediate variable $A = g(S, C)$.
  • Graph Independence: The exogenous variables affecting a node are independent of the node's color (structural context).
• Identifiability: Under these conditions, the authors prove that the interventional distribution $P(x|do(s)=s)$ is identifiable via adjustment on the structural variable $C$. They derive a representation (Theorem 4) showing that observational and interventional distributions share a common latent functional component, differing only in how they average over the structural variable $C$.

2. Estimation Framework: Message Passing Variational Autoencoder (MPVA)
To estimate the interventional distributions without explicitly recovering latent variables, the authors propose MPVA, a deep learning framework combining:

• Message Passing Neural Networks (MPNN): To learn the intermediate representation $\hat{A}$ by aggregating causal influences from neighbors, effectively approximating the message-passing mechanism $g(S, C)$.
• Conditional Variational Autoencoder (cVAE): To model the conditional distribution $P(X|\hat{A}, Z)$, capturing the shared functional component between the intermediate representation and the outcome.
• Inference Process: The framework follows an Abduction-Action-Prediction structure:
  1. Abduction: Encode observed outcomes to infer latent variables.
  2. Action: Apply the intervention $do(s)$ to the intermediate representation $\hat{A}$ via the MPNN.
  3. Prediction: Decode the intervened representation to estimate the interventional outcome.

3. Fair Node Classification
The estimated interventional distributions are integrated into a node classification task via a causal fairness regularization term. The objective minimizes the discrepancy in predictions between favorable ($s^+$) and unfavorable ($s^-$) demographic groups under intervention:
$$\ell_f = E[h(\tilde{x})|do(s^+)] - E[h(\tilde{x})|do(s^-)]$$
This term is added to the standard classification loss, allowing the model to learn representations that are causally fair while maintaining predictive accuracy.

Key Contributions

• Theoretical Extension: The paper provides a rigorous theoretical foundation for extending causal inference (specifically do-calculus) to non-IID graph data by formalizing the NSCM and identifying conditions (Decomposability and Graph Independence) that restore invariance.
• Novel Framework: It introduces MPVA, a novel architecture that combines MPNNs and cVAEs to approximate interventional distributions in graph settings, overcoming the limitations of direct do-calculus application in heterogeneous networks.
• Fairness Regularization: It proposes a method to incorporate causal fairness constraints directly into the training of node classifiers by leveraging estimated interventional distributions.

Experimental Results

The authors evaluate MPVA on both semi-synthetic datasets (derived from the Credit Dataset with controlled causal mechanisms) and real-world datasets (Credit Defaulter and German Credit).

• Performance: Empirical results demonstrate that MPVA outperforms conventional methods (including those assuming IID and existing graph fairness baselines) in approximating interventional distributions.
• Fairness: The method achieves improved fairness metrics (specifically reducing risk differences and causal discrepancies) while maintaining competitive prediction accuracy.
• Generalizability: The framework is shown to be effective in scenarios where causal mechanisms vary with local network structures, a setting where standard methods fail.

Significance and Claims

The paper claims to address a fundamental challenge in fair machine learning: the application of causal fairness to interconnected, non-IID data. By demonstrating that structural representations (via WL colors) can restore the invariance required for causal inference, the work motivates a shift from purely statistical fairness to causality-based fairness in complex ML applications. The authors position their findings as a step toward relaxing the classic IID assumptions in algorithmic fairness, providing a principled approach to mitigate bias induced by network structures and interference. The work does not claim to solve all graph fairness problems but specifically targets the gap in principled causal exploration for non-IID settings.