Empirical geodesic graphs and CAT(k) metrics for data analysis

A methodology is developed for data analysis based on empirically constructed geodesic metric spaces. For a probability distribution, the length along a path between two points can be defined as the amount of probability mass accumulated along the path. The geodesic, then, is the shortest such path and defines a geodesic metric. Such metrics are transformed in a number of ways to produce parametrised families of geodesic metric spaces, empirical versions of which allow computation of intrinsic means and associated measures of dispersion. These reveal properties of the data, based on geometry, such as those that are difficult to see from the raw Euclidean distances. Examples of application include clustering and classification. For certain parameter ranges, the spaces become CAT(0) spaces and the intrinsic means are unique. In one case, a minimal spanning tree of a graph based on the data becomes CAT(0). In another, a so-called “metric cone” construction allows extension to CAT(k) spaces. It is shown how to empirically tune the parameters of the metrics, making it possible to apply them to a number of real cases.

Funding was provided by JST, PRESTO (JPMJPR14E3) and JSPS, KAKENHI (26280009,16K02843), Japan. The first author would like to thank Masayuki Sakai, Takaaki Koike and Tatsuhiro Aoshima for their excellent computation and visualization of the results. He also appreciates Reiko Miyaoka and Hiroshi Kokubu for their helpful and encouraging advice.

Authors and Affiliations

1. Keio University, 3-14-1 Hiyoshi, Kohoku-ku, Yokohama, 223-8522, Japan

   Kei Kobayashi

2. London School of Economics, Houghton Street, London, WC2A 2AE, UK

   Henry P. Wynn

Corresponding author

Correspondence to Kei Kobayashi.

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

JST PREST, JSPS KAKENHI Grant Numbers 16K02843 and 26280009.

A Proof of Theorem 6

(1) Denote the mapped points of a, b, c and x by the projection \(\tilde{{\mathcal {X}}}_\beta \rightarrow {\mathcal {X}}_\beta \) as A, B, C and X, respectively, as shown in Fig. 14 (left). Denote the origin of the metric cone as O. If the sum of the lengths of the geodesics \({\widetilde{AB}}\), \({\widetilde{AC}}\) and \({\widetilde{BC}}\) in \({\mathcal {X}}_\beta \) exceeds \(2\pi \beta \), it is easy to see that the cone spanned by \({\overline{ab}} \cup {\overline{ac}} \cup {\overline{bc}}\) becomes CAT(0) and \(\varDelta abc\) satisfies the CAT(0) property. Therefore, assume that \(|{\widetilde{AB}}|+|{\widetilde{AC}}|+|{\widetilde{BC}}|\le 2 \pi \beta \).

