Source-linked AI summary
Community Detection in Networks with Node Attributes
Jaewon Yang, Julian McAuley, Jure Leskovec
TL;DR
Community detection often uses either network structure or node attributes, despite communities reflecting both. CESNA jointly models these sources with hard overlapping memberships, achieving stronger accuracy and scalability while identifying attributes relevant to each community.
Problem
Existing community detection and clustering methods typically focus separately on network structure or node attributes, limiting their use of the available information.
Method
CESNA uses a generative model in which hard community memberships generate both network structure and node attributes, fitted by block-coordinate ascent.
Results
CESNA outperforms every baseline at 95% significance on philosophers, Flickr, and Twitter, and nearly all baselines on Facebook.
Takeaways & Limitations
CESNA supports overlapping, non-overlapping, and hierarchically nested communities while helping interpret them through relevant node attributes.
Abstract
from arXiv · showhide
Community detection algorithms are fundamental tools that allow us to uncover organizational principles in networks. When detecting communities, there are two possible sources of information one can use: the network structure, and the features and attributes of nodes. Even though communities form around nodes that have common edges and common attributes, typically, algorithms have only focused on one of these two data modalities: community detection algorithms traditionally focus only on the network structure, while clustering algorithms mostly consider only node attributes. In this paper, we develop Communities from Edge Structure and Node Attributes (CESNA), an accurate and scalable algorithm for detecting overlapping communities in networks with node attributes. CESNA statistically models the interaction between the network structure and the node attributes, which leads to more accurate community detection as well as improved robustness in the presence of noise in the network structure. CESNA has a linear runtime in the network size and is able to process networks an order of magnitude larger than comparable approaches. Last, CESNA also helps with the interpretation of detected communities by finding relevant node attributes for each community.
I. INTRODUCTION
CESNA addresses the limitation of treating network structure and node attributes separately by modeling them jointly for overlapping community detection. It combines hard memberships, community–attribute dependence, and scalable fitting, while improving accuracy, scalability, and community interpretation.
- Motivation: Network communities can be inferred from both node attributes and connections, but conventional clustering and community detection methods typically use only one modality.Attributes can help classify sparsely connected nodes, while network structure can connect nodes lacking attribute information.
- Limitations of prior work: Existing methods combining both modalities often cannot detect overlapping communities or assume soft memberships that may model overlaps unrealistically.Single-assignment methods prohibit overlap, while topic-model approaches use soft memberships.
- CESNA: CESNA models hard node-community memberships and allows communities to generate both the network and node attributes, capturing dependence between these sources.The model is a generative approach for networks with node attributes and supports overlapping memberships.
- Scalability: CESNA fits its model with block-coordinate ascent whose updates are linear in the number of network edges, enabling processing of substantially larger networks.The paper reports that CESNA can handle networks 100 times larger than LDA-based methods under the same runtime budget.
- Evaluation: Across evaluated social, information, and content-sharing networks, CESNA is compared against structure-only, attribute-only, and joint methods using hand-labeled communities.The evaluation includes Facebook, Google+, Twitter, Wikipedia, and Flickr.
- Interpretation: CESNA also identifies relevant attributes for detected communities, such as education attributes on Facebook and Islamic-culture subjects among philosopher communities.The method distinguishes attributes associated with community structure from attributes that are not related to it.
II. RELATED WORK
Prior work differs in how it models dependence among communities, attributes, and networks, and in whether memberships are hard or soft. These choices create limitations around overlap detection and the realism of community assignments.
- Modeling dependence: Related methods either let community memberships generate both graph structure and attributes or treat communities and attributes independently before generating the graph.The paper uses these two paradigms to organize prior work.
- Hard memberships: Heuristic single-assignment methods use hard memberships but cannot detect overlapping communities because each node belongs to exactly one community.Their restriction is the single-community assignment itself.
- Soft memberships: LDA-based topic models allow overlapping communities but assume soft memberships, producing assumptions about community overlaps that the paper describes as unrealistic.These methods model communities as generating links and node attributes under the Figure 1(a) paradigm.
III. CESNA MODEL DESCRIPTION
CESNA is a probabilistic generative model that combines network topology, node attributes, and overlapping community memberships. It models edges through shared affiliations and attributes through logistic relationships with community memberships.
- CESNA jointly models community memberships, network topology, and node attributes in a probabilistic generative framework.
- Modeling node attributes: The model assumes that nodes in the same community are likely to share common attributes, while allowing alternative attribute models for other data types.For real-valued attributes, the paper notes that linear regression could be used; the separate-logistic-model design assumes relatively few attributes.
- Communities can overlap because each node has an independent non-negative affiliation weight for every community.A zero affiliation means the node does not belong to that community.
- Modeling the links of the network: The network-link model is designed so community affiliations influence connection likelihood, with community-specific and independent effects.
- Modeling the links of the network: Each community independently connects node pairs with probability 1−exp(−F_uc·F_vc), while shared membership in multiple communities increases connection likelihood.Nodes with zero affiliation in a community have zero connection probability from that community.
- Modeling node attributes: CESNA models each binary node attribute with a logistic model whose inputs are community memberships and whose weights measure attribute relevance.A bias term is also included for each attribute.
IV. INFERRING COMMUNITIES WITH CESNA
CESNA infers community memberships and attribute relationships by maximizing a joint likelihood over the observed graph and attributes. Its alternating optimization, thresholding, holdout selection, and implementation choices support scalable inference.
- CESNA estimates N·C community memberships and K·(C+1) logistic parameters from the observed network and binary node attributes.
- The objective maximizes the joint likelihood log P(G, X|F, W), which decomposes into network and attribute likelihoods under conditional independence.The optimization also applies l1-regularization to W to learn sparse community-attribute relationships and avoid overfitting.
- Block coordinate ascent alternates between updating each node’s memberships with fixed other parameters and updating logistic weights with fixed memberships.This decomposes the non-convex objective into convex subproblems.
- Updating community memberships: Membership updates use projected gradient ascent on a convex subproblem, followed by projection onto the non-negative real numbers.The learning rate is selected with backtracking line search.
- Updating logistic parameters: Logistic parameters are updated separately for each attribute using l1-regularized logistic regression and gradient ascent.The network likelihood is ignored during this update because the graph does not depend on W.
- Determining community memberships: Memberships are converted to community assignments using a threshold chosen so connectedness to other members exceeds edge probability 1/N.The paper reports that this threshold performs well in practice.
- Choosing the number of communities: The number of communities is selected by fitting candidate models on 90% of node-pair and node-attribute pairs and choosing the maximum held-out likelihood.
- Computational complexity of CESNA: A full CESNA iteration takes O(|E| + NK) operations, linear in the number of edges, nodes, and attributes.Weight updates can be parallelized across attributes, and membership updates can be parallelized across nodes in practice.
V. EXPERIMENTAL EVALUATION
CESNA is evaluated on diverse attributed networks against methods using network structure, node attributes, or both. It achieves strong accuracy, robustness to missing edges, and scalability while retaining interpretability through learned attribute-community associations.
- Evaluation setup: CESNA is evaluated on five attributed networks spanning information, content-sharing, and online social domains, using ground-truth communities for accuracy assessment.The datasets include philosophers, Flickr, Facebook, Google+, and Twitter networks.
- Accuracy: CESNA statistically significantly outperforms all considered methods overall.Significance is assessed with one-sided Z-tests at the 95% level.
- Accuracy: 47% relative improvement in accuracy is achieved over methods combining network structure and node attributes.The comparison includes CODICIL, Block-LDA, and Circles.
- Accuracy: CESNA achieves the best performance in 8 out of 10 dataset-metric cases and improves average performance over every listed baseline.Average gains range from 6% over BigCLAM to 112% over MAC.
- Robustness: As edges are randomly removed, CESNA’s improvement over BigCLAM increases, while gains over attribute-using methods remain constant or shrink depending on the dataset.These results indicate that CESNA continues leveraging node attributes when network structure becomes unreliable.
- Scalability: CESNA is the second-fastest method overall and processes a 300,000-node network in 10 minutes with 24 threads.It is about an order of magnitude faster than methods with the same overlapping, attributed-community-detection goal.
VI. ANALYSIS OF DETECTED COMMUNITIES
CESNA improves community interpretation by identifying attributes associated with detected communities and improves qualitative accuracy by combining attributes with network structure. In Facebook and philosopher networks, the learned attributes correspond to meaningful social, educational, religious, and philosophical groupings.
- Interpretability: CESNA characterizes communities through attributes with high logistic weights, making detected groups easier to interpret.Highly positive weights indicate likely attributes of community members, while highly negative weights indicate attributes members are unlikely to have.
- Facebook communities: Facebook communities were associated mainly with schools, education types, and majors, whereas work dates and locale were not social factors around which communities formed.
- Philosophers communities: In the philosophers network, attributes such as “Early Islamic Philosophy” identified an Islamic-philosopher community without querying member names.The attributes also included non-philosophical people related to Islam.
- Philosophers communities: “Catechism of the Catholic Church” identified a theologian community, whose related attributes also included several priests.
- Accuracy: BigCLAM included highly influential but thematically mismatched philosophers, while CESNA excluded Aristotle because he lacked attributes shared with Islamic philosophers or theologians.Aristotle’s many network connections caused BigCLAM to place him in both communities.
VII. CONCLUSION
The paper presents CESNA as a scalable method for overlapping community detection using network structure and node attributes. It reports improved accuracy and scalability, while also supporting community interpretation through relevant attributes; future work extends the attribute and information settings.
- CESNA is a scalable method for detecting overlapping communities in networks with node attributes.
- CESNA improves detected-community accuracy and scalability compared with state-of-the-art baselines.
- Linear runtime in network size enables CESNA to process networks an order of magnitude larger than comparable approaches.
- CESNA supports interpretation by finding relevant node attributes for each community.
- Future work includes more general attributes, attribute topics, and information sources such as diffusion or edge attributes.