Real-world phenomena are often partially observed. This partial observability leads to incomplete data. Acquiring more data is often expensive, hard, or impossible. We present a feasibility study on the limits of online learning to reduce incompleteness in network data. In particular, we investigate the following problem: given a network and limited resources to collect more data (i.e., a budget), can an optimal strategy be learned for reducing the network's in-completeness? Reducing the incompleteness of a network can be interpreted in different ways. For example, it could mean: observe as many previously unobserved nodes as possible, or observe as many new nodes with a certain property, or observe as many new nodes and triangles, etc. Here, we focus on the first interpretation-i.e., we use the given budget to increase the number of nodes in the incomplete graph. Using one unit of the budget means querying an oracle that has access to the fully observed network and getting back full information about a single node's neighbors (at the time of query). We refer to this process as probing a node. Examples of probing nodes include using APIs to get information about an account, placing monitors on routers to get information about Inter-net traffic flow, etc. We make no assumptions about the underlying model generating the network data or how the incomplete network was observed. Our findings on synthetic and real-world networks showcase when learning is feasible, when it is not and when one should just use a heuristic (i.e., when learning is unnecessary or redundant).