pith. sign in

arxiv: 1906.11009 · v1 · pith:UO5Y7BUSnew · submitted 2019-06-26 · 💻 cs.CV · q-bio.QM

Generalized Median Graph via Iterative Alternate Minimizations

Nicolas Boria , S'ebastien Bougleux , Benoit Ga\"uz\`ere (LITIS) , Luc Brun This is my paper

Pith reviewed 2026-05-25 15:57 UTC · model grok-4.3

classification 💻 cs.CV q-bio.QM
keywords generalized median graphblock coordinate descentgraph edit distanceiterative optimizationgraph prototype
0
0 comments X

The pith

Block coordinate descent approximates generalized median graphs by alternating node and edge edit optimizations.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper develops an iterative algorithm based on block coordinate descent to compute a generalized median graph that minimizes total graph edit distance across a set of input graphs. The process alternates between optimizing edit operations on nodes and then on edges while handling labels on both. This decomposition turns the NP-hard exact computation into a sequence of more manageable subproblems. A reader would care because such median graphs act as prototypes that support downstream tasks like clustering and classification on graph data.

Core claim

The central claim is that an alternating minimization procedure, which optimizes node edits in one block and edge edits in the next within a coordinate descent loop, produces an efficient approximate generalized median graph for labeled graphs.

What carries the argument

Block coordinate descent that alternates between optimizing node edit operations and edge edit operations.

If this is right

  • The method works for graphs whose nodes and edges both carry labels.
  • It yields a practical computational procedure for an NP-hard problem.
  • Experiments across multiple datasets confirm that the procedure runs efficiently.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Different initialization graphs could be tested to see how much the final median cost varies with starting point.
  • The alternation pattern might be applied to other graph prototype problems that separate node and edge contributions.
  • The same block structure could be combined with local search heuristics to escape poorer local solutions.

Load-bearing premise

That alternating between node and edge optimization blocks produces a result close to the true generalized median instead of a poor local minimum that depends heavily on initialization.

What would settle it

On small collections of graphs where an exact generalized median can be computed by exhaustive search, measure whether the alternating method returns a graph whose total edit cost to the set is substantially higher than the exact minimum.

Figures

Figures reproduced from arXiv: 1906.11009 by Benoit Ga\"uz\`ere (LITIS), Luc Brun, Nicolas Boria, S'ebastien Bougleux.

