Seeded Graph Matching for Correlated Erdos-Renyi Graphs
Authors: Vince Lyzinski, Donniell E. Fishkind, Carey E. Priebe
JMLR 2014 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We conclude this paper with simulations and a real-data example from human connectomics. These simulations and experiments illuminate the relationship between seeded graph matching via Frank-Wolfe and restricted-focus graph matching via the Hungarian algorithm. We demonstrate that Frank-Wolfe methodology is often superior to restrictedfocus graph matching, an unsurprising result as the Frank-Wolfe methodology merges restricted-focus graph matching with seedless Frank-Wolfe methodology. |
| Researcher Affiliation | Academia | Vince Lyzinski EMAIL Human Language Technology Center of Excellence Johns Hopkins University Baltimore, MD, 21218, USA Donniell E. Fishkind EMAIL Carey E. Priebe EMAIL Department of Applied Mathematics and Statistics Johns Hopkins University Baltimore, MD, 21218, USA |
| Pseudocode | No | The paper describes the algorithms (Frank-Wolfe methodology, SGM algorithm, RGM) in prose, detailing the mathematical formulations and steps involved. However, it does not present any formal pseudocode blocks or algorithms labeled as such. |
| Open Source Code | No | The paper does not explicitly state that source code for the described methodology is being released, nor does it provide any direct links to a code repository. It mentions data availability, but not code. |
| Open Datasets | Yes | Our data set consists of 45 graphs, each on 70 vertices, these graphs constructed respectively from diffusion tensor (DT) MRI scans of 45 distinct healthy patients. We have 21 scans from the Kennedy Krieger Institute (KKI), with raw data available at http://www.nitrc.org/projects/multimodal/, and 24 scans from the Nathan Kline Institute (NKI), with a description of the raw data available at http://fcon_1000.projects.nitrc.org/indi/pro/e NKI_RS_TRT/Front Page.html. All graphs can be found at http://openconnecto.me/data/public/.MR/ MIGRAINE/. |
| Dataset Splits | No | For the real-data experiment, the paper describes matching pairs of graphs from two different institutes (NKI and KKI) and performing Monte Carlo replicates for different seed levels, but it does not specify traditional training/validation/test splits. For simulations, it states running '100 simulations' for each parameter combination, which describes experimental runs rather than a dataset split strategy. |
| Hardware Specification | No | The paper does not provide specific details about the hardware (e.g., CPU, GPU models, memory) used to run the simulations or real-data experiments. It only mentions the source of the data (MRI scans) and the general processing pipeline. |
| Software Dependencies | No | The paper discusses various algorithms and methodologies like Frank-Wolfe, Hungarian algorithm, SGM, and FAQ. However, it does not specify any software names or versions for these, or any other ancillary software components used for implementation or analysis. |
| Experiment Setup | Yes | We explore the above further in Figure 1. There we compare the performance of SGM against solving RGM for correlated Erd os-R enyi graphs with n = 300 vertices, p = 0.5, seeding levels ranging from s = 0 to 275, and correlation ranging from ϱ = 0.1 to 1. For each value of ϱ and s, we ran 100 simulations and plotted the fraction of nonseeded vertices correctly matched across the graphs, with corresponding error bars of 2 s.e. Moreover, if 100 |V (G1)| and G1 is selected with a discrete-uniform distribution (i.e., all possible graphs on V (G1) are equally likely) and G2 is an isomorphic copy of G1 with V (G2) being a discrete-uniform random permutation of V (G1), then the probability that FAQ (with, say, 20 Frank-Wolfe iterations allowed) yields the correct isomorphism is empirically observed to be very nearly 1. |