Community detection with nodal information

Haolei Weng, Yang Feng

Abstract

Community detection is one of the fundamental problems in the study of network data. Most existing community detection approaches only consider edge information as inputs, and the output could be suboptimal when nodal information is available. In such cases, it is desirable to leverage nodal information for the improvement of community detection accuracy. Towards this goal, we propose a flexible network model incorporating nodal information, and develop likelihood-based inference methods. For the proposed methods, we establish favorable asymptotic properties as well as efficient algorithms for computation. Numerical experiments show the effectiveness of our methods in utilizing nodal information across a variety of simulated and real network data sets.

Introduction

In network science, community detection aims to identify clusters of nodes that exhibit denser internal connections compared to their connections with the rest of the network. Traditionally, this task has been dominated by the Stochastic Block Model (SBM), which relies exclusively on the graph's adjacency matrix (edge information). However, modern datasets often provide rich metadata—or "nodal information"—such as user demographics in social networks or keywords in citation indices.

Ignoring these attributes represents a significant loss of information. When community membership is correlated with node attributes, integrating this data can drastically improve detection accuracy, particularly in sparse networks where edge data is insufficient. This paper introduces the Node-coupled Stochastic Block Model (NSBM), a mathematically rigorous framework designed to fuse edge and nodal information for superior community recovery.

The Node-coupled Stochastic Block Model (NSBM)

The NSBM framework integrates two distinct data generating processes into a single joint likelihood:

  1. The Edge Model: This follows a standard SBM where the probability of an edge existing between two nodes is determined by their respective community assignments.
  2. The Attribute Model: This utilizes a multi-logistic regression framework to link a node’s covariates (attributes) to its probability of belonging to a specific community.

By combining these, the model captures the dual nature of community structure: nodes in the same community are not only more likely to be connected but are also more likely to share similar characteristics.

Inference and Computational Strategy

Estimating the parameters of the NSBM is challenging because the likelihood functions are non-convex, making them prone to local optima. To address this, the authors propose a robust two-step inference algorithm:

Step 1: Initialization via Semidefinite Programming (SDP)

To avoid the pitfalls of random initialization, the algorithm begins with a convex relaxation of the community detection problem. By using Semidefinite Programming, the method obtains a "warm start" that is theoretically guaranteed to be in the neighborhood of the global optimum.

Step 2: Iterative Refinement

Starting from the SDP initialization, the model parameters are refined using likelihood-based methods. The authors explored three approaches: Maximum Likelihood (ML), Variational Expectation-Maximization (VEM), and Maximum Profile Likelihood (MPL). Among these, Variational EM was found to offer the best balance between computational efficiency and accuracy.

Experimental Evaluation

Simulation Studies

The model was tested under two primary conditions:

  • Scenario A (Well-specified): Data generated exactly according to the NSBM assumptions.
  • Scenario B (Misspecified): Data where the relationship between attributes and communities did not perfectly follow the logistic model, testing the framework's robustness.

In both scenarios, the inclusion of nodal information significantly outperformed edge-only methods. In cases where edge data alone achieved a Normalized Mutual Information (NMI) of 0.70, the NSBM pushed accuracy above 0.90.

Real-World Application: Manufacturing Company Data

The authors applied the NSBM to a dataset of 77 employees in a manufacturing company. The network consisted of information-sharing links, while nodal information included office location, tenure, and organizational level.

  • Edge-only NMI: 0.881
  • NSBM (Edges + Attributes) NMI: 0.920

This improvement demonstrates that even in high-quality networks, nodal information provides the necessary nuance to resolve ambiguous community boundaries.

Key Insights and Theoretical Contributions

  • The Sparsity Buffer: Nodal information acts as a critical buffer in sparse networks. When the number of edges is low, the attributes provide the signal necessary to maintain high detection accuracy.
  • Asymptotic Consistency: The paper provides mathematical proof that the NSBM estimators are consistent. As the network size increases, the probability of misclassifying a node approaches zero, provided the network density stays above a certain threshold.
  • Robustness to Model Misspecification: Even when the underlying attribute distribution does not perfectly match the model's logistic assumptions, the NSBM remains more effective than ignoring the attributes entirely.

Limitations and Future Work

While the NSBM is a powerful tool, several avenues for future research remain. Currently, the model assumes the number of communities ($K$) is known; future iterations could incorporate methods for automated $K$ estimation. Additionally, in high-dimensional settings where nodes have thousands of attributes, the model may require regularization techniques (like Lasso) to prevent overfitting. Finally, the authors note that in "ultra-sparse" networks, there exists a theoretical limit beyond which even nodal information cannot guarantee perfect recovery, a boundary that warrants further investigation.

Summary updated

Abstract

Community detection is one of the fundamental problems in the study of network data. Most existing community detection approaches only consider edge information as inputs, and the output could be suboptimal when nodal information is available. In such cases, it is desirable to leverage nodal information for the improvement of community detection accuracy. Towards this goal, we propose a flexible network model incorporating nodal information, and develop likelihood-based inference methods. For the proposed methods, we establish favorable asymptotic properties as well as efficient algorithms for computation. Numerical experiments show the effectiveness of our methods in utilizing nodal information across a variety of simulated and real network data sets.
BibTeX
@inproceedings{weng2022community,
  author = {Haolei Weng and Yang Feng},
  title = {{Community detection with nodal information}},
  booktitle = {Stat},
  year = {2022},
  url = {https://openreview.net/forum?id=QNhYjDIVJz},
}
Figure