  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.
