Algorithms and Hardness for Active Learning on Graphs

Yes

Yes. The proofs seem fine.

No.

The key contribution of this paper is a new algorithm for the graph label selection problem (itself related to active learning on graphs) for arbitrary underlying graphs with $O(\log(|V|))$ slack. Previously algorithms (with slack) were only known for trees, with heuristic methods suggested for general graphs. The authors also prove the first NP-hardness result for GLS with no slack, though this aspect is not particularly surprising given typical hardness of such graph-based combinatorial problems.

Not to my knowledge.

Yes.

Yes. I checked all the theorems and lemmas to the best of my ability. The theoretical results are the bulk of the contribution.

There seem to be typos / inconsistencies in Section 6 and Lemma 6.1. This whole section seems somewhat carelessly written compared to the rest of the paper. In particular, halfway through the proof of Lemma 6.1, the authors switch from talking about $\Delta$-regular graphs to the specific case of $\Delta=3$.

Yes. I read through the description of the datasets and the metrics. No issues identified.

The key contributions of the paper are clearly novel and provide new insights on the hardness of GLS. Since GLS is a simplified version of the active learning task, the paper contributes theoretical results on the hardness of active learning. This is one core task in machine learning / data science.

No.

The proposed methodology leverages a reduction of the graph label selection problem to a flow-based formulation inspired by the densest subgraph problem. The authors introduce a flow gadget, where labeling vertices translates into adding edges to increase the max-flow, enabling a greedy selection process. Though the original objective $\Psi(L)$ is neither submodular nor supermodular, the derived surrogate measure (flow increase) is submodular, allowing established submodular optimization guarantees. They complement this with a binary search approach to efficiently pinpoint feasible threshold values. Technical assumptions (like polynomially bounded edge weights) are clearly stated and justified, with full details provided in appendices.

The evaluation methods—worst-case approximation analysis and empirical $\Psi(L)$ values—are appropriate for the theoretical nature of the paper. Empirically, the authors demonstrate improvements over baseline methods through controlled experiments on both synthetic and real-world graphs. While the evaluation does not directly address prediction accuracy, the chosen proxy ($\Psi(L)$) suitably reflects the intended smoothness goal. Overall, the methods and evaluation criteria are thoughtfully designed, effectively validating the proposed approach.

The theoretical claims are significant and appear correct based on the provided material. The main results include:

• Approximation Algorithm (Theorem 1.1): By allowing a factor-$O(\log n)$ more labels than the budget $k$, the algorithm achieves an objective equal to the optimal solution for exactly $k$ labels. The authors provide a plausible proof sketch (detailed proofs in Appendix B), relying on standard submodularity and flow techniques. The assumptions (e.g., polynomially bounded integral weights) are clearly stated and reasonable.

• Hardness Result (Theorem 1.2): The authors show it is NP-hard to distinguish between cases where the optimal value is at most 2 or at least 3, implying constant-factor hardness of approximation. This reduction from known NP-hard problems on 3-regular graphs seems correct and convincing, clearly establishing the problem’s theoretical difficulty.

• Generalization to Weighted Vertex Importance: The paper extends the approximation results to scenarios with vertex importance weights, offering a generalization that appears logically sound and consistent, though I did not verify proofs exhaustively.

Overall, the theoretical contributions are rigorous, clearly presented, and supported by well-known techniques. While the runtime complexity ($(|V|+|E|)^{1+o(1)}$ per iteration) is slightly super-linear and somewhat limits practical scalability, it does not undermine the theoretical validity of the results presented.

The proposed method uses a flow-based formulation inspired by the densest subgraph problem, constructing a flow gadget to guide greedy vertex selection. Although the original label selection objective ($\Psi(L)$) is neither submodular nor supermodular, the authors identify a submodular surrogate measure (flow increase), enabling standard greedy approximation techniques. They combine this with binary search for threshold estimation, clearly outlining assumptions and deferring details to appendices.

The evaluation methodology (theoretical approximation ratio, empirical objective values) is suitable for the paper's goals. Empirical results on synthetic corner-case graphs and two real-world graphs from SNAP consistently demonstrate better performance over baseline methods (Guillory & Bilmes, 2009; Cesa-Bianchi et al., 2010). A notable limitation is the relatively small scale of experiments (max ~4k nodes), acknowledged by authors due to computational complexity. Nonetheless, the experiments convincingly support the claims within the tested scope. Reproducibility is reasonably addressed through clear descriptions and standard datasets, though explicit code release is not mentioned.

Guillory & Bilmes, 2009: Label selection on graphs. Cesa-Bianchi et al., 2010: Active learning on trees and graphs.

The paper positions itself clearly within existing literature, referencing both foundational works and recent advancements in relevant fields, specifically:

• Graph-based Semi-supervised Learning: (Blum & Chawla, 2001; Zhu et al., 2003; Belkin et al., 2004; Bengio et al., 2006).
• Active Learning on Graphs: (Guillory & Bilmes, 2009; Cesa-Bianchi et al., 2010; Dasarathy et al., 2015)
• General and Deep Active Learning: (Settles, 2009; Ren et al., 2021; Mac Aodha et al., 2014; Kushnir & Venturi, 2020)
• Algorithmic Graph Theory (densest subgraph): (Goldberg, 1984; Boob et al., 2020; Chekuri et al., 2022)

Overall, the paper effectively builds upon previous theoretical frameworks (e.g., Guillory & Bilmes, 2009; Cesa-Bianchi et al., 2010) and clearly outlines how it extends prior limitations, such as handling general graphs rather than special cases (trees). While the paper does not deeply explore sequential active learning, this omission is justified given its scope.

Standard Citations:

• Blum, A., & Chawla, S. (2001). Learning from labeled and unlabeled data using graph mincuts. ICML.
• Zhu, X., Ghahramani, Z., & Lafferty, J. (2003). Semi-supervised learning using Gaussian fields and harmonic functions. ICML.
• Belkin, M., Matveeva, I., & Niyogi, P. (2004). Regularization and semi-supervised learning on large graphs. COLT.
• Guillory, A., & Bilmes, J. A. (2009). Label selection on graphs. NeurIPS.
• Cesa-Bianchi, N., Gentile, C., Vitale, F., & Zappella, G. (2010). Active learning on trees and graphs. COLT.
• Dasarathy, G., Nowak, R., & Zhu, X. (2015). S2: An efficient graph-based active learning algorithm. COLT.
• Settles, B. (2009). Active learning literature survey. University of Wisconsin-Madison.
• Ren, P., et al. (2021). A survey of deep active learning. ACM Computing Surveys.
• Mac Aodha, O., Campbell, N. D., Kautz, J., & Brostow, G. J. (2014). Hierarchical subquery evaluation for active learning on a graph. CVPR.
• Kushnir, D., & Venturi, L. (2020). Diffusion-based deep active learning. arXiv preprint arXiv:2003.10339.
• Goldberg, A. V. (1984). Finding a maximum density subgraph. Technical report, UC Berkeley.
• Boob, D., et al. (2020). Flowless: Extracting densest subgraphs without flow computations. WWW.

Overall, the literature review is thorough and clearly situates the paper’s contribution within the broader field.

No essential references appear missing. Literature coverage seems thorough, and relevant works are adequately cited.