# DIGRAC: Digraph Clustering Based on Flow Imbalance

arXiv: https://arxiv.org/abs/2106.05194 · HTML: https://mlsanity.com/paper/2106.05194/

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 70 references that are in the map.
- First posted on arXiv 9 Jun 2021.

## Builds on (most cited first, 26 of 26)

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [From Louvain to Leiden: guaranteeing well-connected communities](https://mlsanity.com/paper/1810.08473/) (2018)
- [Detecting causal associations in large nonlinear time series datasets](https://mlsanity.com/paper/1702.07007/) (2017)
- [Gromov-Wasserstein Learning for Graph Matching and Node Embedding](https://mlsanity.com/paper/1901.06003/) (2019)
- [MagNet: A Neural Network for Directed Graphs](https://mlsanity.com/paper/2102.11391/) (2021)
- [Scalable Gromov-Wasserstein Learning for Graph Partitioning and Matching](https://mlsanity.com/paper/1905.07645/) (2019)
- [Directed Graph Convolutional Network](https://mlsanity.com/paper/2004.13970/) (2020)
- [MotifNet: a motif-based Graph Convolutional Network for directed graphs](https://mlsanity.com/paper/1802.01572/) (2018)
- [Granger Causality: A Review and Recent Advances](https://mlsanity.com/paper/2105.02675/) (2021)
- [Clustering and Community Detection in Directed Networks: A Survey](https://mlsanity.com/paper/1308.0971/) (2013)
- [Spectral-based Graph Convolutional Network for Directed Graphs](https://mlsanity.com/paper/1907.08990/) (2019)
- [Generalized Spectral Clustering via Gromov-Wasserstein Learning](https://mlsanity.com/paper/2006.04163/) (2020)
- [Hermitian matrices for clustering directed graphs: insights and applications](https://mlsanity.com/paper/1908.02096/) (2019)
- [Gromov-Wasserstein Factorization Models for Graph Clustering](https://mlsanity.com/paper/1911.08530/) (2019)
- [Higher-Order Spectral Clustering of Directed Graphs](https://mlsanity.com/paper/2011.05080/) (2020)
- [Evaluation of Community Detection Methods](https://mlsanity.com/paper/1807.01130/) (2018)
- [Graph Traversal with Tensor Functionals: A Meta-Algorithm for Scalable Learning](https://mlsanity.com/paper/2102.04350/) (2021)
- [Regularized spectral methods for clustering signed networks](https://mlsanity.com/paper/2011.01737/) (2020)
- [Evaluating accuracy of community detection using the relative normalized mutual information](https://mlsanity.com/paper/1501.03844/) (2015)
- [Anomaly Detection in Networks with Application to Financial Transaction Networks](https://mlsanity.com/paper/1901.00402/) (2019)
- [Optimal Kullback-Leibler Aggregation via Information Bottleneck](https://mlsanity.com/paper/1304.6603/) (2013)
- [Scalable Constrained Clustering: A Generalized Spectral Method](https://mlsanity.com/paper/1601.04746/) (2016)
- [Efficient method for estimating the number of communities in a network](https://mlsanity.com/paper/1706.02324/) (2017)
- [Core-Periphery Structure in Directed Networks](https://mlsanity.com/paper/1912.00984/) (2019)

## Built on by (most cited first, 15 of 15)

- [MSGNN: A Spectral Graph Neural Network Based on a Novel Magnetic Signed Laplacian](https://mlsanity.com/paper/2209.00546/) (2022)
- [Breaking the Entanglement of Homophily and Heterophily in Semi-supervised Node Classification](https://mlsanity.com/paper/2312.04111/) (2023)
- [PyTorch Geometric Signed Directed: A Software Package on Graph Neural Networks for Signed and Directed Graphs](https://mlsanity.com/paper/2202.10793/) (2022)
- [GNNRank: Learning Global Rankings from Pairwise Comparisons via Directed Graph Neural Networks](https://mlsanity.com/paper/2202.00211/) (2022)
- [LightDiC: A Simple yet Effective Approach for Large-scale Digraph Representation Learning](https://mlsanity.com/paper/2401.11772/) (2024)
- [DiRW: Path-Aware Digraph Learning for Heterophily](https://mlsanity.com/paper/2410.10320/) (2024)
- [Improving Graph Neural Networks by Learning Continuous Edge Directions](https://mlsanity.com/paper/2410.14109/) (2024)
- [Robust Angular Synchronization via Directed Graph Neural Networks](https://mlsanity.com/paper/2310.05842/) (2023)
- [Towards Data-centric Machine Learning on Directed Graphs: a Survey](https://mlsanity.com/paper/2412.01849/) (2024)
- [Toward Effective Digraph Representation Learning: A Magnetic Adaptive Propagation based Approach](https://mlsanity.com/paper/2501.11817/) (2025)
- [Understanding the Design Principles of Link Prediction in Directed Settings](https://mlsanity.com/paper/2502.15008/) (2025)
- [Toward Data-centric Directed Graph Learning: An Entropy-driven Approach](https://mlsanity.com/paper/2505.00983/) (2025)
- [Online Sparsification of Bipartite-Like Clusters in Graphs](https://mlsanity.com/paper/2508.05437/) (2025)
- [State Space Models over Directed Graphs](https://mlsanity.com/paper/2509.13735/) (2025)
- [Hierarchical Clustering and Signal Denoising on Digraphs](https://mlsanity.com/paper/2609.34670/) (2026)

## Abstract (arXiv)

Node clustering is a powerful tool in the analysis of networks. We introduce a graph neural network framework, named DIGRAC, to obtain node embeddings for directed networks in a self-supervised manner, including a novel probabilistic imbalance loss, which can be used for network clustering. Here, we propose textitdirected flow imbalance measures, which are tightly related to directionality, to reveal clusters in the network even when there is no density difference between clusters. In contrast to standard approaches in the literature, in this paper, directionality is not treated as a nuisance, but rather contains the main signal. DIGRAC optimizes directed flow imbalance for clustering without requiring label supervision, unlike existing graph neural network methods, and can naturally incorporate node features, unlike existing spectral methods. Extensive experimental results on synthetic data, in the form of directed stochastic block models, and real-world data at different scales, demonstrate that our method, based on flow imbalance, attains state-of-the-art results on directed graph clustering when compared against 10 state-of-the-art methods from the literature, for a wide range of noise and sparsity levels, graph structures, and topologies, and even outperforms supervised methods.