Ellipsoidal Embeddings of Graphs

SIAM Journal on Applied Mathematics, vol. 85, pp. 413–432

Abstract

Abstract. Due to their flexibility to represent almost any kind of relational data, graph-based models have enjoyed tremendous success over the past decades. While graphs are inherently only combinatorial objects, however, many prominent analysis tools are based on the algebraic representation of graphs via matrices such as the graph Laplacian, or on associated graph embeddings. Such embeddings associate to each node a set of coordinates in a vector space, a representation that can then be employed for learning tasks such as the classification or alignment of the nodes of the graph. As the geometric picture provided by embedding methods enables the use of a multitude of methods developed for vector space data, embeddings have thus gained interest from a theoretical as well as a practical perspective. Inspired by trace optimization problems, often encountered in the analysis of graph-based data, here we present a method to derive ellipsoidal embeddings of the nodes of a graph, in which each node is assigned a set of coordinates in a hyperellipsoid. Our method may be seen as an alternative to popular spectral embedding techniques, with which it shares certain similarities we discuss. To illustrate the utility of the embedding we conduct a case study in which we analyze synthetic and real world networks with modular structure, and compare the results obtained with known methods in the literature.

Authors 4

1. Michaël Fanuel

   Centre National de la Recherche Scientifique · Université de Lille · Centre de Recherche en Informatique, Signal et Automatique de Lille · Centrale Lille Institut

   Affiliation as printed

   Université de Lille, CNRS, Centrale Lille, UMR 9189-CRIStAL, F-59000 Lille, France

2. Antoine Aspeel

   University of Michigan

   Affiliation as printed

   Electrical Engineering and Computer Science Department, University of Michigan, Ann Arbor, MI 48109 USA

3. Michael T. Schaub Aachen

   RWTH Aachen University

   Affiliation as printed

   RWTH Aachen University, North-Rhine Westphalia, Germany

4. Jean‐Charles Delvenne

   UCLouvain · KU Leuven

   Affiliation as printed

   ICTEAM and CORE, Université catholique de Louvain, Louvain, Belgium