Using Active Queries to Infer Symmetric Node Functions of Graph Dynamical Systems

Discrete dynamical systems and their significance

Discrete dynamical systems are used in a host of settings to understand population-level social contagion dynamics in terms of individual (human) agent behavior. Examples include the spread of health behaviors (Valente, 2010) such as needle sharing in drug use (Latkin, 1998;Valente, 2012) and overdose prevention (Sherman et al., 2009); segregation (Schelling, 1971); financial contagions (Gai and Kapadia, 2010); starting to use online communication tools (Karsai et al., 2014); and coordination (Rosenthal et al., 2015). The frameworks in these papers and our paper are network representations of populations, where nodes and edges represent entities (such as humans) and pairwise interactions, respectively. Our focus is on a particular class of discrete dynamical systems, called Synchronous Dynamical Systems (SyDSs). A formal definition of this model is given in Section 2.

Each of the works cited above can be viewed as capturing influence through threshold models (Granovetter, 1978;Schelling, 1978), where a node v i contracts a contagion if at least a particular number of its neighbors have already contracted it. This number for node v i is called its threshold τ i . We are interested in complex contagions (Centola and Macy, 2007) that are characteristic of social contagions. In this case, some agents may need multiple reinforcing interactions to adopt a contagion; that is, some nodes have thresholds of 2 or more. These models are used to study many problems, such as those defined above, and other social phenomena (e.g., Granovetter (1978); Schelling (1978); Centola and Macy (2007); Valente (1995); Easley and Kleinberg (2010)). Furthermore, Watts (2002) argues that threshold models are used in a host of settings where incomplete information exists or when there is insufficient time to make more deliberate decisions. Thus, threshold models are used widely in the social sciences for understanding social contagions.

Active querying and its significance

In general, an inference algorithm may receive observed data about the dynamical system or submit queries to the system and obtain responses from the system. The former approach, which has been studied by many researchers (e.g., González-Bailón et al. (2011); Adiga et al. (2017); Romero et al. (2011a)), will be discussed briefly in Section 1.5. In this paper, we pursue the latter approach. We study inference by active querying, where the user has some control over what information is extracted from the dynamical system by querying it. Several behavioral studies have been conducted in a network setting in the context of public goods games, collective identity, and team-building exercises (Broere et al., 2019;Cedeno-Mieles et al., 2020;Charness et al., 2014). In all these works, human subjects (agents) are allowed or required to coordinate with one another (thus forming a network) to achieve their goals. The principal who conducts these games designs situations by providing incentives for agents to act in a certain manner. The individual and collective behaviors resulting from these experiments are then analyzed. Such settings have been effectively modeled as network dynamical systems (Santos et al., 2008;Cedeno-Mieles et al., 2020). Active querying of a dynamical system is akin to such controlled experimentation in the real-world experiments to understand agent behavior in a network setting. Since every experiment has a cost associated with it, a natural objective is to minimize the number of queries used to infer a system.

Here, we focus on a model where each query is a system configuration C, with each configuration being an ordered tuple of states of the nodes of a dynamical system at a particular time t. The response from the system is the successor C of C, that is, the configuration of the system at time t + 1. The goal is to infer the node functions of the system from the responses. Our query model is motivated by the following two lines of research.

1. First, learning Boolean functions is an important area of learning theory (e.g., Abasi et al. (2014); Angluin and Slonim (1994); Sloan et al. (2013); Angluin et al. (1992Angluin et al. ( , 1993))). In this setting, each query (usually referred to as a membership query) specifies an input α to an unknown function f and an oracle returns the value f (α). Our query model is an extension of membership queries to a network setting. In our case, since multiple Boolean functions (one for each node of the dynamical system) must be inferred, each query (i.e., a configuration) provides inputs to all the functions, and the output is another configuration which provides the values of all the functions for the specified inputs. Our work is similar in form to the teacher model (e.g., Goldman and Kearns (1995); Dasgupta et al. (2019)) in the context of concept learning, where a teacher selects instances so that a student can learn the target concept from a concept class. In all these cases (including ours), the objective is to find a minimum set of queries that is sufficient to learn the object.

2. Second, our query model can also be thought of as an idealized version of hypothetical queries (i.e., alternate scenarios) that are useful in inferring local behaviors of individuals in the context of social contagions such as opinions or health issues (e.g., Sloan et al. (2013); Centola (2010Centola ( , 2011))). For concreteness, we consider opinion propagation over a network, where the values 0 and 1 represent respectively positive and negative opinions on a certain topic. To understand when an individual (corresponding to a node in a social network) will change her opinion, a principal (e.g., a social scientist or a healthcare professional) may pose a query of the form "If the opinions of your neighbors are represented by this Boolean vector v, what will be your opinion?". Such queries do not set the opinions of the nodes in the social network to true (or actual) values. Instead, the principal tries to determine the situations that cause changes in an individual's behavior by analyzing the responses of the individual to a set of queries where the opinions of the neighbors of the individual are hypothetical values. While this can be done by issuing such queries to each node separately (Centola (2010(Centola ( , 2011))), the underlying network provides a way to combine these individual queries into a single configuration so that the number of queries can be further reduced. Thus, our query model exploits the network structure in constructing a small set of queries to learn the local functions.

Our work is similar in spirit-but quite different in problem domain and results-to some of the recent works on inference (e.g., Kleinberg et al. (2017)) or the popular and well-studied area of active learning (Settles, 2009;Dasgupta and Langford, 2009). We will discuss this in more detail in Section 1.5. To the best of our knowledge, this is the first work which approaches the inference problem for dynamical systems from a combinatorial and algorithmic perspective. In doing so, we relate it to well-studied graph theoretic approaches such as node coloring and probabilistic methods. The formulation also enables us to quantify rigorously the complexity of inferring such systems.

Summary of Results

Our focus is on the following problem: given the underlying graph of a dynamical system, construct queries to identify all the local functions. We study two query modes, namely batch and adaptive modes, that differ in their degrees of control. Under the batch mode, all the queries must be submitted together. In the adaptive mode, queries can be submitted in several stages, and queries at a stage can depend on the answers to previous queries; this strategy is similar to the one used in games such as "Twenty Questions" 1 . The optimization goal is to minimize the number of queries. We present both theoretical and experimental results as summarized below. In the following, we use G to denote the underlying network of the SyDS with n nodes and ∆ to denote the maximum node degree of G.

(a) Generating concise query sets for symmetric node functions under the batch mode. We develop an algorithm for generating query sets under the batch mode to correctly identify all the symmetric local functions of the dynamical system. Such a set is called a complete query set. The main idea used in this algorithm is distance-two vertex coloring of the network G. We show that the size of a complete query set is at most χ(G 2 ) + 1 ≤ min{∆ 2 + 2, n + 1}, where χ(G 2 ) is the minimum number of colors required for distance-two coloring of G (Theorem 10). We also establish a lower bound of ∆ + 2 on the size of any complete query set (Proposition 3).

(b) Complexity of generating optimal query sets. The query set generated by the method in (a) satisfies a monotonicity property (defined in Section 4.1). We show that the problem of finding an optimal monotone complete query set is . This provides an indication of the difficulty of efficiently generating optimal query sets.

(c) Sharper bounds based on probabilistic methods. We show that a query set of size O(∆ 1.5 log n) which is complete with probability at least 1 -1 n can be obtained using a sampling technique (Theorem 12). Using more sophisticated techniques based on Lovász Local Lemma (Mitzenmacher and Upfal, 2005), we show that there exists a complete query set of size O(∆(log ∆) 2.5 ) (Theorem 13). We note that this bound is asymptotically better than the ∆ 2 + 2 bound based on distance-two coloring mentioned above.

(d) Query set compaction. We formulate the problem of query set compaction, i.e., minimizing the size of a query set by deleting redundant queries. We show that the problem is, in general, NP-complete. We present an approximation algorithm for the problem and prove that it achieves the best performance guarantee to within constant factors, under the common assumption that P = NP (Theorems 23 and 26).

(e) Inferring threshold functions under the adaptive query mode. As can be expected, adaptive query mode, when applicable, can produce significantly smaller query sets compared to the batch mode. Our results for adaptive querying are based on binary search. This enables us to find the threshold of a node whose local function has k inputs using O(log k) queries. Using an extension of this technique, we show that the thresholds of all the nodes in a scale-free (i.e., power law) graph with exponent γ ≥ 1 can be found using O [n log n] 2 γ+1 queries (Theorem 22). In addition, we show that for a dynamical system where the underlying network is a clique and each node is associated with a threshold function, n + 1 queries are necessary even under the adaptive query mode (Theorem 5). For general graphs, we develop a greedy heuristic based on binary search and distance-two coloring to construct query sets.

