Shallow Unsupervised Graph Embedding

Oct 6^th 2026

BMI/CS 775 Computational Network Biology�Fall 2026

Anthony Gitter

https://bmi775.sites.wisc.edu

These slides, excluding third-party material, are licensed under CC BY-NC 4.0 by Sushmita Roy and Anthony Gitter

Topics in this section

• Shallow unsupervised graph embedding
• Graph neural networks
• Graph neural network extensions and limitations
• Experimental design and evaluation for graph machine learning
• Graph transformers
• Deep unsupervised graph embedding

Goals for today

• The case for learning representations in unsupervised problems for graphs

​

• Shallow, graph structure-based representations

​

• OhmNet: Application of node2vec for multi-tissue networks

Representation learning of graphs

Hamilton, Ying, Leskovec, 2018

Learning representations for unsupervised problems on graphs

• What do we mean by unsupervised learning on graphs?
• No labels/output variables
• Why learn representations for such problems?
• Problem of interest is unsupervised in nature, e.g. community detection
• Pre-training to learn task agnostic representations and finetune later
• Could improve performance even in supervised tasks
• How?
• Some form of “self-supervised” or “unsupervised” learning
• Encoder-decoder framework
• We will largely focus on node representations

​

From graphs to embeddings

DeepWalk embedding of Zachary Karate Club social network

Hamilton, Ying, Leskovec, 2018

Nodes in graph

You already know one way to do this!

Nodes in graph

What algorithm have we seen in class?

You already know one way to do this!

First 2 eigen vectors of the Zachary Karate Club graph

(Not the same embedding)

Overview of algorithms we will see

• Shallow, structure only
• Matrix factorization
• Random walk-based methods: Node2vec, DeepWalk

Goals for today

• The case for learning representations in unsupervised problems for graphs

​

• Shallow, graph structure-based representations

​

• Application of node2vec for multi-tissue networks

Notation

Unsupervised representation learning on graphs

Encoder-decoder framework of representation learning

Hamilton, Ying, Leskovec, 2018. Representation Learning on Graphs: Methods and Applications

Encoder-decoder framework

A set of training node pairs

Classes of node embedding methods

• Shallow embedding
• Matrix factorization-based methods
• Laplacian eigenmaps
• Graph factorization
• GraRep
• HOPE
• Random walk-based methods
• DeepWalk
• Node2vec
• Deep embedding (later)
• Graph autoencoders
• Deep Graph Infomax

​

Laplacian eigenmaps

• Encoder:

​

• Decoder:

​

​

• Loss function

​

​

Coming from the original graph

Graph factorization, GraRep, HOPE

Random-walk based methods

• Previous approaches used eigen decomposition which might not scale for large graphs
• Alternative methods are based on random walk statistics
• Key idea: nodes that co-occur in the same short random walks should have similar embeddings
• Encoders are similar to matrix factorization methods
• These measures are more flexible than matrix factorization
• DeepWalk
• Node2vec

Hamilton, Ying, Leskovec, 2018;

See also node2vec+ better handles edges weights. Liu et al. Bioinformatics 2023 http://doi.org/10.1093/bioinformatics/btad047

Random walk-based methods

• Random walk: Instead of deterministically traversing a graph, we can probabilistically transition from a vertex to its neighbor

Motivation for node2vec

• Node embedding can consider community structure or structure similarity
• DFS: Depth-first gives community structure
• BFS: Breadth-first gives structure similarity
• Since real graphs have a combination of community and structure similarity, we want to combine BFS or DFS style walk

​

Grover et al. 2016

Node2vec key steps

• Generate node neighborhoods

​

• Optimize an objective function that maximizes the probability of the neighborhoods

Node2vec: generating neighborhood

d_tx: Shortest path distance from t to x

distances wrt t

Node2vec: Objective function

Maximize the likelihood of neighborhoods

“Neighborhood” of u from sampling strategy S

Conditional independence assumption over individual source-neighbor pairs

Node2vec: Objective function

Likelihood of source-neighbor node pair

Node2vec implementation

• Important arguments:
• Graph structure
• Embedding dimension d
• Random walk length
• Random walks per node
• p
• q
• Number of negative samples per positive sample

Node2vec training

• Create positive samples
• Close node pairs from random walks using walk length, p, and q
• Create negative samples
• Node pairs from randomly sampled requested number of nodes from the graph
• Compute loss
• Positive loss term: encourage high similarity within each positive pair
• Negative loss term: encourage low similarity within each negative pair
• Sum positive and negative loss terms

