Network　latency　is　an　important　metric　for　network　performance　evaluation.　However,　device　faults　inevitably　occur　during　the　data　collection　process,　resulting　in　abnormal　data　or　even　missing　data.　It　is　desirable　to　accurately　estimate　the　network　latencies　and　detect　the　abnormal　data.　Existing　approaches　can　not　provide　reliable　performance　due　to　the　limitation　in　exploiting　the　spatial-temporal　correlations　of　latency　data.　In　this　paper,　we　propose　a　novel　Robust　Spatial-Temporal　Graph-Tensor　Recovery　(RSTGTR)　algorithm　which　simultaneously　recovers　the　missing　data　and　detects　the　anomalies　in　network　latencies.　Firstly,　we　model　the　network　latency　data　as　a　novel　graph-tensor　for　exploring　the　topological　structure　of　networks.　Secondly,　we　develop　spatial-temporal　constraints　and　propose　a　graph-tensor　recovery　algorithm　(RSTGTR).　Finally,　we　conduct　extensive　experiments　to　evaluate　the　performance　of　the　proposed　algorithm　by　using　a　real-world　latency　dataset.　Experimental　results　show　the　proposed　algorithm　outperforms　existing　methods　in　terms　of　latency　estimation　and　anomaly　detection.　©　2022　IEEE.