In this paper, we posit how semi-static (i.e., not changing very often) complex computer network-based intelligence using graphbased analytics can become enablers of Cyber Situational Awareness (CSA) (i.e., perception, comprehension, and projection of situations in a cyber environment). A plethora of newly surfaced cyber security researchers have used graph-based analytics to facilitate particular down tasks in dynamic complex cyber environments. This includes graph-, node- and edge-level detection, classification, and others (e.g., credit card fraudulent transactions as an edge classification problem). To the best of our knowledge, very limited efforts have consolidated the outputs of heterogeneous computer network monitoring and reconnaissance tools (e.g., Nmap) in enabling actionable CSA. As such, in this work, we address this literature gap while describing several use cases of graph traversal, graph measures, and subgraph mining in vulnerability and security state assessment, attack projection and mitigation, and device criticality estimation. We highlight the benefits of the graph-based approaches compared to traditional methods. Finally, we postulate open research and application challenges in graph-based analytics for CSA to prompt promising research directions and operational capabilities.