Response to AC's comments
We appreciate AC's insightful theoretical questions! The point-by-point responses are as follows:
**Q1** Denote the eigenvalue distribution $F(\omega)= \frac{1}{n}\sum_{i=1}^n\mathbf{1}(\lambda_i \leq \omega) $ and the eigenvector space $\mathbf{U_d} = \text{Span}(U_1,\cdots,U_d)$, where ${(\lambda_i)}_{i=1}^{n}$, and ${(U_i)}$ are eigenvalues and $d$-leading eigenvectors of the normalized graph laplacian. Assuming the frequency of $\mathbf{f}$ is lower than $\omega_0$,
we have $\mathbf{f}\in \mathbf{U}_d$ with $d = \lceil nF(\omega_0) \rceil$. Wlog, we assume $r_d = d$ in Theorem 3, i.e, $\mathbf{f}$ has component on each $U_i,i=1,\cdots,d$. With MSE $\frac{1}{n}\mathbf{E}\| \hat{\mathbf{f}} - \mathbf{f}\|_2^2$ fixed, the label complexity of our method is $O(d)$, while that of passive learning is $O(\tilde{d}\log \tilde{d})$ [1] with $\tilde{d} = \lceil nF\big(\frac{n}{\mathcal{B}}F^{-1}(\frac{d}{n})\big)\rceil$ where $\mathcal{B}<n$ is the number of query. Notice that $\tilde{d}>d$ due to the monotonicity of $F(\cdot)$ and $\tilde{d} \rightarrow d$ as $\mathcal{B}$ increases. Our method improves in two aspects: (1) the information selection identifies $\mathbf{f}$ via $O(d)$ queries, and passive learning uses $O(\tilde{d})$ queries, though this improvement decreases as $\mathcal{B}$ increases. (2) Our method improves by a log factor compared to passive learning via actively controlling the condition number of the covariate matrix, therefore the estimation variance.
**Q2** In the real world, data labels aren’t always accurate/reliable. In this paper, we introduce label noise via a probabilistic model $Y_i = \mathbf{f}(i) + \epsilon_i$, where $Y_i$ and $\mathbf{f}(i)$ are the queried and true label on the $i$th node, and $(\epsilon_i)_{i=1}^n$ are independent errors satisfying $\mathbf{E}(\epsilon_i) = 0$ and $\mathbf{Var}(\epsilon_i) = \sigma^2$. Our noise model generalizes to different label types in applications. For continuous labels $Y_i$, one can set $\epsilon_i \sim \text{Normal}(0,\sigma^2)$. For binary label with $\mathbf{f}(i) = -1 \ \text{or} 1$, the typical noise model is $ Y_i = \mathbf{f}(i)$ with prob. $p>0.5$ and $ Y_i = - \mathbf{f}(i)$ with $1-p$. The binary noise model can be reparameterized via our noise model as $Y_i = \text{sign}(Y^*_i)$ where $Y^*_i = \mathbf{f}(i) + \epsilon_i$. The binary $\epsilon_i = 2\mathbf{f}(i)(1-p)$ with prob. $p$ and $\epsilon_i = -2\mathbf{f}(i)p$ with $1- p$, and $\mathbf{E}(\epsilon_i) = 0$ and $\mathbf{Var}(\epsilon_i) = 4p(1-p)$. Similarly, our noise model also accommodates multi-class labels via one-vs-other reparameterization. While most literature consider noise level $\sigma^2$ as constant, our method theoretically guarantees recovery as long as noise level $\sigma^2 = O(\mathcal{B}^\eta)$ with $\eta<1$. This result is useful when human labelling errors increase with workload. Additionally, our node selection strategy is invulnerable to label noise due to the offline nature, and our graph function space alleviates high-frequency noise in node features $\mathbf{X}$ due to network smoothing.
**Q3** For a random graph $G(n,p)$, one has both lower and upper bounds on the node degree with high probability. Specifically, with probability greater than $1 - \exp\big(-np(c-1)^2\big)$, the maximum node degree $d_{max} \leq cnp$ with constant $c>1$. Given $np \rightarrow \infty$, the difference in information gain between the proposed method and random sampling can be simplified as
$$ \mathbf{E}(\Delta) - \mathbf{E}(\Delta_R) > O(\frac{1}{ c^3 p^2 n^2}) -\frac{1}{n},$$
with probability larger than $1 - \exp\big(-np(c-1)^2\big)$. Therefore, the proposed method achieves larger information gain under the network sparsity regime $p = O(n^{-1/2}$), covering a broad range of real networks.
**Q4** Following the same definition as in Q1, and assuming that the frequency of $\mathbf{f}$ is lower than $\omega$, the generalization error in Theorem 3 is
$$ \frac{1}{n}\mathbf{E}\| \hat{\mathbf{f}} - \mathbf{f}\|_2^2 \leq O\Big(\frac{\text{rank}(\mathbf{U}_d^T\mathbf{X})}{\mathcal{B}}\Big),$$
where $d = nF(\omega)$, $\mathcal{B}$ is the number of queries, and $\mathbf{X}$ is node covariate matrix. With a fixed complexity of $\mathbf{f}$, the MSE decays at a rate of $\frac{1}{\mathcal{B}}$. The network topology affects the convergence rate through both the size of eigenvector space ($d$) and the alignment between two column spaces ($\mathbf{U}_d^T\mathbf{X}$). For illustration, we can obtain a looser bound as $O\Big(\frac{nF(\omega)}{\mathcal{B}}\Big)$. For random graph, the eigenvalue distribution of graph laplacian $F(\omega;n,p)$ can be analytically represented as the convolution of the standard normal distribution and the Wigner’s semi-circular distribution [2].
[1] Randomized algorithms for matrices and data. Found. and Trend. in Mach. Learn. (2011)\
[2] Spectral distributions of adjacency and Laplacian matrices of random graphs. Ann. of App. Prob. (2010)