Exploring Edge Probability Graph Models Beyond Edge Independency: Concepts, Analyses, and Algorithms

Authors: Fanchen Bu, Ruochen Yang, Paul Bogdan, Kijung Shin
Primary area: learning on graphs and other geometries & topologies
Keywords: Random graph models, edge dependency, triangle density, subgraph densities, tractability, variability

Abstract:
Desirable random graph models (RGMs) should 
*(i)* reproduce *common patterns* in real-world graphs (e.g., high clustering),
*(ii)* generate *variable* (i.e., not overly similar) graphs, and 
*(iii)* remain *tractable* to compute and control graph statistics.
A common class of RGMs (e.g., Erd\H{o}s-R\'{e}nyi and stochastic Kronecker) outputs edge probabilities, and we need to realize (i.e., sample from) the edge probabilities to generate graphs.
Typically, each edge's existence is assumed to be determined independently for simplicity and tractability.
However, with edge independency, RGMs theoretically cannot produce high subgraph densities and high output variability simultaneously.
In this work, we explore realization beyond edge independence that can better reproduce common patterns while maintaining high tractability and variability.
Theoretically, we propose an edge-dependent realization framework called *binding* that provably preserves output variability, and derive *closed-form* tractability results on subgraph (e.g., triangle) densities in generated graphs.
Practically, we propose algorithms for graph generation with binding and parameter fitting of binding.
Our empirical results demonstrate that binding exhibits high tractability and well reproduce patterns such as high clustering, significantly improving upon existing RGMs assuming edge independency.

Decision: reject
Reviewer scores: 5, 6, 6, 6

Reviews and discussion:
<thread>
creation date:
1729435843867

thread_type:
official_review

<thread_object>
creator: reviewer_xvy1

<content>
summary:
This paper proposes a new configurable way to generate random graphs with dependencies between the edges, in a fine-grained way that make it possible to control parameters such as the number of triangles, clustering coefficients, etc. 

The simplest and most famous random graph models, such as Erdos-Renyi, have edges appear independently of each other (in Erdos-Renyi for example the probability of each edge to appear is $p$, independently of all others). This kind of behavior makes analysis easier, but on the other hand it provably cannot capture properties of realistic graphs, such as a large number of triangles/motifs, and the tendancy of realistic graphs to be relatively clustered.

More modern random graph models, that are better at capturing real world characteristics, tend to have dependencies between the edges. One example is random geometric graphs, where points are randomly located on a high-dimensional sphere. But still, most of these models are not very flexible, they are controlled by some global parameters but it may be difficult/impossible for the designer to build a graph that matches specific desired properties.

This paper provides several variants of a new and simple method, called binding, to generate random graphs with high variability (i.e., that do not match a single specific pattern) but also being realistic (having high triangle density, high clusterability, etc). The core idea is simple, and stems from the following question: what is the random graph model with all edges appearing with probability $p$ (possibly dependently), and, say, the largest expected number of triangles? It turns out that this is the distribution which is equal to a complete graph with probability $p$, and empty graph otherwise. Binding is a similar process, picking the same "threshold" to groups of random nodes in order to create small cliques / dense graphs. The proposed model allows to work with predetermined edge probabilities, not necessarily uniform.

The authors propose a couple of different binding methods, one that is sequential and another one that is parallelizable and easier to analyze. They prove several theoretical results: for example, that it is possible to efficiently match a target expected number of triangles by a suitable optimization process. The authors also run some experiments demonstrating the verstality of this method in practice, showing ability to generate diverse and realistic degree distributions or obtain a large triangle coefficient. Another experiment shows that the running time is decently fast, especially for the parallelizable version.

strengths:
- An elegant, novel and flexible method to generate random graphs. Although the generated graphs from, say, the local binding model do not yet seem fully realistic to me, this is a good step in the right direction and the basic binding primitive is natural and analyzable.

- The paper is well written in general. The mathematical statements are clear, intuitive, interesting, and believable (I have not fully checked the proofs).

- The topic of "realistic" random graph models is very important and this paper certainly advances the literature (even if by a small step) on this topic.

weaknesses:
- The experimental section does not provide a lot of information beyond the theoretical part of the paper. It is relatively clear to me, without the experiments or even looking at the proofs, that this model will be able to capture a target triangle density, for example. I would have hoped for the experimental section to show other directions in which this model is realistic. (See questions below.)

questions:
My questions are mostly about how "realistic" this random process is:

1. What are some types of real-world network properties you believe *cannot* be captured by the binding processes you outlined in the paper?
Can it capture realistic community structure faithfully?

2. One thing missing from the paper, as outlined in the weaknesses part, is an experimental part showing the this specific model is useful for downstream applications (and not just as proxy for estimating quantities that are practically useful in downstream applications, such as triangle density). I would imagine that one way to instantiate it is by pre-training some graph neural network on this kind of graphs and show that this pretraining helps improve the performance on some applied benchmark. Do you think it will be possible/realistic to design such an experiment? In what context do you think this random model could come up useful?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730084254231

thread_type:
official_review

<thread_object>
creator: reviewer_lprh

<content>
summary:
This paper proposes the concept of binding to upgrade edge-independent random graph models, which are RGMs in which each edge is sampled independently. Binding allows for sampling a graph with given marginal probabilities for each edge, but with some dependence between the edges, allowing for more realistic graph distributions in terms certain statistics, like high clustering coefficient. The idea is to partition all possible edges, then to sample a single uniform random variable for each group in the partition, and add edges to the sampled graph if the random variable is less than edge's marginal probability. This adds edge dependence in the sense that if $e$ and $e'$ are in the same partition, and the marginal probability of the former edge is higher, then the sampling of the former guarantees the sampling of the latter. The paper then proposes a scheme for finding a partition at sampling time, as well as a parallelized scheme which relaxes the edge partition to independent edge groupings. Finally, the paper presents theoretical validation of the tractability of their methods, showing that the samples are generated in quadratic time; and empirical validation of the increased quality of samples when using binding, showing that upon fitting parameters of their model to match the input graph's triangle count, samples indeed match the triangle count closely, while not harming how well the node degree and node pair distance distributions are matched.

strengths:
- The central problem that is tackled, alleviating limitations of edge-independent / inhomogeneous ER graphs, is well-motivated in the text.
- The proposed concept of binding can be applied to augment several different edge-independent random graph models.
- Experiments demonstrate the effective of binding at matching triangle on four well-known kinds of RGMs and several well-known graph datasets.
- There is theoretical work guaranteeing the tractability of the sampling algorithms.
- The organization of the paper is generally logical and clear.

weaknesses:
- Some writing could be clearer. For example, at the end of page 1, the authors say they will explore EPGMs, but it is not clear at that point what it is, or whether it is a previously-proposed concept versus something being proposed in this paper. More natural language descriptions of math, e.g., Property 4.4, would facilitate reading.
- Given that binding is perhaps the main concept of this work, its formal definition should be in the main paper, and there should probably be some natural language description of the idea of general binding along with Algorithm 1 (e.g., as given in the summary above). There could also be more description of the modeling implications of binding: Does binding reflect some natural process that gives rise to real-world graphs? On the other hand, could the model assumption in binding be limiting in some way?
- At least in the main paper, the theoretical work gives guarantees about the tractability of the sampling algorithms, but there is no proof that binding can alleviate modeling issues beyond Proposition 5.2, which is fairly vague - "binding produces higher or
equal subgraph densities", but how much higher? E.g., does binding solve the motivating issue in Theorem 3.3 that edge-independent models cannot generate many triangles with low overlap?

questions:
Two kinds of questions are asked above regarding 1) the modeling side of binding, and 2) possible guarantees that binding alleviates the dense subgraph count vs overlap issue that motivates the work.

