DARPA Modeling Adversarial Activity Program: Team UMass/UMD, JHU, BU

This work is sponsored by the Air Force Research Laboratory and DARPA, under agreement numbers FA8750-18-2-0035 and FA8750-20-2-1001. The U.S. Government is authorized to reproduce and distribute reprints for Governmental purposes notwithstanding any copyright notation thereon. The views and conclusions contained herein are those of the authors and should not be interpreted as necessarily representing the official policies or endorsements, either expressed or implied, of the Air Force Research Laboratory and DARPA, or the U.S. Government.

Our team

Also funded (in some part):

Project: Methods for Graph Matching and Graph Matching Matched Filters

Our work in MAA is roughly broken down into two main areas: template detection and more general graph matching/merging

Template detection via Graph Matching Matched Filters

Goal: Detect noisy induced multiplex template in a larger multiplex background network by leveraging a multiplex analogue of the classical graph matching problem to use the template as a matched filter for efficiently searching the background for candidate template matches

Key papers:

Graph matching and merging

Goal: Develop robust graph alignment tools for richly featured graphs that are robust to topological heterogeneity across networks

Key papers:

iGraphMatch

All of our work in MAA has been implemented in iGraphMatch, our R package funded (in part) by the MAA program

Goal: Provide a suite of tools for easy simulation and comparison of graph matching algorithms; Become a flexible central repository for state of the art matching algorithms.

Furthering the Science

In addition to (and including) the work above, the following papers were funded/inspired by our work in the MAA program.

Graph Matching

  • “Matched Filters for Noisy Induced Subgraph Detection,” by Sussman, Park, Priebe, Lyzinski. IEEE TPAMI 2019.
  • “Graph Matching via Multi-Scale Heat Diffusion,” by Li and Sussman. IEEE Big Data, 2019.
  • “Seeded graph matching,” by Fishkind, Adali, Pastolic, Meng, Singh, Lyzinski, Priebe. Pattern Recognition 2019.
  • “Alignment Strength and Correlation for Graphs,” by Fishkind, Meng, Sun, Priebe, Lyzinski. Pattern Recognition Letters, 2019.
  • “Mulitplex Graph Matching Matched Filters,” by Pantazis, Sussman, Park, Priebe, and Lyzinski. GTA3.0 Workshop, 2019.
  • “Matchability of heterogeneous networks pairs,” by Lyzinski, Sussman. IMA Information and Inference, 2020.
  • “Maximum Likelihood Estimation and Graph Matching in Errorfully Observed Networks,” by Arroyo, Sussman, Priebe, Lyzinski. JCGS 2021.
  • “Graph matching between bipartite and unipartite networks: to collapse, or not to collapse, that is the question,” by Arroyo, Priebe, and Lyzinski, IEEE TNSE 2021.
  • “On a complete and sufficient statistic for the correlated Bernoulli random graph model,” by Fishkind, Athreya, Meng, Lyzinski, and Priebe. EJS 2021.
  • “The Phantom Alignment Strength Conjecture: Practical use of graph matching alignment strength to indicate a meaningful graph match,” by Fishkind, Parker, Sawczuk, Meng, Bridgeford, Athreya, Priebe, Lyzinski, Applied Network Science 2021.
  • “Tractable graph matching via soft seeding,” by Fang, Sussman, and Lyzinski. Submitted, 2018.
  • “Seeded Graph Matching Via Joint Optimization of Fidelity and Commensurability,” by Patsolic, Adali, Vogelstein, Park, Priebe, Li, Lyzinski. Revision submitted 2019.

Network Clustering

  • "On a ‘Two Truths’ Phenomenon in Spectral Graph Clustering’ by Priebe, Park, Vogelstein , Conroy , Lyzinski, Tang , Athreya , Cape , Bridgeford. PNAS 2019.
Graph embedding/ testing/ time-series
  • “Joint Embedding of Graphs,” by Wang, Arroyo, Vogelstein, and Priebe. IEEE TPAMI 2019.
  • “Ergodic Limits, Relaxations, and Geometric Properties of Random Walk Node Embeddings,” by Lin, Sussman, and Ishwar. Submitted 2021
  • “A central limit theorem for an omnibus embedding of multiple random graphs and implications for multiscale network inference,” by Levin, Athreya, Tang, Lyzinski, Park, Priebe, Revision submitted, 2019.
  • “Bias-Variance Tradeoffs in Joint Spectral Embeddings,” by Draves and Sussman, Submitted 2020.
  • “The Importance of Being Correlated: Implications of Dependence in Joint Spectral Inference across Multiple Networks,” by Pantazis, Athreya, Frost, Hill, and Lyzinski, Submitted 2020.
  • “Multiple Network Embedding for Anomaly Detection in Time Series of Graphs,” by Chen, Arroyo, Athreya, Cape, Vogelstein, Park, White, Larson, Yang, and Priebe, Submitted 2020.
  • “Valid Two-Sample Graph Testing via Optimal Transport Procrustes and Multiscale Graph Correlation: Applications in Connectomics,” by Chung, Varjavand, Arroyo, Alyakin, Agterberg, Tang, Vogelstein, and Priebe, Revision submitted 2020
Estimation/Causal Inference
  • “Connectome Smoothing via Low-rank Approximations,” by Tang, Ketcha, Badea, Calabrese, Margulies, Vogelstein, Priebe, Sussman. IEEE TMI 2018.
  • “Estimation of the Epidemic Branching Factor in Noisy Contact Networks,” by Li, Sussman, Kolaczyk, Submitted 2020
  • “Causal Inference under Network Interference with Noise.” by Li, Sussman, Kolaczyk, Submitted, 2021
Vertex Nomination
  • “On consistent vertex nomination schemes,” by Lyzinski, Levin, Priebe. JMLR 2019.
  • “Vertex Nomination, Consistent Estimation, and Adversarial Modification,” by Agterberg, Park, Larson, White, Priebe, and Lyzinski, EJS, 2020.
  • “Vertex nomination: The canonical sampling and the extended spectral nomination schemes,” by Yoder, Chen, Pao, Bridgeford, Levin, Fishkind, Priebe, Lyzinski. Computational Statistics & Data Analysis, 2020.
  • “On the role of features in vertex nomination: Content and context together are better (sometimes),” by Levin, Priebe, and Lyzinski, Submitted 2020.
  • “Learning to rank via combining representations ,” by Helm, Basu, Athreya, Park, Vogelstein, Winding, Zlatic, Cardona, Bourke, Larson, White, and Priebe, Submitted 2020.
  • “Vertex nomination between graphs via spectral embedding and quadratic programming,” by Zheng, Lyzinski, Priebe, Tang, Submitted 2020
  • “Subgraph nomination: Query by Example Subgraph Retrieval in Networks,” by Al-Qadhi, Priebe, Helm Lyzinski, Submitted 2021
  • “Leveraging semantically similar queries for ranking via combining representations,” by Helm, Abdin, Pedigo, Mahajan, Lyzinski, Park, Basu, White, Yang, and Priebe. Submitted 2021.