Dynamic Graph clustering

Nov 3^rd 2022

BMI/CS 775 Computational Network Biology�Fall 2022

Sushmita Roy

https://compnetbiocourse.discovery.wisc.edu

Goals for this lecture

• Network dynamics and dynamic modules on networks
• Classes of algorithms for identifying dynamic modules
• Dynamic Stochastic block models
• Spectral clustering and smoothing

​

​

Network dynamics

• What does modeling “dynamics” mean?
• The activity of nodes change over time and we want to model how this happens
• The network (structure or parameters) changes with time
• Structure can change due to changes at the node or edge level
• Local changes in connectivity could result in more global changes in community structure
• How to model changes in the community structure?

Dynamic modules

Sun et al., Entropy 2020

How might network modules change over time?

Adding nodes

Deleting nodes

Adding edges

Deleting edges

Sun et al., Entropy 2020

Notation

• T: denotes time points
• G₁.. G_T denotes a set of graphs across time
• E₁..E_T denotes the set of adjacency matrices across time
• Z₁.. Z_T denotes the set of communities

Problem definition

• Given
• G₁.. G_T representing graphs across time, where Gt denotes the graph at the t^th time point
• Do
• Identify the communities, Z₁.. Z_T for each time point
• (optionally) identify how communities change over time

​

Different ways of dynamic module identification

• Modularity based
• DynaMo, Zhuang et al., 2019
• See review https://www.ncbi.nlm.nih.gov/pmc/articles/PMC7516902
• Dynamic Stochastic block models
• DSBM
• HSBM
• Extended Kalman Filtering
• Spectral clustering and smoothing
• PisCES (Liu et al., 2017)
• Spectral fusion (Huang et al., 2018)

Goals for this lecture

• Network dynamics and dynamic modules on networks
• Classes of algorithms for identifying dynamic modules
• Dynamic Stochastic block models
• Spectral clustering and smoothing

​

​

​

Stochastic block model (SBM)

• Let G={V,E} be a graph, with vertex set V and edge set E
• Let M denote the membership of v in one of K groups
• SBM is a generative model of the edges given M for G
• Using an SBM we can compute a likelihood of a given module assignment to V
• We will use “hole” to denote the absence of an edge

Park and Bader BMC Bioinformatics 2011

SBM notation

Probability of a grouping structure from the stochastic block model

e_ij: Number of edges between groups i and j

t_ij: Number of possible edges between groups i and j

h_ij: Number of holes between groups i and j

h_ij = t_ij - e_ij

Probability of edge and hole patterns between group i and j

Park and Bader BMC Bioinformatics 2011

Stochastic block model for flat clustering for K=3 groups

Group 3 (7 vertices)

Group 1 (7 vertices)

Group 2 (6 vertices)

Stochastic block model for flat clustering for K=3 groups

Group 3

Group 1

Group 2

Probability of observing these interaction patterns

Learning an SBM

Maximum likelihood Parameter estimation

cluster of node i

Total number of vertices

number of edges between clusters k and l

number of holes between clusters k and l

Expectation maximization

• An framework to learn probability distribution parameters where there are hidden variables
• E step
• Estimate the “expected” values of hidden variables given the observed data
• M step
• Estimate the parameters given expected values

Inference

Dynamic stochastic block models

• SBMs are meant for static networks
• Dynamic SBMs extend SBMs to model dynamic membership
• Dynamic Stochastic Block Model. Yang et al 2011
• Extended Kalman Filter. Xu et al., 2014
• Gaussian approximation of the probabilities
• Hierarchical Stochastic block model. Amini et al 2021

​

Dynamic Stochastic Block Model

• Extends SBMs to handle dynamically evolving modules over time
• General idea:
• Assume we have the communities/clusters for time t
• Evolve the community assignment at t+1 from the previous time point
• We will need a “transition” matrix to model this evolution
• Fully Bayesian approach

​

Yang et al, Machine learning 2011

DSBM notation

DSBM generative model

How the modules change

How the edges get generated

DSBM Likelihood

Graphs at each time point

Module membership at each time point

Edge generation

Community/cluster evolution

DSBM Likelihood

Edge generation/Emission probability

Transition probability

Probability of observing interactions between communities k and l

DSBM learning

Simulated block structure at different noise levels

• 128 nodes, 4 communities
• Noise controlled by changing the intra and inter community probabilities
• To simulate dynamics, community assignment of 10% of the nodes were changed at each time point from the previous

Comparing DSBM to other algorithms

Extended Kalman Filters

