Random Graphs with Dependent Edges

You are reading version 1 of this direction, frozen 2026-10-04. The latest version is version 2.

Version 1 of 2201 papers252 conceptsfrozen 2026-10-04

In classical network theory, we often treat the existence of an edge between two nodes as a coin flip. In the Erdős-Rényi model, every possible connection is an independent Bernoulli trial. In the Stochastic Block Model (SBM), these trials are still independent, just with different probabilities based on group membership.

However, real-world networks—from protein interactions to social circles—rarely behave this way. If Alice knows Bob and Bob knows Charlie, the probability that Alice knows Charlie is significantly higher than a random flip would suggest. This "triadic closure" is a fundamental violation of edge independence. Recent research has shifted toward models that explicitly account for these dependencies, moving from simple pairwise probabilities to complex structural distributions.

The Failure of the Independence Assumption

The assumption that edges are independent is mathematically convenient but structurally fragile. When we assume independence, we lose the ability to model "contagious" interactions. As Hadeel Soliman and Subhadeep Paul argue in their work on Multivariate Community Hawkes Models, real-world communication often triggers cascades where one event directly influences the likelihood of another, forming triangles and reciprocated links that independent models simply cannot predict.

This gap is particularly visible in vertex degrees. Kaisheng Lin demonstrated that in inhomogeneous random graphs, degree counts are inherently correlated. The number of nodes with degree $k$ is not independent of the number of nodes with degree $k+1$. Failing to account for this leads to deceptive visualizations and inaccurate statistical tests, especially in the "tails" of the distribution where high-degree hubs reside.

Mathematical Frameworks for Dependency

To move beyond independence, researchers are developing new probabilistic foundations. Alan M. Frieze and Santosh S. Vempala introduced Logconcave Random Graphs, a powerful generalization where edge weights are drawn from a logconcave distribution. This allows for complex correlations between edges while maintaining enough mathematical structure to prove that properties like connectivity and Hamiltonicity still emerge at predictable thresholds.

In the realm of Bayesian inference, Simón Lunagómez and Sayan Mukherjee proposed geometric representations where nodes are points in a $d$-dimensional space. Here, the dependency is spatial: if two nodes are close to a third, they are likely close to each other. This geometric constraint naturally captures the clustering and sparsity that independent Bernoulli models struggle to replicate.

Generative Models and the Triad Problem

In deep learning, the "edge independence" problem manifests in Graph Auto-Encoders (GAEs). Most GAE decoders predict the existence of an edge by looking at only two node embeddings at a time. Han Shi and James Kwok addressed this by introducing the Triad Decoder, which predicts edges in groups of three. By explicitly modeling triadic closure, the model generates more realistic graphs and improves link prediction.

Similarly, Sudhanshu Chanpuriya and Cameron Musco established a theoretical hierarchy showing that models with higher edge dependency—such as those using global latent variables—are far more efficient. They can replicate complex structures like cliques without "memorizing" the training data, whereas independent models require massive overlap with the training set to achieve the same structural fidelity.

Applications in Causal Discovery and Biology

The shift toward dependency is not just theoretical; it is essential for accuracy in applied fields:

  • Causal Discovery: Yashas Annadani and Cheng Zhang developed BayesDAG, which uses gradient-based sampling to find Directed Acyclic Graphs (DAGs). They argue that traditional methods using independent Bernoulli masks fail to capture the structural interdependencies required to ensure a graph remains a valid DAG.
  • Connectomics: In brain network analysis, Joshua T. Vogelstein and colleagues found that while signal-subgraph classifiers can work under independence assumptions, they ignore the high edge correlation inherent in biological systems.
  • Community Detection: Subhadeep Paul and Yuguo Chen introduced the Superimposed Stochastic Block Model to account for higher-order motifs, proving that clustering based on these dependencies is often more reliable than clustering based on individual edges.

The Path Forward

The core intuition of this research direction is that the whole is more than the sum of its edges. By treating a graph as a joint distribution of interdependent connections rather than a collection of independent ones, we can build models that are not only more realistic but also more statistically robust. Whether through sequential generation with RNNs or topology-aware tensor decomposition, the field is moving toward a "structural" view of networks that respects the inherent coupling of real-world data.

Papers in this version

Showing 60 of 201 papers.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 141 papers
  2. Version 1 · 2026-10-04 · 201 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_edge_independence_assumption_independent_03b395b5,
  title = {edge independence assumption (independent edge assumption)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/edge-independence-assumption-independent-edge-assumption/rdr_03b395b5d70448358b54436899d818f3},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 1, frozen text):

@misc{lacuna_random_graphs_with_dependent_edges_03b395b5_v1,
  title = {Random Graphs with Dependent Edges},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/random-graphs-with-dependent-edges/rdr_03b395b5d70448358b54436899d818f3/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}