# Clustered Graph Matching for Label Recovery and Graph Classification

arXiv: https://arxiv.org/abs/2205.03486 · HTML: https://mlsanity.com/paper/2205.03486/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 85 references that are in the map.
- First posted on arXiv 6 May 2022.

## Builds on (most cited first, 26 of 26)

- [Convolutional Networks on Graphs for Learning Molecular Fingerprints](https://mlsanity.com/paper/1509.09292/) (2015)
- [Learning Convolutional Neural Networks for Graphs](https://mlsanity.com/paper/1605.05273/) (2016)
- [Statistical inference on random dot product graphs: a survey](https://mlsanity.com/paper/1709.05454/) (2017)
- [Settling the Sharp Reconstruction Thresholds of Random Graph Matching](https://mlsanity.com/paper/2102.00082/) (2021)
- [Inference for multiple heterogeneous networks with a common invariant subspace](https://mlsanity.com/paper/1906.10026/) (2019)
- [Exact alignment recovery for correlated ErdHos-R'enyi graphs](https://mlsanity.com/paper/1711.06783/) (2017)
- [The impossibility of low rank representations for triangle-rich complex networks](https://mlsanity.com/paper/2003.12635/) (2020)
- [Improved Achievability and Converse Bounds for ErdHos-R'enyi Graph Matching](https://mlsanity.com/paper/1602.01042/) (2016)
- [(Nearly) Efficient Algorithms for the Graph Matching Problem on Correlated Random Graphs](https://mlsanity.com/paper/1805.02349/) (2018)
- [Correlated Stochastic Block Models: Exact Graph Matching with Applications to Recovering Communities](https://mlsanity.com/paper/2107.06767/) (2021)
- [Hypothesis Testing For Network Data in Functional Neuroimaging](https://mlsanity.com/paper/1407.5525/) (2014)
- [Limit theorems for eigenvectors of the normalized Laplacian for random graphs](https://mlsanity.com/paper/1607.08601/) (2016)
- [Network Regression with Graph Laplacians](https://mlsanity.com/paper/2109.02981/) (2021)
- [Network classification with applications to brain connectomics](https://mlsanity.com/paper/1701.08140/) (2017)
- [Joint Embedding of Graphs](https://mlsanity.com/paper/1703.03862/) (2017)
- [Optimal De-Anonymization in Random Graphs with Community Structure](https://mlsanity.com/paper/1602.01409/) (2016)
- [Asymptotically efficient estimators for stochastic blockmodels: the naive MLE, the rank-constrained MLE, and the spectral](https://mlsanity.com/paper/1710.10936/) (2017)
- [Information Recovery in Shuffled Graphs via Graph Matching](https://mlsanity.com/paper/1605.02315/) (2016)
- [Matched Filters for Noisy Induced Subgraph Detection](https://mlsanity.com/paper/1803.02423/) (2018)
- [Maximum Likelihood Estimation and Graph Matching in Errorfully Observed Networks](https://mlsanity.com/paper/1812.10519/) (2018)
- [Seeded Graph Matching Via Joint Optimization of Fidelity and Commensurability](https://mlsanity.com/paper/1401.3813/) (2014)
- [MIGRAINE: MRI Graph Reliability Analysis and Inference for Connectomics](https://mlsanity.com/paper/1312.4875/) (2013)
- [Connectome Smoothing via Low-rank Approximations](https://mlsanity.com/paper/1609.01672/) (2016)
- [The Phantom Alignment Strength Conjecture: Practical use of graph matching alignment strength to indicate a meaningful graph match](https://mlsanity.com/paper/2103.00624/) (2021)
- [The Multiple Random Dot Product Graph Model](https://mlsanity.com/paper/1811.12172/) (2018)
- [Systematic assessment of the quality of fit of the stochastic block model for empirical networks](https://mlsanity.com/paper/2201.01658/) (2022)

## Built on by (most cited first, 2 of 2)

- [Gotta match 'em all: Solution diversification in graph matching matched filters](https://mlsanity.com/paper/2308.13451/) (2023)
- [Detection of Model-based Planted Pseudo-cliques in Random Dot Product Graphs by the Adjacency Spectral Embedding and the Graph Encoder Embedding](https://mlsanity.com/paper/2312.11054/) (2023)

## Abstract (arXiv)

Given a collection of vertex-aligned networks and an additional label-shuffled network, we propose procedures for leveraging the signal in the vertex-aligned collection to recover the labels of the shuffled network. We consider matching the shuffled network to averages of the networks in the vertex-aligned collection at different levels of granularity. We demonstrate both in theory and practice that if the graphs come from different network classes, then clustering the networks into classes followed by matching the new graph to cluster-averages can yield higher fidelity matching performance than matching to the global average graph. Moreover, by minimizing the graph matching objective function with respect to each cluster average, this approach simultaneously classifies and recovers the vertex labels for the shuffled graph. These theoretical developments are further reinforced via an illuminating real data experiment matching human connectomes.