Smooth Modeling of Flows on Graphs
Abstract
Countless signals can be expressed as functions or distributions over the vertices of a graph, from quantities of passengers traveling between airports to packets passing between computers connected by wireless routers. These tasks suggest the value of constructing a theory of signal analysis specifically tuned to data defined over a graph, accompanied by practical numerical optimization methods. Fundamentally, this theory should be geometric in nature, expressing the fact that signals on graphs typically propagate from one vertex to another along paths of edges. Existing theoretical and computational tools for this task are purely discrete, written as finite-dimensional optimization problems involving quantities associated with graph nodes and edges. While this facilitates the use of traditional algorithms from the computer science literature, it obscures the connection to real-world sources of graph data. That is, in many applications, the agent interacting with a graph moves smoothly in time along edges from vertex to vertex rather than bopping from one vertex to the next. Beyond this disconnect between modeling and reality, from a mathematical standpoint existing graph-based optimization problems often have non unique solutions and are unregularized, making them unsuitable for data analysis. With the goal of connecting theory and practice, this project will bridge the gap between theoretical developments in the field of optimal transportation-- designed to understand flows along smooth domains---and the analysis of signals over graphs. In contrast to existing combinatorial algorithms, our approach will be inspired by continuous ideas from differential equations, functional analysis, and geometry. We will propose fundamentally different constructions from well-known graph algorithms that more directly link smooth (continuously-varying in time and space) and discrete interpretations of flows. This project finds application in several fields of importance to the scientific mission of the Army Research Laboratory. In communications, the proposed methods can be used to understand and manipulate flows of information over chains of interconnected wireless devices and sensors. More abstractly, many classes of data are best represented as high-dimensional data points linked by common features or relationships, requiring noise-resilient and mathematically justified models for their analysis. On a broader scale, the same algorithms used for graph signal processing can be applied to understanding signals over domains with stronger geometric structure, e.g. point clouds, triangulated surfaces, and splines. As a candidate specifically for the Army Young Investigator Award, a secondary objective of the proposed project is to open lines of communication and feedback between the PI (Prof. Justin Solomon) and the various research and engineering organizations supported by the Army. PI Solomon already has carried out several projects in the areas of geometry, machine learning, optimization, and graph processing that should be of interest to Army applications experts. Moving forward, ARL/RDECOM program managers and scientists would serve as invaluable contacts to shape a research program poised to address realistic demands of maintaining strategic defense infrastructure.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Feb 14, 2019
- Source ID
- W911NF1710068
Entities
People
- Justin Solomon
Organizations
- Army Contracting Command
- Massachusetts Institute of Technology
- United States Army