<p>Attributed Network Clustering (ANC) has garnered significant attention in research for identifying communities within a complex network like a social, biological, or information network. Generally, such networks are represented as a graph where the nodes denote entities and edges are relationships between two adjacent nodes. In real-world networks, nodes are associated with attributes to express their properties. In this context, a community is defined as a group of nodes that interact more frequently with each other than with nodes outside their group. ANC involves creating a mapping function that converts nodes and associated attributes into lower-dimensional vector representations. Once transformed into these vectors, various machine learning algorithms are used to cluster the nodes and reveal the underlying communities. However, most ANC methods confront two major challenges. First, they assimilate node attribute information from the local neighborhood, as a result, they can’t explore the mutual affinity between node and attribute. Second, they do not consider the values of the community membership of the nodes at the time of clustering. This leads to poor performance, as the embedding method and clustering methods are independent. To address this, this article proposes a method named Mutual Affinity Propagation-based Nonnegative Matrix Factorization (MAP-NMF). The proposed method works in two phases. In the first phase, an attribute-augmented transition probability matrix is constructed to capture the mutual affinity between the node and attribute and obtain node representation using singular value decomposition of the same. The second phase produces community membership from the obtained latent representation through an NMF-based joint optimization. Moreover, a novel updating rule is proposed for the joint optimization method. Empirical study on both real-world and artificial networks proves the superiority of our proposed algorithm.</p>