We consider the problem of inferring the structure of a network from co- occurrence data: observations that indicate which nodes occur in a signaling path- way but do not directly reveal node order within the pathway. This problem is motivated by network inference problems arising in computational biology and communication systems, in which it is difficult or impossible to obtain precise time ordering information. Without order information, every permutation of the activated nodes leads to a different feasible solution, resulting in combinatorial explosion of the feasible set. However, physical principles underlying most net- worked systems suggest that not all feasible solutions are equally likely. Intu- itively, nodes that co-occur more frequently are probably more closely connected. Building on this intuition, we model path co-occurrences as randomly shuffled samples of a random walk on the network. We derive a computationally efficient network inference algorithm and, via novel concentration inequalities for impor- tance sampling estimators, prove that a polynomial complexity Monte Carlo ver- sion of the algorithm converges with high probability.