(f ) Extensive experimentation on synthetic and real-world networks. We evaluated the various query generation algorithms under the batch mode on more than 20 real-world and synthetic networks. For most real-world networks, our algorithm based on distance-two coloring generates query sets of minimum size. We present experimental results to show that the combination of randomized query generation followed by query set compaction produces small query sets under the batch mode for many well known social networks. We evaluated the greedy heuristic under the adaptive mode (mentioned in Item (e) above) for various settings of networks and threshold assignments. Our results (Section 7) show that for most cases, it significantly outperforms the batch mode algorithms. We also study the effect of network structure and threshold assignments on the size of query sets.

Related Work

The problem of inferring unknown components of systems has received attention in the literature. There are several works on the passive mode of inference. For instance, many researchers have studied the problem of learning automata (e.g., Murphy (1996)). Kearns and Vazirani (1994) study the problem of learning normal forms and Boolean functions. Works such as (González-Bailón et al., 2011;Romero et al., 2011b) infer thresholds from social media data. Abrahao et al. (2013), Gomez-Rodriguez et al. (2010) and Soundarajan and Hopcroft (2010) consider the problem of inferring the network structure given the contagion propagation model. Learning the source nodes of infection for contagion spreading is addressed in (Zhu et al., 2017). Many of these problems are formally hard even for simple local functions. The work of (Adiga et al., 2017) provides several problems aimed at inferring thresholds in threshold-based discrete dynamical systems. Recently, there have been several works on learnability of dynamical system properties under the Probably Approximately Correct (PAC) learning framework. Lokhov (2016) uses a dynamic message-passing algorithm to reconstruct parameters of a spreading model given infection cascades. Narasimhan et al. (2015) and He et al. (2016) have studied the learnability of the influence function of popular stochastic propagation models, and Adiga et al. (2019) consider the problem of learning node thresholds. Inference problems for a class of local functions, motivated by user behavior in Facebook like networks, are studied in Adiga et al. (2020). Several works show the sensitivity of results to other dynamical systems features, such as network structure (Allen and Gale, 2000;Ganesh et al., 2005;Chakrabarti et al., 2008;Prakash et al., 2012).

Active querying is studied in (Kleinberg et al., 2017) in the context of determining user choices from a finite set of ranked options-the choice set problem. The goal is to minimize the number of queries of arbitrary subsets S of size k, of a universal set U , to learn a user's choice from among the elements of each set S. With these results, the algorithm can then predict the user's choice for any subset S ⊆ U of size k. They show that this can be accomplished with O(n log n) queries where n = |U |. The independent cascade model under the active query model has also been studied (Adiga et al., 2018a).

We note that our work is different from the area of active learning (e.g., Dasgupta and Langford (2009); Settles (2009)). An active learning algorithm has access to a limited number of labeled instances and a large number of unlabeled instances initially. The algorithm submits appropriately chosen unlabeled instances as queries to an oracle which returns the labels of those instances. This process allows an algorithm to learn more effectively using fewer labeled instances since the algorithm is allowed to select the instances used in the learning process. The main difference in our setting is that there are no labels; instead, our inference algorithms use queries, with each query specifying a configuration C and requiring the oracle to return the successor configuration C . Like active learning, our algorithms also choose queries appropriately so that the local functions can be inferred with a small number of queries.

There are several challenges in determining individual node thresholds in realistic settings: (i) data are collected at discrete time intervals (not continuously), (ii) there may be time delay effects in agents observing their neighborhoods, and (iii) inherent stochasticity (Valente, 1996;Berry and Cameron, 2017). Practical guidelines and issues for threshold measurement are discussed in (Berry and Cameron, 2017). Here, we investigate problems of inferring local functions using rigorous formulations, supplementing them with experimental results from heuristics.

Classes of Local Functions

We consider two classes of local functions, namely threshold and symmetric functions. They are defined below. (i) Threshold functions: The local function f v associated with node v of a SyDS S is a τ v -threshold function for some integer τ v ≥ 0 if the following condition holds: the value of f v is 1 if the number of ones in the input to f v is at least τ v ; otherwise, the value of the function is 0. Let d v denote the degree of node v, and let τ v denote the threshold of node v.

The number of inputs to the function

(The threshold values 0 and d v + 2 allow us to realize local functions that always output 1 and 0 respectively.) (ii) Symmetric functions: A local function f v at node v is symmetric if the value of the function depends only on the number of ones in the input. Thus, a symmetric function f v with k inputs can be specified using a table with k + 1 rows, with row i specifying the value of the function when the number of ones in the input to the function is exactly i, 0 ≤ i ≤ k. Note that each threshold function is also a symmetric function; however, symmetric functions are more general than threshold functions. For example, consider the following symmetric function f with five inputs: let the value of f be 1 when the number of ones in its input is (exactly) 1; otherwise, the value of f is 0. This is not a threshold function since the value of the function is 1 when the number of ones in the input is 1 but changes to 0 when the number of ones in the input is larger than 1. We will use the term "symmetric SyDS" ("threshold SyDS") to refer to a SyDS whose local functions are all symmetric (threshold).

Example: Consider the graph of a threshold SyDS shown in Figure 1(a). The thresholds are assigned in Figure 1(b). Also, we show an example trajectory (i.e., time sequence of configurations) of the system given that initially nodes 4, 6 and 7 are in state 1 and the rest are in state 0. Once the system reaches the configuration C = (1, 1, 1, 0, 0, 1, 0) at time step 3, it remains in that configuration forever; that is, C is a fixed point for this system. Additional Terminology: If a given SyDS can transition in one step from a configuration C to a configuration C , then C is a successor of C and C is a predecessor of C . Since our local functions are deterministic, each configuration has a unique successor; however, a configuration may have zero or more predecessors. Given a graph G(V, E) and a node

Thus, the inputs to the function f i at v i are the states of the nodes in N [v i ].

Lower Bounds on Sizes of Query Sets

Here, we present lower bounds under batch and adaptive query modes. We begin with a result that provides a lower bound for any symmetric SyDS under the batch mode.

Proposition 3 Let S be a symmetric SyDS where the underlying graph G(V, E) has a maximum node degree ∆. Under the batch query model, every complete query set must contain at least ∆ + 2 queries.

Proof: Under the batch mode, suppose a complete query set Q has fewer than ∆+2 queries. Since G has a node v of degree ∆, the number of ones in the input to the symmetric function f v at v varies from 0 to ∆ + 1, a total of ∆ + 2 values. Thus, there is at least one value k such that none of the queries in Q has a score of k with respect to v. Hence, the query set cannot correctly determine the value of the function f v when the number of ones in the input to f v is exactly k. This contradicts the assumption that Q is a complete query set. The proposition follows.

As a simple consequence of the above proposition, the following result points out that there are SyDSs with n nodes for which every complete query set must have n + 1 queries. This lower bound matches the upper bound of n + 1 given by Theorem 10 (Section 4) for all graphs.

Corollary 4 For symmetric SyDSs whose underlying graph is a clique on n nodes, every complete query set under the batch mode must have at least n + 1 queries.

We now establish a lower bound under the adaptive query model to show that there are threshold SyDSs for which a large number of queries are needed even under the adaptive query mode. However, this result does not rule out the possibility of smaller query sets for special graph classes.

Theorem 5 For every n ≥ 1, there is a threshold SyDS whose underlying graph is a clique on n nodes such that at least n + 1 queries are necessary under the adaptive query mode to correctly identify all the threshold values.

Proof: Consider a threshold SyDS S whose underlying graph G(V, E) is a clique on n nodes. Let V = {v 1 , v 2 , . . . , v n }. We will tentatively choose the threshold of node v i to be i to answer queries under the adaptive model, We will show that if the total number of queries is less than n + 1, the answers to the queries cannot distinguish between this tentative assignment and a slightly different assignment of threshold values.

Suppose Q is a sequence of queries under the adaptive model, with |Q| ≤ n. We generate the responses to the queries using the chosen tentative assignment of threshold values to nodes. The threshold of any node of S is in the range 0 through n + 1 (where the threshold value n + 1 indicates the function which is zero for every input). Since G is a clique, the the closed neighborhood of each node is the node set V . Thus, each query q ∈ Q provides the same score to each node of G. There are n + 1 scores in the range 0 through n. Since Q has at most n queries, there is at least one value k, 0 ≤ k ≤ n, such that none of the queries in Q provides the score k. We have three cases depending on the value of k.

Case 1: k = 0. In this case, from the responses to the queries in Q, one cannot distinguish between the case where the threshold of node v 1 is 0 and the case where the threshold of v 1 is 1. (In both cases, the new state of v 1 is 1 in the response to each query in Q.)

Case 2: k = n. In this case, from the responses to the queries in Q, one cannot distinguish between the case where the threshold of node v n is n and the case where the threshold of v n is n + 1. (In both cases, the new state of v n is 0 in the response to each query in Q.)

Case 3: 1 ≤ k ≤ n -1. In this case, from the responses to the queries in Q, one cannot distinguish between the case where the threshold of node v k is k and the case where the threshold of v k is k + 1. (In both cases, the responses have the following property. For any query q ∈ Q where score(q,v k ) ≤ k -1, the new state of v k is 0 in the response. For any query q ∈ Q where score(q,v k ) ≤ k + 1, the new state of v k is 1 in the response.) Thus, under the adaptive model, a query set with n or fewer queries cannot correctly identify all the thresholds for the chosen SyDS. This completes the proof of Theorem 5.