• Dynamic stochastic blockmodels for time-evolving social networks
• Works with the logit of the module interaction probabilities
• Approximates the state and emissions with Gaussians

​

​

​

Xu et al, 2014

Module assignments

Adjacency matrices

Parameters of a Gaussian

Hierarchical Stochastic Block model

• A general approach based on SBMs to handle “multi-type” networks
• Each type could be a time point
• Similarity of module memberships between time points modeled via prior distributions

​

Amini et al, 2021

Adjacency matrices

Module interactions

Module assignment

HSBM compared to other algorithms

Results on simulated networks with different transition probabilities

Goals for this lecture

• Network dynamics and dynamic modules on networks
• Classes of algorithms for identifying dynamic modules
• Dynamic Stochastic block models
• Spectral clustering and smoothing

​

​

​

PisCES: Global spectral clustering in dynamic networks

​

• Based on spectral clustering and eigen vector smoothing framework
• The number of clusters per time point could vary

PisCES notation

• n: Number of nodes in the graph
• V_t : n X K denote the matrix of K eigen vectors of the graph Laplacian at time t
• U_t=V_t*V_t’ denotes a reconstructed graph of nodes

n

n

n

k

n

n

How to obtaining smoothly varying clusters over time?

Kmeans objective

Mean of cluster z_t(i)

mismatch in cluster assignment

This is in general hard to optimize. However, we can obtain a relaxed version of this as:

N

K

PisCES algorithm

• PisCES uses an iterative algorithm to find the constrained clustering solution:

Extracts eigen vectors and gets an outer product

First time point

Last time point

All other time points

PisCES algorithm key steps

Evaluation on simulated data

Application to real data

• Gene expression time course developing rhesus monkey
• Six pre-natal stages and four postnatal stages
• Samples were further divided into different brain regions
• The authors focused only on the medial pre-frontal cortex (mPFC)
• Goal: study changes in co-expression patterns over time
• Infer co-expression networks with WGCNA and then apply PisCES to the time-point specific networks

Identification of temporal modules in macaque brain co-expression networks

Zooming into a pair of time points

Finding module level differences

E40

E50

1. Some clusters exhibit a big change in density, e.g. cluster 2->3, 3->6, 9->10, 9->16.

2. Genes in some dense clusters, e.g. 7, 8, 13 move to 9

A gene subnetwork exhibiting substantial rewiring

NPG: Neural projection guidance

Conclusions

• Many social and biological networks are dynamic
• Dynamic module identification requires us to infer the network modules at each time point
• Algorithms differ based on
• Optimization framework
• Allowing variable number of communities
• Explicit model of community dynamics
• Dynamic Stochastic Block models are based on a probabilistic model of community structure
• PisCES used a spectral smoothing approach

Concluding remarks for graph clustering

• We talked about graph clustering and different types of extensions
• Standard classical algorithms
• Optimize modularity
• Kmeans on Graph Laplacian
• Graph neural networks and module detection
• AE based methods: Graphs with no attributes
• GCN based methods: Graphs with attributes
• Clustering graphs over time

References

• General review
• Sun Z, Sheng J, Wang B, Ullah A, Khawaja F. Identifying Communities in Dynamic Networks Using Information Dynamics. Entropy (Basel). 2020;22(4):E425. doi:10.3390/e22040425
• Spectral smoothing:
• Liu F, Choi D, Xie L, Roeder K. Global spectral clustering in dynamic networks. Proc Natl Acad Sci USA. 2018;115(5):927-932. doi:10.1073/pnas.1718449115
• Huang Q, Zhao C, Zhang X, Yi D. Community discovering in temporal network with spectral fusion. Chaos. 2019;29(4):043122. doi:10.1063/1.5086769
• Stochastic block models
• Amini AA, Paez MS, Lin L. Hierarchical Stochastic Block Model for Community Detection in Multiplex Networks. arXiv:190405330 [cs, stat]. Published online August 11, 2021. Accessed November 11, 2021. http://arxiv.org/abs/1904.05330
• Xu KS, Hero III AO. Dynamic stochastic blockmodels for time-evolving social networks. IEEE J Sel Top Signal Process. 2014;8(4):552-562. doi:10.1109/JSTSP.2014.2310294
• Yang T, Chi Y, Zhu S, Gong Y, Jin R. Detecting communities and their evolutions in dynamic social networks—a Bayesian approach. Mach Learn. 2011;82(2):157-189. doi:10.1007/s10994-010-5214-7
• Matias, C. & Miele, V. Statistical clustering of temporal networks through a dynamic stochastic block model. at http://arxiv.org/abs/1506.07464 (2016).

​

​