Shay Deutsch: Spectral Embedding of Graph Networks

We introduce an unsupervised graph embedding that trades off local node similarity and connectivity and global structure. Our proposed graph embedding captures the structure of a graph with both local and global characteristics by incorporating basis functions that can be derived from the spectral representation of a graph. The key idea is to transform the given graph into one whose weights measure the centrality of an edge by the fraction of the number of shortest paths that pass through that edge and employ its spectral proprieties in the representation. We propose two different approaches: the first, is rooted in the study of signal localization on irregular graphs, and it trades off vertex and spectral domains to balance representations that capture the local and structural similarity between the graph nodes. The second, called Graph Sylvester Embeddings (GSE), is motivated by similar considerations and is derived from solving a Sylvester equation. The proposed Graph Sylvester Embeddings allow more flexibility and control beyond scalar modulation between two basis functions. Testing the resulting graph network representation shows significant improvement over the state of the art in data analysis tasks including social networks and material science. We also test our method on node classification from the human-SARS CoV-2 protein-protein interactome.