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

• URL: http://arxiv.org/abs/2405.16726v2
• Date: Tue, 22 Oct 2024 07:05:57 GMT
• Title: Exploring Edge Probability Graph Models Beyond Edge Independency: Concepts, Analyses, and Algorithms
• Authors: Fanchen Bu, Ruochen Yang, Paul Bogdan, Kijung Shin,
• Abstract summary: Desirable random graph models (RGMs) should generate realistic structures such as high clustering (i.e., high subgraph densities) A common class of RGMs (e.g. triangle preservesg., ErdHos-R'enyi and Kronecker) outputs edge probabilities. With edge independency, RGMs theoretically cannot produce high subgraph densities and high output variability simultaneously.
• Score: 26.550266795403022
• License:
• Abstract: Desirable random graph models (RGMs) should (i) generate realistic structures such as high clustering (i.e., high subgraph densities), (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 produce more realistic structures while maintaining high traceability 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 generates realistic graphs with high clustering, significantly improving upon existing RGMs assuming edge independency.

Related papers

• Gradient-Based Spectral Embeddings of Random Dot Product Graphs [7.612218105739107]
  In this paper, we show how to better solve the embedding problem of the Random Dot Product Graph (RDPG) We develop a novel feasible optimization method in the resulting manifold. Our open-source algorithm implementations are scalable, and unlike the they are robust to missing edge data and can track slowly, latent positions from streaming graphs.
  arXiv  Detail & Related papers  (2023-07-25T21:09:55Z)
• HiGen: Hierarchical Graph Generative Networks [2.3931689873603603]
  Most real-world graphs exhibit a hierarchical structure, which is often overlooked by existing graph generation methods. We propose a novel graph generative network that captures the hierarchical nature of graphs and successively generates the graph sub-structures in a coarse-to-fine fashion. This modular approach enables scalable graph generation for large and complex graphs.
  arXiv  Detail & Related papers  (2023-05-30T18:04:12Z)
• Graph Generation with Diffusion Mixture [57.78958552860948]
  Generation of graphs is a major challenge for real-world tasks that require understanding the complex nature of their non-Euclidean structures. We propose a generative framework that models the topology of graphs by explicitly learning the final graph structures of the diffusion process.
  arXiv  Detail & Related papers  (2023-02-07T17:07:46Z)
• Collaborative likelihood-ratio estimation over graphs [55.98760097296213]
  Graph-based Relative Unconstrained Least-squares Importance Fitting (GRULSIF) We develop this idea in a concrete non-parametric method that we call Graph-based Relative Unconstrained Least-squares Importance Fitting (GRULSIF) We derive convergence rates for our collaborative approach that highlights the role played by variables such as the number of available observations per node, the size of the graph, and how accurately the graph structure encodes the similarity between tasks.
  arXiv  Detail & Related papers  (2022-05-28T15:37:03Z)
• A Robust and Generalized Framework for Adversarial Graph Embedding [73.37228022428663]
  We propose a robust framework for adversarial graph embedding, named AGE. AGE generates the fake neighbor nodes as the enhanced negative samples from the implicit distribution. Based on this framework, we propose three models to handle three types of graph data.
  arXiv  Detail & Related papers  (2021-05-22T07:05:48Z)
• Learning non-Gaussian graphical models via Hessian scores and triangular transport [6.308539010172309]
  We propose an algorithm for learning the Markov structure of continuous and non-Gaussian distributions. Our algorithm SING estimates the density using a deterministic coupling, induced by a triangular transport map, and iteratively exploits sparse structure in the map to reveal sparsity in the graph.
  arXiv  Detail & Related papers  (2021-01-08T16:42:42Z)
• Factorizable Graph Convolutional Networks [90.59836684458905]
  We introduce a novel graph convolutional network (GCN) that explicitly disentangles intertwined relations encoded in a graph. FactorGCN takes a simple graph as input, and disentangles it into several factorized graphs. We evaluate the proposed FactorGCN both qualitatively and quantitatively on the synthetic and real-world datasets.
  arXiv  Detail & Related papers  (2020-10-12T03:01:40Z)
• Unsupervised Graph Embedding via Adaptive Graph Learning [85.28555417981063]
  Graph autoencoders (GAEs) are powerful tools in representation learning for graph embedding. In this paper, two novel unsupervised graph embedding methods, unsupervised graph embedding via adaptive graph learning (BAGE) and unsupervised graph embedding via variational adaptive graph learning (VBAGE) are proposed. Experimental studies on several datasets validate our design and demonstrate that our methods outperform baselines by a wide margin in node clustering, node classification, and graph visualization tasks.
  arXiv  Detail & Related papers  (2020-03-10T02:33:14Z)
• Residual Correlation in Graph Neural Network Regression [39.54530450932135]
  We show that conditional independence assumption severely limits predictive power. We address this problem with an interpretable and efficient framework. Our framework achieves substantially higher accuracy than competing baselines.
  arXiv  Detail & Related papers  (2020-02-19T16:32:54Z)
• Block-Approximated Exponential Random Graphs [77.4792558024487]
  An important challenge in the field of exponential random graphs (ERGs) is the fitting of non-trivial ERGs on large graphs. We propose an approximative framework to such non-trivial ERGs that result in dyadic independence (i.e., edge independent) distributions. Our methods are scalable to sparse graphs consisting of millions of nodes.
  arXiv  Detail & Related papers  (2020-02-14T11:42:16Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.