Obtaining a Query Sequence From Node Coloring

Overview: We begin by defining the notion of a monotone query sequence. The sequence of queries constructed can be submitted as a batch to learn all the local functions of a symmetric SyDS. Using the notion of "sequence" allows us to point out an interesting connection between the problem of identifying symmetric local functions and a variant of the node coloring problem for the underlying graph. We remind the reader that each query is a bit vector.

Definition 6 (a) Given two queries q 1 and q 2 , we use the notation q 1 ≤ q 2 to mean that every bit which is 1 in q 1 is also 1 in q 2 . (b) A query sequence q 1 , q 2 , . . . , q r is monotone if for each i, 1 ≤ i ≤ r -1, q i ≤ q i+1 . (c) Let S be a symmetric SyDS and let M be a monotone query sequence. If M is also a complete query set for S (i.e., each node v of S is covered by M ), then M is a complete monotone query sequence.

The following lemma points out a property of complete monotone query sequences.

Lemma 7 Let S be a symmetric SyDS and let M = q 1 , q 2 , . . . q r be a complete monotone query sequence with 2 or more queries for S. Then q 1 is the vector of all zeros and q r is the vector with all ones.

Proof: Suppose q 1 is not the vector with all zeros. Let v i be a node such that the value assigned by q 1 to v i is 1. Thus, score(q 1 ,v i ) ≥ 1. Since M is a monotone query sequence, score(q j ,v i ) ≥ 1 for 2 ≤ j ≤ r. In other words, there is no query q j ∈ M for which score(q j , v i ) = 0, contradicting the assumption that M covers v i . Likewise, if q r is not the vector with all ones, there is a node v k such that the value assigned to v k by q r is 0. Thus, there is no query q j in M such that score(q j ,v k ) = degree(v k )+1. In other words, M does not cover v k .

We now present an algorithm to show that if the underlying graph G has n nodes, then there is a monotone complete query sequence M for S with at most min{∆ 2 + 2, n + 1} queries, where ∆ is the maximum node degree of G. This sequence of queries can be submitted as a batch to learn all the symmetric local functions. To establish this result, we recall the following definitions.

Definition 8 (a) Given an undirected graph H(V H , E H ) and an integer k ≥ 1, a k-coloring of H assigns a color from {1, 2, . . . , k} to each node of H such that for each edge {u, v} ∈ E H , the colors assigned to u and v are different. (b) Given an undirected graph G(V, E), the square of G, denoted by G 2 (V, E ), is an undirected graph on the same vertex set V . The edge set E is defined as follows: {u, v} ∈ E iff there is a path with at most 2 edges between u and v in G.

We will also use the following result called Brooks' Theorem (West, 2001, Theorem 5.1.22).

Lemma 9 Let H(V H , E H ) be a graph with maximum node degree ∆ H . Then, H can be colored efficiently using at most ∆ H + 1 colors.

. ., C k denote the color classes created in the above coloring step.

(Color class C j consists of all nodes assigned color j, 1 ≤ j ≤ k.) 4 Create the query sequence M = q 0 , q 1 , . . . , q k with k + 1 queries as follows: query q 0 is a bit vector where every element is 0. 5 for j = 1, 2, . . . , k do 6 Create query q j by choosing the value 1 for all the nodes in C 1 ∪ . . . ∪ C j and 0 for the other nodes.

7 end 8 Output the query sequence M .

Our algorithm Alg-Monotone-Seq for generating a monotone complete query sequence M for the given SyDS S is shown in Algorithm 1. It is easy to see that the algorithm runs in polynomial time. The following theorem shows its correctness and estimates the number of queries generated.

Theorem 10 Let S be a symmetric SyDS whose graph G(V, E) has n nodes and maximum node degree ∆. Algorithm Alg-Monotone-Seq (Algorithm 1) produces a monotone complete query sequence M with at most min{∆ 2 + 2, n + 1} queries.

Proof: We first show that Step 2 of the algorithm can indeed color G 2 using at most min{∆ 2 + 1, n} colors. Since the maximum node degree in G is ∆, each node v of G has at most ∆ neighbors and at most ∆(∆ -1) nodes at a distance of 2 from v. Thus, the maximum node degree in G 2 is at most ∆(∆ -1) + ∆ = ∆ 2 . Hence, by Lemma 9, G 2 can be colored using at most ∆ 2 + 1 colors. Since G 2 has n nodes, n colors are always sufficient. Thus, G 2 can be colored with at most k = min{∆ 2 + 1, n} colors. Hence, the number of queries in M = k + 1 is at most min{∆ 2 + 2, n + 1}.

We now argue that the query sequence M = q 0 , q 1 , . . . , q k is monotone. Query q 0 is the bit vector with all zeros. For any j ≥ 1, query q j sets all the nodes in color classes C 1 through C j to 1 and the remaining nodes to 0. Thus, each node that is set to 1 in query q j remains 1 in all the subsequent queries q j+1 , . . ., q k . In other words, the sequence is monotone.

Thus, we are left with the proof that M is complete; that is, for each node v with degree α in G and each value , 0 ≤ ≤ α + 1, there is a query q in M such that score(q,v) =

. Query q 0 ensures that score(q,v) = 0. For the other values of , consider the closed neighborhood

, there is a path consisting of at most two edges in G. Thus, the nodes in

appear, and assume without loss of generality that j 1 < j 2 < . . . < j α+1 . It is easy to see that for 1 ≤ ≤ α + 1, query q j ensures that score(q j ,v) = . This completes the proof of Theorem 10.

Generating Coloring from a Monotone Complete Query Sequence

The above algorithm and Theorem 10 show that a monotone complete query sequence can be constructed from the coloring of the graph G 2 . Theorem 11 shows that this relationship is not accidental; indeed, a valid coloring of G 2 can be generated from any monotone complete query sequence. This result is useful in proving that it is NP-hard to generate complete monotone query sequences of minimum length.

Theorem 11 Let G(V, E) be the underlying graph of a symmetric SyDS S. Suppose there is a monotone complete query sequence M with queries for S. Then, G 2 can be colored using -1 colors.

Proof: Let M = q 1 , q 2 , . . . , q denote the given monotone complete query sequence for S. Let C i denote the set of nodes of G which have the value 0 in q i and the value 1 in q i+1 , 1 ≤ i ≤ -1. Assign color i to all the nodes in C i , 1 ≤ i ≤ -1. We now prove that this scheme assigns a color to each node and that this is a valid coloring of G 2 .

First, we prove that each node is assigned a color. To see this, note that since M is a monotone complete query sequence, by Lemma 7, query q 1 has all its bits set to 0 and q has all its bits set to 1. Therefore, for each node v, there is an index r such that the value assigned to v in q r is 0 and that in q r+1 is 1. Thus, v appears in set C r and receives color r. The monotonicity of M ensures that v remains 1 in queries q r+1 through q .

We now prove by contradiction that the above method produces a valid coloring of G 2 . So, suppose that v i and v j are two nodes that receive the same color, say k, but G 2 has the edge {v i , v j }. By our coloring scheme, both v i and v j had the value 0 in q k and the value 1 in q k+1 . There are two cases to consider.

Case 1: The edge {v i , v j } is in G.

Note that both v i and v j have color k. Let score(q k ,v i ) = α. Since both v i and v j changed from 0 in q k to 1 in q k+1 and {v i , v j } is an edge in G, score(q k+1 ,v i ) ≥ α + 2. Because M is monotone, none of the other queries in M provides a score of α + 1 to v i . This contradicts the assumption that M is complete.

Case 2: The edge

In this case, there is a node v x such that the edges {v i , v x } and {v j , v x } are in G. Let score(q k ,v x ) = β. Since both v i and v j changed from 0 to 1 in q k+1 and both {v i , v x } and {v j , v x } are edges in G, score(q k+1 ,v x ) ≥ β + 2. Because M is monotone, none of the other queries in M provides a score of β + 1 to v x . Again, this contradicts the assumption that M is complete, and Theorem 11 follows. Figure 3 gives an example of a batch query set generated using the distance-2 coloring method discussed above. The figure also includes a query set generated using an adaptive query algorithm discussed in Section 7. Color → a b c d 1 0 1 1 1 1 2 0 0 1 1 1 3 0 0 0 1 1 4 0 0 0 0 1 5 0 1 1 1 1 6 0 0 0 1 1 7 0 0 1 1 1 (c) Batch mode query set 1 2 3 4 5 1 0,4 0 0,2 0 0,1 0 0,1 0 1,1 0 1,1 2 0,4 1 0,2 0 0,1 0 0,1 0 0,0 0 0,0 3 0,5 1 0,2 1 2,2 1 2,2 0 2,2 1 2,2 4 0,5 0 2,5 1 3,5 1 4,5 0 4,5 1 4,4 5 0,5 0 2,5 1 3,4 1 4,4 1 4,4 1 4,4 6 0,4 1 0,2 0 1,1 0 1,1 1 1,1 0 1,1 7 0,5 1 2,5 0 3,4 1 3,4 1 3,3 1 3,3 (d) Adaptive querying Figure 3: Query sets for the threshold SyDS of in Figure 1. In (c), the shaded rows correspond to nodes which have been assigned the color indicated by the column heading. In (d), the queries were generated adaptively using Algorithm 3 described in Section 7. There are five iterations and therefore, five queries. For each iteration, the corresponding query as well as the uncertainty (range) in the thresholds of the vertices are shown.

