Exact Matching in Correlated Networks with Node Attributes for Improved Community Recovery

We study community detection in multiple networks whose nodes and edges are jointly correlated. This setting arises naturally in applications such as social platforms, where a shared set of users may exhibit both correlated friendship patterns and correlated attributes across different platforms. Extending the classical Stochastic Block Model (SBM) and its contextual counterpart (CSBM), we introduce the correlated CSBM, which incorporates structural and attribute correlations across graphs. To build intuition, we first analyze correlated Gaussian Mixture Models, wherein only correlated node attributes are available without edges, and identify the conditions under which an estimator minimizing the distance between attributes achieves exact matching of nodes across the two databases. For correlated CSBMs, we develop a two-step procedure that first applies k-core matching to most nodes using edge information, then refines the matching for the remaining unmatched nodes by leveraging their attributes with a distancebased estimator. We identify the conditions under which the algorithm recovers the exact node correspondence, enabling us to merge the correlated edges and average the correlated attributes for enhanced community detection. Crucially, by aligning and combining graphs, we identify regimes in which community detection is impossible in a single graph but becomes feasible when side information from correlated graphs is incorporated. Our results illustrate how the interplay between graph matching and community recovery can boost performance, broadening the scope of multi-graph, attribute-based community detection. Identifying community labels of nodes from a given graph or database-often referred to as community recovery or community detection-is a fundamental problem in network analysis, with wide-ranging applications in machine learning, social network analysis, and biology. The principal insight behind many community detection approaches is that nodes within the same community are typically more strongly connected or share similar attributes compared to nodes in different communities.