An official website of the United States government
We investigate questions related to the time evolution of discrete graph dynamical systems where each node has a state from {0,1}. The configuration of a system at any time instant is a Boolean vector that specifies the state of each node at that instant. We say that two configurations are similar if the Hamming distance between them is small. Also, a predecessor of a configuration B is a configuration A such that B can be reached in one step from A. We study problems related to the similarity of predecessor configurations from which two similar configurations can be reached in one time step. We address these problems both analytically and experimentally. Our analytical results point out that the level of similarity between predecessors of two similar configurations depends on the local functions of the dynamical system. Our experimental results, which consider random graphs as well as small world networks, rely on the fact that the problem of finding predecessors can be reduced to the Boolean Satisfiability problem (SAT).
more »
« less
On the Consistency of Maximum Likelihood Estimators for Causal Network Identification
In this letter we consider the problem of identifying parameters of a particular class of Markov chains, called Bernoulli Autoregressive ( BAR) processes. The structure of any BAR model is encoded by a directed graph. Incoming edges to a node in the graph indicate that the state of the node at a particular time instant is influenced by the states of the corresponding parental nodes in the previous time instant. The associated edge weights determine the corresponding level of influence from each parental node. In the simplest setup, the Bernoulli parameter of a particular node’s state variable is a convex combination of the parental node states in the previous time instant and an additional Bernoulli noise random variable. This letter focuses on the problem of edge weight identification using Maximum Likelihood( ML) estimation and proves that the ML estimator is strongly consistent for two variants of the BAR model. We additionally derive closed-form estimators for the aforementioned two variants and prove their strong consistency.
more »
« less
- Award ID(s):
- 2032321
- PAR ID:
- 10312116
- Date Published:
- Journal Name:
- IEEE control systems letters
- Volume:
- 6
- ISSN:
- 2475-1456
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
This paper presents a state-variable formulation to model and simulate the 2D unsteady aerodynamics of an airfoil undergoing arbitrary motion kinematics. The model builds upon a large-angle unsteady aerodynamic formulation in which the airfoil is represented using a lumped vortex element (LVE) model. The airfoil is divided into several panels, with a bound vortex placed on each panel. At any time instant, the bound-vortex strengths are determined by employing zero-normal-flow conditions at the control points located on each panel. The vorticity shed from the trailing edge of the airfoil is modeled using discrete vortices that move freely in the flow field. The required state variables are first identified, and all the time derivative terms of the state variables are then derived to form the final state-variable representation. Trailing-edge vortex shedding is incorporated using the Kelvin condition. The final state variable equation can be solved as an ordinary differential equation using any standard ODE-solving algorithm. Three case studies are presented here to evaluate the predictions of the model. In the cases considered here, the airfoil undergoes various unsteady plunge motions. The aerodynamic load history and the wake patterns are compared against the results from the low-order model developed by Narsipur et al. [1] in previous research. The comparison shows that the current state-variable formulation captures the unsteady flow characteristics and the aerodynamic load in good agreement with the reference results.more » « less
-
In this paper, we consider the task of discovering the common objects in images. Initially, object candidates are generated in each image and an undirected weighted graph is constructed over all the candidates. Each candidate serves as a node in the graph while the weight of the edge describes the similarity between the corresponding pair of candidates. The problem is then expressed as a search for the Maximum Weight Clique (MWC) in this graph. The MWC corresponds to a set of object candidates sharing maximal mutual similarity, and each node in the MWC represents a discovered common object across the images. Since the problem of finding the MWC is NP-hard, most research of the MWC problem focuses on developing various heuristics for finding good cliques within a reasonable time limit. We utilize a recently very popular class of heuristics called local search methods. They search for the MWC directly in the discrete domain of the solution space. The proposed approach is evaluated on the PASCAL VOC image dataset and the YouTube-Objects video dataset, and it demonstrates superior performance over recent state-of-the-art approaches.more » « less
-
Diffusion-based graph generative models are effective in generating high-quality small graphs. However, it is hard to scale them to large graphs that contain thousands of nodes. In this work, we propose EDGE, a new diffusion-based graph generative model that addresses generative tasks for large graphs. The model is developed by reversing a discrete diffusion process that randomly removes edges until obtaining an empty graph. It leverages graph sparsity in the diffusion process to improve computational efficiency. In particular, EDGE only focuses on a small portion of graph nodes and only adds edges between these nodes. Without compromising modeling ability, it makes much fewer edge predictions than previous diffusion-based generative models. Furthermore, EDGE can explicitly model the node degrees of training graphs and then gain performance improvement in capturing graph statistics. The empirical study shows that EDGE is much more efficient than competing methods and can generate large graphs with thousands of nodes. It also outperforms baseline models in generation quality: graphs generated by the proposed model have graph statistics more similar to those of training graphs.more » « less
-
Diffusion-based graph generative models are effective in generating high-quality small graphs. However, it is hard to scale them to large graphs that contain thousands of nodes. In this work, we propose EDGE, a new diffusion-based graph generative model that addresses generative tasks for large graphs. The model is developed by reversing a discrete diffusion process that randomly removes edges until obtaining an empty graph. It leverages graph sparsity in the diffusion process to improve computational efficiency. In particular, EDGE only focuses on a small portion of graph nodes and only adds edges between these nodes. Without compromising modeling ability, it makes much fewer edge predictions than previous diffusion-based generative models. Furthermore, EDGE can explicitly model the node degrees of training graphs and then gain performance improvement in capturing graph statistics. The empirical study shows that EDGE is much more efficient than competing methods and can generate large graphs with thousands of nodes. It also outperforms baseline models in generation quality: graphs generated by the proposed model have graph statistics more similar to those of training graphs.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1109/CDC42340.2020.9304475