Generating query sets based on probabilistic methods

In Section 4.1, we showed that for any symmetric SyDS whose underlying graph has n nodes and maximum node degree ∆, one can obtain a complete query set with at most min{∆ 2 + 2, n + 1} queries. For some graphs with maximum node degree ∆, this method may generate a query set with Ω(∆ 2 ) queries. Here, using probabilistic methods, we provide better bounds. First, using a simple sampling technique, we will show that there exists a query set of size at most O(∆ 1.5 log n) that is complete with high probability. This is asymptotically better than the previously established bounds for graphs where ∆ ≥ (log n) 2 . Moreover, such a query set can be generated efficiently. Next, using more sophisticated techniques from Füredi and Kahn (1986) based on the Lovász Local Lemma, we show an upper bound of O(∆(log ∆) 2.5 ) on the size of complete query sets.

Theorem 12 Let S be a symmetric SyDS with graph G(V, E) where |V | = n and maximum node degree = ∆. A query set Q of size O(∆ 1.5 log (n)) which is complete with probability at least 1 -1 n can be constructed for S.

The proof of the above theorem appears in Appendix A. Here, we provide the general idea for the query set construction method used in proving the above theorem. Let D(p) be a probability distribution defined on the set of configurations of a SyDS such that the state of each vertex is set to 1 independently with probability p. For a query q, we use the notation q ∼ D(p) to mean that query q is drawn from the distribution D(p). We will generate a query set

for some number of repetitions r. This construction enables us to prove that for any vertex v and positive integer k ≤ ∆ + 1, with high probability, there is a query q ik ∈ Q for which score(q ik , v) = k. The reader is referred to Appendix A for details. Now, we show an upper bound of O(∆(log ∆) 2.5 ) on the size of complete query sets under the batch mode for SyDSs with symmetric local functions.

Theorem 13 Let G(V, E) be the underlying graph of a symmetric SyDS S. Let ∆ denote the maximum node degree in G. Under the batch mode, for any ∆ ≥ 2, there is a complete query set Q for S with |Q| = O ∆(log ∆) 2.5 .

The following lemma is a key ingredient for the proof of Theorem 13. Suppose G(V, E) is a graph and

The following notation is used in our proof of the lemma. Given a positive real number x, we let x to denote the integer obtained by rounding x to the nearest integer; that is, x = x if the fractional part of x is less than 0.5; otherwise,

Proof: The all zeros query 0 is such that ∀v ∈ V , score(v, 0) = 0. The configuration q with all vertices of V in state 1 yields ∀v ∈ V , score(v, q) = |N [v, V ]|. These two queries account for the additive term of 2. Let D(p, V ) be the distribution where each q ∼ D(p, V ) is constructed as follows: ∀v ∈ V , Pr(q(v) = 1) = p and ∀v ∈

where the second inequality follows from Lemma 27 which is given in Appendix A.

Pr score(v, q) = b for any

Note that if ∃v ∈ V and b ∈ {1, . . . , } such that score(v, q) = b for any q ∈ Q, then there is a subset of V of size ≤ for which in no query, b vertices are in state 1. Therefore, using union bound,

Hence, there exists a query set of size at most |Q| = ( -1) × 22 √ + 1 log |V | + 2 < 22 3/2 log |V | + 2 that satisfies the conditions in the statement of the lemma.

We also use the following two lemmas of Füredi and Kahn (Füredi and Kahn, 1986) that are based on the Lovász Local Lemma (Mitzenmacher and Upfal, 2005).

Lemma 15 Let H(V, E H ) be a hypergraph on a set of n elements V such that each hyperedge has at most b elements and each element belongs to at most b hyperedges, where b ≥ 500.

Proof of Theorem 13: We will prove that for any ∆ ≥ 2, the query set size is at most 2500∆(log ∆) 2.5 . We first note that Lemma 15 has a technical requirement that b be at least 500. In order to apply that result, we require ∆ ≥ 500. Hence, we first consider the case ∆ ≤ 500 separately. From Theorem 10, we have |Q| ≤ ∆ 2 + 2. For any constant c ≥ 42, it can be verified that |Q| ≤ ∆ 2 +2 ≤ c∆(log ∆) 2.5 for the entire range 2 ≤ ∆ ≤ 500. Therefore, the bound holds trivially for this case. So, we will assume for the remainder of this proof that ∆ > 500.

For any graph G, let H be the hypergraph where each hyperedge H v corresponds to the closed neighborhood of vertex v. Since the maximum degree is ∆, for all v, |H v | ≤ ∆ + 1 and v belongs to at most ∆ + 1 hyperedges. By Lemma 15, for any ∆ ≥ 500, the vertices of G can be partitioned into α ≤ ∆+1 log(∆+1) subsets X 1 , X 2 , . . . , X α , such that every vertex is adjacent to at most = 4.7 log(∆ + 1) vertices in any X i . For 1 ≤ i ≤ α, let n ≤i (v) denote the number of neighbors of v in j≤i X j . The query set Q is structured in the following manner. It is partitioned into

for each v, where n ≤0 (v) = 0 by definition. In the remaining part, we will show that this can be achieved with |Q i | ≤ 22 √ ∆ log 2 ∆ + 2 for each i. We will partition each X i into subsets X i1 , X i2 , . . . , X ik such that every vertex in V is adjacent to at most one vertex in X ij for any j.

we note that there exist at most 22 2 √ log k + 2 ≤ 23 2 √ log( ∆) queries q such that ∀v ∈ V , q(v) = 0 and for each b = 0, 1, ..., |N [v, X i ]|, there exists a query q such that v is adjacent to exactly b vertices in {x ij | 1 ≤ j ≤ k}. Let this set of configurations be denoted by Q i .

For each q ∈ Q i , we construct a query q ∈ Q i as follows: ∀v ∈ X j , j < i, we set q(v) = 1, and ∀v ∈ X j , j > i, we set q(v) = 0. For v ∈ X i , q(v) = q(X ij ), where X ij is the set to which v belongs. Suppose in a configuration q, v ∈ V has b neighbors in state 1. We will now show that score(v, q) = n ≤i-1 (v) + b. By definition of q, for any u ∈ X i , q(u) = 1 if and only if q(X ij ) = 1. Since v is adjacent to at most one vertex in X ij for any j, there are exactly b vertices of N [v, X i ] with state 1 in q. Further, recalling that every vertex with color < i is in state 1 in q, score(v, q) = n ≤i-1 (v) + b. Finally, since for every b = n ≤i-1 (v) + 1, . . . , n ≤i (v), there exists a query q ∈ Q with b neighbors of v in state 1, the proof follows.

Thus,

, where the last inequality is due to the fact that = 4.7 log(∆ + 1) . Theorem 13 follows.

Complexity of Generating Small Monotone Complete Query Sequences

Here, we present a result that provides an indication of the difficulty of efficiently generating small query sets. In particular, we will show the NP-completeness of the following problem.

Short Monotone Complete Query Sequence (SMCQS) Given: The underlying graph G(V, E) of a symmetric SyDS S and a positive integer k. Question: Is there a monotone complete query sequence Q with at most k queries for S?

Theorem 17 Problem SMCQS is NP-complete.

Proof: It is easy to see that SMCQS is in NP. To prove NP-hardness, we use a reduction from the Distance-2 Coloring (D2C) problem defined as follows: given an undirected graph G(V, E) and an integer r, is G 2 r-colorable? It is known that D2C is NP-complete (McCormick, 1983) even for planar graphs (Lloyd and Ramanathan, 1992).

The reduction is straightforward. Given an instance of the D2C problem consisting of graph G and integer r, we obtain an instance of the SMCQS problem where the graph is G itself and the length k of the query sequence is r + 1. It was shown in the proof of Theorem 10 that when G 2 is r-colorable, there is a monotone complete query sequence with k = r + 1 queries. Also, from Theorem 11, from any monotone complete query sequence of length r + 1, one can obtain a valid coloring of G 2 with r colors. Thus, there is a solution to the SMCQS problem iff there is a solution to the D2C problem, and this completes the proof.

Generating Concise Query Sets: A Generalized Version

