Graph Spectral Embedding using the Geodesic Betweenness Centrality

Shay Deutsch, Stefano Soatto
Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, PMLR 206:10505-10519, 2023.

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v206-deutsch23a, title = {Graph Spectral Embedding using the Geodesic Betweenness Centrality}, author = {Deutsch, Shay and Soatto, Stefano}, booktitle = {Proceedings of The 26th International Conference on Artificial Intelligence and Statistics}, pages = {10505--10519}, year = {2023}, editor = {Ruiz, Francisco and Dy, Jennifer and van de Meent, Jan-Willem}, volume = {206}, series = {Proceedings of Machine Learning Research}, month = {25--27 Apr}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v206/deutsch23a/deutsch23a.pdf}, url = {https://proceedings.mlr.press/v206/deutsch23a.html}, 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.} }
Endnote
%0 Conference Paper %T Graph Spectral Embedding using the Geodesic Betweenness Centrality %A Shay Deutsch %A Stefano Soatto %B Proceedings of The 26th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2023 %E Francisco Ruiz %E Jennifer Dy %E Jan-Willem van de Meent %F pmlr-v206-deutsch23a %I PMLR %P 10505--10519 %U https://proceedings.mlr.press/v206/deutsch23a.html %V 206 %X 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.
APA
Deutsch, S. & Soatto, S.. (2023). Graph Spectral Embedding using the Geodesic Betweenness Centrality. Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 206:10505-10519 Available from https://proceedings.mlr.press/v206/deutsch23a.html.

Related Material