An algorithm for reconstruction of triangle-free linear dynamic networks with verification of correctness

• URL: http://arxiv.org/abs/2003.02870v2
• Date: Tue, 10 Nov 2020 19:10:29 GMT
• Title: An algorithm for reconstruction of triangle-free linear dynamic networks with verification of correctness
• Authors: Mihaela Dimovska, Donatello Materassi
• Abstract summary: We present a method that either exactly recovers the topology of a triangle-free network certifying its correctness or outputs a graph that is sparser than the topology of the actual network. We prove that, even in the limit of infinite data, any reconstruction method is susceptible to inferring edges that do not exist in the true network.
• Score: 2.28438857884398
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Reconstructing a network of dynamic systems from observational data is an active area of research. Many approaches guarantee a consistent reconstruction under the relatively strong assumption that the network dynamics is governed by strictly causal transfer functions. However, in many practical scenarios, strictly causal models are not adequate to describe the system and it is necessary to consider models with dynamics that include direct feedthrough terms. In presence of direct feedthroughs, guaranteeing a consistent reconstruction is a more challenging task. Indeed, under no additional assumptions on the network, we prove that, even in the limit of infinite data, any reconstruction method is susceptible to inferring edges that do not exist in the true network (false positives) or not detecting edges that are present in the network (false negative). However, for a class of triangle-free networks introduced in this article, some consistency guarantees can be provided. We present a method that either exactly recovers the topology of a triangle-free network certifying its correctness or outputs a graph that is sparser than the topology of the actual network, specifying that such a graph has no false positives, but there are false negatives.

Related papers

• SINDER: Repairing the Singular Defects of DINOv2 [61.98878352956125]
  Vision Transformer models trained on large-scale datasets often exhibit artifacts in the patch token they extract. We propose a novel fine-tuning smooth regularization that rectifies structural deficiencies using only a small dataset.
  arXiv  Detail & Related papers  (2024-07-23T20:34:23Z)
• Coding schemes in neural networks learning classification tasks [52.22978725954347]
  We investigate fully-connected, wide neural networks learning classification tasks. We show that the networks acquire strong, data-dependent features. Surprisingly, the nature of the internal representations depends crucially on the neuronal nonlinearity.
  arXiv  Detail & Related papers  (2024-06-24T14:50:05Z)
• Formal Verification of Graph Convolutional Networks with Uncertain Node Features and Uncertain Graph Structure [7.133681867718039]
  Graph neural networks are becoming increasingly popular in the field of machine learning. They have been applied in safety-critical environments where perturbations inherently occur. This research addresses the non-passing gap by preserving the dependencies of all elements in the underlying computations.
  arXiv  Detail & Related papers  (2024-04-23T14:12:48Z)
• Inferring networks from time series: a neural approach [3.115375810642661]
  We present a powerful computational method to infer large network adjacency matrices from time series data using a neural network. We demonstrate our capabilities by inferring line failure locations in the British power grid from its response to a power cut.
  arXiv  Detail & Related papers  (2023-03-30T15:51:01Z)
• Neural Abstractions [72.42530499990028]
  We present a novel method for the safety verification of nonlinear dynamical models that uses neural networks to represent abstractions of their dynamics. We demonstrate that our approach performs comparably to the mature tool Flow* on existing benchmark nonlinear models.
  arXiv  Detail & Related papers  (2023-01-27T12:38:09Z)
• Simple initialization and parametrization of sinusoidal networks via their kernel bandwidth [92.25666446274188]
  sinusoidal neural networks with activations have been proposed as an alternative to networks with traditional activation functions. We first propose a simplified version of such sinusoidal neural networks, which allows both for easier practical implementation and simpler theoretical analysis. We then analyze the behavior of these networks from the neural tangent kernel perspective and demonstrate that their kernel approximates a low-pass filter with an adjustable bandwidth.
  arXiv  Detail & Related papers  (2022-11-26T07:41:48Z)
• An Approach for Link Prediction in Directed Complex Networks based on Asymmetric Similarity-Popularity [0.0]
  This paper introduces a link prediction method designed explicitly for directed networks. It is based on the similarity-popularity paradigm, which has recently proven successful in undirected networks. The algorithms approximate the hidden similarities as shortest path distances using edge weights that capture and factor out the links' asymmetry and nodes' popularity.
  arXiv  Detail & Related papers  (2022-07-15T11:03:25Z)
• Equilibrated Zeroth-Order Unrolled Deep Networks for Accelerated MRI [14.586911990418624]
  Recently, model-driven deep learning unrolls a certain iterative algorithm of a regularization model into a cascade network. In theory, there is not necessarily such a functional regularizer whose first-order information matches the replaced network module. This paper propose to present a safeguarded methodology on network unrolling.
  arXiv  Detail & Related papers  (2021-12-18T09:47:19Z)
• Latent Network Embedding via Adversarial Auto-encoders [15.656374849760734]
  We propose a latent network embedding model based on adversarial graph auto-encoders. Under this framework, the problem of discovering latent structures is formulated as inferring the latent ties from partial observations.
  arXiv  Detail & Related papers  (2021-09-30T16:49:46Z)
• Manifold Regularized Dynamic Network Pruning [102.24146031250034]
  This paper proposes a new paradigm that dynamically removes redundant filters by embedding the manifold information of all instances into the space of pruned networks. The effectiveness of the proposed method is verified on several benchmarks, which shows better performance in terms of both accuracy and computational cost.
  arXiv  Detail & Related papers  (2021-03-10T03:59:03Z)
• Enabling certification of verification-agnostic networks via memory-efficient semidefinite programming [97.40955121478716]
  We propose a first-order dual SDP algorithm that requires memory only linear in the total number of network activations. We significantly improve L-inf verified robust accuracy from 1% to 88% and 6% to 40% respectively. We also demonstrate tight verification of a quadratic stability specification for the decoder of a variational autoencoder.
  arXiv  Detail & Related papers  (2020-10-22T12:32:29Z)

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.