We now consider the complexity of a more general version of the problem of generating concise complete query sets under the batch model. Recall that for a symmetric SyDS, for each node v and each integer in {0, 1, . . ., degree(v)+1}, a complete query set Q must have a query q such that score(q,v) = . In the version of the problem considered below, we will only require the query set to provide a small subset of score values. This problem can be formulated as follows.

Concise Query Set for Specified Scores (CQS-SS) Instance: The underlying graph G(V, E) of a SyDS S where each local function is symmetric, a set L of score values and a positive integer k.

Question: Is there a query set Q with at most k queries for S such that for each node v and each score value s ∈ L, there is a query q ∈ Q for which score(q,v) = s?

We now show the CQS-SS problem is NP-complete even when the set L of scores contains only one value and the underlying graph is highly restricted (e.g., graphs of maximum node degree 4, planar graphs). To prove this result, we use a reduction from the One-In-Three 3SAT (OIT-3SAT) problem which is defined as follows: given a set of Boolean variables X = {x 1 , x 2 , . . . , x n } and a collection C = {C 1 , C 2 , . . . , C m } of clauses where each clause C j is a disjunction of exactly three variables from X, is there a truth assignment to the variables such that exactly one variable is set to true in each clause? In the definition of OIT-3SAT, note that none of the clauses contains negated literals. It is well known that OIT-3SAT is NP-complete (Garey and Johnson, 1979). The NP-completeness holds even under some restrictions as indicated in the following theorem.

Theorem 18 OIT-3SAT is NP-complete even when either of the following conditions hold.

(a) Each variable occurs in exactly three clauses (Schmidt, 2010).

(b) Consider the following graph H(V H , E H ) constructed from an OIT-3SAT instance. V H contains one node for each variable in X and one node for each clause in C. For a variable x i and clause C j , there is an edge between the corresponding nodes if x i appears in C j . OIT-3SAT is NP-hard even when graph H is planar (Hunt III et al., 1998;Mulzer and Rote, 2008).

Theorem 19 Problem CQS-SS is NP-complete even when set of scores has only one value. The problem remains NP-complete even when the underlying graph is constrained to belong to one of the following classes: (a) graphs with maximum node degree 4 or (b) planar graphs.

Proof: It is easy to see that CQS-SS is in NP. To prove NP-hardness, we use a reduction from OIT-3SAT defined above. Consider an instance of OIT-3SAT consisting of the variable set X and the clause set C. We construct an instance of the CQS-SS problem as follows.

We first describe the construction of the underlying graph G(V, E).

1. For each variable x i , V has a node v i , 1 ≤ i ≤ n. For each clause C j , V has a node w j , 1 ≤ j ≤ m.

2. For each variable x i and clause C j , if x i occurs in C j , then E contains the edge {v i , w j }, 1 ≤ i ≤ n and 1 ≤ j ≤ m.

3. For each node v i , G has another node z i and the edge {v i , z i }.

4. For each node w j , G has 4 additional nodes, denoted by y 1 j , y 2 j , y 3 j and y 4 j , and the following four edges: {w j , y 1 j }, {y 1 j , y 2 j }, {y 1 j , y 4 j }, {y 2 j , y 3 j }.

An example of this graph construction is shown in Figure 4. The local function at each node is symmetric. The set L of scores contains just one value, namely 1. The number of queries k is set to 1. This completes the construction of the CQS-SS instance, and it can be seen that the construction can be done in polynomial time. We now prove that the resulting CQS-SS instance has a solution iff the OIT-3SAT instance has a solution.

Suppose the OIT-3SAT instance has a solution. We construct the query q which provides a score of 1 to each node of G as follows. Note that G has a total of N = 2n + 5m nodes. For each node v of G, we will use the notation q(v) to denote the value of v in q.

(a) Consider each variable x i , 1 ≤ i ≤ n. If it is set to true in the solution to OIT-3SAT, set q(v i ) to 1 and q(z i ) to 0; otherwise, set q(v i ) to 0 and q(z i ) to 1.

(b) For each clause C j , 1 ≤ j ≤ m, set q(w j ) to 0.

(c) For each clause C j , 1 ≤ j ≤ m, the values in q for the nodes y 1 j through y 4 j are chosen as follows: q(y 1 j ) = q(y 2 j ) = 0 and q(y 3 j ) = q(y 4 j ) = 1.

It is easy to verify that for each v ∈ V , score(q,v) = 1. In other words, we have a solution to the CQS-SS instance.

Now suppose the CQS-SS instance has a solution. Let q be the corresponding query. We have the following claim.

Claim 1: (a) For 1 ≤ j ≤ m, q(w j ) = 0. (b) For 1 ≤ j ≤ m, q(y 1 j ) = 0. Proof of Claim 1: Part (a): Suppose q(w j ) = 1 for some j, 1 ≤ j ≤ m. Then since {w j , y 1 j } is an edge in E and q provides a score of 1 to each node, we must have q(y 1 j ) = 0. Now, since y 1 j is the only neighbor of y 4 j and score(q,y 4 j ) = 1, we must have q(y 4 j ) = 1. Now, however, score(q,y 1 j ) > 2 (since q(w j ) = 1 and q(y 4 j ) = 1). This contradicts the validity of q and establishes Part (a) of Claim 1.

Part (b): Suppose q(y 1 j ) = 1 for some j, 1 ≤ j ≤ m. Then since {y 1 j , y 2 j } is an edge in E and q provides a score of 1 to each node, we must have q(y 2 j ) = 0. Now, since y 2 j is the only neighbor of y 3 j and score(q,y 3 j ) = 1, we must have q(y 3 j ) = 1. Now, however, score(q,y 2 j ) = 2 (since q(y 1 j ) = 1 and q(y 3 j ) = 1). This contradicts the validity of q and establishes Part (b) of Claim 1.

We now continue with the main proof. We choose an assignment to the variables of X as follows. Consider each variable x i , 1 ≤ i ≤ n. If q(v i ) = 1, set x i to true; otherwise, set x i to false. To prove that this is a solution to the OIT-3SAT instance, we need to prove that each clause has exactly one variable set to true. Consider any clause C j and the corresponding node w j of G. We know that score(q,w j ) = 1. Since q(w j ) = 0 and q(y 1 j ) = 0 (Claim 1), the q provides a score of 1 to w j , there is exactly one node v r such that q(v r ) = 1 and the variable x r appears in clause C j . Since we set x r to true, exactly one of the variables in C j is set to true. In other words, we have a solution to the OIT-3SAT instance. This completes the proof of NP-hardness of CQS-SS for general graphs.

To obtain the NP-hardness of CQS-SS for graphs with maximum node degree of 4, we carry out the above reduction from the version of OIT-3SAT in which each variable occurs in exactly three clauses (Part (a) of Theorem 18). To obtain the NP-hardness of CQS-SS for planar graphs, we use the a reduction from the version of OIT-3SAT mentioned in Part (b) of Theorem 18 and note that the additional vertices and edges used in the construction do not affect planarity.

Query Sets Under the Adaptive Mode: Results for Threshold Functions

We now consider the adaptive mode of queries. We show that for threshold SyDSs, the adaptive query mode can reduce the number of queries significantly. To illustrate this, consider a SyDS whose underlying graph is a star graph with n nodes; that is, there is one node v 1 with degree n -1 which is the root of the tree and each of the other nodes v 2 through v n is child of the root. Under the adaptive mode, using the following method, O(log n) queries are sufficient.

The idea is simple: use binary search to identify the threshold of node v 1 whose degree is n -1 using O(log n) queries. Note that the threshold of v 1 can vary from 0 to n + 1. We first try a query q for which score(q,v 1 ) = n/2 . Depending on the response to the query, the range of possible threshold values for v 1 changes to either 0 through n/2 -1 or n/2 + 1 through n + 1. When this is repeated, after O(log n) queries under the adaptive model, we can identify the threshold of v 1 . After this, the following 3 additional queries are sufficient to identify the thresholds of the remaining n -1 nodes: a query with all zeros, a second query with all ones and a third one in which v 1 has the value 1 and all the remaining nodes have the value 0. Thus, all the thresholds can be identified using O(log n) queries under the adaptive mode. The following proposition summarizes the above discussion.

Proposition 20 For a SyDS where the underlying graph is the star graph with n nodes and each local function is a threshold function, O(log n) queries are sufficient under the adaptive query mode to determine all the local functions.

Since the center node of a star graph with n nodes has a degree of n -1, its threshold can be any one of the n + 1 values in {0, 1, . . . , n + 1}. Thus, a simple information theoretic argument points out that Ω(log n) is a lower bound on the number of adaptive queries needed to infer the threshold values of all the nodes of a star graph. Thus, the upper bound given by Proposition 20 is tight to within a constant factor.

As was shown in Section 3, in the batch mode, n + 1 queries are sometimes necessary to identify all the thresholds. Thus, the adaptive query mode can reduce the number of queries significantly.

