CAREER: Scalable Techniques for Visualizing Very Large Graphs

University Of Nebraska-Lincoln, Lincoln NE

Investigators

Abstract

Graphs, also called networks, are important data structures used to represent structural relationships between different entities. Graph models have been ubiquitously employed in scientific applications (e.g., computational molecular biology and ecology) and industrial applications (e.g., world wide web and social network services). With advanced computing techniques, real-world applications can generate graph datasets of unprecedented scales, such as a worldwide social network, where a large graph can contain billions or trillions of vertices (identities) and edges (relationships). Graph visualization, creating visual or diagrammatic representations of graphs, has been commonly used as an effective means to facilitate users to gain meaningful overviews of graph structures and capture regions of interest. However, there is still a lack of scalable visualization solutions that are efficient and practical for very large graph datasets and allow users to explore and discover possible insights in a timely manner. Such solutions can only be obtained with a holistic coordination of processing, organization, and visualization of large graphs, which however has not been fully investigated in most of the previous graph visualization work. This project seeks techniques to ensure the scalability and the usability of large graph visualization by tackling an end-to-end graph visualization pipeline including graph processing, organization, and visualization. Since graphs exist in many scientific and industrial applications as a critical data model, through the outreach activities and the collaboration with domain experts, graph visualization tools and optimization techniques developed in this research can greatly benefit a broader class of fields and communities. The education objective of this project is to leverage real-world large graph visualization to effectively promote students' engagement and learning efficiency in science and engineering studies. In particular, the project aims to leverage interdisciplinary synergies to develop and renovate undergraduate and graduate courses to facilitate the learning of both major and non-major students. Interdisciplinary graph applications will be used to enhance outreach, student recruitment, and research opportunities. Teaching effectiveness will be assessed with an involvement of educators from different disciplines. The project will develop scalable visualization techniques for very large graphs by exploiting graph structure properties and computer systems optimization. To accomplish this goal, the project has the following objectives. First, scalable parallel clustering methods will be developed to extract sub-graphs with dense intra-connections from large graphs. Second, new algorithms will be designed to address the fundamental data locality problem by identifying and organizing sub-graphs according to their potential access patterns in support of graph processing and visualization. Third, structure-aware visualization techniques, adopting a hierarchical manner, will be developed to provide users an efficient and effective visual guide for large graph exploration. These results will transform conventional visualization methods, which were not ready for handling graphs with billions or trillions of vertices and edges, to efficient and practical techniques for real-world large-scale graph applications. The research and education results from this project will be disseminated in premier conferences and journals and other forms. The project website (http://cse.unl.edu/~yu/research/nsf17_graph/) provides the pointers to the project results, including publications, datasets, software, demos, and educational materials, with the corresponding descriptions.