Following the definition by Kamarthi et al. [1]}, an induced subgraph \(G_0\)  is assumed to be observable at a very early stage. When \(G_0\)  is not initially available, such a subgraph can be obtained by querying a few nodes at random. To retrieve additional structural information from the underlying network \(G\) , we are allowed to perform \(T\)  node queries. Specifically, when we query a single node, we are capable of discovering neighbors of the queried node. The observable subgraph can then be expanded accordingly, which essentially follows the same setting as prior work in the field [2]}, [1]}, [4]}. \(G_t = (\mathcal {V}_t, \mathcal {E}_t)\)  is the subgraph discovered after \(t\)  queries, where \(\mathcal {V}_t\)  and \(\mathcal {E}_t\)  are the set of nodes and the set of edges, respectively, in the subgraph \(G_t\) . During the \((t+1)\) -th node query, we choose a node \(v_t\)  from \(G_t\) , which enables us to observe an expanded graph \(G_{t+1} = (\mathcal {V}_t \cup \mathcal {N}_G(v_t), \mathcal {E}_t \cup \mathcal {E}(\mathcal {N}_G(v_t), {v_t}))\) , where \(\mathcal {N}_G(v_t)\)  indicates a set of neighbors of node \(v_t\)  in \(G\)  and \(\mathcal {E}(\mathcal {N}_G(v_t),v_t)\)  is a set of all edges to which each node in \(\mathcal {N}_G(v_t)\)  and node \(v_t\)  are incident. An example of this query process is illustrated in Fig. REF , where an initially induced subgraph \(G_0\)  consists of two nodes \(v_1\)  and \(v_2\) , and we observe another graph \(G_1\)  consisting of four nodes (i.e., \(v_1\) , \(v_2\) , \(v_3\) , and \(v_5\) ) after querying node \(v_2\) . The finally discovered subgraph \(G_T = (\mathcal {V}_T, \mathcal {E}_T)\)  is used as input of the IM process, where a set of seed nodes (i.e., a subset of observable nodes) of size \(k\) , \(S\subseteq \mathcal {V}_T\) , is chosen to diffuse the influence.Due to the limited availability of the network structure, it is typical to select seed nodes only among the retrieved nodes. We refer to [2]}, [1]}, [7]} for more details.
