Abstract
Most real-world networks contain well-defined community structures where nodes are densely connected internally within communities. To learn from these networks, we develop MarkovGNN that captures the formation and evolution of communities directly in different convolutional layers. Unlike most Graph Neural Networks (GNNs) that consider a static graph at every layer, MarkovGNN generates different stochastic matrices using a Markov process and then uses these community-capturing matrices in different layers. MarkovGNN is a general approach that could be used with most existing GNNs. We experimentally show that MarkovGNN outperforms other GNNs for clustering, node classification, and visualization tasks.
Introduction
Standard message-passing Graph Neural Networks (GNNs), such as GCN or GAT, typically rely on a static graph structure across all layers. While stacking layers allows nodes to gather information from wider neighborhoods, this approach suffers from three primary issues: over-smoothing, where node embeddings become indistinguishable; neighbor explosion, which creates computational bottlenecks; and a failure to explicitly prioritize intra-community messages over inter-community ones.
MarkovGNN addresses these challenges by using a Markov diffusion process to generate a sequence of increasingly community-aware, sparsified graphs. By feeding a different, evolved graph into each GNN layer, MarkovGNN acts as a plug-and-play module that improves performance on networks with strong community structures while remaining computationally efficient.
Methodology
MarkovGNN introduces a dynamic topological approach. Instead of a single static graph, it utilizes a series of matrices generated by a Markov Diffusion Process. Before training, the algorithm simulates how random walks become trapped in natural graph communities through three iterative operations:
- Expansion: Squaring the adjacency matrix to simulate random walks and expand neighborhoods.
- Inflation: Applying an element-wise power to the matrix to amplify high-probability paths (intra-community) and weaken low-probability paths (inter-community).
- Pruning: Dropping edge weights below a threshold to maintain sparsity.
Rather than using only the final converged matrix, MarkovGNN saves intermediate matrices ($M_1, M_2, \dots, M_k$) and assigns them to corresponding GNN layers. This allows the network to "zoom in" on communities as depth increases. Residual connections are incorporated to support deeper architectures without degradation.
Experimental Setup
The framework was evaluated on eight standard benchmark graphs, stratified by their Average Clustering Coefficient (ACC) to measure community strength:
- High ACC (Strong communities): USAir, Chameleon, Squirrel, Email
- Low ACC (Weak communities): Cora, Citeseer, PPI, Actor
Key Results and Discussion
MarkovGNN variants (e.g., MarkovGCN, MarkovGAT) consistently outperformed base models and diffusion baselines like GDC in clustering metrics such as the Adjusted Rand Index (ARI). The performance gains were most significant on datasets with high clustering coefficients.
Beyond accuracy, MarkovGNN offers substantial computational advantages. The pruning step prevents neighbor explosion, making deeper layers cheaper to compute. MarkovGCN demonstrated speedups of 10x to 100x over baselines like GraphSAINT. For instance, on the USAir dataset, MarkovGCN trained in 7.7 seconds, compared to 212.4 seconds for GraphSAINT. Furthermore, t-SNE visualizations confirm that MarkovGNN produces cleaner, better-separated clusters than vanilla GCNs.
Conclusion and Limitations
MarkovGNN represents a paradigm shift from static to dynamic layer-wise topology. While highly effective for graphs with inherent community structures, its advantages are less pronounced on graphs with low clustering coefficients (e.g., Cora or Citeseer). Future work may explore alternative dynamic graph generation processes to extend these benefits to networks lacking strong homophily.
Summary updated