Discrete dynamical systems have been used as a formal models for numerous cascade processes, such as the spread of social behaviors, information, diseases, and biological phenomena (Battiston et al. 2020;Ji et al. 2017;Cohen et al. 2010;González-Bailón et al. 2011;Romero, Meeder, and Kleinberg 2011;Sabhapandit, Dhar, and Shukla 2002). A discrete dynamical system consists of an underlying graph with vertices representing entities (e.g., individuals, genes), and edges representing connections between the entities. Each vertex has a state and an interaction function (i.e., behavior), which specify how the state changes over time. Overall, vertices update their states using interaction functions as the system dynamics proceeds in discrete time.
Due to the large size of real-world systems, a complete specification of the underlying dynamical system is often not available. To this end, learning the unknown components of a system is an active area of research (Adiga et al. 2019;Chen and Poor 2022;Conitzer, Panigrahi, and Zhang 2020;Dawkins, Li, and Xu 2021). One ongoing line of work is Copyright © 2024, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.
to infer the unknown interaction functions or the topology of a system. Network topology and interaction functions play critical roles in the system dynamics. The topology encodes the underlying relationships between the entities, while the interaction functions provide the decision rules that entities employ to update their contagion states. The class of threshold interaction functions (Granovetter 1978), which are widely used to model the spread of social contagions (Watts 2002), is one such example. Specifically, each entity in the network has a decision threshold that represents the tipping point for a behavioral (i.e., state) change. In the case of a rumor, a person's belief shifts when the number of neighbors believing in the rumor reaches a certain threshold.
Previous research (Adiga et al. 2017) has presented efficient algorithms for inferring classes of interactions functions (e.g., threshold functions) based on the observed dynamics, assuming that the underlying network is known. To our knowledge, the more challenging problem of learning a system from observed dynamics, where both the interaction function and the topology are unknown, has not been examined. In this work, we fill this gap with a theoretical study of the problem of learning both the topology and the interaction functions of an unknown dynamical system. Problem description. Consider a black-box networked system where both the interaction functions and the network topology are unknown. Our objective is to recover a system that captures the behavior of the true but unknown system while providing performance guarantees under the Probably Approximately Correct (PAC) model (Valiant 1984). We learn from snapshots of the true system's dynamics, a common scheme considered in related papers (e.g., (Chen et al. 2021;Conitzer, Panigrahi, and Zhang 2020;Wilinski and Lokhov 2021)). Since our problem setting also involves multiclass learning, we examine the Natarajan dimension (Natarajan 1989), a well-known generalization of the VC dimension (Vapnik and Chervonenkis 2015). In particular, the Natarajan dimension quantifies the expressive power of the hypothesis class and characterizes the sample complexity of learning. Overall, we aim to answer the following two questions: (i) Can one efficiently learn the blackbox system, and if so, how many training examples are sufficient? (ii) What is the expressive power of the hypothesis class of networked systems?
The key challenges of our learning problem arise from the incomplete knowledge of the network topology and the interaction functions of the nodes in the system. For example, when we consider systems whose underlying graphs are undirected and interaction functions are Boolean threshold functions, the number of potential systems is Θ(2 ( n 2 ) • n n ), where n is the number of nodes in the underlying graph. Therefore, a learner needs to find an appropriate hypothesis from a very large space. Further, in general, the training set (which consists of snapshots of the system dynamics) may not contain sufficient information to recover the underlying network structure efficiently. (Indeed, we show that the problem is computationally intractable.) Our main contributions are summarized below. 1. Hardness of PAC learning: We show that in general, hypothesis classes corresponding to dynamical system where both the network topology and the interaction functions are unknown are not efficiently PAC learnable unless NP = RP. We prove this result by first formulating a suitable decision problem and showing that the problem is NP-complete. We use the hardness result for the decision problem to establish the hardness of PAC learning. Our results show that the learning problem remains hard for several classes of dynamical systems (e.g., systems on undirected graphs with threshold interaction functions). 2. Efficient PAC learning algorithms for special classes: In contrast with the general hardness result above, we identify some special classes of systems that are efficiently PAC learnable. The two classes that we identify correspond to systems on directed graphs with bounded indegree and those where the underlying graph is a perfect matching. In both cases, the interaction functions are from the class of threshold functions. These results are obtained by showing that these systems have efficient consistent learners and then appealing to the known result (Shalev-Shwartz and Ben-David 2014) that hypothesis classes for which there are efficient consistent learners are also efficiently PAC learnable. 3. Learning under a relaxed setting: We consider a relaxed setting where the underlying network is partially observed and present an efficient PAC learner for the setting. We also establish the sample complexity. 4. Expressive power: We present an analysis of the Natarajan dimension (Ndim), which measures the expressive power of the hypothesis class of networked systems. In particular, we give a construction of a shatterable set and prove that the Ndim of the hypothesis class is at least ⌊n 2 /4⌋, where n is the number of vertices. Further, we show that the upper bound on Ndim for this class is O(n 2 ). Thus, our lower bound is tight to within a constant factor. Our result also provides a lower bound on the sample complexity. Related work. Learning unknown components of networked systems is an active area of research. Many researchers have studied the problem of identifying missing components (e.g., learning the diffusion functions at vertices, edge parameters, source vertices, and contagion states of vertices) in contagion models by observing the propagation dynamics. For instance, Chen et al. (Chen et al. 2021) infer the edge probability and source vertices under the independent cascade model. Conitzer et al. (Conitzer, Panigrahi, and Zhang 2020) investigate the problem of inferring opinions (states) of vertices in stochastic cascades under the PAC scheme. Lokhov (Lokhov 2016) studies the problem of reconstructing the parameters of a diffusion model given infection cascades. Inferring threshold functions of vertices from social media data is considered in (González-Bailón et al. 2011;Romero, Meeder, and Kleinberg 2011). Identifying the source vertices of infections due to a contagion is addressed in (Zhu, Chen, and Ying 2017;Shah and Zaman 2011). The problem of inferring the network structure has also been studied; see, e.g., (Huang et al. 2019;Pouget-Abadie and Horel 2015;Abrahao et al. 2013;Gomez Rodriguez, Leskovec, and Krause 2010;Soundarajan and Hopcroft 2010). The problem of inferring the network structure and the interaction functions of dynamical systems has been studied under a different model in (Rosenkrantz et al. 2022), where a user can construct queries to the system and obtain responses. This is fundamentally different from our model where a learning algorithm must rely on a given set of observations and cannot interact with the unknown system.
The work that is closest to ours is (Adiga et al. 2017), where the problem of inferring the interaction functions in a system from observations is considered, under the assumption that the network is known. It is shown in (Adiga et al. 2017) that the interaction function inference problem can be solved efficiently. However, the techniques used in (Adiga et al. 2017) are not applicable to our context, since the network is unknown.
For space reasons, many proofs have been omitted. Detailed proofs can be found in (Qiu et al. 2023).
A Synchronous Dynamical System (SyDS) S over the Boolean domain B = {0, 1} is a pair S = (G, F ), where • G = (V, E) is the underlying undirected graph. We let n = |V|. Each vertex in V has a state from B, representing its contagion state (e.g., inactive or active). • F = (f 1 , f 2 , . . . , f n ) is a collection of functions, where f i is the interaction function of vertex v i ∈ V, 1 ≤ i ≤ n. Interaction functions. The system evolves in discrete time steps, with vertices updating their states synchronously using the interaction functions. For a graph G and a vertex v, we let N (G, v) and N + (G, v) denote the open and closed neighborhoods of v, respectively. At each time step, the inputs to the interaction function f i ∈ F are the states of the vertices in N + (G, v i ); f i computes the next state of v i .
Our work focuses on the class of threshold interaction functions, which is a classic framework for modeling social contagions (Watts and Strogatz 1998;Granovetter 1978). Specifically, each vertex v i ∈ V has an integer threshold τ vi ≥ 0, and f i outputs 1 if the number of 1's in the input to f i (i.e., the number of state-1 vertices in N + (G, v i )) is at least τ vi ; f i outputs 0 otherwise. An example of such a SyDS is shown in Figure 1.
A configuration C of a SyDS S at a given time step is a binary vector of length n that specifies the states of all the vertices at that time step. Let X = {0, 1} n be the set of all configurations. For a given vertex v, let C(v) denote the state of v in C, and for a given vertex set Y ⊆ V, let C[Y] denote the projection of C onto Y. If the system S evolves from C to a configuration C ′ in one step, denoted by S(C) = C ′ , then C ′ is called the successor of C. Since the interaction functions considered in our work are deterministic, each configuration has a unique successor. For a given configuration C and vertex set Y, we let score(C, Y) denote the number of vertices v ∈ Y such that C(v) = 1. SyDSs over directed graphs. SyDSs can also be defined over directed graphs. The inputs to the local function at a vertex v i are the state of v i and those of the in-neighbors of v i (i.e., vertices from which v i has incoming edges). All the other definitions for SyDSs on directed graphs are the same as those for SyDSs on undirected graphs.
Hypotheses. Let S * = (G, F ) be a ground truth SyDS. The learner does not know either the graph G or the set of functions F . Other than the training set, the only information provided to the learner consists of the number n of vertices, the class of interaction functions, and the class of the underlying graph. The learner must find a hypothesis consisting of an underlying graph (from the given graph class) and an interaction function (from the given class of interaction functions) for each node of the graph from the set of all such hypotheses. As an illustration, let H UNDIR,THRE denote the hypothesis class where the underlying graph of S * is undirected, and the interaction functions are threshold functions. Since there are 2 ( n 2 ) undirected graphs with n nodes and each node may have Θ(n) choices for threshold values, the hypothesis class H UNDIR,THRE has Θ(2 ( n 2 ) n n ) systems (i.e., hypotheses). The learner aims to infer a system S ∈ H UNDIR,THRE that is close to the true system S * by constructing the graph and the interaction functions of S. Learning setting. Our algorithms learn the ground truth system S * from its observed dynamics.
be a training set of q examples, each consisting of a snapshot of the dynamics of S * in the form of a configurationsuccessor pair. Specifically, C i is a drawn i.i.d. from a distribution (unknown to the learner) D over X , and
Note that the hypothesis being learned represents a successor function.
For simplicity, we present the necessary definitions for the PAC model (see e.g., (Shalev-Shwartz and Ben-David 2014)) using H UNDIR,THRE . These definitions also apply to other hypothesis classes considered in this paper. The true error of a hypothesis S ∈ H UNDIR,THRE is defined as
In the PAC model, the goal is to infer a hypothesis S ∈ H UNDIR,THRE s.t. with probability at least 1 -δ over O ∼ D q , the true error L (D,S * ) (S) ≤ ϵ, for any given ϵ, δ ∈ (0, 1). The class H UNDIR,THRE is efficiently PAC learnable if such an S ∈ H UNDIR,THRE can be inferred in polynomial time (w.r.t. n, 1/δ and 1/ϵ). The minimum number of training examples needed to achieve the above guarantee is called the sample complexity of learning H UNDIR,THRE . Natarajan dimension. A hypothesis S can be viewed as a function X → X , where each of the 2 n possible target configurations is considered a class. Thus, our learning problem involves multiclass classification. The Natarajan dimension (Natarajan 1989) is a generalization of the concept of VC dimension to a multiclass setting, and measures the expressive power of a given hypothesis class H UNDIR,THRE . Formally, a set R of configurations is shattered by H UNDIR,THRE if there exists two functions g 1 , g 2 : X → X , such that:
The Natarajan dimension of H UNDIR,THRE , denoted by Ndim(H UNDIR,THRE ), is the maximum size of a shatterable set. In general, the larger the Natarajan dimension of a hypothesis class, the higher is its expressive power.
We first establish the intractability of efficiently PAC learning threshold dynamical systems over general graphs. We then present efficient algorithms for learning systems over several graph classes. We also analyze the sample complexity of learning the corresponding hypothesis classes.
To establish the hardness of learning, we first formulate a decision problem for SyDSs and show that the problem is NP-hard. We use this to establish a general hardness result under the PAC model.
We define restricted classes of SyDSs by specifying constraints on the underlying graph and the interaction functions. For example, we use the notation (UNDIR, THRESH)-SyDSs to denote the restricted class of SyDSs whose (i) underlying graphs are undirected and (ii) interaction functions are threshold functions. Several other restricted classes of SyDSs will be considered in this section.
Given a set O of observations, with each observation being a pair of the form (C, C ′ ) where C ′ is the successor of C, we say that a SyDS S is consistent with O if for each observation (C, C ′ ) ∈ O, the successor of C produced by S is C ′ . A basic decision problem in this context is the following: given a set O of observations, determine whether there is a SyDS that is consistent with O. One may also want the consistent SyDS to be in a restricted class Γ. We refer to this problem as the Γ-Consistency problem: Definition 3.1 (Γ-Consistency) Instance: A vertex set V and a set of observations O over V. Question: Is there a SyDS in the class Γ that is consistent with O?
Hardness. The following lemma shows the hardness of Γ-consistency for two restricted classes of SyDSs: (i)(UNDIR, THRESH)-SyDSs, where the graph is undirected and each interaction function is a threshold function, and (ii) (TREE, THRESH = 2)-SyDSs, where the graph is a tree and each interaction function is a 2-threshold function. For space reasons, we only provide a proof sketch for (i) here. A full proof of the lemma appears in (Qiu et al. 2023).
Lemma 3.1 The Γ-Consistency problem is NP-complete for the following classes of SyDSs: (i) (UNDIR, THRESH)-SyDSs and (ii) (TREE, THRESH = 2)-SyDSs.
Proof sketch for (i): It can be seen that the problem is in NP. The proof of NP-hardness is via a reduction from 3SAT. Let the given 3SAT formula be f , with variables X = {x 1 . . . . , x n } and clauses C = {c 1 . . . . , c m }. For the reduction, we construct a node set V and transition set O.
The constructed node set V contains 2n + 2 nodes. For each variable x i ∈ X, V contains the two nodes y i and y i . Intuitively, node y i corresponds to the literal x i , and node y i corresponds to the literal x i . We refer to these 2n nodes as literal nodes. There are also two additional nodes: z and z ′ . Transition set O contains n + m + 2 transitions, as follows:
O 1 contains two transitions. In the first of these transitions, the predecessor has only node z equal to 1, and the successor has all nodes equal to 0. In the second transition, the predecessor has only the two nodes z and z ′ equal to 1, and the successor has only node z equal to 1. O 2 contains n transitions, one for each variable in X. For each variable x i ∈ X, O 2 contains a transition where in the predecessor only nodes y i and y i are equal to 1, and the successor has all nodes equal to 0. O 3 contains m transitions, one for each clause of f . For each clause c j of f , O 3 contains a transition where in the predecessor only node z and the nodes corresponding to the literals that occur in c j are equal to 1, and the successor has only node z equal to 1. It can be shown that f is satisfiable iff there exists a threshold-SyDS that is consistent with O.
The usefulness of establishing NP-hardness results for the Γ-Consistency problem is pointed out by our next result (Lemma 3.2), which states that if Γ-Consistency is NPhard, then the hypothesis class for Γ SyDSs is not efficiently PAC learnable, unless the complexity classes NP and RP coincide. Here, RP denotes the class of problems that can be solved in randomized polynomial time. It is widely believed that the complexity classes NP and RP are different; see (Arora and Barak 2009) for additional details regarding these complexity classes.
Lemma 3.2 Let Γ be any class of SyDS for which Γ-Consistency is NP-hard. The hypothesis class for Γ SyDSs is not efficiently PAC learnable, unless NP = RP.
Proof sketch. If the hypothesis class for Γ-SyDS admits an efficient PAC learner A PAC , then one can construct an RP algorithm A ERM (based on A PAC ) for the Γ-Consistency problem, thereby implying NP = RP. See (Qiu et al. 2023) for a detailed proof.
The following theorem on the hardness of learning is a direct consequence of Lemmas 3.1 and 3.2.
Theorem 3.1 Unless NP = RP, the hypothesis classes for the following classes of SyDSs are not efficiently PAC learnable: (i) (UNDIR, THRESH)-SyDSs and (ii) (TREE, THRESH = 2)-SyDSs.
Sample complexity. For any finite hypothesis class H, given the PAC parameters ϵ, δ > 0, the following is a well known (Haussler 1988) upper bound on the sample complexity m H (δ, ϵ) for learning H: m H (δ, ϵ) ≤ 1 ϵ log(|H| + log(1/δ) . As mentioned earlier, the size of the hypothesis class H UNDIR,THRE is O(2 ( n 2 ) •n n ). Thus, one can obtain an upper bound on the sample complexity of learning H UNDIR,THRE :
From the above inequality, it follows that m HUNDIR,THRE (δ, ϵ) = O (1/ϵ) • (n 2 + log (1/δ)) . In a later section, we will prove a lower bound on the sample complexity which is tight to within a constant factor of the upper bound (1), thereby showing that m HUNDIR,THRE (δ, ϵ) = Θ (1/ϵ) • (n 2 + log (1/δ)) .
Preview for the results in Sections 3.2 and 3.3: In the next subsections, we present classes of SyDSs which are efficiently PAC learnable. In both cases, we obtain the result by showing that for the corresponding class of SyDSs, the Γ-Consistency problem is efficiently solvable. In other words, given a training set O, these algorithms represent efficient consistent learners for the corresponding classes of SyDSs. As is well known, an efficient consistent learner for a hypothesis class is also an efficient PAC learner (Shalev-Shwartz and Ben-David 2014).
Let (MATCH,THRESH)-SyDSs denote the set of SyDSs where the underlying graph is a perfect matching, and the interaction functions are threshold functions. In this section, we present an efficient PAC learner for the hypothesis class H MATCH , consisting of (MATCH,THRESH)-SyDSs.
As mentioned earlier, we obtain an efficient PAC learner for this class by presenting an efficient algorithm for the Γ-Consistency problem. We begin with a few definitions. Threshold-Compatibility. For a pair of distinct vertices u and v, we say that u and v are threshold-compatible if for all
Informally, u and v are threshold-compatible iff there exist threshold functions f u for u and f v for v, such that f u and f v are each consistent with O.
Compatibility Graph. The threshold-compatibility graph G ′ = (V, E ′ ) of O is an undirected graph with vertex set V, and an edge }u, v} ∈ E ′ for each pair of thresholdcompatible vertices u and v.
Algorithm 1: Full-Infer-Matching (V)
If G does not have a perfect matching, answer "No" and stop. Let E ′′ be the edge set of a perfect matching in An efficient learner. Our efficient algorithm for the Γ-Consistency problem for the class of (MATCH,THRESH)-SyDSs appears as Algorithm 1. The algorithm first constructs the threshold-compatibility graph G ′ = (V, E ′ ) of O. The reason for this computation is given in the following lemma. A proof of the lemma appears in (Qiu et al. 2023). Lemma 3.3 The answer to the Γ-Consistency problem for (MATCH,THRESH)-SyDSs is "Yes" if and only if the threshold-compatibility graph G ′ = (V, E ′ ) of O contains a perfect matching.
Next, the algorithm finds a maximum matching in G ′ . Let E ′′ be the edge set of this maximum matching. Note that, from Lemma 3.3, G ′ contains a perfect matching, so E ′′ is a perfect matching of G. The learned hypothesis S is a (MATCH,THRESH)-SyDSs on V whose graph has edge set E ′′ , and interaction function f v for each vertex v, with incident edge (v, u) in E ′′ , is any threshold function of variables v and u that is consistent with O[{v, w}]. Remark. To estimate the running time of Algorithm 1, note that for any pair of nodes, determining compatibility can be done in O(nq) time, where n is the number of nodes and q is the number of given observations. Thus, the time to construct the compatibility graph is O(n 3 q). All the other steps (including the computation of perfect matching which can be done in O(n 3 ) time (Cormen et al. 2009)) are dominated by the time to construct the compatibility graph. Thus, the overall running time is O(n 3 q), which is polynomial in the input size. Hence, we have an efficient consistent learner for the class of (MATCH,THRESH)-SyDSs and so: Theorem 3.2 The hypothesis class associated with (MATCH,THRESH)-SyDSs is efficiently PAC learnable.
In this section, we present an efficient PAC learner for the hypothesis class H DIR,∆-BOUNDED consisting of SyDSs where the underlying graph of the target system is directed, with in-degree bounded by some fixed ∆, and the interaction functions are threshold functions. As before, we establish this result by presenting an efficient algorithm for the Γ-Consistency problem, where Γ is the class of SyDSs on directed graphs where the maximum indegree is bounded by a constant ∆ and the interaction functions are threshold functions. We refer to these as (DIR, ∆, THRESH)-SyDSs. We say that a given vertex v is threshold-consistent with a given training set O via a given vertex set
A key lemma that leads to our algorithm is the following. Lemma 3.4 There exists a system S ∈ H DIR,∆-BOUNDED that is consistent with a given training set O if and only if every vertex v is threshold-consistent with O via a vertex set N v of cardinality at most ∆.
As shown below, the above lemma provides a straightforward algorithm for the Γ-Consistency problem for the class of (DIR, ∆, THRESH)-SyDSs. Lemma 3.5 For any fixed value ∆, the Γ-Consistency problem for the class of (DIR, ∆, THRESH)-SyDSs can be solved efficiently. Proof. Since the graph is directed, each vertex can be treated independently. For each vertex v, an algorithm can enumerate all possible vertex sets Y ⊆ V \ {v} of cardinality at most ∆ and find the corresponding N v . The number of such vertex sets is O(n ∆ ). Further, for each such a set, we check if v is threshold-consistent under this set, which takes O(∆q) time. Thus, for each vertex, the time to find an N v is O(n ∆ • δq), and the overall running time is O(n ∆+1 • δq).
Since we have an efficient consistent learner for the hypothesis class H DIR,∆-BOUNDED for any constant ∆, we have: Theorem 3.3 For any fixed value ∆, the hypothesis class H DIR,∆-BOUNDED is efficiently PAC learnable.
In this section, we consider the learning problem for (UNDIR, THRESH)-SyDSs when the network is partially observed, with at most k missing edges from the true network G. Let G obs denote the observed network of the system, and let H OBS denote the corresponding hypothesis class. The goal is to learn a system in H OBS with underlying graph G ′ being a supergraph of G obs , with at most k additional edges.
We first provide an upper bound on the sample complexity of learning H OBS based on a detailed analysis of hypothesis class size. Then, for the scenario where at most one edge is missing for each vertex, we present an efficient PAC learner. Theorem 4.1 Given a partially observed network G obs , for any ϵ, δ > 0, the sample complexity of learning the hypothesis class H OBS satisfies M(ϵ, δ) ≤ 1 ϵ n log(d avg (G obs ) + 3) + ck log(n 2 /k) + log(1/δ) for some constant c > 0, where d avg (G obs ) is the average degree of G obs .
Proof. We first bound the size of the hypothesis class H of all possible SyDSs in the class (UNDIR, THRESH)-SyDSs, given G obs as the partially observed network. This includes all such SyDSs with the underlying graph being G obs and up to k more edges. Our sample complexity bound is then based on the following result by (Haussler 1988)
Given a graph G, let H G denote the set of threshold SyDSs with G as the underlying graph. From (Adiga et al. 2018), the size of H G can be bounded by accounting for the number of threshold assignments possible for each vertex and is given by
for some constant c ′ > 0. In particular, the last inequality can be obtained as follows:
Lastly, setting y = 2x log(en) -x log x, we have for another constant c ′′ > 0. It follows that
for a suitable constant c ′′ > 0.
Remark. For the case where the network is fully known, the work by (Adiga et al. 2018) provides a polynomial-time algorithm that outputs a consistent learner in time O(qn) where q is the size of O. In our case, where at most k edges are missing, we note that the method of considering all possible supergraphs of G obs with at most k extra edges and checking the consistency takes O n 2k pn time since there are at most n 2k such graphs.
By simply setting G obs to be a graph with no edges, Theorem 4.1 implies the following corollary when the only information known about the network topology is that it has at most m edges.
Corollary 4.1 The sample complexity of learning the hypothesis class H UNDIR,THRE given that the underlying network has at most m edges is ≤ 1 ϵ c m log(n 2 /m) + log(1/δ) for a suitable constant c > 0.
We now examine the case when the hypothesis class H OBS misses at most k edges, of which at most one missing edge is incident on each vertex. We propose an efficient PAC learner for this case.
We begin with some definitions. Consider a given training set O and set of vertices
Step one. To infer a SyDS consistent with the observations O, we first compute ℓ(v, N + (G obs , v)) and h(v, N + (G obs , v)) for each vertex v. In this process, we also identify all vertices v for which ℓ(v, N + (G obs , v)) ≥ h(v, N + (G obs , v)); G obs violates the threshold consistency condition for each such v. Let V ′ denote the set of vertices such that ℓ(v, N + (G obs , v)) = h(v, N + (G obs , v)), and V ′′ denote the set of vertices such that ℓ(v, N + (G obs , v)) > h(v, N + (G obs , v)).
Observation 4.1 Each vertex in V ′′ requires at least two additional incident edges, so if V ′′ ̸ = ∅, there is no system in H OBS that is consistent with O.
So, henceforth we assume that V ′′ = ∅.
Step two. Next, we construct a maximum-weighted matching problem instance with vertex set V, where the edge weights are all positive integers. In particular, we say that a vertex pair
and (iii) adding the edge (u, v) to G obs would result in u and v both satisfying the consistency condition, i.e.,
The constructed graph G m has an edge for each viable vertex pair. Let E 1 denote the edges in G m with exactly one endpoint in V ′ , and E 2 the edges in G m with both endpoints in V ′ . The edges in E 1 are given weight t, and the edges in E 2 are given weight 2t + 1.
Step three. Lastly, the constructed matching problem is solved, producing a maximum weight matching, M. If M matches all the vertices in V ′ and consists of at most k edges, then we construct the new graph G ′ by adding the edges in M to G obs . Since all added edges are viable, and each vertex is the endpoint of at most one added edge, we have that for all
If the maximum weight matching does not match all vertices in V ′ or contains more than k edges, then there is no SyDS in H OBS that is consistent with the training set O. Correctness. Consider a matching M ′ within G m . Let µ(M ′ ) denote the number of vertices in V ′ that are covered by M ′ , and W (M ′ ) denote the weight of M ′ . Suppose that µ(M ′ ) contains e 1 edges from E 1 and e 2 edges from E 2 . Then µ(M ′ ) = e 1 + 2e 2 and W (M ′ ) = qe 1 + 2qe 2 + e 2 . Since e 2 ≤ q/2 < q, µ(M ′ ) = ⌊W (M ′ )/q⌋. Thus, no other matching matches more vertices in V ′ than M. Moreover, of those matchings that match the same number of V ′ vertices as M, none has more edges from E 2 , so none consists of fewer edges than M. Thus, M matches as many vertices from V ′ as possible, and does so with the minimum number of edges possible.
We note that both (i) construction of the matching graph G m and (ii) finding a maximum matching in G m can be done in polynomial time. It follows that the learning problem considered is efficiently PAC learnable. Theorem 4.2 Suppose G obs (V, E) is missing at most k edges, with at most one is incident on each vertex. The corresponding hypothesis class is efficiently PAC learnable.
In this section, we study the expressiveness of the hypothesis class H UNDIR,THRE for (UNDIR, THRESH)-SyDSs, measured by the Natarajan dimension (Natarajan 1989) Ndim(H UNDIR,THRE ). Specifically, a higher value of Ndim(H UNDIR,THRE ) implies a greater expressive power of the class H UNDIR,THRE . Further, Ndim(H UNDIR,THRE ) characterizes the sample complexity of learning H UNDIR,THRE . Theorem 5.1 The Natarajan dimension of the hypothesis class H UNDIR,THRE is ≥ ⌊n 2 /4⌋, irrespective of the graph structure. Proof. We establish the result by specifying a shattered set R ⊂ X of size ⌊n 2 /4⌋. Let the set V of n vertices be partitioned into two subsets: Y consisting of ⌊n/2⌋ vertices, and Z consisting of the other ⌈n/2⌉ vertices. Set R consists of |Y||Z| = ⌊n 2 /4⌋ configurations, as follows. Each configuration in R has exactly two vertices in state 1, one of which is in Y, and the other in Z.
Let g 1 be the function that maps each configuration C into the configuration where each vertex in Y has the same state as in C, and each vertex in Z has state 0. Let g 2 be the function that maps each configuration into the configuration where every vertex has state 0.
We now show that the two requirements for shattering are satisfied. For requirement (i), for each C ∈ R, the state-1 vertex in Y under C is in state 1 in g 1 (C) and in state 0 in g 2 (C), so g 1 (C) ̸ = g 2 (C). For requirement (ii), consider each subset R ′ ⊆ R. Let S R ′ = (G R ′ , F R ′ ) ∈ H be the following SyDS. Graph G R ′ is bipartite with vertex sets Y and Z; it contains an edge {y, z} iff there is configuration in R ′ in which y and z are both in state 1. Each interaction function is a threshold function, where the threshold of every vertex in Y is 2, and the threshold of every vertex in Z is 3. We now claim that ∀C ∈ R ′ , S(C) = g 1 (C) and ∀C ∈ R \ R ′ , S(C) = g 2 (C). Consider any C ∈ R. Let y ∈ Y and z ∈ Z be the two vertices that are in state 1 in C. If C ∈ R ′ , then G R ′ contains the edge (y, z), so S(C) = g 1 (C). If C ∈ R \ R ′ , then y and z are not neighbors in G R ′ , so S(C) = g 2 (C). This completes our proof of the claim and also that of Theorem 5.1.
From (Shalev-Shwartz and Ben-David 2014), the sample complexity of learning H UNDIR,THRE is at most:
(2) Thus, we have the following corollary:
We examined the problem of learning both the topology and the interaction functions of an unknown networked dynamical system under the PAC model. We showed that the problem is, in general, computationally intractable. We also identified efficiently solvable special cases. Further, we studied a setting where the underlying network is partially observed, and proposed an efficient PAC learner. It would be interesting to extend our efficient algorithms to the case where the observation set includes other forms of a system's dynamics instead of single transitions (e.g., positive and negative examples of single transitions, trajectories with two or more transitions). It would also be of interest to consider the problem where additional information about the graph (e.g., maximum node degree, the size of a maximum clique) and/or the interaction functions (e.g., upper bounds on the threshold values) is also available.
The Thirty-Eighth AAAI Conference on Artificial Intelligence
Thirty-Eighth AAAI Conference on Artificial Intelligence