On the Relation between the Common Labelling and the Median Graph

Nicola Rebagliati, Albert Solé-Ribalta, Marcello Pelillo, Francesc Serratosa

Introduction

In structural pattern recognition, representing objects as attributed graphs—where nodes and edges carry specific properties—is a standard approach. A fundamental challenge in this domain is finding a "representative" graph for a set of observations, a concept known as the Generalized Median Graph (GMG). The GMG serves as a structural "average," yet its computation is notoriously difficult due to a circular dependency: finding the median requires optimal matchings between the median and the set, but those matchings cannot be determined without the median itself.

To circumvent this, researchers often employ Common Labelling (CL). CL seeks a consistent set of matchings across all graphs simultaneously, bypassing the need for an initial median. While CL has been a successful heuristic for years, its formal mathematical relationship to the true GMG remained unproven. This paper provides the first rigorous proof linking these two problems, establishing that the cost of common labelling acts as a tight upper bound for the median graph's cost.

Methodology and Conceptual Framework

The authors establish their findings through mathematical proofs, assuming the graph comparison cost function is a metric (satisfying identity, positivity, symmetry, and the triangle inequality). The study explores two primary scenarios: general metric costs and weighted graphs using squared Euclidean distance.

Workflow of extracting attributed graphs and computing a prototype via common labelling.

To illustrate the practical application, the paper references electrical circuit sketches. As shown in Figure 1, resistors and components are extracted as nodes in an attributed graph. These graphs are then mapped to a "virtual node set" during the Common Labelling process to compute a prototype or "average" graph.

Theoretical Bounds and Key Insights

The core contribution of this work is the establishment of mathematical bounds between the optimal Common Labelling cost ($CL^*$) and the true Median Graph cost ($GM^*$).

The Bound of Two

The most significant result is the inequality: $$CL^* \ge GM^* \ge \frac{1}{2} CL^*$$ This theorem proves that the "error" introduced by using the Common Labelling approach instead of the true median is mathematically constrained. It guarantees that a low-cost common labelling will yield an approximated median graph that is structurally close to the theoretical ideal.

Geometric representation of the relationships between individual graphs, the true median, and the common labelling approximation.

As visualized in Figure 4, the relationships between the input graphs ($G_i$), the true median ($G^*$), and the common labelling result ($\bar{G}$) are governed by these distance metrics. The paper further proves that the distance between the approximated median and the true median is at most four times the cost of the true median ($d(\bar{G}, G^*) \le 4GM^*$).

The Euclidean Case

In the specific context of weighted graphs using squared Euclidean distance, the relationship becomes even more precise. The authors utilize Huygens' theorem to show that the two problems are equivalent: $\frac{1}{2} CL^* = GM^*$. In this common mathematical space, solving for common labelling is exactly equivalent to solving for the median graph.

Conclusion

This research provides the "missing link" that justifies the use of Common Labelling in structural pattern recognition. By proving these bounds, the authors validate years of heuristic-based research and provide a theoretical foundation for evaluating the quality of non-exact algorithms. While finding the optimal Common Labelling remains NP-hard, these results offer a framework for understanding the theoretical limits and performance of practical engineering applications in graph-based recognition.

Summary updated

Abstract

In structural pattern recognition, given a set of graphs, the computation of a Generalized Median Graph is a well known problem. Some methods approach the problem by assuming a relation between the Generalized Median Graph and the Common Labelling problem. However, this relation has still not been formally proved. In this paper, we analyse such relation between both problems. The main result proves that the cost of the common labelling upper-bounds the cost of the median with respect to the given set. In addition, we show that the two problems are equivalent in some cases.
BibTeX
@inproceedings{rebagliati2012relation,
  author = {Nicola Rebagliati and Albert Solé-Ribalta and Marcello Pelillo and Francesc Serratosa},
  title = {{On the Relation between the Common Labelling and the Median Graph}},
  booktitle = {SSPR/SPR},
  year = {2012},
  url = {https://openreview.net/forum?id=vFDVzuY0hGDj},
}
Figure