### Typos / minor
- Lines 3-5 in Algorithm 2: Is this simply a for-loop from $1$ to $R$? That might be slightly clearer if so. 
- Line 371 "EGPMs" -> "EPGMs"
</content>
</thread_object>

</thread>
<thread>
creation date:
1730556636866

thread_type:
official_review

<thread_object>
creator: reviewer_syr6

<content>
summary:
The paper introduces the concept of EPGM, which is wider than the edge-independent graph models. The authors propose a general binding algorithm, as well as local and parallel binding algorithms, to generate networks with high variability and clustering. They
also present closed-form results concerning triangles and discuss time complexities. The authors conduct simulation studies to evaluate their models. Overall, the idea of binding is interesting.

strengths:
The authors propose a general binding algorithm, as well as local and parallel binding algorithms, to generate networks with high variability and clustering. They also present closed-form results concerning triangles and discuss time complexities.

weaknesses:
1. Only provides results for triangles
2. Focus on a specific subclass of EPGM
3. Simulation results are not very convincing

questions:
(a)  Similar effort can be found in the exchangeable network models, in view of relaxing conditional independence among edges. See for example 

Harry Crane and Walter Dempsey. Edge exchangeable models for interaction networks.
Journal of the American Statistical Association, 113(523):1311–1326, 2018. PMID:
30467447.

Weichi Wu, Sofia Olhede, and Patrick Wolfe. Tractably modeling dependence in networks
beyond exchangeability. Bernoulli, 31(1):584 – 608, 2025

Please discuss more on this in literature.
		