The above idea can be applied to a more general class of graphs. Let α and β be nonnegative integers. We say that a graph is (α, β)-simple, if α nodes have degree > β and the remaining nα nodes have a degree of at most β. For example, any star graph on n nodes is a (1, 1)-simple graph. Trivially, every graph is a (0, n -1)-simple graph. However, when α and β are required to be constants independent of n, a clique on n nodes is not an (α, β)-simple graph. Under the adaptive query model, we can obtain small query sets for (α, β)-simple graphs when α and β are small. In what follows, we show that the number of adaptive queries required for an (α, β)-simple graph is at most α( log n + 1) + β 2 + 2. When α and β are constants, this bound is O(log n).

Theorem 21 For any threshold SyDS whose underlying graph G belongs to the class of (α, β)-simple graphs, α( log n + 1) + β 2 + 2 queries are sufficient in the adaptive mode to identify all the threshold values. In particular, if α and β are constants independent of n, the number of queries used in this approach is O(log n).

Proof: We present an approach that uses at most α( log n + 1) + β 2 + 2 queries under the adaptive query mode. To discuss this approach, let V 0 denote the subset of nodes of G such that each node in V 0 has a degree larger than β. Thus, |V 0 | = α. Let V 1 denote the set of remaining nα nodes (each of which has a degree of at most β). The steps of our method are as follows.

1. We first construct a set Q 1 of queries which are submitted in a single batch to identify the thresholds of all the nodes in V 1 as follows.

(a) Let G 1 be the subgraph of

Since the degree of each node in G 1 is at most β, the maximum node degree in G 2 1 is at most β 2 . Hence, by Lemma 9, G 2 1 can be efficiently colored using at most k = β 2 + 1 colors. Let C 1 , C 2 , . . . , C k denote the color classes generated in this step.

(c) Choose an arbitrary order, say v i 1 , v i 1 , . . ., v iα , for the nodes in V 0 . The first α + 1 queries of Q 1 , denoted by Q j 1 , 0 ≤ j ≤ α, are chosen as follows. In Q 0 1 , all the nodes have the value 0. In Q j 1 , 1 ≤ j ≤ α, nodes v i 1 through v i j have the value 1 and all other nodes have the value 0.

(d) The remaining k queries of Q 1 , denoted by Q j 1 , α + 1 ≤ j ≤ α + k, are chosen as follows. For all these queries, the values for all the α nodes of V 0 are 1. The values for the nodes in V 1 are chosen as follows. In Q j 1 , all the nodes in color classes C 1 through C j have the value 1 and all the remaining nodes of V 1 have the value 0, 1 ≤ j ≤ k.

