Graph Spectral Embedding using the Geodesic Betweenness Centrality

Shay Deutsch, Stefano Soatto

Abstract

We introduce the Graph Sylvester Embedding (GSE), an unsupervised graph representation of local similarity, connectivity, and global structure. GSE uses the solution of the Sylvester equation to capture both network structure and neighborhood proximity in a single representation. Unlike embeddings based on the eigenvectors of the Laplacian, GSE incorporates two or more basis functions, for instance using the Laplacian and the affinity matrix. Such basis functions are constructed not from the original graph, but from one whose weights measure the centrality of an edge (the fraction of the number of shortest paths that pass through that edge) in the original graph. This allows more flexibility and control to represent complex network structure and shows significant improvements over the state of the art when used for data analysis tasks such as predicting failed edges in material science and network alignment in the human-SARS CoV-2 protein-protein interactome.

Introduction

Graph embeddings, which map nodes into low-dimensional vector spaces, are fundamental to modern network analysis. Traditional methods, such as Laplacian Eigenmaps, often rely on a "smoothness" assumption: nodes that are connected in the graph should be close in the embedding space. While effective for capturing local similarity, this approach frequently fails to represent structural similarity—where nodes may share functional roles (e.g., acting as "bridges" between communities) despite being distant in the network. The Graph Sylvester Embedding (GSE) addresses this by balancing local connectivity with global topological importance.

Methodology

The GSE framework integrates three key components to create a comprehensive representation of graph structure.

1. Betweenness Centrality Graph (BCG)

Instead of operating directly on the original graph weights, GSE transforms the graph into a Betweenness Centrality Graph. It calculates the Edge Betweenness Centrality (EBC), defined as the fraction of all shortest paths passing through a specific edge. This transformation highlights edges that serve as critical bottlenecks or bridges, effectively revealing the network's "skeleton."

2. The Sylvester Equation

To fuse different perspectives of the graph, GSE solves the discrete-time Sylvester equation: $$W^{BE} X L^{BE} - X = I$$ where $W^{BE}$ is the affinity matrix representing local similarity and $L^{BE}$ is the Laplacian representing global structure, both derived from the BCG. The solution $X$ captures the complex interplay between these two operators.

Overview of the Graph Sylvester Embedding (GSE) pipeline.

3. Spectral Descriptors

The solution $X$ is further processed using spectral descriptors, such as the Spectral Graph Wavelet (SGW) transform. This allows the embedding to capture features across multiple scales, from immediate neighborhoods to broad structural patterns. Importantly, the resulting embedding is invariant to node reordering, a critical property for tasks like network alignment.

Experimental Evaluation

GSE was evaluated on two distinct domains: material science and bioinformatics.

Predicting Material Failure

In disordered 2D lattices representing granular materials, the task was to predict structural failure (fracture) based on network topology. GSE, utilizing the SGW descriptor, achieved an average success rate of 86.8%, significantly outperforming Laplacian Eigenmaps (70.1%) and node2vec (61.4%).

Protein Network Alignment

GSE was applied to the alignment of human protein-protein interaction (PPI) networks related to SARS-CoV-2. The goal was to identify corresponding proteins across different networks based on their structural roles.

Illustration of network alignment using GSE.

On the STRING dataset, GSE achieved 76.4% accuracy, vastly exceeding specialized alignment algorithms like Isorank (23%) and iNEAT (37%). This demonstrates GSE's superior ability to capture functional structural roles in biological systems.

Conclusion

Graph Sylvester Embedding (GSE) provides a robust, unsupervised method for capturing both local and global graph properties. By leveraging edge betweenness centrality and the Sylvester equation, it offers a more nuanced representation than traditional spectral methods. While the computational complexity of calculating EBC remains a challenge for massive networks, GSE's performance in material science and bioinformatics highlights its potential for complex structural analysis. Future work will focus on optimizing EBC computation and extending the framework to dynamic and multi-layer graphs.

Summary updated

Abstract

We introduce the Graph Sylvester Embedding (GSE), an unsupervised graph representation of local similarity, connectivity, and global structure. GSE uses the solution of the Sylvester equation to capture both network structure and neighborhood proximity in a single representation. Unlike embeddings based on the eigenvectors of the Laplacian, GSE incorporates two or more basis functions, for instance using the Laplacian and the affinity matrix. Such basis functions are constructed not from the original graph, but from one whose weights measure the centrality of an edge (the fraction of the number of shortest paths that pass through that edge) in the original graph. This allows more flexibility and control to represent complex network structure and shows significant improvements over the state of the art when used for data analysis tasks such as predicting failed edges in material science and network alignment in the human-SARS CoV-2 protein-protein interactome.
BibTeX
@inproceedings{deutsch2023graph,
  author = {Shay Deutsch and Stefano Soatto},
  title = {{Graph Spectral Embedding using the Geodesic Betweenness Centrality}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2023},
  url = {https://openreview.net/forum?id=5CDQP692zB},
}
Figure