(b) The organization of the paper can be improved. For example, Definition 3.1 and Theorem 3.3  seem to take up too much space without demonstrating any clear importance. By contrast, the key definition of binding is placed in the appendix. 

(c) The authors focus a specific subclass ( good subsets ) of EPGM in section 4, however, why are the subsets considered are important? The paper can be improved if more motivation besides the feasibility are given. 

(d)   The authors should compare and discuss more general models, such as the graphon model and the exponential random graph model  as mentioned in their Section 3.2 in addition to the four specific models in Section 5.4.  These models exhibit edge dependence, and is able to produce many triangles (especially the exponential random graph). It would be beneficial if the authors could provide a discussion on these models. 

(e) Theorem 5.7 provides the probability result for 3-motifs only, and the proof uses an enumeration method  that could be difficult to extend to higher order motifs, which can be restrictive sometime in practice.  A way to alleviate this is to provide codes in package for motives 4,5,6 as discussed  in page 21. Also, please discuss how the closed-form varies with changes in \( p \), \( g \), and \( R \) for readers to better understand the results. Is it possible to consider several motives together? 

(f) Besides triangle, other network motives such as transitivity, can be important. Could the binding methods extend to 'transitivity' and 'triangle' simultaneously?  Also please add some reference for the importance of triangle since the paper focuses on this quantity. 

(g)The authors conduct fittings in their simulations, however, the discussion of fitting in the main text is quite limited. If possible, the authors could provide some discussion on the properties of fitting, such as consistency.

(h) The results in Table 1 is a little confusing. In the caption it writes ``The statistics are averaged over 100 random trails".  But the number of triangles are solved by  tractability results. The data set is given, so what does the `random trial mean'? For edge independent models, densities of triangles can be computed tractably, too. On the other hand, the results in Table 1 might not be very meaningful. First, the results show that a parameter of a model is close to the corresponding real world data. However, what really matter is that the proposed method can produce a graph with similar property in high probability, which can be evaluated using simulated mean squared of $($ground true $\Delta$-generated $\Delta$$)^2$. Second, the comparison is not meaningful. For instance, in the case of the ER model, the authors estimate the connection probability matrix using the ER graph, then optimize their model parameters (number of triangles) based on a loss function that relates to the triangles, and subsequently compare the number of triangles from their model with those from the ER graph. Then the results are surely better since the authors are optimizing the number of triangles (with respect to the observed number of triangles) in a large class of model that include the ER graph. On the other hand, ER model, or other independent edge model is not necessarily good for the real data set in addition to the discrepancy of the numbers of triangles. Therefore, improving in triangle numbers comparing with those possibly inappropriate model could be less significant in practice. The authors could consider comparing with other models that take into account triangles, such as exponential random graphs and others.
		
(i)  Please discuss in  detail the differences between LOCLBDG and PARABDG, as these two methods are distinct (as evidenced by the results in Figure 3). It would be beneficial to explain under which scenario one should choose LOCLBDG (or PARABDG)
</content>
</thread_object>

</thread>
<thread>
creation date:
1730572643456

thread_type:
official_review

<thread_object>
creator: reviewer_qw53

<content>
summary:
The authors propose a generative random graph model that aims to balance realism of the generated graphs with computational efficiency of the generation process, seeking to increase clustering and variability in graphs generated by traditional models like Erdős-Rényi and stochastic block models. To achieve this, the paper uses an edge-dependent graph model (EPGM), which they use to create controlled dependencies among edges, and proposes a tractable algorithm for graph generation. The study includes a theoretical framework, practical algorithms, and experimental validation to demonstrate the generation of graphs.

strengths:
- The paper builds on a solid theoretical foundation of edge-dependent random graph models, extending existing work to improve clustering and variability.
- The supplementary materials provide sufficient details for understanding and reproducing the experiments.
- The paper demonstrates a clustering and variability across by fitting different real-world datasets.
- The paper offers a _potentially_ useful tool for generating random graphs with enhanced clustering and variability by fitting model parameters to specific datasets.
- The authors provide a thorough reproducibility package, including all experimental workflows, parameters, and scripts, though this package could benefit from more comprehensive documentation.

