Random Geometric Graphs on Euclidean Balls

• URL: http://arxiv.org/abs/2010.13734v1
• Date: Mon, 26 Oct 2020 17:21:57 GMT
• Title: Random Geometric Graphs on Euclidean Balls
• Authors: Ernesto Araya Valdivia
• Abstract summary: We consider a latent space model for random graphs where a node $i$ is associated to a random latent point $X_i$ on the Euclidean unit ball. For certain link functions, the model considered here generates graphs with degree distribution that have tails with a power-law-type distribution.
• Score: 2.28438857884398
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider a latent space model for random graphs where a node $i$ is associated to a random latent point $X_i$ on the Euclidean unit ball. The probability that an edge exists between two nodes is determined by a ``link'' function, which corresponds to a dot product kernel. For a given class $\F$ of spherically symmetric distributions for $X_i$, we consider two estimation problems: latent norm recovery and latent Gram matrix estimation. We construct an estimator for the latent norms based on the degree of the nodes of an observed graph in the case of the model where the edge probability is given by $f(\langle X_i,X_j\rangle)=\mathbbm{1}_{\langle X_i,X_j\rangle\geq \tau}$, where $0<\tau<1$. We introduce an estimator for the Gram matrix based on the eigenvectors of observed graph and we establish Frobenius type guarantee for the error, provided that the link function is sufficiently regular in the Sobolev sense and that a spectral-gap-type condition holds. We prove that for certain link functions, the model considered here generates graphs with degree distribution that have tails with a power-law-type distribution, which can be seen as an advantage of the model presented here with respect to the classic Random Geometric Graph model on the Euclidean sphere. We illustrate our results with numerical experiments.

Related papers

• Information-Theoretic Thresholds for Planted Dense Cycles [52.076657911275525]
  We study a random graph model for small-world networks which are ubiquitous in social and biological sciences. For both detection and recovery of the planted dense cycle, we characterize the information-theoretic thresholds in terms of $n$, $tau$, and an edge-wise signal-to-noise ratio $lambda$.
  arXiv  Detail & Related papers  (2024-02-01T03:39:01Z)
• The Exact Determinant of a Specific Class of Sparse Positive Definite Matrices [5.330240017302621]
  For a specific class of sparse Gaussian graphical models, we provide a closed-form solution for the determinant of the covariance matrix. In our framework, the graphical interaction model is equal to replacement product of $mathcalK_n$ and $mathcalK_n-1$.
  arXiv  Detail & Related papers  (2023-11-11T18:31:25Z)
• A Unified Framework for Uniform Signal Recovery in Nonlinear Generative Compressed Sensing [68.80803866919123]
  Under nonlinear measurements, most prior results are non-uniform, i.e., they hold with high probability for a fixed $mathbfx*$ rather than for all $mathbfx*$ simultaneously. Our framework accommodates GCS with 1-bit/uniformly quantized observations and single index models as canonical examples. We also develop a concentration inequality that produces tighter bounds for product processes whose index sets have low metric entropy.
  arXiv  Detail & Related papers  (2023-09-25T17:54:19Z)
• Graph Fourier MMD for Signals on Graphs [67.68356461123219]
  We propose a novel distance between distributions and signals on graphs. GFMMD is defined via an optimal witness function that is both smooth on the graph and maximizes difference in expectation. We showcase it on graph benchmark datasets as well as on single cell RNA-sequencing data analysis.
  arXiv  Detail & Related papers  (2023-06-05T00:01:17Z)
• Spectral clustering under degree heterogeneity: a case for the random walk Laplacian [83.79286663107845]
  This paper shows that graph spectral embedding using the random walk Laplacian produces vector representations which are completely corrected for node degree. In the special case of a degree-corrected block model, the embedding concentrates about K distinct points, representing communities.
  arXiv  Detail & Related papers  (2021-05-03T16:36:27Z)
• Testing correlation of unlabeled random graphs [18.08210501570919]
  We study the problem of detecting the edge correlation between two random graphs with $n$ unlabeled nodes. This is formalized as a hypothesis testing problem, where under the null hypothesis, the two graphs are independently generated. Under the alternative, the two graphs are edge-correlated under some latent node correspondence, but have the same marginal distributions as the null.
  arXiv  Detail & Related papers  (2020-08-23T19:19:45Z)
• Lipschitz regularity of graph Laplacians on random data clouds [1.2891210250935146]
  We prove high probability interior and global Lipschitz estimates for solutions of graph Poisson equations. Our results can be used to show that graph Laplacian eigenvectors are, with high probability, essentially Lipschitz regular with constants depending explicitly on their corresponding eigenvalues.
  arXiv  Detail & Related papers  (2020-07-13T20:43:19Z)
• Tight Nonparametric Convergence Rates for Stochastic Gradient Descent under the Noiseless Linear Model [0.0]
  We analyze the convergence of single-pass, fixed step-size gradient descent on the least-square risk under this model. As a special case, we analyze an online algorithm for estimating a real function on the unit interval from the noiseless observation of its value at randomly sampled points.
  arXiv  Detail & Related papers  (2020-06-15T08:25:50Z)
• Markov Random Geometric Graph (MRGG): A Growth Model for Temporal Dynamic Networks [0.0]
  We introduce Markov Random Geometric Graphs (MRGGs), a growth model for temporal dynamic networks. We show how MRGGs can be used to detect dependence structure in growing graphs and to solve link prediction problems.
  arXiv  Detail & Related papers  (2020-06-12T08:35:54Z)
• Semiparametric Nonlinear Bipartite Graph Representation Learning with Provable Guarantees [106.91654068632882]
  We consider the bipartite graph and formalize its representation learning problem as a statistical estimation problem of parameters in a semiparametric exponential family distribution. We show that the proposed objective is strongly convex in a neighborhood around the ground truth, so that a gradient descent-based method achieves linear convergence rate. Our estimator is robust to any model misspecification within the exponential family, which is validated in extensive experiments.
  arXiv  Detail & Related papers  (2020-03-02T16:40:36Z)
• 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.