Graph-based visual analysis for large-scale hydrological modeling

Related work

In recent years, a number of hydrological web-based visualization service-oriented applications have been developed that use site-specific study sites for sharing data. As one example, the Iowa Flood Information System provides access to flood inundation maps with real-time flood conditions and flood forecasts for gauges and sensors throughout the state of Iowa, USA, using web services and distributed services for data, map, analysis, and visualization.^13,14 Another service includes HydroShare, with similar goals to share hydrological data and models.^15,16

For a general overview of graph visualization techniques and research challenges, we refer to von Landesberger et al. ¹⁷ and Herman et al. ¹⁸ There exist several studies with large graph scales of social and Internet networks with relational datasets using simplification, matrices, and clustering visualization techniques.^19–21 Although the NHD data products we use contain relational datasets, graph layout and simplifications were not explored here; our goal is to retain details to inform the user in situ for decision making about edge connections. Instead, our research here focuses on designing a visual interface to reveal layers of large amounts of data with navigate, view, and filtering manipulation techniques, inspired by Kandel, Heer, and Shneiderman to handle data wrangling for large graphs in hydrology.^22–26 Some of the key wrangling steps taken here include the following: (1) integrating visualization in the iterative process of diagnosing graph connection problems, (2) determining how to scale large hydrology data, (3) correcting erroneous values with constraints and automation, and (4) capturing editing and data provenance using graph workflows.

Method to create a CONUS graph using HUCs

NHD data structures provide an implied graph by specifying a target HUC from a source HUC, or a directed connection. Unfortunately, within the NHD graph, there are instances when targets do not exist, and thousands of connections are not touching neighbors. ²⁸ Additionally, the NHD data structures imply only one connection when level-12 HUCs have multiple connections with adjacent HUCs. Hence, we needed to create a derived CONUS graph using NHD to resolve these problems.

The method to create a graph using CONUS level-12 HUCs with NHD geodatabases started by developing a dictionary containing unique level-12 HUC keys. ²⁸ By treating each HUC geometry as a node, 83,016 keys were identified. Checking the target keys identified by NHD, it was discovered that 38 unique keys did not exist and were used by a total of 221 HUC-12s. ²⁸ With a relatively low number of level-12 HUCs, it appeared that manual intervention was feasible. However, by creating a list of neighboring HUCs for each HUC, it was discovered that 1940 HUCs had target keys that did not touch the source. ²⁸ Using our strategy not only includes multiple neighboring targets (edges), but HUCs called closed basins were also selected. Closed basins are watersheds that do not have surface streams that connect to another watershed but are needed for groundwater and lake modeling.

To determine edges and directions between level-12 HUC nodes, the intersection of each stream with HUC boundaries was calculated. Each point was then buffered (a polygon enclosing the intersection point) at 15-, 45-, 60-, 75-, and 90-m intervals, creating more points along the stream geometry. Using the National Elevation Dataset (NED) which has a 30-m resolution, elevation values were assigned to these points with the goal to determine high- and low-elevation values. This technique was not effective due to inadequate elevation resolution, short stream reaches, lack of smooth stream reaches, and/or watershed boundaries, and the large number of flat-sloped areas at these intersections.

Instead, the chosen solution was to live with dirty data by assuming that the digitized direction is from down- to upstream and then identify edges that require direction corrections. These corrections were identified by creating upstream depth-first search (DFS) graphs at all major river outlets (root nodes) and identifying holes within the generated polygons. The DFS-generated polygons were then automatically compared with well-known large-watershed boundary polygons for verification. See Leonard and Duffy ²⁸ for further details and here we demonstrate our DFS graph process with the Juniata watershed shown in Figure 1.

OPEN IN VIEWER

Figure 1.

(a) By selecting the root HUC-12 node (asterisk), using DFS or BFS algorithms, 97 HUC-12s are selected that form the Juniata watershed. The green circles mark the locations where edges connect to adjacent HUC-12s (watershed outlets) and (b) the insert shows the streams (light blue) and the numbers denote graph distance from root node.

