CAREER: Principled Structure Discovery for Network Analysis

University Of Notre Dame, Notre Dame IN

Investigators

Abstract

Behind every social, technological, and biological system is an intricate network that encodes the relationship between the objects in the system. Thus, extracting the useful and interesting building blocks of a network is critical to the understanding of many systems. Indeed, the most pivotal moments in the development of a scientific field are centered on discoveries about the structure of a network. For example, chemists have found that many chemical interactions are the result of the structural principles of interactions between the elements. Biologists agree that tree structures are useful when organizing the evolutionary history of life, sociologists find that triangles are important in the development of communities, and neuroscientists continue to untangle the network dynamics of neurons in the brain. To aide in these discoveries, principled strategies for extracting network patterns are needed to discover the precise mechanisms that govern network structure and growth. This is exactly the focus of this project: to develop and evaluate techniques that learn the building blocks of real world networks that, in aggregate, simply describe the interactions expressed by the network. This project will also support educational and outreach programs that will broaden participation in computer science. Open source software implementations of the new algorithms will be made available to the public, and will also serve as an educational tool. Research supervision and career mentoring will be made available to K-12 students through the development and publication of science fair projects in computing, and undergraduate and graduate student training will be offered through a new course in data and network science. This project will develop and evaluate principled techniques that learn the building blocks of real world networks. The ideas in this proposal originate from a newfound relationship between graph theory and formal language theory that allow for a Hyperedge Replacement Grammar (HRG) to be extracted from any graph without loss of information. Like a context free grammar, but for graphs, the extracted HRG contains the precise building blocks of the network as well as the instructions by which these building blocks ought to be pieced together. In this project, we take the first steps towards reconciling the disparate fields of formal language and graph theory by asking incisive questions about the extraction, inference, and analysis of network patterns in a mathematically elegant and principled way. Graph mining research has scientific applications of societal importance, such as new drug therapies, knowledge networks, and natural language understanding, which will be explored as part of this project. In addition, this project will result in the formation of new interdisciplinary scientists, career mentoring, graduate and undergraduate research, and the development of science fair projects in computing for K-12 students, focusing on economically disadvantaged youth. The results will also be disseminated through tutorial and workshop organization at renowned international conferences.