(e) The total number of queries in Q 1 generated in Steps 1(c) and 1(d

2. Recall that |V 0 | = α. We use the adaptive mode for the nodes in V 0 ; that is, we use a separate binary search for each of the α nodes in V 0 . For each node v ∈ V 0 with degree d v , the batch queries in Q 1 include a query with scores 0 and d v + 1. Therefore, the binary search needs to consider only scores 1 through d v for v. This uses at most log (d v + 1) queries for v; this number is at most log n since d v < n. Thus, for all the α nodes in V 0 , the number of adaptive queries is at most α log n . Q 0 denote the set of queries used in this step.

As argued above, the queries in Q 0 identify the thresholds of all the nodes in V 0 . We now argue that the resulting query set Q 1 covers all the nodes of V 1 . To see this, consider any node v ∈ V 1 , and let d v be the degree of V in G. Thus, we need to show that for every value γ ∈ {0, 1, . . . , d v + 1}, there is a query q ∈ Q 1 such that score(q,v) = γ. Let r 0 and r 1 denote the number of neighbors of v in V 0 and V 1 respectively. Thus, d v = r 0 + r 1 . For 0 ≤ j ≤ α, in query Q j 1 , exactly j nodes from V 0 are 1 and all the other nodes are 0. Thus, for each value γ, where 0 ≤ γ ≤ r 0 , there is a query q ∈ Q 1 such that score(q,v) = γ. Now consider any value γ in the range r 0 + 1 through

may appear in the same color class. Let C p 1 < C p 2 < . . . < C p r 1 +1 denote the color classes in which nodes of N 1 [v] appear. It can be seen that for 1 ≤ ≤ r 0 + r 1 + 1, query Q 1 is such that score(Q 1 ,v) = . Thus, Q 1 covers all the nodes in V 1 , and this completes the proof.

From the above discussion, |Q 0 | ≤ α log n and |Q 1 | ≤ α + β 2 + 2. Thus, the total number of queries used by the above method is at most α( log n + 1) + β 2 + 2. This completes the proof of Theorem 21.

The above result can be used to establish an upper bound on the number of queries under the adaptive mode for scale-free graphs. Following Easley and Kleinberg (2010), we say that a graph with n nodes and maximum degree ∆ is scale-free with exponent γ if there are constants c > 0 and γ > 1 such that for any integer d, 0 ≤ d ≤ ∆, the fraction of nodes with degree d in G is given by c /d γ . Our upper bound for the number of queries for scale-free graphs is stated below.

Theorem 22 For a threshold SyDS whose underlying graph G(V, E) is scale-free with exponent γ > 1, the thresholds can be found using O [n log n] 2 γ+1 queries under the adaptive query mode.

Proof:

Part (a): It is easy to see that QSC is in NP. We prove NP-hardness through a reduction from MSC. Let the given instance of MSC consist of base set X = {x 1 , x 2 , . . . , x n }, collection Y = {Y 1 , Y 2 , . . . , Y m } of nonempty subsets of X and integer α ≤ m. Without loss of generality, we may assume that each element of X appears in some subset in Y ; otherwise, there is no solution to the MSC instance. We will construct the underlying graph G(V, E) of a SyDS S and a complete query set Q for S as follows.

one correspondence with the base set X = {x 1 , x 2 , . . . , x n } of the MSC instance and V 2 = {v n+1 } consists of just one node. (Thus, V has a total of n + 1 nodes.)

2. The edge set E of G is empty; that is, the degree of each node is 0. Thus, for each node v ∈ V , the number of ones in the input to the local function f v at v can only be either 0 or 1.

3. The query set Q consists of m + 1 queries (where m = |Y |) constructed as discussed below. Note that each query is an (n + 1)-bit vector, where the i th bit specifies the value of node v i , 1 ≤ i ≤ n + 1.

(a) For each Y j ∈ Y , 1 ≤ j ≤ m, Q contains a query q j constructed as follows. Let Y j = {x j 1 , x j 2 , . . . , x jr }. Then, in query q j , the bits corresponding to the nodes v j 1 , v j 2 , . . . , v jr are all 1 and the other bits are 0.

(b) We add one more query q m+1 to Q; in query q m+1 , bits 1 through n are set to 0 and bit n + 1 is set to 1.

4. The upper bound on the size of the required subset Q of queries is set to α + 1.

This completes the construction of the QSC instance. It can be seen that the construction can be carried out in polynomial time. We now show that Q is a complete query set for S.

Claim 1: The query set Q constructed above is a complete query set for S.

Proof of Claim 1: We must show that for each node v i ∈ V , Q contains two queries, say q i 0 and q i 1 , such that score(q i 0 ,v i ) = 0 and that score(q i 1 ,v i ) = 1. First, consider any node v i , where 1 ≤ i ≤ n. Query q m+1 sets the value of v i to 0; thus score(q m+1 ,v i ) = 0. Suppose the element x i (corresponding to node v i ) appears in subset Y j . By our construction, query q j sets the value of v i to 1; thus, score(q j ,v i ) = 1. For node v n+1 , each query q j created from Y j sets the value of v n+1 to 0; that is, score(q j ,v n+1 ) = 0; Also, query q m+1 sets the value of v n+1 to 1; thus, score(q m+1 ,v n+1 ) = 1. The claim follows.

We now prove that there is a solution to the QSC instance if and only if there is a solution to the MSC instance.

Part 1: Suppose there is a solution Y to the MSC instance consisting of sets Y j 1 , Y j 2 , . . ., Y j , for some ≤ α. Consider the query set Q = {q j 1 , q j 2 , . . . , q j , q m+1 }, which includes the queries corresponding to the sets in Y along with query q m+1 . Note that Q ⊆ Q. Also, since ≤ α, |Q | ≤ α + 1. Thus, we only need to show that Q is a complete query set. Consider any node v i , where 1 ≤ i ≤ n. Query q m+1 sets the value of v i to 0; thus, score(q m+1 ,v i ) = 0. Further, Since Y is a set cover, the element x i (corresponding to node v i ) appears in some subset Y jz ∈ Y . By our construction, in query q jz , the value of v i is 1; thus, score(q jz ,v i ) = 1. For node v n+1 , each query q ∈ Q -{q m+1 } sets the value of v n+1 to 0; thus, score(q,v n+1 ) = 0. Further, query q m+1 sets the value of v n+1 to 1; thus, score(q m+1 ,v n+1 ) = 1. Hence, Q is a complete query set.

Part 2: Let Q be a solution to the QSC instance with |Q | ≤ α + 1. We claim that q m+1 ∈ Q . This is because q m+1 is the only query for which score(q m+1 , v n+1 ) is 1. Define Q = Q -{q m+1 }. Let |Q | = and note that ≤ α. Further, let Q = {q j 1 , q j 2 , . . . , q j }. Consider the following subcollection Y of Y given by Y = {Y j 1 , Y j 2 , . . . , Y j }. We now show that Y is a solution to the MSC instance. To see this, consider any element x i ∈ X, where 1 ≤ i ≤ n. Query q m+1 ∈ Q sets node v i to 0. Since Q is a complete query set, some query q jz ∈ Q must set v i to 1. By our construction, the subset Y jz contains x i . Thus, Y is a set cover. Since |Y | ≤ α, Y is a solution to the MSC instance, and this completes the NP-hardness proof.

We use the same reduction to prove the non-approximability result. Suppose A is an approximation algorithm that provides a performance guarantee of ρ = o(log n) for the QSC problem, where n is the number of nodes in the underlying graph of the SyDS. We will show that A can be used to construct a 2ρ = o(log n) approximation algorithm for the MSC problem, contradicting the known non-approximability result for MSC. Towards this proof, consider any instance of the MSC optimization problem. Let OPT(MSC) denote the value of an optimal solution (i.e., the minimum size of a set cover) for the MSC instance and let OPT(QSC) denote the value of an optimal solution (i.e., the minimum size of a complete query subset) for the QSC instance constructed from the MSC instance. In the NP-hardness proof, we showed that OPT(QSC) ≤ OPT(MSC) + 1.

(2)

Suppose we run Algorithm A on the resulting QSC instance. Since A provides a ρ approximation, the solution produced by A has at most ρ OPT(QSC) queries. From this query set, it was shown in the NP-hardness proof that a solution to the MSC instance with ρ OPT(QSC) -1 subsets can be constructed. Letting APPROX(MSC) denote the resulting number of subsets, we have

Thus, if A provides a performance guarantee of ρ = o(log n) for the QSC problem, then there is a 2ρ = o(log n) approximation algorithm for the MSC problem. This completes the proof of Theorem 23.

An Approximation Algorithm for QSC

To complement the non-approximability result of the previous section, we will present an efficient approximation algorithm with a performance guarantee of O(log n) for the QSC problem. The basic idea is to use a reduction from the QSC problem to the MSC problem and then to use a known (greedy) approximation algorithm (Vazirani, 2001) for the MSC problem.

Algorithm 2: Steps of Algorithm Approx-QSC Input: The underlying graph G(V, E) of a symmetric SyDS S and a complete query set Q. Output: A subset Q ⊆ Q such that Q is also a complete query set and |Q | is a good approximation for a complete query set of minimum size. 1 To construct the base set X of the MSC instance, consider each node v i ; let d i denote the degree of v i . Create a set A i of d i + 1 elements, given by

3 Use the greedy algorithm (Vazirani, 2001) to get an approximate solution Y to the resulting MSC instance. 4 Construct the query set Q by choosing the query corresponding to each subset in Y and output Q .

The steps of our approximation algorithm Approx-QSC for QSC are shown in Algorithm 2. We assume that an instance of the QSC problem is specified by an underlying graph G(V, E) and a complete query set Q. Let V = {v 1 , v 2 , . . . , v n } and Q = {q 1 , q 2 , . . . , q m }. Note that each query q j ∈ Q is an n-bit vector, with bit i specifying the value of node

Steps 1 and 2 of the algorithm construct an instance of the MSC problem consisting of the base set X and a collection

Step 3 applies a well known greedy algorithm (which, in each iteration adds a subset Y j from Y such that Y j contains the maximum number of elements of X which have not yet been covered) to construct an approximate solution Y to the MSC problem. The final step chooses a query corresponding to each subset in Y and outputs the resulting query subset Q . It can be seen that the approximation algorithm runs in polynomial time. To establish the performance guarantee provided by Approx-QSC, we need the following lemma.

Lemma 24 The reduction from QSC to MSC used in Steps 1 and 2 of Approx-QSC (Algorithm 2) produces an instance of MSC such that any solution with r subsets to the MSC instance is a solution with r queries to the QSC instance and vice versa.

Proof: First, consider any solution Y = {Y j 1 , Y j 2 , . . . Y jr } with r subsets to the MSC instance. Let Q = {q j 1 , q j 2 , . . . , q jr } be the corresponding query set with r queries. We need to show that Q is a complete query set; that is, for any node v i (1 ≤ i ≤ n) and any integer k, 0 ≤ k ≤ d i , there is a query q ∈ Q such that score(q, v i ) = k. To see this, note that Y is a set cover. Thus, there is a set Y jz ∈ Y such that the element a ik ∈ X appears in Y jz . By our construction, a ik was added to Y jz because score(q jz , v i ) = k.

To prove the converse, let Q = {q j 1 , q j 2 , . . . , q jr } be a solution with r queries to the QSC instance. Consider the collection Y of sets given by Y = {Y j 1 , Y j 2 , . . . Y jr }. We claim that Y is a solution to the MSC instance. To see this, consider any element a ik ∈ X. Since Q is a complete query set, there is some query q jz ∈ Q such that score(q jz , v i ) = k. By our construction, set Y jz contains the element a ik . In other words, Y is a solution to the MSC instance with r sets.

The following is an immediate consequence of the above lemma.

Observation 25 Let OPT(QSC) denote the size of an optimal query set for a given QSC instance and let OPT(MSC) denote the size of an optimal solution to the MSC instance obtained at the end of Step 2 of Approx-QSC. Then, OPT(QSC) = OPT(MSC).

We can now establish the performance guarantee provided by Approx-QSC.

Theorem 26 Algorithm Approx-QSC provides a performance guarantee of O(log n) for the QSC problem, where n is the number of nodes in the underlying graph of the SyDS.

Proof: Let OPT(QSC) denote the size of an optimal query set for the QSC instance and let OPT(MSC) denote the size of an optimal solution to the MSC instance. We observe that the size of the base set X is 2|E| + n. To see this, note that for each node v i ∈ V with degree d i , the the number of elements added to X in Step 1 of the algorithm in Algorithm 2 is d i + 1. Therefore, |X| = n i=1 (d i + 1) = ( n i=1 d i ) + n = 2|E| + n since the sum of all the node degrees is 2|E|. Since |E| < n 2 , |X| < 3n 2 . The greedy algorithm for MSC provides a performance guarantee of O(log |X|), which is O(log n) since |X| < 3n 2 . Thus, the approximation algorithm for MSC produces a solution with at most O(log n) OPT(MSC) sets. By Lemma 24, any solution to MSC with r subsets leads to a solution with r queries for QSC. Thus, the size of the resulting query set is at most O(log n) OPT(MSC) which is equal to O(log n) OPT(QSC) by Observation 25. Thus, Approx-QSC has a performance guarantee of O(log n).

Overview

The theoretical results of the previous sections establish that finding a smallest set of queries to infer the local functions of threshold or symmetric SyDSs is non-trivial. In this section, through extensive experimentationfoot_0 on more than 20 real-world and synthetic networks, we seek to answer the following questions.

1. We study the performance of the proposed algorithms for batch mode. How do the the resulting query sets compare with the lower bounds and thus the optimal query set sizes for these networks? We studied an approach based on coloring G 2 for inferring threshold and symmetric SyDS.

2. While we were able to develop algorithms for batch mode with provable performance guarantees, coming up with a technique for adaptive mode for general graphs turns out to be hard. We propose a greedy heuristic inspired by distance-two coloring to infer thresholds of a SyDS (namely, Algorithm 3 presented in Section 7.4). How does this heuristic perform relative to the developed lower bounds? We experimentally analyze this question.

3. The bounds established above are in terms of maximum degree or the size of the graph. However, many real-world networks are scale-free, having a low average degree, but a very high maximum degree. How do our algorithms perform on these networks? Does network density (number of edges) have any role in determining the query set size?

4. We note that the query set size depends not only on the network structure, but also on threshold assignments. How does the uncertainty in the range of values the threshold can take influence the query set size? Our experiments also study this question.

Networks and threshold assignment. The diverse real-world and synthetic networks considered in this work are listed in Table 1 along with some of their properties. As indicated in that table, all the mined networks used in our experiments are from the SNAP library (Leskovec and Krevl, 2014). We present representative results for selected networks, with other networks exhibiting the same behavior unless stated otherwise. We assigned thresholds in the following manner. Let 0 ≤ θ ≤ 1 be a real number. For a fixed value of θ, each node v was assigned a threshold value uniformly at random from the interval (d(v) + 2)(1θ)/2, (d(v) + 2)(1 + θ)/2 . Note that for θ = 0, the interval corresponds to the fixed threshold of (d(v) + 2)/2 and for θ = 1, any value from 0 to d(v) + 2 is possible.

Our theoretical results indicate that both network structure and the threshold assignments influence the number of queries required to infer the system. The experiments conducted were designed to further explore these aspects. Details regarding the computing environment used for our experiments are presented in Appendix B which also includes plots showing wall clock times for generating queries. We studied the performance of Alg-Monotone-Seq (Algorithm 1). For most real world networks considered in this paper, this algorithm gives the best possible performance of ∆ + 2 (Proposition 3). This is due to the fact that in all these cases, n c (G 2 ), the number of colors used to color G 2 is equal to ∆ + 1, the lower bound on the number of required colors. Compare the values in Table 1 for columns "max. deg. ∆" and "Results: Query set size, Method 1." For synthetic networks (random regular and Erdős-Rény though, n c (G 2 ) is significantly higher than ∆ + 2, yet much lower than ∆ 2 + 2, the upper bound (Theorem 10). The should note that the observed performance is due to a combination of the structure of G 2 and the nature of the greedy coloring scheme. We observe that unlike the synthetic networks considered, most of the real-world networks are scalefree with maximum degree being much larger than average degree d avg . This is a possible reason for the superior performance of this approach. We also compared the results to the spectral radius bound, that is, the number of colors needed to color G 2 is at most 1 + λ 2 max (Miao and Fan, 2014), where λ max is the largest eigenvalue of the adjacency matrix of G.

Again, see Table 1 and "λ max ." It is a well-known fact that √ ∆ ≤ λ max ≤ ∆, and for the real-world networks considered, λ max is indeed much less than ∆. However, despite this fact, we observe that λ 2 max + 1 is much larger than n c (G 2 ) + 1 in these cases.

Compaction. We note that the query set generated by this approach is already compact, i.e., no proper subset of queries can be complete. To see this, suppose this set is not compact. Then, there exists at least one query which is not required. We recall that by construction, the query set can be arranged as a monotone increasing sequence q 0 , q 1 , . . . , such that in query q i all nodes of color i are set to state 1. Suppose query q k is not required for the set to be complete. Then, using the arguments in the proof of Theorem 11, it can be seen that if all vertices of color k were assigned color k + 1, the coloring would still be valid. This means that in the greedy strategy, all nodes colored k + 1 could actually have been assigned color k. Since the greedy strategy always gives the minimum color available to nodes, this is a contradiction.

Experiments on Query Compaction

Here, we present some experimental results obtained by first generating query sets using the probabilistic method discussed in Section 4.2 and then applying the query set compaction heuristic presented in Section 6.3. To generate the complete query sets, we used the method of Theorem 12. Recall that the query set contains the configurations of all zeros, of all ones and ∆ random queries where queries are sampled from distributions D(i/∆) for 1 ≤ i ≤ ∆.

The query set generation process may have to be repeated a number of times to obtain a complete set. The resulting set, even though large, can be compressed using the compaction algorithm.

We constructed 50 such query sets for three values of (2, 5 and 10) and checked whether each of them is a complete set. For = 2, out of the 50 sets constructed, none of them was complete. However, for = 10, from 5 to 50 query sets turned out to be complete sets depending on the network. We applied the compaction algorithm on the complete sets generated by the randomized algorithm. The results for = 10 are in Table 2. The compaction ratio depends on the size of complete set which was given as input. We note that compaction of query sets generated by this method yields around 80% reduction in the size of the query set in most cases (Table 2). On the average, the combination of randomized algorithm and compaction gives query sets of size around 1.5 to 2 times that of the monotone query sequence method discussed in Section 4.1. However, the method of random query set generation followed by compaction is comparatively much easier to implement.

Method 2: An Adaptive Algorithm

While the previous methods are for the batch mode, here we develop an adaptive algorithm to infer the thresholds. We give an outline of the approach. The steps of the algorithm are shown in Algorithm 3. In this algorithm, we use the notation N [v, G 2 ] to denote the set of nodes of v that are at distance of at most 2 in G (including v). We note that N [v, G 2 ] can be computed by a two-step breadth-first search of G starting at v.

For every node, let t L (v) and t H (v) be the minimum and maximum possible values of threshold that v can be assigned. These values quantify the uncertainty about the threshold. The threshold is said to have been inferred when t H (v) = t L (v). In a query q, if score(q, v) falls in the range [t L (v), t H (v)-1], the uncertainty reduces to either [score(q, v)+1, t H (v)-1] or [t L (v), score(q, v)] depending on the state observed in the successor configuration. In this heuristic, we use a greedy adaptive approach where the current query is constructed iteratively in the following way. Initially, all the nodes are in state 0. We first choose a vertex, say v max , for which the threshold range is maximum. We set exactly (t L (v) + t H (v))/2 of nodes in its closed neighborhood to state 1. This guarantees a reduction in the range by half. In the next iteration, we ignore all nodes in G within distance-2 of v max and repeat this process. The query is fully constructed when there are no more vertices to consider. After each query, the range [t L (v), t H (v) -1] for every v is updated based on its state in the Algorithm 3: Greedy heuristic to infer the thresholds.

Data: Network G(V, E); true thresholds t v for every node v. (These thresholds are not available to the inference algorithm; they are used only to compute the successor for a query.) Result: Infer the thresholds of all the nodes of G. (For data analysis purposes, the algorithm also returns the set Q of all the queries used in the inference procedure.)

the set of nodes for which threshold needs to be inferred; 5 Let Q = ∅ be the query set; successor. We terminate this process when for all v, t L (v) = t H (v). Results are summarized in the last column of Table 1. The analysis of our experimental results follows.

Influence of threshold values and ranges. In general, the number of queries required is highly dependent on the possible threshold values the nodes can be assigned. We conducted experiments in the following manner. Recall the threshold assignment procedure described in Section 7.1. The results are in Figures 5(a) and 6(a) for random k-regular and real-world networks respectively. For the random-regular graphs, the number of queries (averaged over 10 instances of graphs for each k) increases from an order of log k to as high as n, the size of the graph. We note that for k = n -1, this is in accordance with Theorem 5. For the real-world graphs, we see that increasing the range of threshold has the effect of gradually increasing the number of queries, but the number is less than 1.5∆. In Figure 5(b), we investigate the influence of the threshold value on query set size. Again, we considered random k-regular graphs with varying k. Every node was assigned the same threshold. We see that the number of queries used is a maximum when the threshold is around ∆/2, and it decreases as the threshold approaches either 0 or ∆.

Influence of network structure. The theoretical results developed in the previous sections provide bounds with respect to size of the graph and maximum degree. Here, our objectives are two-fold. Firstly, we compare our adaptive approaches to the non-adaptive bounds, particularly the number of queries required relative to ∆. Secondly, we investigate the effect of graph density and degree distribution on the performance of the heuristic. We note that graph density plays an important role in the performance of the algorithm. First, we consider synthetic networks. In Figure 5(b), we see that for low values of k the number of queries required is very small, but it increases rapidly (for higher values of thresholds). When the graph is sparse, for every node, the number of nodes within distance two (i.e., k 2 + 1) is small. Therefore, for every query constructed by the heuristic, the uncertainty range of around n/k 2 nodes (the "v max " vertices) is halved. However, as k increases, this number decreases drastically. Hence we see that the number of queries used increases. However, as the graph density increases, the intersection of neighborhoods of any two nodes is large which has the effect of reducing the variation in the scores of nodes. Therefore, particularly when the range of threshold values is limited, the thresholds can be inferred with fewer queries than for sparser networks.

Progress towards inferring thresholds. In Figure 6(b), we plot the accumulated threshold ranges for all vertices as the algorithm moves from one query to the next. We note that for most of the networks considered, within one-tenth of the total query size, the total accumulated threshold range decreases to 5% of its original value for all the studied networks. Thus, the uncertainty in the threshold range can be decreased significantly using a small number of adaptive queries.

In Appendix B, we have provided plots (Figure 7) for the wall clock time taken by Method 2 to generate queries.

Directions for Future Work

In this work, we studied the problem of inferring the behavior of a networked dynamical system through active querying. We now discuss several avenues for future work. We first mention an open problem that arises directly from our results. Theorem 13 shows the existence of a small complete query set for SyDSs with symmetric functions. Developing an efficient algorithm that can construct such a query set is an interesting research question.

In our framework, the user has complete knowledge of the network, and queries and the responses from the system are assumed to specify the states of all the nodes in the system. In a typical real-world scenario, only partial knowledge of the system is available. Besides, the user might only require partial information from the system. For example, it may be sufficient for a user to know whether the threshold of every node is at most some chosen integer α. Methods that can accomplish threshold inference with a small number of queries in such contexts are of practical interest. Another useful direction to explore is to develop inference methods when the system response consists of successors for k ≥ 2 time steps (instead of a single time step). It is also of interest to explore the use of queries to infer other components of a dynamical system (e.g., the network topology).

where the inequality in the second of the three lines above follows from Lemma 27 (below). Now, Pr f v (b) is not queried by Q ≤ Pr f v (b) is not queried by q zj , 1 ≤ j ≤ 22 √ ∆ + 2 log(n∆) .

The quantity on the right hand side of the above inequality is at most 1 -

< 1 (n∆) 2 .