Why corrections require expert intervention

The above approach to create upstream graphs is successful for major river basins without restriction on graph size, as we can identify holes within watershed polygons. However, our goal is to use the graph to create dynamic graph sizes anywhere in the CONUS where we cannot rely on holes to determine missing HUCs. For example, we have access to a 64-node HPC cluster and we want to restrict the graph to 64 level-12 HUCs at a time, with 64 being considered changing as we follow the path of a major storm. From experiments conducted with the Juniata watershed (Figure 1), it became apparent that our assumption that the digitized direction (down- to upstream) was not sufficient and required too many expert edits.

The most common reasons for expert intervention at the level-12 HUC scale included conflicting edge directions, edges that pass back and forth along HUC boundaries, and edges within flat-sloped elevations as summarized in Figure 2(a). The number of corrections was in the thousands at the CONUS scale by treating each HUC as a node and focusing at the connection locations only. The next logical progression is to search beyond the intersection locations and buffered intersections, by following the entire length of the stream in both directions to determine the correct flow direction.

OPEN IN VIEWER

Figure 2.

(a) Examples of edge direction issues, (b) streams within same elevation values, and (c) Juniata edge directions.

To search from the intersection requires a corrected stream network at the CONUS scale. There are 29,560,501 named NHD v2.1 ⁶ stream objects in the CONUS, but when every edge is split into individual segments with existing digitized vertices, there are 851,265,305 edges and 683,298,991 nodes. Table 3 summarizes graph sizes with various scale watersheds within the CONUS. This shows that there are hundreds of thousands of the same issues as are summarized for one example in Figure 2(a). Additional issues found include streams that are disconnected (that happen in karst environments characterized by underground drainage with sinkholes and caves) and streams interconnected with human-made canals that change natural flow directions. Many of these issues require expert intervention as there is a lack of elevation detail that would be required to make corrections automatically.

OPEN IN VIEWER

Table 3.

Graph sizes for various watershed scales.

US watersheds (spatial scale)	Number of HUC-12s	Number of streams	Unique edges	Unique nodes
Juniata	97	15,255	310,940	310,616
Susquehanna	1038	151,605	4,993,721	3,513,452
Chesapeake	6305	751,910	16,740,974	9,644,155
Mississippi	40,425	12,950,292	309,308,615	446,693,961
CONUS	83,016	33,338,895	851,265,305	683,298,991

HUC: hydrological unit code; CONUS: continental United States; NHD: National Hydrography Dataset.

The number of edges is NHD ⁶ streams, while unique edges and nodes are these same streams split by digitized vertices.

The NED resolution is 30 m, which is not sufficient to automatically correct and verify flow directions. The gridded lines in Figure 2 indicate the elevation value for the entire rectangle. Clearly, when so many stream vertices share the same elevation value, determining direction is problematic, especially when there are multiple streams in the same region with conflicting directions (Figure 2(b)). The reader may suggest to determine directions for connecting edges by searching further than the intersection location and use the result to judge the likelihood direction. Unfortunately, as described earlier, there are hundreds of thousands of issues with the stream networks. Instead, we propose a two-tier solution by having expert intervention at the HUC intersections first, followed by validating stream networks within each HUC to create a valid graph.

Visual analytic objectives

Since resolution of available elevation data does not support full automation to address issues with stream networks, we propose a visual analytics approach that leverages expert knowledge. We illustrate the approach for the Juniata watershed. Figure 2(c) illustrates the 15,255 streams or 310,940 edge segments within the Juniata watershed (Table 3). The arrowheads indicate the direction of each edge. Clearly, by visual inspection, determining which edge directions are correct or not is a time-consuming and tedious task, even with a relatively small watershed size. Following the visual analytics mantra, ²⁹ we propose that our visual analytics tools do the following to create and validate large graphs for hydrological modeling using national datasets:

