Network attack graphs are widely used as templates to extrapolate network security state by analyzing observed intrusion evidence. Existing attack graph node belief computation methods are suffering from generality problems, high computational complexity, or the overuse of empirical formulas to solve problems. This paper improves one of the Bayesian network inference algorithms—the likelihood weighting algorithm into a novel graph node belief computation algorithm, which supports the temporal partial ordering relationship among intrusion evidences. Experiment results show that the method can achieve high computation accuracy in linear computational complexity, a feature making it feasible to be used to process large scale attack graphs in real-time.