weaknesses:
- **Validation**: The term "desirable" graph properties---namely, realistic structures, patterns, and variability---is vague, highly domain-dependent, and lacks formalization in the paper, making it challenging to assess whether the proposed model achieves these goals. A formal definition and visual examples earlier in the text could maybe help clarify these aims.
- **Limited Exploration of Desirable Properties**: The paper does not fully explore the binding approach’s effects on other important network properties, such as modularity, conductance, and resilience, which are also highly desirable in certain domains.
- **Dependence on Parameter Fitting**: The model generates graphs after fitting model parameters to real-world networks, rather than directly from scratch. It is unclear whether this model could lend itself to straightforward manual parameterization to generate synthetic graphs independently, a feature offered by models like the Lancichinetti-Fortunato-Radicchi (LFR) benchmark graph generator. This suggest that the graph generator has a narrow practical use.
- **Scalability**: It is unclear if the model can efficiently generate realistic extremely large graphs, given that the experimental results focus on relatively small networks.
- **Unclear Tractability**: The explanation of the binding schemes' tractability could be more detailed and intuitive, especially as it seems that binding is computationally slower than edge-independent methods, which could hinder its scalability to larger graphs.
- **Comparison with Established Benchmarks**: The paper does not compare with the Lancichinetti–Fortunato–Radicchi (LFR) benchmark data generator, which also generates graphs with **power-law degree distributions, variability, and high clustering**. Given that the LFR model shares similar motivations and goals with the proposition, a comparison here would add necessary context. Additionally, faster and more efficient follow-up models to LFR align well with the goals of this study, particularly in terms of tractability.

questions:
-/-
</content>
</thread_object>

</thread>
<thread>
creation date:
1733200949315

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Summary of Discussions (Part 1/2: Strengths)

comment:
Dear (S)ACs and Reviewers,

As the discussion period is ending, we would like to present a summary of our discussions with the reviewers for reference. 
First, we thank all the reviewers for their invaluable time and constructive comments.

---

We are greatly encouraged that the reviewers found our work has the following strengths, aligning with our claims in the paper:

### **[Strength 1] An important and motivating problem of improving upon edge-independent graph models to develop better random graph models**
- [LPrH] `The central problem that is tackled, alleviating limitations of edge-independent / inhomogeneous ER graphs, is well-motivated in the text`
- [xVy1] `The topic of "realistic" random graph models is very important and this paper certainly advances the literature (even if by a small step) on this topic`

### **[Strength 2] An interesting idea of edge-dependent graph models (EPGMs) with solid theoretical contributions**
- [qw53] `The paper builds on a solid theoretical foundation of edge-dependent random graph models`
- [sYr6] `Overall, the idea of binding is interesting`
- [sYr6] `They also present closed-form results concerning triangles and discuss time complexities`
- [LPrH] `The proposed concept of binding can be applied to augment several different edge-independent random graph models`
- [LPrH] `There is theoretical work guaranteeing the tractability of the sampling algorithms`
- [xVy1] `An elegant, novel and flexible method to generate random graphs`
- [xVy1] `A good step in the right direction and the basic binding primitive is natural and analyzable`

### **[Strength 3] Empirical strengths of the proposed models and algorithms to generate better random graphs**
- [qw53] `The paper demonstrates a clustering and variability across by fitting different real-world datasets`
- [qw53] `The paper offers a potentially useful tool for generating random graphs with enhanced clustering and variability`
- [LPrH] `Experiments demonstrate the effective of binding at matching triangle on four well-known kinds of RGMs and several well-known graph datasets`
- [LPrH] `Empirical validation of the increased quality of samples when using binding, showing that upon fitting parameters of their model to match the input graph's triangle count, samples indeed match the triangle count closely, while not harming how well the node degree and node pair distance distributions are matched`
- [xVy1] `The authors also run some experiments demonstrating the verstality of this method in practice, showing ability to generate diverse and realistic degree distributions or obtain a large triangle coefficient. Another experiment shows that the running time is decently fast, especially for the parallelizable version`

### **[Strength 4] Clear and logical writing**
- [LPrH] `The organization of the paper is generally logical and clear`
- [xVy1] `The paper is well written in general. The mathematical statements are clear, intuitive, interesting, and believable`

### **[Strength 5] Good reproducibility with public code and details in the supplementary materials**
- [qw53] `The supplementary materials provide sufficient details for understanding and reproducing the experiments`
- [qw53] `The authors provide a thorough reproducibility package, including all experimental workflows, parameters, and scripts`
</content>
</thread_object>

</thread>


Metareview:
metareview:
Reviews on this paper were split. Reviewers felt that the problem being addressed by the paper (the inability of edge-independent graph models to capture realistic network features) is important. The solution of correlating edge selections together via `binding' is simple and elegant, and allows for a theoretically tractible model. The binding technique can be applied to any underlying edge-independent model. 

However, there are concerns that the binding model may not be the best choice in terms of generating realistic graphs. Of course, binding by design can allow targeting any specified triangle density in the generated graph. But this is just one property that one may consider when looking at the realism of a graph model. The authors did add experiments during the rebuttal studying other important graph properties like conductance and vertex centrality measures. They show that the binding approach at least doesn't hurt here, but it doesn't seem to help much either.

Overall, this paper was at the borderline of the bar for acceptance.