Machine Learning under Non-IID Graph Dependencies

34 concepts35 papers1 proposal

The bedrock of classical statistical learning theory is the assumption that data points are Independent and Identically Distributed (i.i.d.). In an i.i.d. world, every sample drawn from a distribution provides a clean, uncoupled piece of information.

Graph-structured data fundamentally violates this assumption. In a social network, a protein-protein interaction web, or a citation graph, nodes are explicitly interconnected by edges. The label or feature profile of a single node is inherently dependent on its neighbors. If you alter the properties of one node, the structural context of its entire neighborhood shifts.

This relational data dependency creates severe challenges across the machine learning lifecycle. Standard uncertainty quantification fails because prediction errors are correlated across edges. Generalization bounds collapse because we cannot simply count independent samples to prove a model will perform well on unseen data. Even basic validation techniques like train-test splits suffer from data leakage due to topological links.

To build trustworthy models on graphs, researchers are rewriting statistical frameworks to natively account for non-i.i.d. graph dependencies.


Restoring Conformal Guarantees without Exchangeability

A core requirement of trustworthy machine learning is uncertainty quantification. We want models to output not just a point prediction, but a prediction set that is mathematically guaranteed to contain the true label with a user-defined probability (e.g., 95%). Conformal Prediction (CP) is the gold standard for this, but it relies on exchangeability—a property implying that the order of data points does not affect their joint distribution.

Because graph topology couples nodes together, graph data is non-exchangeable. If a Graph Neural Network (GNN) mispredicts a well-connected hub node, it is highly likely to mispredict that hub's neighbors as well. Standard conformal prediction ignores this correlation, leading to prediction sets that are either invalid or unnecessarily large.

To fix this, researchers are designing topology-aware calibration mechanisms that adapt to local graph structures:

  • Localized Calibration: Jase Clarkson introduces Neighborhood Adaptive Prediction Sets (NAPS) in Distribution Free Prediction Sets for Node Classification. Instead of calibrating a model using a random, global subset of data, NAPS localizes the calibration process to a node's immediate graph neighborhood. This ensures that the calibration samples share the exact same structural dependencies as the target node, yielding tighter and more valid prediction sets.
  • Topology-Aware Corrections: Kexin Huang et al. develop CF-GNN in Uncertainty Quantification over Graph with Conformalized Graph Neural Networks. The authors use a correction model that explicitly accounts for network topology, shrinking prediction sets by up to 74% compared to standard methods while preserving the exact user-defined coverage guarantees.
  • Link Prediction Guarantees: Moving from nodes to edges, Tianyi Zhao et al. introduce Conformalized Link Prediction (CLP) in Conformalized Link Prediction on Graph Neural Networks. They discover a direct relationship between a graph's "power-law-ness" (its degree distribution) and prediction efficiency, using this structural insight to narrow prediction intervals without sacrificing statistical rigor.

By leveraging transductive learning properties where the graph structure is known upfront, frameworks developed by Pranav Maneriker et al. in Conformal Prediction: A Theoretical Note and Benchmarking Transductive Node Classification in Graphs and Aditya T. Vadlamani et al. in A Generic Framework for Conformal Fairness demonstrate how to scale these rigorous guarantees to massive networks while maintaining fairness across subgroups.


Quantifying Generalization in Interconnected Spaces

How do we know a model will perform well on unseen data? In standard machine learning, generalization bounds (like Rademacher complexity) scale with the number of independent training samples. On a graph, however, message-passing operations mix features across edges, meaning a single node's representation is contingent on its entire multi-hop neighborhood. The loss values of connected nodes are deeply entangled.

To bound the "generalization gap" (the difference between training and test performance) on graphs, theorists must model how these structural dependencies propagate:

Standard ML (IID):      [Sample 1]       [Sample 2]       [Sample 3]  (Uncoupled)

