On the Power of Edge Independent Graph Models
Authors: Sudhanshu Chanpuriya, Cameron Musco, Konstantinos Sotiropoulos, Charalampos Tsourakakis
NeurIPS 2021 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Our theoretical results help explain why, despite performing well in a variety of other metrics, edge independent graph generative models have been reported to generate graphs with many fewer triangles and squares on average than the real-world graphs that they are trained on. Rendsburg et al. [23] test a suite of these models, including their own CELL model and the related Net GAN model [3]. ... We now present our evaluations of different edge independent graph generative models in terms of the tradeoff achieved between overlap and performance in generating graphs with similar key statistics to an input network. |
| Researcher Affiliation | Academia | Sudhanshu Chanpuriya University of Massachusetts Amherst schanpuriya@umass.edu Cameron Musco University of Massachusetts Amherst cmusco@cs.umass.edu Konstantinos Sotiropoulos Boston University ksotirop@bu.edu Charalampos E. Tsourakakis Boston University & ISI Foundation tsourolampis@gmail.com |
| Pseudocode | Yes | Algorithm 1 Fitting the odds product model input graphical degree sequence d Rn, error threshold ϵ output symmetric matrix P (0, 1)n n with row/column sums approximately d |
| Open Source Code | Yes | For implementation details and code, see the supplemental material. |
| Open Datasets | Yes | POLBLOGS [1] 1,222 33,428 101,043 CITESEER [26] 2,110 7,336 1,083 WEB-EDU [11] 3,031 12,948 10,058 CORA [26] 2,485 10,138 1,558 ROAD-MINNESOTA [24] 2,640 6,604 53 PPI [30] 3,852 75,682 91,461 FACEBOOK [18] 4,039 176,468 1,612,010 |
| Dataset Splits | No | No explicit training, validation, or test dataset splits with specific percentages or counts are provided. The paper mentions training models on a 'given training graph' or 'input network' but does not detail how the data was partitioned for different phases of model development and evaluation. |
| Hardware Specification | No | The paper does not provide any specific details regarding the hardware used to run the experiments, such as GPU models, CPU types, or memory specifications. |
| Software Dependencies | No | The paper mentions general software components like 'Python' or 'scikit-learn' but does not provide specific version numbers for any software or libraries used in the experiments. |
| Experiment Setup | Yes | To control overlap, we follow the approach of the original paper, halting training once the generated graph exceeds a specified overlap threshold with the input graph. We set the rank parameter to a value that allows us to get up to 75% overlap (typical values are 16 and 32). ... For TSVD, letting L be the low-rank approximation of the adjacency matrix, we learn a scalar shift parameter σ using Newton s method such that P = max(0, min(1, L + σ)) has volume V (G). ... we use P = (1 ω)P + ωA, where 0 ω 1. |