Node2vec: effect of p and q

Grover et al. 2016

p = 1

q = 0.5

p = 1

q = 2

Les Misérables character co-appearance network: 77 nodes, 237 edges

Colors: clusters on learned embeddings

TopHat

Experiments: Node classification

• Consider standard supervised learning task of node classification
• Compare to spectral clustering, DeepWalk, LINE
• Use a one vs rest logistic regression classifier

Experiments: Link prediction

• Consider standard supervised learning task of link prediction
• Compare to spectral clustering, DeepWalk, LINE
• Evaluate with AUC

Goals for today

• The case for learning representations in unsupervised problems for graphs

​

• Shallow, graph structure-based representations

​

• OhmNet: Application of node2vec for multi-tissue networks

OhmNet: Predicting multicellular function through�multi-layer tissue networks

• Motivation:
• How to predict the function of a protein in a tissue-specific manner?
• Can we use the embeddings for different/multiple tasks?
• Requires explicit modeling of tissues
• Extract rich feature representations of proteins in each tissue-specific network
• Use these rich feature representations to predict tissue-specific function of proteins

​

​

Zitnik, M. & Leskovec, J. Predicting multicellular function through multi-layer tissue networks. Bioinformatics 33, i190–i198 (2017).

​

OhmNet representation of multi-layered networks

Tissue

Feature encoding in OhmNet

OhmNet overview

• OhmNet framework has two parts

​

• Single network objective: embeddings of nodes with similar neighborhoods should be similar

​

• Hierarchical dependency: nodes in nearby layers in the hierarchy have similar embeddings

​

Encoding each network

Incorporating the hierarchy

OhmNet objective

• This has two parts

Per network objective

Hierarchical part

OhmNet Algorithm

Sample neighborhoods

Go over all leaf nodes in the tissue tree

OhmNet Algorithm

Learn the encodings

OhmNet evaluation dataset

• 107 tissues with tissue-specific networks from Greene 2015
• Unweighted PPI has 21,557 nodes and 342,353 interactions
• Tissue-specific
• An edge exists in tissue t if either both partners are co-expressed
• OR one partner is expressed in the tissue and the other partner is ubiquitous
• Gene function
• 584 tissue-specific cellular functions covering 48 tissues
• All functions for a tissue were assigned to the leaf corresponding to the tissue

OhmNet prediction tasks

• Predict tissue-specific function
• Multi-node classification

​

• Transfer learning
• Transfer information from one or more layers to a target layer in tissue hierarchy

​

• Data visualization

Predicting cellular function

Transfer learning task

• For each target tissue t, train a classifier using all tissue network embeddings other than t

​

​

• Predict class using trained classifier for t
• no training

Predicting function in a transfer learning manner

Degradation in performance is expected, but only graceful degradation

Visualizing tissue-specific networks

OhmNet was used only on the brainstem and brain networks and project the nodes in a 2D space

OhmNet key points

• Task independent approach to embed nodes of multiple related networks
• Can accurately predict function in the same or transfer learning mode
• Can be used to visualize hierarchically related networks

Conclusions

• Representation learning on networks finds data-driven encodings that can be input into standard ML methods
• (Shallow) node embeddings can be based on matrix factorization and random walks
• Deep embeddings have the potential to address limitations of shallow embeddings
• Better use of node attributes
• Fewer parameters
• Generalize to new nodes and graphs (inductive)
• OhmNet: node2vec encoding that also uses relationship across samples

References

• Zitnik, M. & Leskovec, J. Predicting multicellular function through multi-layer tissue networks. Bioinformatics 33, i190–i198 (2017).
• Hamilton, W. L., Ying, R. & Leskovec, J. Representation Learning on Graphs: Methods and Applications. arXiv:1709.05584 [cs] (2018).
• Nelson, W. et al. To Embed or Not: Network Embedding as a Paradigm in Computational Biology. Front Genet 10, 381 (2019).
• Grover, A. & Leskovec, J. node2vec: Scalable Feature Learning for Networks. Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (2016).
• Check https://www.youtube.com/watch?v=3XTuhchTWd8&t=227s

​

​

​

DeepWalk

• In DeepWalk, the decoding function is defined as:

​

​

​

​

​

​

​

• Unbiased random walks
• Naively optimizing with this normalization term is expensive: DeepWalk uses node grouping and hierarchical softmax to reduce the number of nodes in the normalization term.

​

​

​

​

​

​

Perozzi et al. 2014