# Trading off Quality for Efficiency of Community Detection: An Inductive Method across Graphs

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 24 of its 62 references that are in the map.
- First posted on arXiv 29 Sep 2022.

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

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [node2vec: Scalable Feature Learning for Networks](https://mlsanity.com/paper/1607.00653/) (2016)
- [DeepWalk: Online Learning of Social Representations](https://mlsanity.com/paper/1403.6652/) (2014)
- [Cluster-GCN: An Efficient Algorithm for Training Deep and Large Graph Convolutional Networks](https://mlsanity.com/paper/1905.07953/) (2019)
- [Community Detection and Stochastic Block Models](https://mlsanity.com/paper/1703.10146/) (2017)
- [Network Embedding as Matrix Factorization: Unifying DeepWalk, LINE, PTE, and node2vec](https://mlsanity.com/paper/1710.02971/) (2017)
- [Identity-aware Graph Neural Networks](https://mlsanity.com/paper/2101.10320/) (2021)
- [Adversarially Regularized Graph Autoencoder for Graph Embedding](https://mlsanity.com/paper/1802.04407/) (2018)
- [A Survey of Community Detection Approaches: From Statistical Modeling to Deep Learning](https://mlsanity.com/paper/2101.01669/) (2021)
- [End to end learning and optimization on graphs](https://mlsanity.com/paper/1905.13732/) (2019)
- [PaSca: a Graph Neural Architecture Search System under the Scalable Paradigm](https://mlsanity.com/paper/2203.00638/) (2022)
- [Efficient Monte Carlo and greedy heuristic for the inference of stochastic block models](https://mlsanity.com/paper/1310.4378/) (2013)
- [Billion-scale Network Embedding with Iterative Random Projection](https://mlsanity.com/paper/1805.02396/) (2018)
- [Homogeneous Network Embedding for Massive Graphs via Reweighted Personalized PageRank](https://mlsanity.com/paper/1906.06826/) (2019)
- [GRAND+: Scalable Graph Random Neural Networks](https://mlsanity.com/paper/2203.06389/) (2022)
- [20 years of network community detection](https://mlsanity.com/paper/2208.00111/) (2022)
- [GAP: Generalizable Approximate Graph Partitioning Framework](https://mlsanity.com/paper/1903.00614/) (2019)
- [Scalable detection of statistically significant communities and hierarchies, using message-passing for modularity](https://mlsanity.com/paper/1403.5787/) (2014)
- [Local Graph Clustering with Network Lasso](https://mlsanity.com/paper/2004.12199/) (2020)
- [Community Detection via Maximization of Modularity and Its Variants](https://mlsanity.com/paper/1507.00787/) (2015)
- [Community detection using fast low-cardinality semidefinite programming](https://mlsanity.com/paper/2012.02676/) (2020)

## Abstract (arXiv)

Many network applications can be formulated as NP-hard combinatorial optimization problems of community detection (CD). Due to the NP-hardness, to balance the CD quality and efficiency remains a challenge. Most existing CD methods are transductive, which are independently optimized only for the CD on a single graph. Some of these methods use advanced machine learning techniques to obtain high-quality CD results but usually have high complexity. Other approaches use fast heuristic approximation to ensure low runtime but may suffer from quality degradation. In contrast to these transductive methods, we propose an alternative inductive community detection (ICD) method across graphs of a system or scenario to alleviate the NP-hard challenge. ICD first conducts the offline training of an adversarial dual GNN on historical graphs to capture key properties of the system. The trained model is then directly generalized to new unseen graphs for online CD without additional optimization, where a better trade-off between quality and efficiency can be achieved. ICD can also capture the permutation invariant community labels in the offline training and tackle the online CD on new graphs with non-fixed number of nodes and communities. Experiments on a set of benchmarks demonstrate that ICD can achieve a significant trade-off between quality and efficiency over various baselines.