As we demonstrate in the next section, visual analytics is critical to direct users efficiently to specific locations for validation and iterate over large graphs using heterogeneous CONUS national datasets.

HydroTerre workflow overview

HydroTerre workflows are initiated via the web application by selecting a level-12 HUC. HydroTerre consists of four workflows forming an end-to-end workflow system for hydrological modeling (Figure 3(a)) in a distributed computing environment.^3,4 First is the ETV data workflow, responsible for selecting, projecting, clipping, and extracting data within the level-12 HUC watershed. ¹ A typical level-12 HUC data bundle contains standard GIS datasets and typically takes about 2 min to create.^1,27

OPEN IN VIEWER

Figure 3.

(a) The HydroTerre end-to-end workflows, (b) the graph workflow, (c) automated large graph data generation process using national data products, (d) large graph corrections with user-defined actions, and (e) automated analysis of the graphs to identify issues that require expert intervention and populates user interface controls.

The ETV data workflow operates as an independent service using file formats common for many models. Conversely, the data-model workflow is dependent and employs the ETV workflow service as data inputs. Four parameters control the watershed level-12 HUC boundary and stream topology that in turn controls unstructured mesh details for hydrological modeling. ² The data-model workflow assigns land-use, initial conditions, and other parameters using the national datasets as a priori values.

The PIHM-model workflow consumes the data-model workflow as data inputs. Using the web application, calibration, initialization, and HPC model parameters are controlled by the expert user. Default values are automatically assigned using data-mining strategies from the previous workflow results. The ETV, data-model, and model workflows have been executed millions of times to investigate the main reasons for failure within the national datasets, or within the models.^2,3

The last HydroTerre workflow is the visualization workflow to encourage iterative and investigative processes by the expert user to rapidly change data-model and model parameters. ⁴ The visualization workflow consumes the data, data-model, and model workflow services as data inputs. This workflow provides maps and data visualizations that allow the expert user to drill-down, interrogate model results, and rapidly test and re-submit hydrological models for further analysis.

Graph workflow overview

The end-to-end workflow described earlier considers an individual level-12 HUC at each phase. The purpose of the graph workflow is to provide the ability to create a dynamic number of level-12 HUCs from a root node. For example, an expert user is interested in following a storm path or the path of a major river basin near a particular town (root node). The other purpose is to provide analysis of the graph networks within these level-12 HUCs and identify issues, with inconsistent edge directions the most common issue.

In practice, we would expect flow direction to be consistent in one direction, from higher (mountains) to lower elevations (oceans). For models such as PIHM, when edge directions meet, the model solvers will either not converge or be inefficient causing simulations to be slower. Based on the analysis of executing workflows, 1.5 million times with CONUS level-12 HUCs, data-model workflows (responsible for transforming ETV data to PIHM inputs) failed 26.91% of the times due to poor graphs.^2,3 The stream graph is essential for generating PIHM meshes and incorrect graphs account for 70.66% of model workflow failures.^2,3

HydroTerre, PIHM, and other hydrological models require verified graphs at both level-12 HUC node and edge scales. However, every model and expert user has different requirements and strategies to analyze these graphs. Therefore, the graph workflow has been designed to be loosely coupled to accommodate these strategies, rather than directly incorporate them into the data workflow (Figure 3(a)). First, we explain the automated steps to create and analyze large graphs for hydrological modeling.

Graph workflow automated steps

Figure 3(b) summarizes the main components of the graph workflow and how it is incorporated into the HydroTerre end-to-end workflow system. From the web application, once the user initiates the workflow, a new job record is created in the database storing the graph workflow properties as summarized in Table 4. This object is used for provenance and reproducibility by storing all workflow parameters selected by the user and those that are automatically generated by the graph workflow for the user interface. The workflows are executed in a distributed compute environment; therefore, this job record is used to serialize and de-serialize properties for both the graph workflow and the web application interface.