The cone spanned by geodesics \({\overline{ab}}\), \({\overline{ac}}\), \({\overline{bc}}\) and \({\overline{ax}}\) (left) and the cone spanned by a comparison triangle \(\varDelta a'b'c'\) (right)

Full size image

Next, let \(\varDelta a'b'c'\) be a comparison triangle of \(\varDelta abc\) and let \(x'\) be a point on a geodesic \(\overline{b'c'}\) such that \(|{\overline{bx}}|=|\overline{b'x'}|\). Thus, \(|\overline{a'x'}|< |{\overline{ax}}|\). Arrange the points \(a'\), \(b'\) and \(c'\) in a three-dimensional Euclidean space with origin \(O'\) such that the lengths of \(\overline{O'a'}\), \(\overline{O'b'}\) and \(\overline{O'c'}\) are equal to the lengths of \({\overline{Oa}}\), \({\overline{Ob}}\) and \({\overline{Oc}}\), respectively. Denote the radial projection of \(a'\), \(b'\), \(c'\) and \(x'\) to a unit sphere as \(A'\), \(B'\), \(C'\) and \(X'\), respectively, as shown in Fig. 14 (right). By the definition of a metric cone, \(|{\overline{Ox}}|=|\overline{O'x'}|\) and the geodesics \(\widetilde{A'B'}\), \(\widetilde{A'C'}\), \(\widetilde{B'C'}\) and \(\widetilde{A'X'}\) in the unit sphere are arcs satisfying \(|\widetilde{A'B'}|=|{\widetilde{AB}}|\), \(|\widetilde{A'C'}|=|{\widetilde{AC}}|\), \(|\widetilde{B'C'}|=|{\widetilde{BC}}|\) and \(|\widetilde{B'X'}|=|{\widetilde{BX}}|\).

From the argument above, \(|\widetilde{A'B'}|+|\widetilde{A'C'}|+|\widetilde{B'C'}|= |{\widetilde{AB}}|+|{\widetilde{AC}}|+|{\widetilde{BC}}|\le 2 \pi \). Since the unit sphere has a positive constant curvature and \({\mathcal {X}}_\beta \) is CAT(0), \(|\widetilde{A'X'}|> |{\widetilde{AX}}|\). However, since \(|{\overline{Oa}}|=|\overline{O'a'}|\) and \(|{\overline{Ox}}|=|\overline{O'x'}|\), \(|\widetilde{A'X'}|> |{\widetilde{AX}}|\) implies that \(|\widetilde{a'x'}|> |{\widetilde{ax}}|\) by the property of a metric cone. Thus, \(\varDelta abc\) has CAT(0) property and (1) of the theorem is proved.

(2) Assume that \(0<\beta _1<\beta _2<\infty \) and a metric cone \(\tilde{{\mathcal {X}}}_{\beta _1}\) is not CAT(0) for proving the latter half of the theorem by contradiction. Then, there is a geodesic triangle \(\varDelta a_1 b_1 c_1\) in \(\tilde{{\mathcal {X}}}_{\beta _1}\) and a point \(x_1\) on the geodesic \(\overline{b_1 c_1}\) such that the geodesic \(\overline{a_1 x_1}\) is longer than the corresponding geodesic of a comparison triangle. By defining \(A_1, B_1, C_1, X_1,a'_1,b'_1,c'_1,x'_1,A'_1, B'_1, C'_1\) and \(X'_1\) as above, we can say that \(|\widetilde{A_1 X_1}|>|\widetilde{A'_1 X'_1}|\).

Next, each of \(A_1, B_1, C_1\) and \(X_1\) corresponds to a point in \({\mathcal {X}}_{\beta _1}\) and we can consider the corresponding points \(A_2, B_2, C_2\) and \(X_2\) in the other metric cone \(\tilde{{\mathcal {X}}}_{\beta _2}\). When restricted to \({\mathcal {X}}_{\beta _1}\), a geodesic \(\widetilde{A_1 X_1}\) is just a rescaling of \(\widetilde{A_2 X_2}\) and \(|\widetilde{A_1 X_1}|=\frac{\beta _1}{\beta _2}|\widetilde{A_2 X_2}|\).

Now, \(\varDelta A_2'B_2'C_2'\) is a geodesic triangle on the unit sphere, but after rescaling by \(\frac{\beta _2}{\beta _1}\), we can get a geodesic triangle \(\varDelta A_2''B_2''C_2''\) on a sphere of radius \(\frac{\beta _2}{\beta _1}\) whose edges have the same length as \(\varDelta A_1'B_1'C_1'\). By a known result on spherical triangles with the same edge lengths on different spheres, a larger radius implies a “thinner” triangle and \(|\widetilde{A_1 X_1}|<|\widetilde{A_2'' X_2''}|\) where \(X_2''\) is a point on the geodesic \(\widetilde{B_2'' C_2''}\) such that \(|\widetilde{B_1 X_1}|=|\widetilde{B_2'' X_2''}|\).

Combining all the arguments gives

Select a non-degenerate geodesic triangle in \(\tilde{{\mathcal {X}}}_{\beta _2}\) by selecting arbitrary points \(a_2,b_2\) and \(c_2\) on the geodesics \(\overline{OA_2}\), \(\overline{OB_2}\) and \(\overline{OC_2}\) in \(\tilde{{\mathcal {X}}}_{\beta _2}\), respectively, and let \(x_2\) be the intersection point of \(\overline{OX_2}\) and \(\overline{b_2 c_2}\). Then, by \(|\widetilde{A_2 X_2}|>|\widetilde{A'_2 X'_2}|\), we can say that \(|\overline{a_2 x_2}|>|\overline{a'_2 x'_2}|\). This implies that \(\tilde{{\mathcal {X}}}_{\beta _2}\) is not CAT(0) and (2) of the theorem is proved.

(3) For \(k=0\), the statement holds by (1). For \(k>0\) and \(\beta \le \pi \), it is sufficient to prove for \(\beta =\pi /\sqrt{k}\) by (2). Let \(\varDelta abc\) be a geodesic triangle in \(\tilde{{\mathcal {X}}}_\beta \) and let \(\varDelta ABC\) be a geodesic triangle in \({\mathcal {X}}_\beta \). Let A, B, C be the projection of a, b, c, respectively. If the perimeter of \(\varDelta ABC\) is longer than or equal to \(2\pi \), the cone spanned by the perimeter becomes CAT(0) by the same argument as that for (1). Therefore, \(\varDelta abc\) is CAT(0) and satisfies the CAT(0) property.

If the perimeter of \(\varDelta ABC\) is smaller than \(2\pi \), since \({\mathcal {X}}\) is CAT(k) and \({\mathcal {X}}_\beta \) is CAT(1), for any \(X\in {\widetilde{BC}}\), \({\widetilde{BX}}\) is shorter than the corresponding great arc \(\widetilde{B'X'}\) of a comparison triangle \(\varDelta A'B'C'\), which is a spherical triangle on the unit sphere. Since a comparison triangle \(\varDelta a'b'c'\) of \(\varDelta abc\) can be embedded on the cone spanned by \(\varDelta A'B'C'\), \({\widetilde{bx}}\) is shorter than the corresponding line segment \(\widetilde{b'x'}\). This means the \(\varDelta abc\) satisfies the CAT(0) property. \(\square \)

Reprints and permissions