Graph Information System
Xifeng Yan, University of California at Santa Barbara
CAREER: Graph Information System: Deciphering Complex Networks, funded by NSF Career IIS-0954125.
Graduate Students: Nan Li (oDesk, now Apple), Arijit Khan (PostDoc, ETH)
Undergraduate Students: Bruce Liu (Pasadena Community College/UCI)
Graphs and networks are ubiquitous, encoding
complex relationships ranging from chemical bonds to social interactions. Hidden
in these networks are the answers to many important questions in biology,
business, and sociology. In order to analyze complex networks, users have to
master sophisticated computing and programming skills. It indeed becomes a pain
point for many scientists and engineers.
This project is to change the state of the art by developing a general graph information system, which is able to address the needs of searching and mining complex networks. Real-life networks are complex, not only having topological structures, but also containing heterogeneous contents and attributes associated with nodes and edges. The mixture of structures and contents raises two challenges that require new solutions for smarter and faster graph analysis. First, new types of graph search and mining operations, such as graph aggregation, graph association, and graph pattern mining, are emerging. Second, when graphs become complex and large, most of existing graph mining algorithms cannot scale well. This project addresses these challenges and performs a comprehensive study of a general graph information system. The proposed system includes three major components: complex graph search, graph pattern mining, and graph indexing. It covers emerging structure queries in social, biological, and information networks, new graph mining operators such as graph summarization and association, and innovative indexing methodologies, e.g., differential graph index.
This research is tightly integrated with education through student mentoring and curriculum development. Publications, software and course materials resulted from this project are disseminated on this website.
2013 Nan Li, Ph.D., "Uncovering
Anomalous Patterns in Large Attributed Graphs."
2013 Arijit Khan, Ph.D., "Towards Querying and Mining of Large-Scale Networks."