OPEN IN VIEWER

Table 4.

The graph workflow job object stored when user execute workflows.

Column name	Type	Description	Column name	Type	Description
JobID	nvarchar	Project GUID key	Email address	nvarchar	User email address
JobSubmit	datetime	Start time	Root_HUC	nvarchar	USGS HUC ID
JobFinished	datetime	Finished time	Folder_ID	nvarchar	Results location
Status_GWF	int	GUI status	Graph_Properties	XML	Graph XML object
Fixes_Used	int	Track number of fixes	User_Graph_Changes	XML	Action list of changes requested by user
Revisions	int	Track all revisions	Fix_Graph_Properties	XML	Fixes implemented by workflow XML object
Stream_Revision	int	Track stream revisions	User_Properties	XML	User XML object
HUC_Revision	int	Track HUC revisions	Data_Properties	XML	Data XML object

HUC: hydrological unit code; SQL: Structured Query Language.

The email, name, HUC, and date objects enable SQL queries for filtering and identifying jobs. The Graph_Properties object stores the revised graph generated with user changes. The User_Graph_Changes object stores the list of requested changes by the user with specific actions. The Fix_Graph_Properties stores the results from the workflow. Data_Properties stores provenance workflow data.

Within the graph workflow, there are two main steps: data preparation and data analysis. Data preparation is partitioned into two sections based on the revision of the graph workflow. When a user defines the graph properties (described in section “Interface for graph visual analytics workflow”) for the first time, the components in Figure 3(c) are executed. Briefly, these create a level-12 HUC graph, followed by clipping elevation, stream, and aerial datasets. The NHD stream networks are then divided into edges and nodes, followed by finding the geolocation of the intersections between HUCs and the graph edges. Statistics and metadata about each of the data products generated are created for populating user interface controls and data detail on demand. These metadata are stored in the graph job record in the HydroTerre databases.

The second partition (Figure 3(d)) of data preparation implements the user-defined actions (described in section “User actions to correct graphs”) to correct graphs and stream networks based on a previous graph version. Using the web application, the user creates a list of actions he or she wants to perform (described in section “Interface for graph visual analytics workflow”) either with the level-12 HUC connections or with the stream networks. To improve performance, most of the data preparation done in the first partition is not re-executed when not affected by any corrections to graph edges.

The second step is data analysis (Figure 3(e)), which happens after each data preparation component. This step identifies actions required by the user to address their modeling requirements. The main components are finding flat-sloped edges within level-12 HUCs, flat edges at HUC outlets, and edges with conflicting directions and root nodes (outlets). The last component of this step is to collate these automated data analyses into the User_Graph_Changes object (Table 4) to populate user controls within the web application.

After the second step, a new versioned map visualization is generated for the user to analyze the impact of their requested changes. Briefly, the GIS and map visualization step prepares data symbology and creates a map service using ESRI ArcGIS Server software development kits. ³⁰ What this map step does is explained in further detail within the interface design section “Interface for graph visual analytics workflow.” First, we explain what the user actions are to correct graphs, as the design and symbology used in maps are dependent on the results of user actions.

User actions to correct graphs

The previous section describes the automated analysis of level-12 HUCs and stream networks based on user parameters to create a large graph. One of the data products generated is an issue list that populates the interface to inform the user of possible changes required for the large graph. The user is required to specify an action for each issue identified by the automated analysis. These methods have been broken into five common actions:

As discussed previously, the user will need to verify the large graphs at two scales: the first scale is at the level-12 HUC, followed by the stream networks within each HUC. At the level-12 HUC scale, the expert user is required to validate HUCs with flat-sloped outlets. The direction of these edges requires confirmation; otherwise, the user will need to decide direction from the above actions. To validate stream networks within each HUC, we have identified the following problem types during the automated graph workflow (Figure 3(e)) that require intervention by the user via the visual interface.