Figure 1
Figure 1. Figure 1: Labeled graphs (label 0 if no edge) and a transformation ( [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
read the original abstract

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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 0 minor

Summary. The paper claims to provide an efficient block coordinate descent algorithm for computing a generalized median graph from a set of (labeled) graphs. The method iteratively alternates between optimizing node edit operations and edge edit operations on a candidate prototype; the problem is acknowledged to be NP-hard, and the approach is evaluated empirically on several datasets to demonstrate practical efficiency.

Significance. A reliable, scalable heuristic for the generalized median graph would be useful for downstream graph clustering and classification tasks. The alternating-minimization framing is a natural coordinate-descent idea, but its value hinges on whether the attained local solutions are sufficiently close to the global median; without supporting analysis this remains an open empirical question.

major comments (2)
  1. [Abstract] Abstract: the central claim that the block coordinate descent procedure 'computes a generalized median graph' is not accompanied by any convergence analysis, approximation bound, or comparison against exact or branch-and-bound solvers, despite the explicit statement that the underlying problem is NP-hard.
  2. [Abstract] Abstract (and method description): because the edit-distance objective couples node and edge labels, an alternation that optimizes nodes then edges (or vice versa) can miss configurations that are jointly optimal; no argument or experiment is supplied showing that the attained cost is close to the true median or that the gap is bounded independently of initialization.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the detailed and constructive report. We agree that the current wording in the abstract overstates the capabilities of the proposed block coordinate descent heuristic for this NP-hard problem. In the revised manuscript we will tone down the claims, explicitly label the method as a heuristic, and add a limitations paragraph discussing the absence of convergence guarantees and approximation bounds.

read point-by-point responses

  1. Referee: [Abstract] Abstract: the central claim that the block coordinate descent procedure 'computes a generalized median graph' is not accompanied by any convergence analysis, approximation bound, or comparison against exact or branch-and-bound solvers, despite the explicit statement that the underlying problem is NP-hard.

    Authors: We accept the criticism. The manuscript will be revised to replace the phrase 'computes a generalized median graph' with 'approximates a generalized median graph via block coordinate descent' in the abstract and introduction. A new paragraph will be added in the discussion section acknowledging that no convergence analysis or approximation guarantees are provided and that the method is a practical heuristic whose quality is assessed only empirically. Direct comparisons against exact solvers are infeasible on the larger datasets used in the experiments; on the smallest synthetic instances we can add a brief note that the heuristic matches the optimum found by exhaustive search. revision: yes

  2. Referee: [Abstract] Abstract (and method description): because the edit-distance objective couples node and edge labels, an alternation that optimizes nodes then edges (or vice versa) can miss configurations that are jointly optimal; no argument or experiment is supplied showing that the attained cost is close to the true median or that the gap is bounded independently of initialization.

    Authors: We agree that the node-edge coupling can cause the alternating procedure to converge to a local rather than global optimum. The revision will explicitly state in Section 3 that the algorithm finds a coordinate-wise local minimum and will report results from multiple random initializations on each dataset to illustrate variability. We do not possess a theoretical bound on the optimality gap that holds independently of initialization, and deriving such a bound appears difficult given the NP-hardness of the underlying problem; the manuscript will therefore not claim any such guarantee. revision: yes

Circularity Check

0 steps flagged

No circularity: algorithmic heuristic for NP-hard problem with no self-referential reduction

full rationale

The paper presents a block coordinate descent algorithm that alternates optimization of node and edge edit operations to approximate the generalized median graph. No equations, parameters, or claims reduce the output to a fitted input, self-definition, or self-citation chain. The method is explicitly positioned as an efficient heuristic for an acknowledged NP-hard problem, without any derivation that equates the attained local optimum to the global median by construction. The central procedure is a direct iterative minimization whose correctness is evaluated empirically rather than proven via tautological steps.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract-only review; no explicit free parameters, axioms, or invented entities are identifiable from the provided text.

pith-pipeline@v0.9.0 · 5626 in / 911 out tokens · 21635 ms · 2026-05-25T15:57:42.173523+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

16 extracted references · 16 canonical work pages

  1. [1]

    In: International Conference on Pattern Recognition

    Bougleux, S., Ga¨ uz` ere, B., Brun, L.: Graph edit distance as a quadratic program. In: International Conference on Pattern Recognition. pp. 1701– 1706 (2016). https://doi.org/10.1109/ICPR.2016.7899881 9 Letter (HIGH) Dataset TS 1st phase 2nd phase pt % SM t(SM) % GM t(GM) % TS t(TS) 10% mBipartite mBipartite 0.023 76.42 0.325 82.82 0.325 83.01 5.275 mBi...

    work page doi:10.1109/icpr.2016.7899881 2016

  2. [2]

    Pattern Recognition Letters 1(4), 245–253 (1983)

    Bunke, H., Allermann, G.: Inexact graph matching for structural pattern recognition. Pattern Recognition Letters 1(4), 245–253 (1983). https://doi.org/10.1016/0167-8655(83)90033-8

    work page doi:10.1016/0167-8655(83)90033-8 1983

  3. [3]

    Pattern Recognition72, 266–284 (2017)

    Chaieb, R., Kalti, K., Luqman, M.M., Coustaty, M., Ogier, J.M., Amara, N.E.B.: Fuzzy generalized median graphs computation: Application to content-based document retrieval. Pattern Recognition72, 266–284 (2017). https://doi.org/10.1016/j.patcog.2017.07.030

    work page doi:10.1016/j.patcog.2017.07.030 2017

  4. [4]

    In: International Conference on Pattern Recognition Applications and Methods

    Daller, ´E., Bougleux, S., Ga¨ uz` ere, B., Brun, L.: Approximate graph edit distance by several local searches in parallel. In: International Conference on Pattern Recognition Applications and Methods. pp. 149–158 (2018). https://doi.org/10.5220/0006599901490158

    work page doi:10.5220/0006599901490158 2018

  5. [5]

    Application to Graph-based Classification and Clustering

    Ferrer, M.: Theory and Algorithms on the Median Graph. Application to Graph-based Classification and Clustering. Ph.D. thesis, Universitat Aut` onoma de Barcelona (2008),http://hdl.handle.net/10803/5788

    work page 2008

  6. [6]

    In: Graph Embedding for Pattern Analysis, pp

    Ferrer, M., Bardaj´ ı, I., Valveny, E., Karatzas, D., Bunke, H.: Median graph computation by means of graph embedding into vector spaces. In: Graph Embedding for Pattern Analysis, pp. 45–71. Springer New York (2013). https://doi.org/10.1007/978-1-4614-4457-2 3 10

    work page doi:10.1007/978-1-4614-4457-2 2013

  7. [7]

    Computer Vision and Image Understanding 115(7), 919– 928 (2011)

    Ferrer, M., Karatzas, D., Valveny, E., Bardaji, I., Bunke, H.: A generic framework for median graph computation based on a recursive embed- ding approach. Computer Vision and Image Understanding 115(7), 919– 928 (2011). https://doi.org/10.1016/j.cviu.2010.12.010

    work page doi:10.1016/j.cviu.2010.12.010 2011

  8. [8]

    Pattern Recognition 43(4), 1642–1655 (2010)

    Ferrer, M., Valveny, E., Serratosa, F., Riesen, K., Bunke, H.: Generalized median graph computation by means of graph embed- ding in vector spaces. Pattern Recognition 43(4), 1642–1655 (2010). https://doi.org/10.1016/j.patcog.2009.10.013

    work page doi:10.1016/j.patcog.2009.10.013 2010

  9. [9]

    Soft Computing 10(1), 47–53 (2006)

    Hlaoui, A., Wang, S.: Median graph computation for graph clustering. Soft Computing 10(1), 47–53 (2006). https://doi.org/10.1007/s00500-005-0464- 1

    work page doi:10.1007/s00500-005-0464- 2006

  10. [10]

    IEEE Trans

    Jiang, X., Munger, A., Bunke, H.: On median graphs: properties, algo- rithms, and applications. IEEE Trans. on Pattern Analysis and Machine Intelligence 23(10), 1144–1151 (2001). https://doi.org/10.1109/34.954604

    work page doi:10.1109/34.954604 2001

  11. [11]

    Pattern Recognition Letters (2018)

    Moreno-Garc´ ıa, C.F., Serratosa, F., Jiang, X.: Correspondence edit dis- tance to obtain a set of weighted means of graph correspondences. Pattern Recognition Letters (2018). https://doi.org/10.1016/j.patrec.2018.08.027

    work page doi:10.1016/j.patrec.2018.08.027 2018

  12. [12]

    Journal of Combinatorial Opti- mization 17(1), 21–44 (2009)

    Mukherjee, L., Singh, V., Peng, J., Xu, J., Zeitz, M.J., Berezney, R.: Gen- eralized median graphs and applications. Journal of Combinatorial Opti- mization 17(1), 21–44 (2009). https://doi.org/10.1007/s10878-008-9184-7

    work page doi:10.1007/s10878-008-9184-7 2009

  13. [13]

    European Journal of Operational Research 254(2), 371– 384 (2016)

    Musmanno, L.M., Ribeiro, C.C.: Heuristics for the generalized median graph problem. European Journal of Operational Research 254(2), 371– 384 (2016). https://doi.org/10.1016/j.ejor.2016.03.048

    work page doi:10.1016/j.ejor.2016.03.048 2016

  14. [14]

    Scalable Funding of Bitcoin Micropayment Channel Networks

    Nienk¨ otter, A., Jiang, X.: Improved prototype embedding based general- ized median computation by means of refined reconstruction methods. In: Structural, Syntactic, and Statistical Pattern Recognition. pp. 107–117. Springer International Publishing (2016). https://doi.org/10.1007/978-3- 319-49055-7 10

    work page doi:10.1007/978-3- 2016

  15. [15]

    In: Structural, Syn- tactic, and Statistical Pattern Recognition

    Rebagliati, N., Sol´ e-Ribalta, A., Pelillo, M., Serratosa, F.: On the relation between the common labelling and the median graph. In: Structural, Syn- tactic, and Statistical Pattern Recognition. pp. 107–115. Springer Berlin Heidelberg (2012). https://doi.org/10.1007/978-3-642-34166-3 12

    work page doi:10.1007/978-3-642-34166-3 2012

  16. [16]

    Advances in Computer Vision and Pattern Recognition, Springer (2015)

    Riesen, K.: Structural Pattern Recognition with Graph Edit Distance. Advances in Computer Vision and Pattern Recognition, Springer (2015). https://doi.org/10.1007/978-3-319-27252-8 11

    work page doi:10.1007/978-3-319-27252-8 2015