The simplex geometry of graphs

Karel Devriendt, Piet Van MieghemJournal of Complex Networks 2019 · DOI

TL;DR

This paper introduces a novel geometric perspective on graphs by establishing an exact correspondence between a graph and a simplex (a higher-dimensional generalization of a triangle). This framework allows graph properties like connectivity, degrees, and eigenvalues to be directly translated into geometric invariants of the simplex, opening new avenues for graph analysis.

What Problem Does This Paper Address?

While graphs are fundamental to many scientific disciplines, they are typically analyzed using combinatorial, algebraic, or probabilistic methods. This paper addresses the challenge of finding a unifying geometric framework that can capture diverse graph properties. The authors highlight Miroslav Fiedler's work on "simplex geometry," which proposes a way to represent graphs as simplices, thereby bridging graph theory and geometry. This approach aims to provide a novel lens through which to understand graph structures and their inherent properties.

Methods

The core of this paper is the graph-simplex correspondence. This correspondence is established by using the Laplacian matrix of a graph. Specifically, the Laplacian matrix $Q$ of a graph $G$ with $N$ nodes is shown to be the Gram matrix of the vertex vectors of a simplex $S$ in $N-1$ dimensions. This means that the inner product of any two vertex vectors of the simplex is equal to the corresponding entry in the Laplacian matrix.

The vertex vectors of the simplex $S$ are derived from the eigendecomposition of the Laplacian matrix. This allows for a direct geometric interpretation of graph properties:

  • Node degrees correspond to the squared Euclidean distance from the simplex centroid to its vertices.
  • Link weights (or connectivity between nodes) correspond to the inner product of vertex vectors.
  • Cut sizes (global connectivity) are related to the lengths of centroid vectors of simplex faces.
  • Laplacian eigenvalues are related to the semi-axes of the Steiner ellipsoid, a unique ellipsoid associated with the simplex.

The paper also introduces the concept of an inverse simplex $S^+$, whose vertices are determined by the pseudoinverse of the Laplacian matrix. This inverse simplex has its own geometric properties that are dual to the original simplex and also relate to graph properties.

Datasets

Not discussed in the paper. The paper focuses on theoretical concepts and mathematical derivations rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Graphs as Geometric Objects: The most striking insight is that a graph can be precisely represented as a geometric object (a simplex) in a high-dimensional space. This transforms abstract graph properties into tangible geometric features.
  • Unifying Framework: The graph-simplex correspondence offers a powerful unifying framework. Properties that are typically studied using different methods (e.g., spectral properties via eigenvalues, connectivity via adjacency) are all captured within the geometry of the simplex.
  • Dual Simplex for Dual Properties: The introduction of the inverse simplex $S^+$ provides a dual geometric representation, mirroring dual graph properties and offering complementary insights.
  • Geometric Interpretation of NP-Hardness: The paper connects graph problems like Max-Cut (which is NP-hard) to geometric problems of finding extremal altitudes in simplices, suggesting that the inherent difficulty of these graph problems is reflected in their geometric counterparts.
  • Steiner Ellipsoid and Eigenvalues: The unique Steiner ellipsoid associated with a simplex has semi-axes directly proportional to the Laplacian eigenvalues, providing a geometric interpretation for spectral graph theory.

Key Results

  • An exact correspondence is established between a connected, undirected graph $G$ on $N$ nodes and a simplex $S$ in $N-1$ dimensions, where the Laplacian matrix $Q$ of $G$ is the Gram matrix of the simplex's vertex vectors.
  • Graph properties such as node degrees, link weights, and cut sizes are shown to have direct geometric interpretations as distances, inner products, and lengths of centroid vectors within the simplex.
  • Laplacian eigenvalues are linked to the semi-axes of the Steiner ellipsoid of the simplex.
  • The number of spanning trees of a graph is shown to be proportional to the volume of its corresponding simplex and its Steiner ellipsoid.
  • The paper demonstrates that the Max-Cut problem on graphs is equivalent to finding extremal altitudes in the inverse simplex, highlighting the NP-completeness of this geometric problem.

Limitations and Future Work

Limitations: * The paper focuses on connected, undirected graphs. The extension to directed or disconnected graphs is not explicitly discussed. * While the paper introduces the correspondence and some basic connections, it acknowledges that this is a focused overview and not an exhaustive exploration of Fiedler's entire body of work.

Future Work: The authors suggest several promising directions for further research:

  • Effective Resistance: Investigating the relationship between the squared distance between vertices in the inverse simplex and the effective resistance of a graph, which is a well-studied graph property.
  • Inverse Relation of Resistance and Laplacian: Exploring Fiedler's earlier work on the inverse relation between the effective resistance matrix and the Laplacian matrix, and its geometric implications for the simplex.
  • Facet Angles: Studying the geometric implications of the angles between facets of the inverse simplex, which are related to graph properties and could offer new insights, especially for non-obtuse angles in simplices derived from graphs with non-negative link weights.
  • Generalization to Other Graph Types: Extending the graph-simplex correspondence to other types of graphs (e.g., directed graphs, weighted graphs with negative weights) and exploring the resulting geometric structures.
  • Algorithmic Applications: Developing new algorithms for graph problems that leverage the geometric interpretations provided by the simplex representation.

Summary updated

Abstract

Abstract Graphs are a central object of study in various scientific fields, such as discrete mathematics, theoretical computer science and network science. These graphs are typically studied using combinatorial, algebraic or probabilistic methods, each of which highlights the properties of graphs in a unique way. Here, we discuss a novel approach to study graphs: the simplex geometry (a simplex is a generalized triangle). This perspective, proposed by Miroslav Fiedler, introduces techniques from (simplex) geometry into the field of graph theory and conversely, via an exact correspondence. We introduce this graph-simplex correspondence, identify a number of basic connections between graph characteristics and simplex properties, and suggest some applications as example.
BibTeX
@article{devriendt2019simplex,
  author = {Karel Devriendt and Piet Van Mieghem},
  title = {{The simplex geometry of graphs}},
  journal = {Journal of Complex Networks},
  year = {2019},
  doi = {10.1093/comnet/cny036},
}
Figure