Clustered Graph Matching for Label Recovery and Graph Classification
Not on the map. Why?
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.
Key facts. Cited by 2 papers in the map (data through 7 Oct 2026). Builds on 26 of its 85 references that are in the map. First posted on arXiv 6 May 2022.
Builds on
26 of 85 references.
References · 26
- 2015Convolutional Networks on Graphs for Learning Molecular Fingerprintscited by 751
- 2016Learning Convolutional Neural Networks for Graphscited by 314
- 2017Statistical inference on random dot product graphs: a surveycited by 70
- 2021Settling the Sharp Reconstruction Thresholds of Random Graph Matchingcited by 45
- 2019Inference for multiple heterogeneous networks with a common invariant subspacecited by 39
- 2017Exact alignment recovery for correlated ErdHos-R'enyi graphscited by 35
- 2020The impossibility of low rank representations for triangle-rich complex networkscited by 32
- 2016Improved Achievability and Converse Bounds for ErdHos-R'enyi Graph Matchingcited by 30
- 2018(Nearly) Efficient Algorithms for the Graph Matching Problem on Correlated Random Graphscited by 29
- 2021Correlated Stochastic Block Models: Exact Graph Matching with Applications to Recovering Communitiescited by 22
- 2014Hypothesis Testing For Network Data in Functional Neuroimagingcited by 20
- 2016Limit theorems for eigenvectors of the normalized Laplacian for random graphscited by 17
14 more
- 2021Network Regression with Graph Laplacianscited by 15
- 2017Network classification with applications to brain connectomicscited by 12
- 2017Joint Embedding of Graphscited by 12
- 2016Optimal De-Anonymization in Random Graphs with Community Structurecited by 11
- 2017Asymptotically efficient estimators for stochastic blockmodels: the naive MLE, the rank-constrained MLE, and the spectralcited by 9
- 2016Information Recovery in Shuffled Graphs via Graph Matchingcited by 8
- 2018Matched Filters for Noisy Induced Subgraph Detectioncited by 6
- 2018Maximum Likelihood Estimation and Graph Matching in Errorfully Observed Networkscited by 6
- 2014Seeded Graph Matching Via Joint Optimization of Fidelity and Commensurabilitycited by 5
- 2013MIGRAINE: MRI Graph Reliability Analysis and Inference for Connectomicscited by 4
- 2016Connectome Smoothing via Low-rank Approximationscited by 4
- 2021The Phantom Alignment Strength Conjecture: Practical use of graph matching alignment strength to indicate a meaningful graph matchcited by 4
- 2018The Multiple Random Dot Product Graph Modelcited by 3
- 2022Systematic assessment of the quality of fit of the stochastic block model for empirical networkscited by 1
Built on by
Citing papers per year: 2023: 2.
2 papers.