A New Perspective on Fast Distributed Computations Over Networks
Abstract
Numerous high-impact mining tasks, such as network inference and node relevance, involve solving linear systems efficiently and, in many settings, require solutions for different sets of priors or queries. For example, inferring missing information and classifying entities in a network setting (e.g., in a sensor or communication network) with limited supervision as additional information is unveiled over time, finding similar entities and anomalous network behaviors (e.g., malicious IPs) in a time-evolving computer network, and evaluating the importance of an entity in a multi-agent network (e.g., trustworthy agents), can all be expressed as a set of linear systems. Such tasks can lead to better decision-making and improved (semi-)autonomous systems under incomplete observations. As datasets grow at unprecedented speed, their corresponding networks may span many millions of entities, thus requiring fast, distributed methods for applying high-impact, linear-system-based tasks. Moreover, in a multi-query setting, efficient online handling of queries is indispensable for near real-time analysis and monitoring. Since exact matrix inversion and LU decomposition do not scale to large networks, iterative approaches are often employed, but most of them lead to approximate solutions with weak convergence guarantees, and cannot handle multiple queries efficiently-they require redundant re-computation per query. Other iterative methods in distributed settings with multiple clusters require costly cross-cluster computations in every iteration, or rely on asynchronous updates without or with limited accuracy guarantees. On the other hand the few existing non-iterative approaches provide approximate answers or cannot handle overlapping data clusters, which are known to be beneficial for iterative approaches in distributed environments. This project aims to fill in these needs: Targeting near real-time analysis of very large graphs in a distributed and multi-query setting, it will introduce a new framework of intuitive, fast and accurate techniques for supporting popular graph algorithms which can be expressed as a set of linear systems. Unlike past work, this proposal targets a general form of linear systems that are prevalent in many core graph mining tasks. Our key idea is to flip the usual way of considering information flow (or messages) over edges to information flow over nodes. Based on that, we propose to tackle four main tasks: (T1) Exact Two-Step Solution over Graph Partitions: We will analytically derive a two-step general formulation, which requires only a one-time cross-cluster synchronization. We will also design fast algorithms, ,with an offline and a fast online stage, for solving linear-system-based graph methods; (T2) Overlapping Clustering for Scalability: We will revise efficient strategies for obtaining overlapping clusters tailored to our two-step approach in order to further speed it up, and we will explore the trade-off between space and runtime; (T3) Approximations in Static and Streaming Settings: We propose novel information-theoretic approximations with probabilistic guarantees and extend our approaches to streaming settings (by using perturbation theory and algebraic derivations) in order to capture network changes over time with- out large overhead in computation; and (T4) Tailored Graph Clustering Approaches: We will study existing graph clustering methods in the context of our proposed formulation and introduce a new clustering paradigm (that minimizes the number of nodes with cross-cluster connections as opposed to the commonly-used edge cut), which can lead to more efficient solutions. The Intelligent Information Networks program managed by Dr. Purush Iyer in the Network Sciences Division is best suited to review this proposal.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Feb 14, 2019
- Source ID
- W911NF1810397
Entities
People
- Danai Koutra
Organizations
- Army Contracting Command
- United States Army
- University of Michigan