Graph ML (Non-IID):     [Node 1] <=======> [Node 2] <=======> [Node 3]  (Coupled via Message Passing)
  • Structural Distance and Fairness: Jiaqi Ma et al. provide a PAC-Bayesian theoretical analysis in Subgroup Generalization and Fairness of Graph Neural Networks. The authors prove that a node's generalization error is fundamentally bounded by its structural distance from the training set in the feature-topological space. This reveals an inherent source of structural unfairness: nodes belonging to isolated or distant subgraphs suffer from higher error rates because the model cannot effectively generalize across the structural gap.
  • The Continuous Graphon Lens: To analyze massive graphs where discrete dependencies become intractable, Sohir Maskey et al. turn to continuous graph limits in Generalization Analysis of Message Passing Neural Networks on Large Random Graphs. By treating discrete graphs as samples generated from an underlying continuous object called a graphon, they prove that the generalization gap decreases not just with the number of training graphs, but also with the average density and node count within a single graph.
  • Architecture Complexity and Optimization: Huayi Tang et al. analyze GNN generalization through the lens of transductive learning and stochastic gradient descent in Towards Understanding Generalization of Graph Neural Networks. They demonstrate that simpler, shallower architectures often generalize better because they possess smaller Lipschitz constants, which prevents local neighborhood perturbations from causing exploding error propagation across the network.

Ultimately, as unified by Antonis Vasileiou et al. in Understanding Generalization in Node and Link Prediction, a GNN's ability to predict unseen structures is dictated by the density of structural correlations and how tightly the training samples are bound to the underlying graph topology.


Splitting and Sampling Non-IID Data

If data points are dependent, how do you perform cross-validation or hypothesis testing without leaking information? If you randomly assign nodes to a training or testing set, edges will inevitably connect the two sets. During training, a GNN will aggregate information from test nodes, leading to severe data leakage and overly optimistic performance estimates.

Random Split (Leakage):   [Train Node] --------(Edge)--------> [Test Node]  *Information Leaks!*

To run valid statistical tests and optimize models reliably, researchers must find ways to decouple the graph without destroying its underlying relational information:

  • Graph Fission: Aaditya Ramdas et al. introduce a powerful solution in Graph fission and cross-validation. Graph fission splits a single, interconnected graph dataset into multiple independent "synthetic" copies. This technique preserves the essential marginal distributions and structural properties of the original graph while eliminating the cross-sample dependencies that violate classical statistical assumptions, enabling valid post-selection inference and cross-validation.
  • Exposing Split Bias: The danger of ignoring these dependencies is quantified by Ansgar Scherp et al. in The Split Matters: Flat Minima Methods for Improving the Performance of GNNs. The authors demonstrate that standard, fixed data splits heavily mask the true generalization benefits of optimization techniques, emphasizing that randomized, dependency-aware splits are essential for accurate evaluation.
  • Hypothesis-Aware Sampling: For large-scale statistical inference, Yun Wang et al. develop PHASE in A Sampling-based Framework for Hypothesis Testing on Large Attributed Graphs. Instead of relying on uniform sampling—which breaks down when nodes have diverse relational properties—PHASE uses hypothesis-aware random walks to preserve local dependencies, accelerating convergence during hypothesis testing on massive networks.

Transferring Knowledge Across Structural Shifts

The challenges of non-i.i.d. graph dependencies multiply when moving from a source domain to a target domain (domain adaptation) or learning from scarce data (few-shot learning). In these settings, models face a double distribution shift: the node attributes change, and the graph topology changes. For instance, transferring a model from a social network (where similar people connect) to a protein network (where dissimilar molecules connect) requires adapting to entirely different relational mechanisms.

Source Domain (Homophily):    [A] <---> [A] (Similar nodes connect)
                                 |
                                 v  *Structural Shift*
Target Domain (Heterophily):   [A] <---> [B] (Dissimilar nodes connect)

To bridge these domain gaps, models must explicitly disentangle invariant features from shifting topological structures:

By moving away from the fiction of i.i.d. data and directly embracing relational dependencies, these frameworks provide the mathematical and practical tools necessary to make graph-based machine learning as rigorous, predictable, and robust as classical statistical learning.

Key Foundational Work

On the Distribution of the Number of Local Minima of a Random Function on a Graph (1989) — contributed 1 concept elements to this direction.
U-statistics on network-structured data with kernels of degree larger than one (2014) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_relational_data_dependency_non_i_i_d_gra_fdd7ab4b,
  title = {relational data dependency (non-i.i.d. graph dependencies)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/relational-data-dependency-non-i-i-d-graph-dependencies/rdr_fdd7ab4b2c2b4d8196c2783159e73ffc},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-22},
}

This exact version (version 1, frozen text):

@misc{lacuna_relational_data_dependency_non_i_i_d_gra_fdd7ab4b_v1,
  title = {relational data dependency (non-i.i.d. graph dependencies)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/relational-data-dependency-non-i-i-d-graph-dependencies/rdr_fdd7ab4b2c2b4d8196c2783159e73ffc/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-22},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake