Ellipsoidal embeddings of graphs

arXiv (Cornell University)

Abstract

Due to their flexibility to represent almost any kind of relational data, graph-based models have enjoyed a 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 which 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 both 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 on the surface of a hyperellipsoid. Our method may be seen as an alternative to popular spectral embedding techniques, to which it shares certain similarities we discuss. To illustrate the utility of the embedding we conduct a case study in which we analyse 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,

   CNRS - Centre National de la Recherche Scientifique (France)

   CRIStAL - Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (Université de Lille - Campus scientifique - Bâtiment ESPRIT - Avenue Henri Poincaré - 59655 Villeneuve d’Ascq - France)

2. Antoine Aspeel

   University of Michigan

   Affiliation as printed

   Electrical Engineering and Computer Science Department , Univ. of Michigan , Ann Arbor , USA,

   University of Michigan [Ann Arbor] (500 Church Street Ann Arbor, MI 48109-1090 - United States)

3. Michael T. Schaub Aachen

   RWTH Aachen University

   Affiliation as printed

   RWTH Aachen University , North-Rhine Westphalia , Germany,

   RWTH - Rheinisch-Westfälische Technische Hochschule Aachen University (RWTH Aachen Templergraben 55 52062 Aachen (Hausanschrift) 52056 Aachen (Postanschrift) - Germany)

4. Jean‐Charles Delvenne

   UCLouvain · KU Leuven

   Affiliation as printed

   ICTEAM and CORE , Université catholique de Louvain , Belgium

   UCLouvain - Université catholique de Louvain (Belgium)