Efficiently Learning the Topology and Behavior of a Networked Dynamical System Via Active Queries

Daniel J Rosenkrantz, Abhijin Adiga, Madhav Marathe, Zirou Qiu, S S Ravi, Richard Stearns, Anil Vullikanti
Proceedings of the 39th International Conference on Machine Learning, PMLR 162:18796-18808, 2022.

Abstract

Using a discrete dynamical system model, many papers have addressed the problem of learning the behavior (i.e., the local function at each node) of a networked system through active queries, assuming that the network topology is known. We address the problem of inferring both the topology of the network and the behavior of a discrete dynamical system through active queries. We consider two query models studied in the literature, namely the batch model (where all the queries must be submitted together) and the adaptive model (where responses to previous queries can be used in formulating a new query). Our results are for systems where the state of each node is from {0,1} and the local functions are Boolean. We present algorithms to learn the topology and the behavior under both batch and adaptive query models for several classes of dynamical systems. These algorithms use only a polynomial number of queries. We also present experimental results obtained by running our query generation algorithms on synthetic and real-world networks.

Cite this Paper

BibTeX
@InProceedings{pmlr-v162-rosenkrantz22a, title = {Efficiently Learning the Topology and Behavior of a Networked Dynamical System Via Active Queries}, author = {Rosenkrantz, Daniel J and Adiga, Abhijin and Marathe, Madhav and Qiu, Zirou and Ravi, S S and Stearns, Richard and Vullikanti, Anil}, booktitle = {Proceedings of the 39th International Conference on Machine Learning}, pages = {18796--18808}, year = {2022}, editor = {Chaudhuri, Kamalika and Jegelka, Stefanie and Song, Le and Szepesvari, Csaba and Niu, Gang and Sabato, Sivan}, volume = {162}, series = {Proceedings of Machine Learning Research}, month = {17--23 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v162/rosenkrantz22a/rosenkrantz22a.pdf}, url = {https://proceedings.mlr.press/v162/rosenkrantz22a.html}, abstract = {Using a discrete dynamical system model, many papers have addressed the problem of learning the behavior (i.e., the local function at each node) of a networked system through active queries, assuming that the network topology is known. We address the problem of inferring both the topology of the network and the behavior of a discrete dynamical system through active queries. We consider two query models studied in the literature, namely the batch model (where all the queries must be submitted together) and the adaptive model (where responses to previous queries can be used in formulating a new query). Our results are for systems where the state of each node is from {0,1} and the local functions are Boolean. We present algorithms to learn the topology and the behavior under both batch and adaptive query models for several classes of dynamical systems. These algorithms use only a polynomial number of queries. We also present experimental results obtained by running our query generation algorithms on synthetic and real-world networks.} }
Endnote
%0 Conference Paper %T Efficiently Learning the Topology and Behavior of a Networked Dynamical System Via Active Queries %A Daniel J Rosenkrantz %A Abhijin Adiga %A Madhav Marathe %A Zirou Qiu %A S S Ravi %A Richard Stearns %A Anil Vullikanti %B Proceedings of the 39th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2022 %E Kamalika Chaudhuri %E Stefanie Jegelka %E Le Song %E Csaba Szepesvari %E Gang Niu %E Sivan Sabato %F pmlr-v162-rosenkrantz22a %I PMLR %P 18796--18808 %U https://proceedings.mlr.press/v162/rosenkrantz22a.html %V 162 %X Using a discrete dynamical system model, many papers have addressed the problem of learning the behavior (i.e., the local function at each node) of a networked system through active queries, assuming that the network topology is known. We address the problem of inferring both the topology of the network and the behavior of a discrete dynamical system through active queries. We consider two query models studied in the literature, namely the batch model (where all the queries must be submitted together) and the adaptive model (where responses to previous queries can be used in formulating a new query). Our results are for systems where the state of each node is from {0,1} and the local functions are Boolean. We present algorithms to learn the topology and the behavior under both batch and adaptive query models for several classes of dynamical systems. These algorithms use only a polynomial number of queries. We also present experimental results obtained by running our query generation algorithms on synthetic and real-world networks.
APA
Rosenkrantz, D.J., Adiga, A., Marathe, M., Qiu, Z., Ravi, S.S., Stearns, R. & Vullikanti, A.. (2022). Efficiently Learning the Topology and Behavior of a Networked Dynamical System Via Active Queries. Proceedings of the 39th International Conference on Machine Learning, in Proceedings of Machine Learning Research 162:18796-18808 Available from https://proceedings.mlr.press/v162/rosenkrantz22a.html.

Related Material