We consider the problem of inferring the structure of a network from co-occurrence data: observations that indicate which nodes occur in a signaling pathway but do not directly reveal node order within the pathway.  This problem is motivated by network inference problems 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 networked systems suggest that not all feasible solutions are equally likely.  Previous approaches treat network inference as the problem of learning the structure of a graphical model, capturing influence relationships between nodes.  In contrast, our approach explicitly models the causal nature of signaling.  Intuitively, 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 importance sampling estimators, prove that a polynomial complexity Monte Carlo version of the algorithm converges with high probability.