The above actions are automatically serialized and stored in databases for provenance and reproducibility within the User_Graph_Changes XML object (Table 4). How users generate these actions to address issues with graph workflows and user interfaces are discussed next.

Interface for graph visual analytics workflow

There are two main steps for the user to analyze large graphs using the visual analytics workflow. The first step (Figure 4(a)) is to create a graph from a root level-12 HUC. The user can select a root HUC via the map using the pick tool (Figure 4(b)), by unique identification or by name (Figure 4(c)). The user specifies the level-12 HUC data source (Figure 4(d)) followed by specifying how to select graphs up- and downstream from the root HUC (Figure 4(e)). There are currently three selection methods: DFS, which selects level-12 HUCs along the dominant stream path first, or the user can specify breadth-first search (BFS) to select HUCs closest to the root HUC first, and the remaining option is to select none.

OPEN IN VIEWER

Figure 4.

To create a large graph for modeling, the main steps are to specify the up- and downstream graph properties from the root node (blue polygon) and methods to clip the graph.

As already discussed, using DFS or BFS searches can create very large graphs that our current cyberinfrastructure cannot support. Therefore, we provide two methods to clip graphs. The first method is to clip graphs at USGS gauges (Figure 3(f)). USGS gauges provide datasets (temperature, etc.) that can be used for hydrological model boundary conditions. For example, if a modeler is interested in following the path of a major flood, he or she can direct HPC resources downstream from the root node (USGS gauge) rather than modeling the watersheds upstream.

The second method is to clip graphs using HPC requirements. There are two options. The first is to restrict the graph by the number of HPC cluster nodes up and downstream (Figure 4(g)). For example, a user has access to a 128-node cluster; he or she can split the up and downstream graph to 64 nodes each. The second option is to restrict the graph by mesh size (Figure 4(h)). During the data-model workflow (Figure 3(a)), meshes are created representing the land surface. When meshes are large, models like PIHM require more HPC resources that may take too long to compute. Hence, we provide this clipping method to aid the modeler to select graph HUCs up to the mesh size of choice, up- and downstream from the root node. All clipping methods can be used in conjunction with each other to create graph selections for different modeling strategies. For our Juniata watershed use case, we used the map point tool to select root node “020503041204.” To replicate the graph of Figure 1, no downstream selection method was chosen (Figure 4(i)) and BFS search was used to select upstream HUCs with no graph clipping (Figure 4(e)).

After specifying up and downstream clippings and selection methods, the user initiates the first version of the graph workflow by clicking on the create graph button (Figure 4(j)). The graph selection methods specified by the user are serialized and assigned to a new graph workflow object (Table 4) in the HydroTerre databases. The compute node executing the graph workflow de-serializes these properties and executes the workflow as described in section “Graph workflow automated steps.” The graph workflow generates an issue list and metadata to populate the user interface and map visualizations. Figure 5 shows the map workflow result and Table 5 summarizes the issue list, data products, and compute times for the Juniata watershed.

OPEN IN VIEWER

Figure 5.

The visual analytics interface to validate the Juniata watershed. The left panel allows users to select graph workflow versions and interrogate the graph and data metadata. The middle panel map shows the graph results, nodes, and edges, with colors and symbols to assist the user to identify problems. The right panel identifies graph issues and controls automated zoom to level of detail. The user creates an action list to fix the graph for modeling.

OPEN IN VIEWER

Table 5.

The main steps for data preparation and analysis of the Juniata graph workflow are summarized below.

Prepare	ms	MB	Prepare	ms	MB	Analysis	ms	MB
HUC graph	6903	10	Flat HUCs	628	5	Conflict Dir.	4	1
Elevation	15191	50	Flat edges	35837	50	Flat outlets	15	1
NHD	50959	1000	Node graph	27022	5	Outlets	6	1
Edge graph	394498	2500	Map Viz	19257	1	Flat streams	45	10
Contour	39334	100	Dictionaries	3548	10	Metadata	1176	30
Total	506885	3660	Total	86292	71	Total	1246	43

