Optimizing the Temporal Resolution in Dynamic Graph Mining
Abstract
Dynamic graph mining can elucidate the activity of in-network processes in diverse application domains from social, mobile and communication networks to infrastructure and biological networks. Compared to static graphs, the temporal information of when graph events occur is an important new dimension for improving the quality, interpretation and utility of mined patterns. However, mining dynamic graphs poses an important, though often overlooked, challenge: observed data must be analyzed at an appropriate temporal resolution (timescale), commensurate with the underlying rate of application-specific processes. If the temporal resolution is too high, evidence for ongoing processes may be fragmented in time; if it is too low, data relevant to multiple processes may be mixed, thus, obstructing discovery. Existing approaches for dynamic graph mining typically adopt a fixed timescale (e.g., minutes, days, years), and they mine for patterns in the corresponding aggregated graph snapshots. However, timescale-aware methods must consider non-uniform resolution in time and the graph, thus accounting for heterogeneous processes of varying rates in different network regions. Research problem: The main objective of the proposed project is to improve the quality and interpretability of dynamic graph mining results by bridging the disconnect between timescale selection and the mining process. Enabling timescale-aware methods and employing them is pivotal to improving the utility of dynamic graphs and their increasingly ubiquitous applications. Technical approaches: Our central premise is that the quality and interpretability of dynamic graph mining tasks (e.g. community tracking, link prediction, influence maximization, anomaly detection) can be greatly improved by jointly learning an appropriate temporal scale to analyze the data. As part of this project we will methodically address the challenges of optimal scale selection across data modalities and timescales, i.e. in addition to aggregation we will develop techniques for disaggregation and interpolation of dynamic graph data. The approaches in each research thrust are summarized below: Thrust R1: Structural dynamics. We will employ interaction and link creation events for community detection and evolution, temporal link prediction and structure inference, node classification, as well as anomaly detection. Thrust R2: Behavioral dynamics. We will mine behavioral event data associated with nodes (e.g. web page access logs, geospatial logs and check-ins, and information cascades) for network diffusion applications and synchronous subgraph detection. Thrust R3: Evolving graph signals. The mining tasks from the previous two thrusts will be approached in a low-resolution setting, investigating optimal disaggregation and interpolation strategies for over-aggregated or under-sampled graph data in time. Anticipated outcomes: This project is the first comprehensive effort to incorporate optimal temporal scale selection into the mining process across different modes of dynamic graph data, mining tasks and applications. We will pursue two families of optimal scale selection approaches: exhaustive search in the space of timescales and model/application-driven optimization of the timescale. Our solutions will advance (i) data mining by introducing novel methods for tensors, graph signals and network structure mining; (ii) network science by bridging theoretical models and real-data analysis; and (iii) the capabilities of analysts at NGA and beyond by improving the quality and interpretability of detected patterns.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Sep 28, 2020
- Source ID
- HM04762010011
Entities
People
- Petko Bogdanov
Organizations
- National Geospatial-Intelligence Agency
- Research Foundation for the State University of New York