# Generalized Median Graph via Iterative Alternate Minimizations

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Jun 2019.

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

- [Kernel-Based Generalized Median Computation for Consensus Learning](https://mlsanity.com/paper/2209.10208/) (2022)
- [Theoretical analysis and computation of the sample Frechet mean for sets of large graphs based on spectral information](https://mlsanity.com/paper/2201.05923/) (2022)
- [Robust Estimation in metric spaces: Achieving Exponential Concentration with a Fr'echet Median](https://mlsanity.com/paper/2504.14161/) (2025)

## Abstract (arXiv)

Computing a graph prototype may constitute a core element for clustering or classification tasks. However, its computation is an NP-Hard problem, even for simple classes of graphs. In this paper, we propose an efficient approach based on block coordinate descent to compute a generalized median graph from a set of graphs. This approach relies on a clear definition of the optimization process and handles labeling on both edges and nodes. This iterative process optimizes the edit operations to perform on a graph alternatively on nodes and edges. Several experiments on different datasets show the efficiency of our approach.