HUC: hydrological unit code; NHD: National Hydrography Dataset; RAM: random-access memory.

Times are in milliseconds and disk size in megabytes. The entire graph workflow took about 10 min on our web-server (Intel Xeon E5-2687W Server with 32 cores and 128 GB RAM. More details about cyberinfrastructure available at Leonard ³ ).

The expert user selects the versioned graph from a list shown in Figure 5(a), which reveals the graph as a map (Figure 5(b)) and populates two user controls. The first control summarizes the graph and metadata properties of the Juniata graph generated by the user (Figure 5(c)). This control provides information about the graph method used, properties about HUCs, streams and supporting datasets, such as NED. These metrics are useful to determine the data requirements, such as forcing datasets, ²⁷ required to execute the end-to-end HydroTerre workflows. To prevent the user being overwhelmed with data, details are not revealed at the first map scale. Rather, the important issues are highlighted with colors and symbols at multiple zoom scales as summarized in Figure 5(d). For example, level-12 HUCs with green edges and white fill indicate no problems (Figure 5(e)), HUCs with blue fill indicate flat-sloped streams and are located within the HUC (Figure 5(f)), and purple HUCs have flat-sloped streams at the outlet (Figure 5(g)). These purple HUCs, numbered in suggested order of correction by distance from a root graph, are suggested to be addressed first by the user to validate the edge direction, as upstream connections may be incorrect affecting the entire graph structure. To aid the user in identifying the locations of the outlets at each HUC, small green circles designate their location without showing edge geometry at this scale extent. Furthermore, there are question mark symbols at each of the outlets that require validation by the user. Based on our graph selection, we know there should be only one outlet, not 16 as the automated analysis revealed.

The second control serves three functions. The first is a help guide, explaining the types of issues and strategies to validate graphs. The second is a map legend that aids users to control level of detail by turning data layers on or off and controlling transparency. The third function is a means to create an action list to validate the graph. The user specifies a problem type he or she wishes to address (Figure 5(i)), which will then fill in the issue by identification control (Figure 5(j)). This control automatically zooms the map to the issue at hand, rather than the user zooming into the map by themselves. The user can override this zoom action at three (HUC, stream (edge), and point) scales (Figure 5(k)). Additionally, the user can control the map with typical zoom and pan tools (Figure 5(l)). Each zoom scale reveals different amounts of data for the user, with point scale revealing all data and then as the zoom extent increases, less data are shown to the user. For example, for a user trying to resolve flat-sloped streams, at the edge scale, elevation values per vertex are labeled, but not NED grids. At the HUC scale, flat-sloped streams are purple lines to alert the user to a data problem requiring attention.

The next step is to select an action (Figure 5(m)) as described in section “User actions to correct graphs” to fix the graph. For provenance, the user has to specify a reason for their action (Figure 5(n)) before adding the action (Figure 5(o)) to the list of actions (Figure 5(p)). The last step is to submit all actions and rebuild the graph (Figure 5(q)). The action list is serialized and added to a new versioned graph workflow job as described previously. A new graph workflow is generated and the user repeats step 2, graph validation, until all issues (old and potentially new issues) have been resolved. For models like PIHM, the 745 issues first identified for the Juniata watershed require modification by the user to improve model performance and took about 2 h to create a corrected large graph. Clearly, even for a small number of level-12 HUCs, fixing these issues is time-consuming and tedious when using standard GIS techniques of manually interacting with map and data taking days to complete corrections. Our graph workflow that automates finding graph issues, combined with visual analytics tools that enable users to zoom directly to the problem and quickly assign an action fix from pre-defined solutions, makes the task of resolving CONUS scale graphs feasible.