A Kernelised Stein Discrepancy for Assessing the Fit of Inhomogeneous Random Graph Models

• URL: http://arxiv.org/abs/2505.21580v1
• Date: Tue, 27 May 2025 09:06:28 GMT
• Title: A Kernelised Stein Discrepancy for Assessing the Fit of Inhomogeneous Random Graph Models
• Authors: Anum Fatima, Gesine Reinert,
• Abstract summary: We develop, test, and analyse a KSD-type goodness-of-fit test for IRG models.<n>The test is applicable to a network of any size and does not depend on the distribution of the test statistic.
• Score: 0.552480439325792
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Complex data are often represented as a graph, which in turn can often be viewed as a realisation of a random graph, such as of an inhomogeneous random graph model (IRG). For general fast goodness-of-fit tests in high dimensions, kernelised Stein discrepancy (KSD) tests are a powerful tool. Here, we develop, test, and analyse a KSD-type goodness-of-fit test for IRG models that can be carried out with a single observation of the network. The test is applicable to a network of any size and does not depend on the asymptotic distribution of the test statistic. We also provide theoretical guarantees.

Related papers

• Generalization of Graph Neural Networks is Robust to Model Mismatch [84.01980526069075]
  Graph neural networks (GNNs) have demonstrated their effectiveness in various tasks supported by their generalization capabilities. In this paper, we examine GNNs that operate on geometric graphs generated from manifold models. Our analysis reveals the robustness of the GNN generalization in the presence of such model mismatch.
  arXiv  Detail & Related papers  (2024-08-25T16:00:44Z)
• Precise Error Rates for Computationally Efficient Testing [67.30044609837749]
  We revisit the question of simple-versus-simple hypothesis testing with an eye towards computational complexity.<n>An existing test based on linear spectral statistics achieves the best possible tradeoff curve between type I and type II error rates.
  arXiv  Detail & Related papers  (2023-11-01T04:41:16Z)
• Graph Out-of-Distribution Generalization with Controllable Data Augmentation [51.17476258673232]
  Graph Neural Network (GNN) has demonstrated extraordinary performance in classifying graph properties. Due to the selection bias of training and testing data, distribution deviation is widespread. We propose OOD calibration to measure the distribution deviation of virtual samples.
  arXiv  Detail & Related papers  (2023-08-16T13:10:27Z)
• On RKHS Choices for Assessing Graph Generators via Kernel Stein Statistics [8.987015146366216]
  We assess the effect of RKHS choice for KSD tests of random networks models. We investigate the power performance and the computational runtime of the test in different scenarios.
  arXiv  Detail & Related papers  (2022-10-11T19:23:33Z)
• AZ-whiteness test: a test for uncorrelated noise on spatio-temporal graphs [19.407150082045636]
  We present the first whiteness test for graphs, i.e., a serial whiteness test for a serial time series associated with the nodes of a graph. We show how the test can be employed to assess the quality-temporal forecasting models by analyzing the prediction residuals to the graphs stream.
  arXiv  Detail & Related papers  (2022-04-23T19:43:19Z)
• Deep Graph-level Anomaly Detection by Glocal Knowledge Distillation [61.39364567221311]
  Graph-level anomaly detection (GAD) describes the problem of detecting graphs that are abnormal in their structure and/or the features of their nodes. One of the challenges in GAD is to devise graph representations that enable the detection of both locally- and globally-anomalous graphs. We introduce a novel deep anomaly detection approach for GAD that learns rich global and local normal pattern information by joint random distillation of graph and node representations.
  arXiv  Detail & Related papers  (2021-12-19T05:04:53Z)
• Testing Directed Acyclic Graph via Structural, Supervised and Generative Adversarial Learning [7.623002328386318]
  We propose a new hypothesis testing method for directed acyclic graph (DAG) We build the test based on some highly flexible neural networks learners. We demonstrate the efficacy of the test through simulations and a brain connectivity network analysis.
  arXiv  Detail & Related papers  (2021-06-02T21:18:59Z)
• A Stein Goodness of fit Test for Exponential Random Graph Models [5.885020100736158]
  We propose and analyse a novel nonparametric goodness of fit testing procedure for exchangeable exponential random graph models. The test determines how likely it is that the observation is generated from a target unnormalised ERGM density.
  arXiv  Detail & Related papers  (2021-02-28T18:16:41Z)
• A practical test for a planted community in heterogeneous networks [0.0]
  For a real network data, the existence of a dense subgraph is generally unknown. The power of the test is theoretically investigated and we evaluate the performance of the test by simulation and real data example.
  arXiv  Detail & Related papers  (2021-01-15T01:34:14Z)
• Efficient Robustness Certificates for Discrete Data: Sparsity-Aware Randomized Smoothing for Graphs, Images and More [85.52940587312256]
  We propose a model-agnostic certificate based on the randomized smoothing framework which subsumes earlier work and is tight, efficient, and sparsity-aware. We show the effectiveness of our approach on a wide variety of models, datasets, and tasks -- specifically highlighting its use for Graph Neural Networks.
  arXiv  Detail & Related papers  (2020-08-29T10:09:02Z)
• 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.