A Unified Framework for Exploratory Learning-Aided Community Detection Under Topological Uncertainty

Yu Hou,
Cong Tran,
Ming Li, Member, IEEE,
and Won-Yong Shin, Senior Member, IEEE
Y. Hou is with the School of Mathematics and Computing (Computational Science and Engineering), Yonsei University, Seoul 03722, Republic of Korea.

E-mail<EMAIL_ADDRESS>C. Tran is with the Faculty of Information Technology, Posts and Telecommunications Institute of Technology, Hanoi 100000, Vietnam.

E-mail<EMAIL_ADDRESS>M. Li is with Key Laboratory of Intelligent Education Technology and Application of Zhejiang Province, Zhejiang Normal University, Jinhua 321004, China.

E-mail<EMAIL_ADDRESS>W.-Y. Shin is with the School of Mathematics and Computing (Computational Science and Engineering), Yonsei University, Seoul 03722, Republic of Korea, and the Graduate School of Artificial Intelligence, Pohang University of Science and Technology (POSTECH), Pohang 37673, Republic of Korea.

E-mail<EMAIL_ADDRESS>
(Corresponding author: Won-Yong Shin.)

In social networks, the discovery of community structures has received considerable attention as a fundamental problem in various network analysis tasks. However, due to privacy concerns or access restrictions, the network structure is often uncertain, thereby rendering established community detection approaches ineffective without costly network topology acquisition. To tackle this challenge, we present , a unified framework for detecting overlapping communities via exploratory learning aided by easy-to-collect node metadata when networks are topologically unknown (or only partially known). Specifically,  consists of three iterative steps in addition to the initial network inference step: 1) node-level community-affiliation embeddings based on graph neural networks (GNNs) trained by our new reconstruction loss, 2) network exploration via community-affiliation-based node queries, and 3) network inference using an edge connectivity-based Siamese neural network model from the explored network. Through extensive experiments on five real-world datasets including two large networks, we demonstrated: (a) the superiority of  over benchmark community detection methods, achieving remarkable gains up to 65.55% compared to the best existing competitor, (b) the impact of each module in , (c) the effectiveness of node queries in  based on empirical evaluations and theoretical findings,  (d) the convergence of the inferred network, and (e) the computational efficiency of META-CODE.

Community detection, exploratory learning, graph neural network, network inference, node query

§ INTRODUCTION

§ INTRODUCTION

§.§ Background and Motivation

Community detection [1, 2] is one of critical and important tasks in various network analyses to understand the fundamental features of networks. In social networks, community memberships are often allowed to overlap, wherein nodes belong to multiple communities at once [3]. Consequently, community detection algorithms need to be designed to accommodate this inherently overlapping nature, and as such, a range of techniques such as clique- and modularity-based approaches [3, 4], non-negative matrix factorization (NMF)-based approaches [5, 6], and deep learning-based approaches [7, 8] have been developed to detect overlapping communities.

While the aforementioned community detection methods always rely on the network structure to detect communities, the underlying true network is initially unknown or only partially known in various domains of real-world network applications [9]. Thus, downstream machine learning (ML) tasks on graphs, including community detection, are ineffective unless the network structure is available. Although one could invest additional efforts into uncovering the complete network prior to downstream applications, collecting complete topological information is prohibitively expensive and labor-intensive [9]. Alternatively, one could leverage network data collected from social media to infer the unknown relationships among nodes in the underlying network. Despite the increasing availability of social media platforms, this source of information is not without limitations, such as restricted resources and more stringent privacy settings specified by users. For example, a demographic analysis of Facebook users in New York City conducted in June 2011 revealed that 52.6% of users hid their friend list [10]. Moreover, network connectivity information often includes many weak links [11], such as outdated friendships, which are not effective at detecting communities. Consequently, as long as network analyses are concerned, one should assume that none or only a part of the network structure is available in practice [12, 13, 14, 15].

On one hand, there have been several attempts to solve ML problems in networks with unknown topology. For instance, exploratory influence maximization [16, 17, 18] was introduced along with a solution to perform information retrieval over unknown networks by querying individual nodes to explore their neighborhoods. Despite the success of exploratory influence maximization in solving the problem of influence maximization, the research related to community detection via exploratory learning remains unexplored yet. On the other hand, in the setting where the network structure is partially observable, there have been attempts to solve the problem of community detection by reconstructing the unobserved part of the underlying network from the observed part and then detecting the community structure [19, 14]. In our study, we focus primarily on the case where the network structure is entirely unknown, treating the scenario of partially observable networks as a special case, for the following reasons. First, assuming the fully unknown topology initially is much more challenging due to the lack of ML tools that operate without structural information. It is worth noting that, as summarized in Table 1, the setting of networks with fully unknown topology poses distinct technical difficulties that much be approached differently from the implementation of community detection methods designed for partially observable networks. Second, our topologically unknown setting naturally accommodates the problem of detecting communities when the underlying network is partially observable; in other words, solving our problem innately leads to a solution to the community detection in networks with partially known topology (which will be specified later).

Summary of the difference among overlapping community detection methods with respect to the degree of topological information and the existence of exploratory learning.

2*Methods     3cRequired information     2*Exploratory learning
Full topology      Partial topology     Metadata

AGM [20], BIGCLAM [5], DANMF [6], vGraph [21]

CESNA [22], NOCD [7], DGLFRM [8]

HGP-EPM [23], KroMFac [14]

In social networks, node metadata (e.g., a user's hobby or education) can be used to solve many ML problems on graphs and boost performance. Such node metadata can often be retrieved from various sources such as user-generated content [24] or inferred from users' behavior [25]. For example, in co-authorship networks, one can infer a topical relationship between authors by simply collecting the keywords in each author's publications. In the case of HIV awareness among homeless youth [26], metadata like name, age, and familial background of individuals as well as homeless individuals can be easily collected through the mandatory registration process at welfare centers, required to pay monthly allowances. Because the node metadata are readily available [24, 25, 26], incorporating them into exploratory learning frameworks can help overcome the practical challenges associated with networks with unknown (or only partially known) topology. In this context, as illustrated in Fig. <ref>, a natural question arising is: “How to effectively perform overlapping community detection under topological uncertainty with the aid of node metadata?”

New challenges for overlapping community detection in networks with unknown topology.

§.§ Main Contributions

To answer this question, we make the first attempt to develop an overlapping community detection method in the absence of structural information by retrieving information from both node queries and node metadata. To this end, we first outline two design challenges that must be addressed when building a new methodology.

* Exploratory learning: how to effectively explore subnetworks with the aid of node queries;

* Exploitation of node metadata: how to design our community detection method by maximally exploiting node metadata.

(Idea 1) It is a quite challenging task to accurately discover community structures based solely on node metadata in networks with unknown topology. To aid community detection, we are capable of harnessing node queries with a given query budget to retrieve structural information.  Then, the node metadata and the explored edges from node queries can be used to infer the connections between two nodes in the unexplored part, which helps identify community affiliations more precisely. In our study, we formulate a new problem that jointly finds the community-affiliation embedding matrix and a sequence of node queries in the sense that the discovered community affiliations make the inferred network and node metadata more probable.

(Idea 2) It is worthwhile to note that existing community detection methods are no longer valid in solving the aforementioned problem (refer to Table <ref>). In other words, we need to present our own overlapping community detection method by establishing entirely new design principles. To achieve this goal, we propose a scalable yet effective community detection method, , via exploratory learning aided by node metadata.  initially infers the network structure and then iteratively performs the following three steps to ensure gradually improved performance on community detection:

* Step 1: Community-affiliation embedding. It has been largely underexplored how to detect overlapping communities in attributed networks where node metadata are available. In our study, motivated by the fact that graph neural networks (GNNs) [27, 28] have been widely studied as a powerful means of learning representations in attributed networks, we are interested in finding node-level community-affiliation embeddings by designing a GNN model trained by our new reconstruction loss. To this end, we first characterize two types of relationships, including the structure–community relationship and the metadata–community relationship, and then leverage them for model training.

Network exploration according to different strategies for query node selection when the underlying true network has three overlapping communities. (a) Selection of query nodes with the highest degree. (b) Selection of query nodes in non-overlapping regions. (c) Selection of query nodes that belong to multiple communities and are distributed across diverse communities.

* Step 2: Network exploration via node queries. Following  prior work [16, 29, 18], we use a sequence of node queries to retrieve additional structural information. However, it is quite a challenging task to select node queries in the sense of expediting network exploration. A simple query strategy does not necessarily result in fast network exploration; for example, in Figs. <ref>a and <ref>b, selecting high-degree nodes or nodes in non-overlapping regions (i.e., those belonging to only one community) may not result in fast network exploration. On the other hand, Fig. <ref>c shows the case where we select the nodes that are (i) within areas of overlapping communities and (ii) distributed across diverse communities. To this end, we present a new node query strategy and validate its effectiveness theoretically.

* Step 3: Network inference. After the network exploration, only a small percentage of edges are further explored, which is not sufficient for the accurate detection of communities. To infer the unexplored part of the underlying network for more accurate community detection, we design an edge connectivity-based Siamese neural network (EC-SiamNet) which incorporates the explored edges, retrieved from the queried nodes, and node metadata. Then, the inferred network is used as the input to the GNN model in Step 1 of the next iteration to obtain enhanced community-affiliation embeddings. Note that our prior work [15] does not have this network inference step and solely infers the network structure initially. In other words, without this network inference module, our prior work [15] does not fully take advantage of the structural information obtained through network exploration, limiting its potential for accurate community detection.

Our main contributions are summarized as follows:

* Novel methodology: We introduce , a scalable end-to-end framework for solving the community detection problem in topologically unknown networks, which constitutes 1) the GNN model trained with our reconstruction loss, 2) the query node selection strategy for accelerating network exploration, and 3) the EC-SiamNet to infer the network structure.

* Analysis and evaluation: We validate the rationality and effectiveness of  through extensive experiments on five real-world datasets including two large networks (e.g., x61.2 and x90.0 scale of the datasets used in [30] in terms of the average number of nodes, respectively). We demonstrate 1) the superiority of  over benchmark overlapping community detection methods while showing gains of 65.55% and 19.84% compared to the best competitor and a simple variant of , respectively, 2) the influence of each component in , 3) the theoretical validation of our node query strategy in , 4) the impact of key hyperparameters, and 5) the scalability along with the computational complexity analysis.

Summary of notations.

Notation    Description

$\mathcal{G}$     Underlying network

$\mathcal{V}$     Set of nodes in $\mathcal{G}$

$\mathcal{E}$     Set of edges in $\mathcal{G}$

$N$     Number of nodes

$\mathcal{X}$     Node metadata

$D$     Dimensionality of each feature vector in $\mathcal{X}$

$K$     Number of communities

$\bf F$     Non-negative weight affiliation matrix

$S_t$     Sequence of $t$ node queries

$T$     Budget of node queries

$\mathcal{E}_t$    Set of explored edges after the $t$-th query step

$\mathcal{\mathcal{G}}^{\left( t \right)}$     Inferred network after the $t$-th node query

$\mathcal{E}^{\left( t \right)} $    Set of edges in $\mathcal{G}^{\left( t \right)}$

§.§ Organization and Notations

The remainder of this paper is organized as follows. In Section 2, we present prior studies related to our work. In Section 3, we explain the methodology of our study, including the problem definition and an overview of our  method. Section 4 describes the technical details of the proposed method. Comprehensive experiment results are shown in Section 5. Finally, we provide a summary and concluding remarks in Section 6.

Table <ref> summarizes the notation that is used in this paper. This notation will be formally defined in the following sections when we introduce our methodology and the technical details.

§ RELATED WORK

Our proposed method is related to four broader areas of research, namely overlapping community detection, community detection using GNNs, community detection in incomplete networks, and network exploration.

Overlapping community detection. Various techniques have been developed to detect overlapping communities. Approaches based on fundamental concepts such as clique and modularity were initially proposed for identifying overlapping communities [3, 4]. The community-affiliation graph model (AGM) [20] was introduced as a means to detect overlapping communities by capitalizing on the observation that nodes within areas of overlapping communities tend to exhibit denser connections compared to those in non-overlapping regions. Building upon the AGM, BIGCLAM [5] and EPM [23] employed NMF and Bernoulli-Poisson  (BP) models, respectively, to detect overlapping communities. DANMF [6], which leverages stacked NMF, and vGraph [21], which utilizes a probabilistic generative model, were also presented. Additionally, a handful of methods were proposed in [31, 22] to detect overlapping communities by incorporating the network structure and node metadata.

Community detection using GNNs. GNNs have been widely employed to solve community detection problems [32, 33, 34, 35, 36, 37]. For instance, methods such as AGC [32] and SGCN [33] leveraged graph convolution networks (GCNs) [27] to capture complex features for community detection, while aggregating neighbors' information of each node through graph convolution layers. DMGI [34] and MAGNN [35] employed graph attention networks (GATs) [28] to learn the importance of each node in the neighborhood adaptively. Additionally, MGAECD [36] and GUCD [37] utilized GCNs in autoencoder (AE)-based techniques to represent communities via embeddings in the hidden layer by reconstructing the original information. Furthermore, in [38], a GNN encoding technique for the multi-objective evolutionary algorithm was proposed to solve the community detection problem in complex attributed networks. While the aforementioned studies have focused on detecting disjoint (i.e., non-overlapping) communities, only a few have addressed the detection of overlapping communities via GNNs [7, 8]. For example, NOCD [7] proposed a GNN-based approach for detecting overlapping communities by fusing the network structure and node metadata, while DGLFRM [8] incorporated a stochastic block model [2] with a GNN architecture for overlapping community detection.

Community detection in incomplete networks. Several studies have explored the problem of identifying communities when the underlying network is incomplete (uncertain) with missing edges. Some of these studies leveraged
additional information, such as node metadata [22] or topological similarity [39], for community detection. There has been a research endeavor that predicted missing edges in an incomplete network and subsequently discovered communities within the predicted topology [19]. A hierarchical gamma process infinite edge partition model [23] was designed not only to identify overlapping communities but also to predict missing edges. Moreover, other studies directly extracted community information from raw data sources, such as influence cascades [40] and time series data [41], in networks with missing edges. In [14], a particular study combined node ranking with NMF to enhance the accuracy of community detection in networks with missing edges. Table <ref> summarizes the difference among overlapping community detection methods when different degrees of topological information, including full topology, partial topology, and (almost) no topology, are used.

Network exploration. The network exploration aims to explore networks whose topology is either completely unknown or partially observable to help solve downstream ML tasks on graphs. The Jump-Crawl model [42] and BEER [43] were proposed as approaches for identifying influential nodes, which are used to explore the unknown network. When dealing with a network lacking topological information, numerous influence maximization methods attempted to find influential nodes and queried nodes that can retrieve their neighbors in unknown networks. Following the concept of active learning [44, 45], HEALER [46] investigated dynamic influence maximization over a series of rounds in which edge information is collected after each round. Additionally, exploratory influence maximization methods such as CHANGE [16] and Geometric-DQN [17] were introduced by learning edges via individual node queries. IM-META [18] introduced a topology-aware ranking strategy to improve the effectiveness of network exploration in performing the influence maximization task.

Remark. Although there has been a considerable amount of research on community detection, most existing methods more or less require the network structure to infer the community structure, which can be labor-intensive in practical situations. Additionally, the idea of leveraging node queries and node metadata has not been explored for community detection in topologically unknown networks.

§ METHODOLOGY

In this section, as a basis for the proposed  method, we first present our network model, outlining basic assumptions. We then formulate the problem of community detection in networks with unknown topology. We also provide an overview of the  method.

§.§ Settings and Basic Assumptions

Let us denote an underlying true network as $\mathcal{G} = \left( {\mathcal{V},\mathcal{E}} \right)$, where $\mathcal{V}$ is the set of $N$ nodes and $\mathcal{E}$ is the set of edges which is initially unavailable. The network $\mathcal{G}$ is assumed to be an undirected unweighted attributed network without self-edges and repeated edges, having collectible node metadata ${\bf \mathcal{X}} \in \mathbb{R}^{N \times D}$ of binary-valued node features,[Non binary-valued node features can be transferred to binary values via one-hot encoding [31].] where $D$ is the dimension of each feature vector. We assume that social networks follow the AGM [20], which claims that the more communities to which a pair of nodes belongs, the higher the probability that the node pair is connected. The community information can be represented by a non-negative weight affiliation matrix ${\bf F}^{(t)}\in\mathbb{R}^{N\times K}$ regarded as node-level community-affiliation embeddings,[To simplify notations, ${\bf F}^{\left( t \right)} $ representing the node-level community-affiliation embeddings in the $t$-th query step will be written as ${\bf F}$ if dropping $t$ does not cause any confusion.] where $K$ is the number of communities and ${\bf F}_u$ is the affiliations of node $u$.

Similarly as in the concept of active learning [44, 45], we select the sequence of node queries, denoted as $S_t$, with a query budget $T$ to retrieve additional structural information from the underlying network $\mathcal{G}$, where $0 \le t \le T-1$. Note that strategies utilizing a budget of queries are widely applied to solve ML tasks on topologically unknown networks [16, 17, 18]. Upon querying a single node $v_t$, we can discover its neighbors, denoted as $\mathcal{N}_\mathcal{G} \left ( v_t \right ) $, and expand the observable subnetwork accordingly, which essentially follows the same setting as prior work [16, 29, 18]. Let us denote the set of explored edges after $t$ queries as $\mathcal{E}_{t}$. Then, during the $(t+1)$-th node query, we choose a node $v_{t}$ from $\mathcal{V}$ to expand and update the set of explored edges ${\cal E}_{t + 1}  = {\cal E}_t  \cup {\cal E}\left( {{\cal N}_{\cal G} \left( {v_{t} } \right),v_{t} } \right)$, where  $\mathcal{E} \left ( \mathcal{N}_\mathcal{G} \left ( v_{t} \right ),v_{t} \right )$ is a set of all edges to which each node in $\mathcal{N}_\mathcal{G} \left ( v_{t} \right ) $ and node $v_{t}$ are incident. Furthermore, the inferred network $\mathcal{G}^{\left( t+1 \right)}$ after the $(t+1)$-th node query is represented as $ \mathcal{G}^{\left( t+1 \right)}  = \left( {\mathcal{V} ,\mathcal{E}^{\left( t+1 \right)} } \right)$, where $\mathcal{E}^{\left( t+1 \right)}$ is the set of edges in $\mathcal{G}^{\left( t+1 \right)}$ and can be updated with $\mathcal{E}^{\left( t+1 \right)}  = \mathcal{E}_{t+1}  \cup \mathcal{E}_I^{\left( t+1 \right)} $. Here, $\mathcal{E}_I^{\left( t+1 \right)}  = f_I \left( {S_{t+1} ,{\cal E}_{t+1} } \right)$, where $f_I $ is the function that infers the network structure based on the relationship between the queried nodes and their neighbors.

§.§ Problem Formulation

In this subsection, we formulate a community detection problem in networks where the topology is initially unknown, which is more challenging than the problem of community detection in partially observable networks. To this end, we aim to jointly find the community-affiliation embedding matrix F and a sequence of node queries $S_T = \left\{ {v_0 ,v_1 , \cdots ,v_{T - 1} } \right\}$ that leads to the finally explored edges ${{\cal E}_T } $, given the query budget $T$, by retrieving information both on node metadata and queried nodes. The likelihood $\mathbb{P}\left( {\mathcal{G}^{\left( T \right)} ,\mathcal{X}\left| \bf F \right.} \right)$ evaluates which affiliation embedding matrix F would make the given inferred network $\mathcal{G}^{\left( T \right)} $ and node metadata $\mathcal{X}$ more probable.

If some nodes belong to common communities according to ${\bf F}$, then they are more likely to be connected in $\mathcal{G}^{\left( T \right)}$, and/or to share common metadata from $\mathcal{X}$. This allows us to discover the communities ${\bf F}$ from the network $\mathcal{G}^{\left( T \right)}$ and node metadata $\mathcal{X}$. We formulate this problem by jointly finding the optimal ${\bf F}^*$ and $S_T^ * $ in the sense of maximizing the likelihood $\mathbb{P}\left( {\mathcal{G}^{\left( T \right)} ,\mathcal{X}\left| \bf F \right.} \right)$ as follows:

\begin{equation}
\left( {{\bf F}^ *  ,S_T^* } \right) = \mathop {\arg \max }\limits_{{\bf F} \ge 0,S_T  \subset \mathcal{V}} \mathbb{P}\left( {\mathcal{G}^{\left( T \right)} ,\mathcal{X}\left| {\bf F} \right.} \right),
\end{equation}

where ${\cal G}^{\left( T \right)}  = \left( {\mathcal{V},\mathcal{E}^{\left( T \right)} } \right) $; $\mathcal{E}^{\left( T \right)}  = \mathcal{E}_T  \cup \mathcal{E}_I^{\left( T \right)} $; and $\mathcal{E}_I^{\left( T \right)}  = f_I \left( {S_T ,{\cal E}_T } \right)$.

In our study, we tackle the following two practical challenges.

* To the best of our knowledge, there is no prior attempt to detect overlapping communities in networks that lack structural information. All the existing community detection methods are no longer valid in solving the aforementioned problem;

* The problem of finding a sequence of node queries $S_T$ among all nodes for estimating $\mathcal{E}$ is NP-hard with an exponential complexity in $N$.

The schematic overview of  consisting of three iterative steps: 1) community-affiliation embedding, 2) network exploration via node queries, and 3) network inference, where the first and second iterations are executed.

$\mathcal{V},\mathcal{X}, S_0  = \emptyset, T$
${\bf F}, S_T$
Beginfunctionend function

$\mathcal{G}^{(0)} \leftarrow$ ($\mathcal{X}$)

$t$ from $0$ to $T$

${\bf F} \leftarrow$ ($\mathcal{G}^{(t)}, \mathcal{X}$)

$t = T$${\bf F},S_T$

$v_t \leftarrow$ (${\bf F}, S_t$)

$S_{t+1} \leftarrow S_{t}  \cup \left\{ {v_{t} } \right\}$

${\cal E}_{t + 1}  \leftarrow {\cal E}_t  \cup {\cal E}\left( {{\cal N}_{\cal G} \left( {v_{t} } \right),v_{t} } \right)$

$\mathcal{E}_I^{\left( t+1 \right)} \leftarrow$ $\left( S_{t+1}, \mathcal{E}_{t+1} \right)$

$ \mathcal{G}^{\left( t+1 \right)}  \leftarrow \left( {\mathcal{V} ,\mathcal{E}_{t+1}  \cup \mathcal{E}_I^{\left( t+1 \right)} } \right)$

This motivates us to present a scalable yet accurate solution to the problem.

§.§ Overview of

In this subsection, we explain our methodology alongside an overview of our  method. We generate the community-affiliation embedding matrix F with the aid of information retrieved from both node metadata and queried nodes. The overall procedure of  is described in Algorithm <ref>. The algorithm starts with inferring an initial network structure $ \mathcal{G}^{\left( 0 \right)}$ based only on node metadata (—refer to line 2). Then, the algorithm iteratively performs the following three steps within our budget $T$: 1) community-affiliation embedding (—refer to line 4); 2) network exploration via node queries (—refer to line 7); and 3) network inference (—refer to line 10). The schematic overview of  is illustrated in Fig. <ref>.

Step 1: Community-affiliation embedding. We tackle the challenge of detecting overlapping communities by generating node-level community-affiliation embeddings $\bf F$ through the use of a GNN architecture. Our GNN model extracts the community-affiliation embeddings $\bf F$ from the inferred network $ \mathcal{G}^{\left( t \right)} $ and node metadata $\mathcal{X}$, which is expressed as:

\begin{equation}
{\bf{F}}: = GNN_\theta  (\mathcal{G}^{\left( t \right)} ,{\cal X}),
\label{eq: gnn}
\end{equation}

where $\theta$ is the trainable parameters in the GNN model.

To ensure that the model accurately captures both structural and attribute information, we train the GNN parameters $\theta$ by establishing our own reconstruction loss in terms of preserving structural and attribute information, which will be specified in Section 4.2.

Step 2: Network exploration via node queries. We explore the network through a node query process, selecting a node to be queried that leads to a high level of network exploration based on the community-affiliation embedding F obtained in Step 1. This step is inspired by the idea that queried nodes (i) belonging to multiple communities and (ii) distributed across diverse communities can expedite the expansion of the explored network, which shall be empirically validated in Section 5.5.3. The selected node $v_t$ is added to the sequence $S_{t+1}  = S_{t}  \cup \left\{ {v_{t} } \right\} $, and its neighbors $\mathcal{N}_\mathcal{G} \left ( v_{t} \right ) $ are found for network exploration. The explored edges are updated as ${\cal E}_{t+1}  = {\cal E}_{t}  \cup {\cal E}\left( {{\cal N}_{\cal G} \left( {v_{t} } \right),v_{t} } \right)$ accordingly. For example, as depicted in Fig. <ref>, when node $v_2$ is queried in the first iteration, we are capable of discovering its two neighbors, namely $v_1$ and $v_3$.

Step 3: Network inference. We adopt the SiamNet model [47], which has been widely used in computer vision and pattern analyses [48, 49, 50], as the inference function $ f_I \left( {S_{t+1} ,{\cal E}_{t+1} } \right)$ that infers the edges ${\cal E}_I^{\left( t+1 \right)}$. In our study, we propose EC-SiamNet as a potent architecture that learns the similarity between two nodes based on connectivity information obtained by the explored edges. This is accomplished by generating an attractive and repulsive force in the embedding space. Specifically, our EC-SiamNet takes node metadata $\mathcal{X}$ as input and returns a set of similarity scores, denoted as $\Psi ^{\left( t+1 \right)} $, as output, while being trained with positive and negative edges based on the queried nodes $S_{t+1}$ and explored edges $\mathcal{E}_{t+1}$. As an example, positive edges correspond to all edges to which each node in $\mathcal{N}_\mathcal{G}(v_2)$ and node $v_2$ are incident (see the network inference step in Fig. <ref>). After training, EC-SiamNet computes the similarity score $\Psi ^{\left( t+1 \right)} $, with the edge between node $u$ and $v$ being added if the score $\psi _{uv}^{\left( t+1 \right)}  \in \Psi ^{\left( t+1 \right)} $ is above a certain threshold. The inferred edges $\mathcal{E}_I^{\left( t+1 \right)} $ are then incorporated into the edges $\mathcal{E}^{\left( t+1 \right)} $ of the inferred network ${\cal G}^{\left( t+1 \right)}$, which is expressed as $\mathcal{E}^{\left( t+1 \right)}  = \mathcal{E}_{t+1}  \cup \mathcal{E}_I^{\left( t+1 \right)} $.

The three steps in our method are iteratively carried out, feeding the updated inferred network $ \mathcal{G}^{\left( t+1 \right)} $ and node metadata $\mathcal{X}$ as input to the GNN model in each iteration to produce increasingly accurate community-affiliation embeddings ${\bf F}$. This iterative process is terminated when a given budget of node queries $T$ is reached. It is worthwhile to note that our method is also applicable to the case where networks are initially partially observable. This is because, while iterating over the three steps, our method naturally addresses the problem of community detection for the already explored subnetworks through node queries, which can be regarded as the partially observable case.

§ PROPOSED  METHOD

In this section, we elaborate on each step in our  method. We also present the theoretical analyses including the effectiveness of network exploration in  and the computational complexity of .

§.§ Initial Network Inference

Initially, we are faced with a lack of structural information. To overcome this, we need to infer an initial network structure based solely on the available node metadata.

To this end, as the first step in initial network inference, following our prior work [15], we adopt the multi-assignment clustering (MAC) approach [51]. This involves determining the initial community memberships ${\bf C} \in \left\{ {0,1} \right\}^{N \times K}$, which assigns nodes to multiple communities based on their similarity with community prototypes derived from the node metadata $\mathcal{X}$. Here, ${\bf C}_{uk}$ indicates whether node $u$ belongs to community $k$. The assignment process relies on the decomposition of $\mathcal{X}$ into ${\bf C} \otimes {\bf U} $, where the matrix ${\bf U} \in \left\{ {0,1} \right\}^{K \times D}$ is community prototypes, and ${\bf U}_{k \cdot } $ denotes the prototype of community $k$. Here, the operator $\otimes$ is defined such that the $d$-th attribute of node $u$ satisfies

\begin{equation}
{\cal X}_{ud}  =  \vee _{k = 1}^K \left[ {{\bf{C}}_{uk}  \wedge {\bf{U}}_{kd} } \right],
\end{equation}

which signifies that the nodes with the same community memberships tend to share similar node metadata, where $\mathcal{X}_{ud}$ is the $d$-th attribute of node $u$.

Then, as the second step in initial network inference, we infer network ${\cal G}^{\left( 0 \right)}  = \left( {\mathcal{V} ,\mathcal{E}^{\left( 0 \right)} } \right) $ from the initial community memberships ${\bf C}$ using the AGM [20], where ${\mathcal{E}^{\left( 0 \right)} } $ represents the set of edges initially inferred. Here, each edge $\left( {u,v} \right) \in \mathcal{E}^{\left( 0 \right)} $ is created with the probability of

\begin{equation}
p\left( {u,v} \right) = 1 - \prod\nolimits_{i = 1}^{c_{uv} } {\left( {1 - p} \right)},
\label{eq:comm_gen}
\end{equation}

where $p$ is the probability of an edge formed between two nodes within a community and $c_{uv} $ is the number of communities shared by nodes $u$ and $v$ according to the community memberships ${\bf C}$. This implies that, if a pair of nodes $u$ and $v$ belongs to more communities in common, then the probability of creating edge $\left( {u,v} \right)$ is higher.

§.§ Community-Affiliation Embedding

Let us recall that the community-affiliation embeddings F can be derived from the GNN model in (<ref>). Using the inferred network ${\cal G}^{\left( t \right)}$ and node metadata $\mathcal{X}$, we aim to design our GNN model that generates node-level embeddings represented as a non-negative weight affiliation matrix ${\bf{F}} = GNN_\theta  (\mathcal{G}^{\left( t \right)} ,{\cal X}) $. To achieve this goal, we characterize the following two relationships.

§.§.§ Structure–Community Relationship
According to the AGM, if two nodes belong to more communities in common, then they are more likely to be interconnected in the network (refer to (<ref>)). This implies that there exists a strong correlation between the network structure and community affiliation.

To characterize the relationship between the network structure and community affiliation in network ${\cal G}^{\left( t \right)}$, we employ a probabilistic generative model in [5]. This involves modeling the probability of having an edge between nodes $u$ and $v$ as $1 - \exp \left( { - {\bf F}_u {\bf F}_v^T } \right) $ based on the community-affiliation embedding matrix ${\bf F}$. A higher value of $1 - \exp \left( { - {\bf F}_u {\bf F}_v^T } \right) $ indicates a higher probability of having an edge between nodes $u$ and $v$ in the network, which implies that, if a pair of nodes belongs to more communities in common, then the probability that the node pair is connected is higher. For example, as illustrated in Fig. <ref>, nodes $v_1$ and $v_2$ sharing the same community memberships have a higher probability of being connected compared to nodes that may belong to different communities such as nodes $v_1$ and $v_3$.

In this context, to determine which community-affiliation embeddings ${\bf F}$ would make the given inferred network $\mathcal{G}^{(t)}$ more probable, we formulate our loss function $\mathcal{L}_1 ({\bf F})$ as:

\begin{equation}
\begin{array}{l}
\mathcal{L}_1 \left( {\bf{F}} \right) =  - \log \mathbb{P} \left( {\mathcal{G}^{\left( t \right)} |{\bf{F}}} \right) \\
\;\;\;\;\;\;\;\;\;\;\;= -\!\!\!\!\! \sum\limits_{\left( {u,v} \right) \in \mathcal{E}^{\left( t \right)} }  \log \left( {1 - \exp \left( { - {\bf{F}}_u {\bf{F}}_v^T } \right)} \right) +\!\!\!\! \sum\limits_{\left( {u,v} \right) \notin \mathcal{E}^{\left( t \right)} }\!\!\! {{\bf{F}}_u {\bf{F}}_v^T },  \\
\end{array}
\label{eq: structue_community}
\end{equation}

where $\mathcal{E}^{(t)}$ is the set of edges in $\mathcal{G}^{(t)}$.

An example illustrating how the network structure $\mathcal{G}$ and node metadata $\mathcal{X}$ can be reconstructed from the community-affiliation embedding matrix ${\bf F}$.

§.§.§ Metadata–Community Relationship
Intuitively, if nodes are in the same community, then they are likely to share common node attributes [22]. As depicted in Fig. <ref>, nodes $v_1$ and $v_2$ with the same community membership share common node metadata. We next state how to characterize the relationship between the node metadata and community structure, which is built upon the attribute modeling in [22] by hypothesizing that incorporating a node's community memberships can facilitate the prediction of each attribute associated with the node.

More formally, by adopting a logistic model to build the relationship, we can probabilistically model the $d$-th attribute of node $u\in\mathcal{V}$ in the binary-valued node metadata $\mathcal{X}$, denoted by $\mathcal{X}_{ud}$, as the sigmoid function:

\begin{equation}
{\cal Q}_{ud}  = \frac{1}{{1 + \exp \left( { - \sum\nolimits_k {{\bf F}_{uk} {\bf W}_{dk}} } \right)}},
\label{eq: metadata_community}
\end{equation}

where ${\bf{F}}_{uk} $ is the $k$-th entry in ${\bf{F}}_{u} $ and ${\bf W}_{dk} $ is the $\left( {d,k} \right) $-th entry of weight matrix ${\bf W} \in \mathbb{R}^{D \times K} $, indicating the relevance of community $k$ to the $d$-th node attribute. As illustrated in Fig. <ref>, the corresponding node metadata can be reconstructed from $\mathcal{Q}_{ud}$. In this context, we formulate our loss function $\mathcal{L}_2 ({\bf F})$ as:

\begin{equation}
\begin{array}{l}
\mathcal{L}_2 \left( {\bf{F}} \right) =  - \log \mathbb{P} \left( {\mathcal{X}|{\bf{F}},{\bf{W}}} \right) \\
\:\:\:\:\:\:\:\:\:\:\:\:\:\:= - \sum\limits_{u,d} {\left( {{\cal X}_{ud} \log {\cal Q}_{ud}  + \left( {1 - {\cal X}_{ud} } \right)\log \left( {1 - {\cal Q}_{ud} } \right)} \right)}.  \\
\end{array}
\label{eq: metadata_reconstruction}
\end{equation}

§.§.§ Model Training

Based on the two aforementioned relationships, we establish our reconstruction loss as follows:

\begin{equation}
\begin{aligned}
\mathcal{L}\left ( {\bf F} \right )&=\mathcal{L}_1({\bf F})+\eta \mathcal{L}_2({\bf F}) \\
&= - \sum\limits_{\left( {u,v} \right) \in {\cal E}^{\left( t \right)} } \!\! {\log \left( {1 - \exp \left( { - {\bf F}_u {\bf F}_v^T } \right)} \right) +\!\!\!\! \sum\limits_{\left( {u,v} \right) \notin {\cal E}^{\left( t \right)} } {{\bf F}_u {\bf F}_v^T } } \\
%&- \eta \sum\limits_{u,k} {\left( {\tilde{X}_{uk} \log Q_{uk}  + \left( {1 - \tilde{X}_{uk} } \right)\log \left( {1 - Q_{uk} } \right)} \right)},
\end{aligned}
\notag
\end{equation}

\begin{equation}
\;\;\;\;\;\;\;- \eta \sum\limits_{u,d} {\left( {\mathcal{X}_{ud} \log \mathcal{Q}_{ud}  + \left( {1 - \mathcal{X}_{ud} } \right)\log \left( {1 - \mathcal{Q}_{ud} } \right)} \right)},
\label{eq:loss}
\end{equation}

where $\eta  \ge 0 $ is the hyperparameter to balance between two terms. Note that the first and second terms in (<ref>) aim at reconstructing the network structure and node metadata, respectively. We update the parameters $\theta $ of our GNN model in the sense of minimizing the loss function.

§.§ Network Exploration via Node Queries

As stated in Section 3.3, we discover as many neighbors as possible for each queried node for network exploration. To this end, we are interested in how to select node queries $S_t$. Although querying high-degree nodes is expected to make the explored network grow fastest, it may not be always true as long as the overlapping community detection task is concerned. As depicted in Fig. <ref>a, querying the nodes with the highest degree (i.e., the degree of 6) may result in a limited number of explored neighbors. Moreover, such topology-aware query strategies would not be possible due to the neighbor unawareness of nodes beforehand.

In our study, the node query strategy is built upon our claim that each queried node should not only belong to more communities but also be distributed over diverse communities for faster network exploration. As shown in Figs. <ref>b and <ref>c, the queried nodes in non-overlapping regions may not facilitate faster network exploration; however, by selecting the queried nodes that are (i) within areas of overlapping communities and (ii) distributed across diverse communities, we are capable of exploring different regions within each community, thus expediting the expansion of the explored network. This eventually leads to a higher accuracy of community detection, which is empirically validated in Section 5.5.3.

In this context, we select the $(t+1)$-th node to query for $t\in\{0,\cdots,T-1\}$ as follows:

\begin{equation}
v_t = \mathop {\arg \max }\limits_v \left( {\left\| {{\bf F}_v } \right\|_1  + \lambda\left( {1 - \frac{1}{{t+1}}\sum\limits_{u \in S_t} {\text{sim}\left( {{\bf F}_v ,{\bf F}_u } \right)} } \right)} \right),
\label{eq:strategy}
\end{equation}

where $\left\|  \cdot  \right\|_1$ represents $L_1$-norm of a vector, $\lambda \ge 0$ is the hyperparameter that balances between the two terms, and $\text{sim}\left( { \cdot , \cdot } \right)$ is the cosine similarity. Here, the second term in (<ref>) controls a node to be selected from one of communities different from those of previously queried nodes.

Once we have selected the queried node $v_t$, it is added to the sequence $S_{t+1}  = S_{t}  \cup \left\{ {v_{t} } \right\} $. Then, we can discover its neighbors $\mathcal{N}_\mathcal{G}(v_t)$ and expand the observable subnetwork by updating the set of explored edges ${\cal E}_{t+1}  = {\cal E}_{t}  \cup {\cal E}\left( {{\cal N}_{\cal G} \left( {v_{t} } \right),v_{t} } \right)$.

§.§ Network Inference

During the query process, the set of explored edges, ${\cal E}_{t+1}$, increases as a result of the node queries $S_{t+1}$. This newly acquired information can then be leveraged to predict additional edges more accurately [18]. To do this, we present the inference function $ \mathcal{E}_I^{(t+1)}=f_I \left( {S_{t+1} ,{\cal E}_{t+1} } \right)$. Note that our prior work [15] does not include the network inference step after query node selection. In other words, it does not make full use of the information obtained by network exploration, which limits the potential to accurately detect communities. In contrast, in our study, the network $\mathcal{G}^{\left( t+1 \right)} $ is updated using the inferred edges $\mathcal{E}_I^{\left( t+1 \right)}$, which gradually approximates the underlying true network $\mathcal{G}$ for every iteration. The updated inferred network $\mathcal{G}^{\left( t+1 \right)} $ can be harnessed to better learn the representation of community-affiliation embedding matrix F in the next iteration. In this context, our primary challenge lies in how to effectively integrate the network inference step into an end-to-end community detection framework.

The inference function $ f_I \left( {S_{t+1} ,{\cal E}_{t+1} } \right)$ is designed by using our EC-SiamNet model, which incorporates the network structure and node metadata to infer edges over the network, whereas only the node metadata $\mathcal{X}$ are utilized in the initial network inference step (see Section 4.1). We now explain how to train EC-SiamNet and how to compute the similarity score $\Psi ^{\left( t+1 \right)} $ in Step 3 of Section <ref>. In our study, we take advantage of the “homophily principle” in social networks, which refers to the tendency of an individual node to connect with similar nodes [52], and is used to learn embeddings that precisely capture the homophily effect. A trained EC-SiamNet inductively maps new input data (i.e., unexplored nodes) whose connectivity information to the training data (i.e., explored nodes) is unknown. As shown in Fig. <ref>, our EC-SiamNet architecture comprises twin multilayer perceptron networks (MLPs) that take two node metadata $\mathcal{X}_u$ and $\mathcal{X}_v$, corresponding to nodes $u$ and $v$, respectively, as input. The MLPs act as encoders that generate embedding vectors, denoted as ${{\bf e}_u }$ and ${{\bf e}_v }$ for nodes $u$ and $v$, respectively. Similarly as in [53], we compute the Hadamard product of two embedding vectors ${\bf e}_u$ and ${\bf e}_v$ and then utilize a sigmoid output layer to infer $\psi _{uv} ^{\left( t+1 \right)} \in \Psi^{(t+1)}$ from the product. That is, we compute

\begin{equation}
\psi _{uv} ^{\left( t+1 \right)}  = \text{sigmoid}\left( {{\bf e}_u  \odot {\bf e}_v } \right),
\end{equation}

where $\odot $ denotes the Hadamard product.

The architecture of our EC-SiamNet for network inference.

Next, we optimize the model parameters ${\bf W}_{Sia} $ of EC-SiamNet. To this end, we establish a contrastive loss built upon the approach in [54]. Specifically, for each mini-batch used in stochastic gradient descent, we sample a pair of nodes $u,v \in \mathcal{V} $ whose connection is certain according to $\mathcal{E}_{t+1}$. Here, to utilize the sparsity of real-world networks and balance between the sampled positive and negative node pairs, we apply negative sampling [55]. Then, our goal is to find parameters ${\bf W}_{Sia} $ in the sense of minimizing the following loss function:

\begin{equation}
\begin{array}{l}
\mathcal{L}\left( {{\bf W}_{Sia} ,\mathcal{X}_v ,\mathcal{X}_v } \right) = \left( {1 - I_{uv} } \right)\frac{1}{2}\left[ {\text{sim}\left( {{\bf e}_u ,{\bf e}_v } \right)} \right]^2  \\
\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; + I_{uv} \frac{1}{2}\left[ {\max \left( {0,r - \text{sim}\left( {{\bf e}_u ,{\bf e}_v } \right)} \right)} \right]^2, \\
\end{array}
\label{eq:loss_siamese}
\end{equation}

where $r$ is the so-called “margin” hyperparameter [54]; and $I_{uv} = 1$ if $\left( {u,v} \right) \in \mathcal{E}_{t+1} $ and $I_{uv} = 0$ otherwise. Note that we make use of information of the explored edges (i.e., the parameter $I_{uv}$) in the stage of EC-SiamNet optimization.

The motivation behind the loss function in (<ref>) is two-fold: 1) to create an attractive force between the embeddings of node pairs with similar metadata, and 2) to generate a repulsive force between dissimilar node pairs that pushes them apart until the distance between them in the embedding space exceeds a certain radius $r$.

By calculating the similarity score $\Psi^{(t+1)}$ via the proposed EC-SiamNet model, we are able to more precisely obtain the set of inferred edges $\mathcal{E}_I^{\left( t+1 \right)} $, which is then incorporated into the edges $\mathcal{E}^{\left( t+1 \right)} $ of network ${\cal G}^{\left( t+1 \right)}$, that is, $\mathcal{E}^{\left( t+1 \right)}  = \mathcal{E}_{t+1}  \cup \mathcal{E}_I^{\left( t+1 \right)} $. The updated network ${\cal G}^{\left( t+1 \right)}$ is then used as the input to the GNN model in Step 1 of the next iteration to obtain an enhanced representation of community-affiliation embedding matrix F. This procedure is repeated until the $T$-th node query is reached.

Let us address how EC-SiamNet converges over iterations. It is worth noting that, as the query process continues, we are capable of having access to more node pairs for training from the explored network. As far as the homophily principle holds, adopting our EC-SiamNet model enables us to infer edges more accurately, leading to the convergence of the network ${\cal G}^{\left( t \right)}$ to its underlying true network $\mathcal{G}$. This results in more precise community-affiliation embeddings.

§.§ Theoretical Analysis

In this subsection, we theoretically analyze the effectiveness of network exploration via node queries in . We also theoretically show the computational complexity of .

§.§.§ Theoretical Findings in

We first analytically show the effectiveness of our node query strategy. For ease of analysis, we make three assumptions for an underlying network $\mathcal{G}=(\mathcal{V},\mathcal{E})$ as follows:

* The underlying network $\mathcal{G}$ follows the AGM, where the probability of forming an edge in each community is identically given by $p$.

* The underlying network $\mathcal{G}$ is composed of $K\left( { \ge 2} \right)$ communities, having a constrained size difference such that

\begin{equation}
N_{\max }  - N_{\min }  \le \varepsilon ,
\label{eq:assumption2}
\end{equation}

where $N_{\max }$ and $N_{\min }$ are the maximum and minimum numbers of nodes in each community, respectively, and $\varepsilon>0$ is an arbitrarily small constant.

* We partition the nodes into $K$ subsets according to the number of communities to which they belong. Let $N_1,N_2,\cdots,N_K$ denote the number of nodes in each subset. Then,

\begin{equation}
\left\{ \begin{array}{l}
\frac{{N_1 }}{N} \le \frac{2}{3} \\
\mathbb{E}_v \left[ {\mathcal{D}\left| {A_1 } \right.} \right]N_1  \ge \sum\limits_{i = 2}^K {\mathbb{E}_v \left[ {\mathcal{D}\left| {A_i } \right.} \right]N_i }, \\
\end{array} \right.
\label{eq:assumption3}
\end{equation}

where $\mathcal{D}$ is the degree distribution of nodes and $A_i$ is the event such that a certain node $v$ belongs to $i$ communities.

Assumption 2 indicates that all communities have approximately the same size, which can be realized by the Girvan–Newman algorithm [56]. Assumption 3 enforces nodes not to belong overly to either only a single community or multiple ($\ge2$) communities. Note that many real-world networks (e.g., Ego-Facebook [30] and citation networks [7]) tend to almost follow Assumption 3. Now, we are ready to show the following two theorems.

For any nodes $u$ and $v$ belonging to $M$ and $M'$ communities, respectively, in an underlying network $\mathcal{G}=(\mathcal{V},\mathcal{E})$, where $M > M'$, if $\varepsilon  \le \frac{{N_{\min }  - 1}}{K} - 1$, then the following inequality holds:

\begin{equation}
\mathbb{E}_{u } \left[ {\mathcal{D}_M } \right] \ge \mathbb{E}_{v } \left[ {\mathcal{D}_{M'} } \right],
\end{equation}

where $\mathbb{E}_{u } \left[ {\mathcal{D}_M } \right]$ and $\mathbb{E}_{v } \left[ {\mathcal{D}_{M'} } \right]$ are the expectations of degree distributions over the nodes belonging to $M$ and $M'$ communities, respectively.

Let us denote the $i$-th community to which a node belongs as $C_i$. Since the AGM is used to generate a network $\mathcal{G}$ by creating edges between nodes in each community independently, the degree distribution of a node in a given community $C_i$, denoted by $Y_{C_i}$, follows the binomial distribution

\begin{equation}
Y_{C_i }  \sim B\left( {N_{C_i }  - 1,p} \right),
\end{equation}

where $N_{C_i}$ is the number of nodes in $C_i$. By the properties of independence and additivity, the degree distribution $\mathcal{D}_M$ (resp. $\mathcal{D}_M'$) of any node $u$ (resp. $v$) belonging to $M$ (resp. $M'$) communities still follows the binomial distribution. Thus, we have

\begin{equation}
\begin{array}{l}
\mathbb{E}_u \left[ {\mathcal{D}_M } \right] - \mathbb{E}_v \left[ {\mathcal{D}_{M'} } \right] \\ = \sum\limits_{i = 1}^M {\left( {N_{C_i }  - 1} \right)} p - \sum\limits_{i = 1}^{M'} {\left( {N_{C_i }  - 1} \right)} p \\
\ge M\left( {N_{\min }  - 1} \right)p - M'\left( {N_{\max }  - 1} \right)p \\
\ge - M'\varepsilon p + \left( {M - M'} \right)\left( {N_{\min }  - 1} \right)p \\
\ge - M'\left(\frac{{N_{\min }  - 1}}{K}-1\right)p + \left( {M - M'} \right)\left( {N_{\min }  - 1} \right)p \\
= \left( {M - M' - \frac{{M'}}{K}} \right)\left( {N_{\min }  - 1} \right)p + M'p \\
\ge 0, \\
\end{array}
\end{equation}

where the second inequality holds due to (<ref>) and the last inequality comes from $M'<M\le K$. This completes the proof of this theorem.

From Theorem 4.1, one can see that selecting a node belonging to more communities is expected to result in faster network exploration due to the fact that more neighbors of the queried node can be discovered. In other words, nodes within areas of more overlapping communities have higher chances of being connected to other nodes, enabling efficient network exploration, which supports our design principle in query node selection.

For any node $u$ belonging to $M$ $(\ge 2)$ communities in an underlying network $\mathcal{G}=(\mathcal{V},\mathcal{E})$ and any arbitrary node $v$ in $\mathcal{G}$, if $\varepsilon  \le \frac{{N_{\min }  - 1}}{K} - 1$, then the following inequality holds:

\begin{equation}
\mathbb{E}_u \left[ {\mathcal{D}_M } \right] \ge \mathbb{E}_v \left[ \mathcal{D} \right],
\end{equation}

where $\mathbb{E}_{u } \left[ {\mathcal{D}_M } \right]$ is the expectation of degree distributions over the nodes belonging to $M$ communities, while $\mathbb{E}_{v } \left[ {\mathcal{D} } \right]$ is the expectation of degree distributions over all the nodes in $\mathcal{G}$.

The average degree of a randomly selected node $v$ in $\mathcal{G}$, denoted by $\mathbb{E}_v \left[ \mathcal{D} \right]$, is given by

\begin{equation}
\begin{array}{l}
\mathbb{E}_v \left[ \mathcal{D} \right] = \sum\limits_{i = 1}^K {\mathbb{E}_v } \left[ {\mathcal{D}\left| {A_i } \right.} \right]\mathbb{P}\left( {A_i } \right) \\
\;\;\;\;\;\;\;\;\;\;\; = \frac{{\sum\limits_{i = 1}^K {\mathbb{E}_v \left[ {\mathcal{D}\left| {A_i } \right.} \right]N_i } }}{N} \\
\;\;\;\;\;\;\;\;\;\;\;\le  \frac{2\mathbb{E}_v \left[ {\mathcal{D}\left| {A_1 } \right.} \right]N_1 }{N} \\
\;\;\;\;\;\;\;\;\;\;\;\le 2\left(N_{\max }-1\right) p\frac{K}{{K + 1}} \\
% \;\;\;\;\;\;\;\;\;\;\;\le 2\left( {N_{\max }  - 1} \right)p\frac{{\frac{{N_{\min }  - 1}}{{\varepsilon  + 1}}}}{{\frac{{N_{\min }  - 1}}{{\varepsilon  + 1}} + 1}} \\
\;\;\;\;\;\;\;\;\;\;\;\le 2\left( {N_{\max }  - 1} \right)p\frac{{N_{\min }  - 1}}{{N_{\min }  + \varepsilon }} \\
\;\;\;\;\;\;\;\;\;\;\; \le 2\left(N_{\max }-1\right) p\frac{{N_{\min } - 1}}{{N_{\max } }} \\
\;\;\;\;\;\;\;\;\;\;\; \le \sum\limits_{i = 1}^M {\left( {N_{C_i }  - 1} \right)} p \\
\;\;\;\;\;\;\;\;\;\;\; =\mathbb{E}_u\left[\mathcal{D}_M \right],
\end{array}
\end{equation}

where the first two inequalities hold due to (<ref>) and the third and fourth inequalities come from $\varepsilon\le\frac{N_\text{min}-1}{K}-1$ and (<ref>), respectively. This completes the proof of this theorem.

Theorem 4.2 further confirms that the proposed node query strategy yields faster network exploration compared to the random selection for node query. Our strategy attempts to select the nodes within areas of overlapping communities, which exhibit denser connections, thus accelerating the expansion of the explored network.

§.§.§ Complexity Analysis

To validate the scalability of our  method, we analytically show its computational complexity by establishing the following theorem.

The computational complexity of the proposed
method is given by $\mathcal{O}\left( {\left| \mathcal{E} \right|} \right)$.

We analyze the computational complexity of each step in . In Step 1, a GNN model is utilized to generate the community-affiliation embedding matrix ${\bf F}$, with a training complexity of $\mathcal{O}\left( {L_1\left| \mathcal{E} \right|} \right) $ per epoch [57], where $L_1$ is the number of GNN layers. In Step 2, the node query strategy in (<ref>) has a complexity of $\mathcal{O}\left( {NK + tNK} \right) $, where $N$ and $K$ are the number of nodes and communities, respectively. Finally, in Step 3, the training of MLPs dominates the complexity of this step and has a complexity of $\mathcal{O}\left( {L_2\left| \mathcal{E} \right|} \right) $ [58],  where $L_2$ is the number of MLP layers, conditioned that the size of model parameters ${\left| {{\bf W}_{Sia} } \right|} $ in MLPs does not scale with ${\left| \mathcal{E} \right|} $. Therefore, the total complexity of our  method is finally bounded by $\mathcal{O}\left( {\left| \mathcal{E} \right|} \right) $. This completes the proof of this theorem.

From Theorem 4.3, one can see that the computational complexity of  scales linearly with the number of edges in the underlying network.

§ EXPERIMENT EVALUATION

In this section, we describe the datasets used in our evaluation and six benchmark overlapping community detection methods, including a simple variant of , for comparison. After describing the performance metrics and experimental settings, we comprehensively evaluate the performance of our  method and the six benchmark methods.
We design our extensive empirical study to answer the following six key research questions (RQs):

* RQ1: How much does  improve the performance of community detection over benchmark overlapping community detection methods?

* RQ2: How does each module in  contribute to community detection accuracy?

* RQ3: How effective is our query node strategy for fast network exploration?

* RQ4: How close is the inferred network to the underlying true network?

* RQ5: How do key parameters affect the performance of ?

* RQ6: How scalable is  with the size of the network?

§.§ Datasets

We conduct our experiments on five real-world datasets across several domains, which include three social networks and two large co-authorship networks. For the sake of consistency, we assume all networks to be undirected. Table <ref> provides a summary of the statistics for each dataset, including the number of nodes, edges, communities, and node features. In the following, we summarize the important characteristics of the datasets.[Additional experimental results on social networks can be found in the supplementary materials. Although there are other social and large co-authorship networks, we have not adopted them since they exhibit similar tendencies to those datasets under consideration.]

Ego-Facebook, Ego-Twitter, and Ego-Google+ [30]. The Ego-Facebook, Ego-Twitter, and Ego-Google+ datasets are social networks that captures friendship ties collected from Facebook, Twitter, Google+, respectively,[As there are a number of ego-networks sampled from the original network, we use Facebook 348, Twitter 745823, and Google+ 100129275726588145876 in our experiments. For brevity, we omit the index of each ego-network.] using breadth-first search (BFS) sampling. Nodes and edges in these datasets represent users and friendship ties, respectively. Node features are anonymized information on each user’s profile.

Coauthorship-Engineering (Engineering) and Coauthorship-Computer Science (Computer Science) [7]. The Coauthorship-Engineering and Coauthorship-Computer Science datasets are two co-authorship networks, constructed from the Microsoft Academic Graph [59]. Here, nodes are authors who are connected by an edge if they co-authored a paper. Node features represent paper keywords for each author’s papers, and communities correspond to research areas.

The statistics of the datasets.

Dataset    Nodes     Edges     Communities     Features

Facebook     227     3,192     14     161

Twitter    249    4,372     8     1,174

Google+     1692     15,148     2     1319

Engineering    14,927    49,305     16     4,839

Computer Science     21,957     96,750     18     7,793

§.§ Benchmark Methods

Since there is no prior work on overlapping community detection in networks with unknown topology, in our experiments, we consider five state-of-the-art overlapping community detection methods originally developed for fully observable networks, which require an extra step to infer the network structure. To this end, we employ two sampling strategies for network exploration via node queries: random sampling (RS) and depth-first search (DFS).[Although other sophisticated sampling strategies such as biased random walks can also be employed, these were not employed in our study since they have similar tendencies to those of RS and DFS.] The benchmark methods are implemented similarly as in , with iterative community detection performed alongside the explored network through sampling given a budget of node queries. We implement all these benchmark methods using the parameter settings described in their original articles.

BIGCLAM [5]. This is a scalable method for detecting overlapping communities in large networks using NMF. The method involves factorizing the network's adjacency matrix into two non-negative matrices that represent the community structure and the affiliation of nodes to communities.

vGraph [21]. This is a generative model that simultaneously performs community detection and node representation learning in a network. vGraph learns community memberships and node representations that are optimized for preserving the local network structure and the community structure.

CLARE [60]. This is a semi-supervised approach that first locates potential communities by seeking communities in the network with few labeled communities as training data. Then, it uses a community rewriter, enhanced by deep reinforcement learning, to further adjust and refine community structures in a flexible manner.

NOCD [7]. This method learns the community affiliations through the combined use of the BP model and GNNs by minimizing the negative log-likelihood of the BP model.

DMoN [61]. This is an unsupervised pooling method inspired by the modularity, utilizing GNNs for graph clustering.

Note that, CLARE, NOCD, and DMoN make use of both the network structure and the node metadata for detecting communities. Additionally, in our experiments, we take into account our own simple variant of , dubbed sim, developed for networks with unknown topology.

sim. This baseline method starts with randomly querying a given percentage of nodes and then discovering the neighbors of these queried nodes for network exploration. As the next step, EC-SiamNet in Section 4.4 is utilized to infer edges based on the explored network. Finally, the GNN model in Section 4.2 is employed to generate the community-affiliation embeddings ${\bf F}$.

Note that, unlike the original , sim runs only once without iterations.

§.§ Performance Metrics

To evaluate the performance of community detection, we quantify the degree of agreement between the ground truth communities and the detected communities by adopting the normalized mutual information (NMI) [62] and the average $\text{F}_1$ score (Avg$\text{F}_1$) [5]. Note that both metrics have values within the range of $\left[ {0,1} \right] $, with higher values indicating better performance. We refer to the supplementary materials for the formal definition of NMI and Avg$\text{F}_1$.

§.§ Experiment Setup

We describe the experiment settings of neural networks (i.e., the GNN and MLP models) in our  method. We adopt GCN [27] with 2 layers to extract the community-affiliation embeddings and two-layer MLPs as the backbone of our EC-SiamNet for network inference. PyTorch Geometric [63], a geometric deep learning extension library in PyTorch, is used to implement the GCN and MLPs. We set the hidden layer dimensions of each GCN and MLP to 128 and 256, respectively. The Adam optimizer [64] with a learning rate of 0.001 and 0.05 is used to train the GNN and MLPs, respectively. Moreover, we tune the hyperparameters $\eta$ and $\lambda$ within designated ranges of $\eta  \in \left[ {1.0,2.0} \right] $ and $\lambda  \in \left[ {1.0,4.0} \right] $.

Next, as a default experiment setting, we conduct experiments for  with a fixed query budget $T$ as a percentage of all nodes in the underlying network, varying from 10% to 40% with an increment of 10% across all datasets, as shown in Table <ref>. It is noted that, in the co-authorship datasets (i.e., Engineering and Computer Science), we perform network inference on every 1% of query nodes, instead of every iteration, for computational efficiency. This is due to the fact that obtaining information from only a single queried node's neighbors does not lead to a significant improvement in network inference for such large datasets. Each experiment is conducted 5 times to evaluate the average performance. All experiments are carried out with Intel (R) 12-Core (TM) E5-1650 v4 CPUs @ 3.60 GHz and 64GB RAM.

§.§ Results and Analyses

In this subsection, we describe the comprehensive experiments conducted to answer the aforementioned RQs. To address RQ1, we provide the experiment results on all datasets. To address RQ2–RQ5, we detail the results on Facebook and Engineering since the results on the other datasets have similar tendencies.

Performance comparison of , sim, and 10 competing methods in terms of two metrics (average $\pm$ standard deviation) when different percentages (%) of nodes are queried among $N$ nodes. Here, the best and second-best performers are highlighted by bold and underline, respectively.

2c|   2|c|10% queried nodes   2c|20% queried nodes   2c|30% queried nodes   2c40% queried nodes

Dataset   Method     NMI    Avg$\text{F}_1$     NMI    Avg$\text{F}_1$     NMI    Avg$\text{F}_1$    NMI    Avg$\text{F}_1$

BIGCLAM+RS     0.0263$\pm$0.0056    0.4349$\pm$0.0213    0.0539$\pm$0.0193    0.5025$\pm$0.0681    0.0703$\pm$0.0135    0.5896$\pm$0.0117    0.1083$\pm$0.0162    0.6503$\pm$0.1299

BIGCLAM+DFS    0.0379$\pm$0.0057    0.4757$\pm$0.0115    0.0571$\pm$0.0211    0.5364$\pm$0.0351    0.0657$\pm$0.0197    0.5452$\pm$0.0733    0.0785$\pm$0.0139    0.5987$\pm$0.0448

vGraph+RS    0.0559$\pm$0.0152    0.5700$\pm$0.0149    0.0914$\pm$0.0089    0.7046$\pm$0.0550    0.1332$\pm$0.0116    0.7233$\pm$0.0461    0.1573$\pm$0.0098    0.7708$\pm$0.0398

vGraph+DFS    0.0601$\pm$0.0221    0.5526$\pm$0.0527    0.0943$\pm$0.0104    0.6614$\pm$0.0288    0.1030$\pm$0.0180    0.7079$\pm$0.0584    0.1272$\pm$0.0103    0.7297$\pm$0.0356

CLARE+RS    0.0681$\pm$0.0110    0.6623$\pm$0.2354    0.0905$\pm$0.0117    0.6945$\pm$0.0277    0.1171$\pm$0.0130    0.7351$\pm$0.0204    0.1312$\pm$0.0113    0.7621$\pm$0.0209

CLARE+DFS    0.0691$\pm$0.0131    0.6843$\pm$0.0200    0.0961$\pm$0.0137    0.7081$\pm$0.0162    0.1008$\pm$0.0121    0.7245$\pm$0.0251    0.1284$\pm$0.0122    0.7548$\pm$0.0130

NOCD+RS    0.0704$\pm$0.0191    0.6503$\pm$0.0960    0.1022$\pm$0.0189    0.6627$\pm$0.0436    0.1422$\pm$0.0111    0.7445$\pm$0.0168    0.1958$\pm$0.0191    0.7652$\pm$0.0399

NOCD+DFS    0.0594$\pm$0.0111    0.5471$\pm$0.0283    0.0965$\pm$0.0213    0.6568$\pm$0.0616    0.1329$\pm$0.0218    0.7352$\pm$0.0713    0.1683$\pm$0.0247    0.7885$\pm$0.0542

DMoN+RS    0.0681$\pm$0.0297    0.6483$\pm$0.0374    0.0914$\pm$0.0209    0.7197$\pm$0.0184    0.1256$\pm$0.0119    0.7596$\pm$0.0325    0.1449$\pm$0.0132    0.7930$\pm$0.0428

DMoN+DFS    0.0702$\pm$0.0178    0.6521$\pm$0.0374    0.0923$\pm$0.0184    0.7258$\pm$0.0446    0.1264$\pm$0.0152    07481$\pm$0.0494    0.1426$\pm$0.0152    0.7715$\pm$0.0358

sim    0.0907$\pm$0.0226    0.7206$\pm$0.0473    0.1572$\pm$0.0335    0.7515$\pm$0.0282    0.2054$\pm$0.0188    0.8287$\pm$0.0408    0.2220$\pm$0.0142    0.8589$\pm$0.0428

0.0980$\pm$0.0242    0.7493$\pm$0.0673    0.1692$\pm$0.0464    0.8029$\pm$0.0688    0.2192$\pm$0.0229    0.8623$\pm$0.0142    0.2517$\pm$0.0097    0.8818$\pm$0.0367

BIGCLAM+RS     0.0307$\pm$0.0083    0.5891$\pm$0.0282    0.0341$\pm$0.0075    0.6102$\pm$0.0289    0.0399$\pm$0.0107    0.6409$\pm$0.0404    0.0450$\pm$0.0057    0.6523$\pm$0.0154

BIGCLAM+DFS    0.0328$\pm$0.0031    0.6001$\pm$0.0162    0.0354$\pm$0.0112    0.6208$\pm$0.0206    0.0376$\pm$0.0056    0.6386$\pm$0.0099    0.0395$\pm$0.0066    0.6454$\pm$0.0281

vGraph+RS    0.0305$\pm$0.0083    0.6102$\pm$0.0374    0.0391$\pm$0.0083    0.6321$\pm$0.0479    0.0456$\pm$0.0051    0.6605$\pm$0.0375    0.0478$\pm$0.0056    0.6703$\pm$0.0440

vGraph+DFS    0.0337$\pm$0.0041    0.5739$\pm$0.0474    0.0431$\pm$0.0113    0.6309$\pm$0.0158    0.0465$\pm$0.0053    0.6470$\pm$0.0282    0.0474$\pm$0.0046    0.6544$\pm$0.0238

CLARE+RS    0.0349$\pm$0.0213    0.5691$\pm$0.0139    0.0424$\pm$0.0340    0.6125$\pm$0.0309    0.0458$\pm$0.0105    0.6362$\pm$0.0261    0.0477$\pm$0.0197    0.6523$\pm$0.0347

CLARE+DFS    0.0361$\pm$0.0112    0.5786$\pm$0.0168    0.0447$\pm$0.0107    0.6222$\pm$0.0322    0.0477$\pm$0.0112    0.6497$\pm$0.0254    0.0483$\pm$0.0120    0.6685$\pm$0.0275

NOCD+RS    0.0402$\pm$0.0101    0.5113$\pm$0.0569    0.0566$\pm$0.0256    0.5910$\pm$0.0372    0.0568$\pm$0.0177    0.6224$\pm$0.0431    0.0894$\pm$0.0260    0.6355$\pm$0.0508

NOCD+DFS    0.0518$\pm$0.0187    0.5487$\pm$0.0939    0.0973$\pm$0.0356    0.6314$\pm$0.0772    0.1101$\pm$0.0094    0.6518$\pm$0.0509    0.1181$\pm$0.0225    0.6645$\pm$0.0474

DMoN+RS    0.0211$\pm$0.0039    0.4380$\pm$0.0498    0.0283$\pm$0.0085    0.4568$\pm$0.0538    0.0450$\pm$0.0183    0.5357$\pm$0.0631    0.0524$\pm$0.0156    0.5403$\pm$0.0786

DMoN+DFS    0.0251$\pm$0.0027    0.4512$\pm$0.0751    0.0321$\pm$0.0053    0.4664$\pm$0.0587    0.0647$\pm$0.0172    0.6424$\pm$0.0413    0.0672$\pm$0.0221    0.6464$\pm$0.0395

sim    0.0712$\pm$0.0172    0.6754$\pm$0.0229    0.1004$\pm$0.0135    0.7068$\pm$0.0171    0.1113$\pm$0.0106    0.7245$\pm$0.0349    0.1188$\pm$0.0125    0.7334$\pm$0.0313

0.0868$\pm$0.0135    0.7322$\pm$0.0437    0.1167$\pm$0.0346    0.7512$\pm$0.0287    0.1209$\pm$0.0237    0.7585$\pm$0.0185    0.1287$\pm$0.0237    0.7897$\pm$0.0368

BIGCLAM+RS     0.0428$\pm$0.0023    0.3741$\pm$0.0318    0.0594$\pm$0.0062    0.4453$\pm$0.0146    0.0845$\pm$0.0285    0.4964$\pm$0.0365    0.1444$\pm$0.0140    0.5113$\pm$0.0365

BIGCLAM+DFS    0.0448$\pm$0.0069    0.3756$\pm$0.0386    0.0689$\pm$0.0245    0.4540$\pm$0.0278    0.0836$\pm$0.0202    0.5069$\pm$0.0312    0.1436$\pm$0.0121    0.5102$\pm$0.0375

vGraph+RS    0.0455$\pm$0.0051    0.4502$\pm$0.0307    0.0555$\pm$0.0126    0.4850$\pm$0.0142    0.0822$\pm$0.0119    0.4986$\pm$0.0213    0.0980$\pm$0.0131    0.5164$\pm$0.0127

vGraph+DFS    0.0425$\pm$0.0081    0.4751$\pm$0.0099    0.0496$\pm$0.0105    0.4799$\pm$0.0167    0.0725$\pm$0.0158    0.4815$\pm$0.0188    0.0924$\pm$0.0158    0.5017$\pm$0.0144

CLARE+RS    0.0452$\pm$0.0125    0.4813$\pm$0.0113    0.0625$\pm$0.0127    0.5009$\pm$0.0165    0.0897$\pm$0.0135    0.5239$\pm$0.0285    0.1097$\pm$0.0134    0.5354$\pm$0.0225

CLARE+DFS    0.0467$\pm$0.0071    0.4958$\pm$0.0129    0.0677$\pm$0.0095    0.5122$\pm$0.0229    0.0889$\pm$0.0113    0.5197$\pm$0.0148    0.1009$\pm$0.0106    0.5285$\pm$0.0174

NOCD+RS    0.1449$\pm$0.0146    0.4971$\pm$0.0272    0.1842$\pm$0.0258    0.5940$\pm$0.0292    0.2644$\pm$0.0189    0.6364$\pm$0.0362    0.2710$\pm$0.0189    0.6864$\pm$0.0409

NOCD+DFS    0.1948$\pm$0.0395    0.5069$\pm$0.0459    0.2222$\pm$0.0264    0.5974$\pm$0.0218    0.2319$\pm$0.0107    0.6215$\pm$0.0218    0.2592$\pm$0.0183    0.6754$\pm$0.0369

DMoN+RS    0.1452$\pm$0.0161    0.5465$\pm$0.0378    0.1681$\pm$0.0104    0.5867$\pm$0.0302    0.1698$\pm$0.0037    0.5882$\pm$0.0188    0.1707$\pm$0.0030    0.6174$\pm$0.0271

DMoN+DFS    0.1510$\pm$0.0092    0.5457$\pm$0.0177    0.1685$\pm$0.0093    0.5868$\pm$0.0187    0.1691$\pm$0.0072    0.6209$\pm$0.0360    0.1732$\pm$0.0083    0.6551$\pm$0.0140

sim    0.2058$\pm$0.0086    0.5528$\pm$0.0142    0.2563$\pm$0.0167    0.5893$\pm$0.0113    0.3024$\pm$0.0104    0.6479$\pm$0.0197    0.3226$\pm$0.0120    0.6911$\pm$0.0185

0.2327$\pm$0.0024    0.5715$\pm$0.0303    0.2766$\pm$0.0116    0.6056$\pm$0.0104    0.3359$\pm$0.0205    0.6651$\pm$0.0314    0.3478$\pm$0.0105    0.7269$\pm$0.0236

BIGCLAM+RS     0.0000$\pm$0.0000    0.1315$\pm$0.0386     0.0000$\pm$0.0000    0.2635$\pm$0.0207    0.0000$\pm$0.0000    0.3015$\pm$0.0531    0.0144$\pm$0.0133     0.4659$\pm$0.0317

BIGCLAM+DFS    0.0029$\pm$0.0066    0.3460$\pm$0.0370    0.0194$\pm$0.0123    0.4530$\pm$0.0674    0.0406$\pm$0.0192    0.5160$\pm$0.0351    0.0590$\pm$0.0088    0.5980$\pm$0.0387

vGraph+RS    0.0000$\pm$0.0000    0.1972$\pm$0.0282    0.0000$\pm$0.0000    0.3334$\pm$0.0080    0.0334$\pm$0.0042    0.4702$\pm$0.0188    0.0522$\pm$0.0116    0.5877$\pm$0.0913

vGraph+DFS    0.0000$\pm$0.0000    0.3219$\pm$0.0084    0.0281$\pm$0.0114    0.4449$\pm$0.0642    0.0368$\pm$0.0054    0.4811$\pm$0.0820    0.0504$\pm$0.0194    0.5217$\pm$0.0137

CLARE+RS    0.0109$\pm$0.0104    0.2641$\pm$0.0129    0.0194$\pm$0.0117    0.3747$\pm$0.0151    0.0541$\pm$0.0122    0.4387$\pm$0.0226    0.0674$\pm$0.0192    0.4954$\pm$0.0174

CLARE+DFS    0.0114$\pm$0.0123    0.2954$\pm$0.0154    0.0189$\pm$0.0110    0.3528$\pm$0.0138    0.0529$\pm$0.0114    0.4219$\pm$0.0245    0.0546$\pm$0.0148    0.5789$\pm$0.0216

NOCD+RS    0.1262$\pm$0.0219    0.7081$\pm$0.0277    0.2148$\pm$0.0113    0.7924$\pm$0.0367    0.2875$\pm$0.0182    0.8387$\pm$0.0238    0.3128$\pm$0.0175    0.8529$\pm$0.0370

NOCD+DFS    0.1466$\pm$0.0322    0.7542$\pm$0.0598    0.2046$\pm$0.0185    0.7760$\pm$0.0638    0.2702$\pm$0.0158    0.8261$\pm$0.0304    0.3038$\pm$0.0172    0.8427$\pm$0.0178

DMoN+RS    0.1782$\pm$0.0276    0.7562$\pm$0.0090    0.2248$\pm$0.0148    0.7854$\pm$0.0432    0.2534$\pm$0.0266    0.8095$\pm$0.0222    0.2693$\pm$0.0265    0.8242$\pm$0.0302

DMoN+DFS    0.1822$\pm$0.0195    0.7691$\pm$0.0402    0.2204$\pm$0.0062    0.7898$\pm$0.0319    0.2396$\pm$0.0271    0.8131$\pm$0.0432    0.2431$\pm$0.0250    0.8237$\pm$0.0356

sim     0.1858$\pm$0.0258    0.7584$\pm$0.0490    0.2324$\pm$0.0246    0.7941$\pm$0.0421    0.2671$\pm$0.0466    0.8105$\pm$0.0240    0.3032$\pm$0.0288     0.8316$\pm$0.0456

0.2072$\pm$0.0198    0.7838$\pm$0.0366    0.2785$\pm$0.0430    0.8208$\pm$0.0341    0.3080$\pm$0.0256    0.8548$\pm$0.0207    0.3288$\pm$0.0326    0.8694$\pm$0.0280

11*90Computer Science
BIGCLAM+RS    0.0000$\pm$0.0000    0.1164$\pm$0.0104    0.0000$\pm$0.0000    0.2167$\pm$0.0089    0.0000$\pm$0.0000    0.2914$\pm$0.0214    0.0042$\pm$0.0003    0.3624$\pm$0.0312

BIGCLAM+DFS    0.0000$\pm$0.0000    0.1739$\pm$0.0213    0.0000$\pm$0.0000    0.2154$\pm$0.0111    0.0000$\pm$0.0000    0.3468$\pm$0.0341    0.0035$\pm$0.0004    0.3719$\pm$0.0272

vGraph+RS    0.0017$\pm$0.0003    0.3140$\pm$0.0152    0.0028$\pm$0.0024    0.3379$\pm$0.0012    0.0050$\pm$0.0061    0.3543$\pm$0.0323    0.0106$\pm$0.0172    0.3579$\pm$0.0181

vGraph+DFS    0.0042$\pm$0.0002    0.2942$\pm$0.0143    0.0046$\pm$0.0004    0.3151$\pm$0.0042    0.0051$\pm$0.0012    0.3308$\pm$0.0073    0.0056$\pm$0.0006    0.3419$\pm$0.0086

CLARE+RS    0.0120$\pm$0.0118    0.3754$\pm$0.0218    0.0278$\pm$0.0141    0.4884$\pm$0.0284    0.0528$\pm$0.0101    0.5187$\pm$0.0235    0.0754$\pm$0.0147    0.5478$\pm$0.0238

CLARE+DFS    0.0145$\pm$0.0111    0.4085$\pm$0.0176    0.0257$\pm$0.0132    0.4548$\pm$0.0213    0.0492$\pm$0.0130    0.4999$\pm$0.0255    0.0698$\pm$0.0127    0.5265$\pm$0.0247

NOCD+RS    0.2568$\pm$0.0411    0.7125$\pm$0.0226    0.3724$\pm$0.0089    0.7810$\pm$0.0144    0.3972$\pm$0.0281    0.8174$\pm$0.0173    0.4205$\pm$0.0221    0.8438$\pm$0.0164

NOCD+DFS    0.1741$\pm$0.0302    0.6738$\pm$0.0377    0.3018$\pm$0.0118    0.7473$\pm$0.0145    0.3617$\pm$0.0275    0.7947$\pm$0.0173    0.4074$\pm$0.0165    0.8250$\pm$0.0270

DMoN+RS    0.2230$\pm$0.0656    0.7569$\pm$0.0541    0.2583$\pm$0.0455    0.7719$\pm$0.0533    0.2914$\pm$0.0123    0.8095$\pm$0.0411    0.3087$\pm$0.0379    0.8128$\pm$0.0420

DMoN+DFS    0.2077$\pm$0.0550    0.7570$\pm$0.0389    0.2414$\pm$0.0438    0.7787$\pm$0.0375    0.2784$\pm$0.0243    0.7799$\pm$0.0310    0.2961$\pm$0.0210    0.8018$\pm$0.0419

sim    0.3138$\pm$0.0177    0.7882$\pm$0.0258    0.3408$\pm$0.0313    0.8113$\pm$0.0289    0.3799$\pm$0.0268    0.8437$\pm$0.0379    0.4223$\pm$0.0261    0.8595$\pm$0.0254

0.3507$\pm$0.0204    0.8124$\pm$0.0381    0.4005$\pm$0.0169    0.8408$\pm$0.0322    0.4237$\pm$0.0360    0.8611$\pm$0.0480    0.4408$\pm$0.0223    0.8820$\pm$0.0389

§.§.§ Comparison With Benchmark Methods (RQ1)

A performance comparison of our  methods as well as five state-of-the-art overlapping community detection methods, each combined with two sampling strategies, is presented in Table <ref>. The comparison is made with respect to two performance metrics, NMI and Avg$\text{F}_1$, across five real-world datasets where a different percentage of nodes are queried among $N$ nodes. We note that the hyperparameters in all the aforementioned methods are tuned differently according to each individual dataset to obtain the best performance. We make the following insightful observations:

Ablation study on Facebook and Engineering. Here, the best and second-best performers are highlighted by bold and underline, respectively.

2c|   2|c|10% queried nodes   2c|20% queried nodes   2c|30% queried nodes   2c40% queried nodes

Dataset    Method     NMI    Avg$\text{F}_1$     NMI    Avg$\text{F}_1$     NMI    Avg$\text{F}_1$     NMI    Avg$\text{F}_1$

0.0783$\pm$0.0199    0.5562$\pm$0.0151    0.1151$\pm$0.0312    0.6230$\pm$0.0137    0.1442$\pm$0.0329    0.6711$\pm$0.0361    0.1647$\pm$0.0081    0.8033$\pm$0.0446

0.0669$\pm$0.0187    0.5335$\pm$0.0170    0.0755$\pm$0.0352    0.5846$\pm$0.0247    0.0981$\pm$0.0255    0.6352$\pm$0.0394    0.1368$\pm$0.0396    0.6958$\pm$0.0641

0.0814$\pm$0.0321    0.7203$\pm$0.0516    0.1588$\pm$0.0245    0.7941$\pm$0.0280    0.2108$\pm$0.0197    0.8098$\pm$0.0696    0.2487$\pm$0.0211    0.8709$\pm$0.0231

0.0791$\pm$0.0198    0.6842$\pm$0.0343    0.1132$\pm$0.0167    0.7221$\pm$0.0567    0.1578$\pm$0.0169    0.7923$\pm$0.0493    0.2003$\pm$0.0164    0.8218$\pm$0.0085

0.0980$\pm$0.0242    0.7493$\pm$0.0673    0.1692$\pm$0.0464    0.8029$\pm$0.0688    0.2192$\pm$0.0229    0.8623$\pm$0.0142    0.2517$\pm$0.0097    0.8818$\pm$0.0367

0.1371$\pm$0.0108    0.5729$\pm$0.0364    0.1532$\pm$0.0276    0.6031$\pm$0.0219    0.1887$\pm$0.0281    0.6598$\pm$0.0210    0.2145$\pm$0.0294    0.6946$\pm$0.0394

0.0921$\pm$0.0135    0.5245$\pm$0.0271    0.1265$\pm$0.0217    0.5725$\pm$0.0428    0.1629$\pm$0.0297    0.6214$\pm$0.0239    0.1968$\pm$0.0204    0.6611$\pm$0.0255

0.1874$\pm$0.0237    0.7619$\pm$0.0331    0.2584$\pm$0.0101    0.8104$\pm$0.0238    0.2934$\pm$0.0274    0.8487$\pm$0.0134    0.3207$\pm$0.0190    0.8602$\pm$0.0207

0.1575$\pm$0.0371    0.7613$\pm$0.0193    0.2177$\pm$0.0207    0.8079$\pm$0.0193    0.2921$\pm$0.0169    0.8431$\pm$0.0177    0.3191$\pm$0.0302    0.8581$\pm$0.0175

0.2072$\pm$0.0198    0.7838$\pm$0.0866    0.2785$\pm$0.0430    0.8208$\pm$0.0341    0.3080$\pm$0.0256    0.8548$\pm$0.0207    0.3288$\pm$0.0326    0.8692$\pm$0.0580

* Our  method consistently and significantly outperforms all the benchmark methods regardless of the datasets and the performance metrics.

* The second-best performer tends to be sim. sim is superior to the five state-of-the-art methods for almost all cases since it contains modules with sophisticated design, which include 1) network inference with the aid of EC-SiamNet and 2) GNN-aided community-affiliation embedding using our reconstruction loss. However, sim is always inferior to the original  due to the lack of network exploration via judicious node queries and iterative steps. In other words, sim overlooks not only the potential of query node selection to expedite network exploration but also the gradual increase of performance in community detection through the iterative process.

* Among the state-of-the-art methods, the best competitor tends to be NOCD with RS in most cases since NOCD also generates community-affiliation embeddings via GNNs with the aid of node metadata, which is capable of precisely discovering communities. In comparison with NOCD, the proposed  and sim methods use reconstruction loss, which takes into account both structure–community and metadata–community relationships to generate community-affiliation embeddings, thereby resulting in better performance than NOCD.

* DMoN leverages modularity for training GNNs, where modularity relies heavily on the network structure. This may result in comparatively lower performance than that of NOCD, especially when only a few nodes are queried.

* The performance gap between  ($X$) and sim ($Y$) is the largest when the Engineering dataset is used; the maximum improvement rate of 19.84% is achieved in terms of NMI, where the improvement rate (%) is given by $\frac{{X - Y}}{Y} \times 100 $. Additionally, the maximum improvement rate between our  method and the best state-of-the-art method is 65.55% in terms of NMI when the Facebook dataset is used.

* The improvement rates of  in terms of NMI and Avg$\text{F}_1$ tend to decrease as the percentage of queried nodes increases. For instance, in the Computer Science dataset, the NMI improvement rates are 14.20%, 5.79%, and 4.03% when the percentage of queried nodes increases from 10% to 20%, 20% to 30%, and 30% to 40%, respectively. This is due to the fact that, as the percentage of queried nodes increases, the size of the unexplored part in the network diminishes and the explored network converges to the underlying true network.

* Let us compare two sampling strategies for network exploration used in the benchmark methods. When a small number of nodes are queried (i.e., the explored network is small), combining each benchmark method with DFS tends to result in better performance compared to the case using RS. However, when a sufficient number of nodes are queried, using RS for network exploration tends to result in better performance. For example, on Facebook, vGraph with DFS is superior to vGraph with RS when 10–20% of nodes are queried, while vGraph with RS performs better when more than 30% of nodes are queried. This is because DFS can locally explore the subnetwork in a single community faster, which is beneficial to the early stage of community detection. On the other hand, as the number of queried nodes increases, the local network in a community may be almost explored and it is better to explore other parts of the underlying network. This supports the claim that the node query strategy in  is designed in such a way that nodes distributed over diverse communities are selected for faster exploration.

§.§.§ Impact of Components in  (RQ2)

To discover what role each component plays in the
success of the proposed  method, we conduct an
ablation study by removing or replacing each module in our method.

* : This corresponds to the original  method.

* : The GNN model in  is replaced with BIGCLAM [5] to generate community-affiliation embeddings.

* : The GNN model in  is replaced with MLP to generate community-affiliation embeddings.

* : The node query strategy in  is replaced with RS for network exploration.

* : The network inference step in  is removed. That is, it becomes our prior work [15].

A performance comparison of the original  and its four variants is presented in Table <ref> with respect to NMI and Avg$\text{F}_1$ using the Facebook and Engineering datasets. Our findings are as follows:

* The original  method always exhibits potential gains over the other variants, which demonstrates that each module plays a critical role together in discovering communities.

* The performance gap between  and  is much higher compared to the other variants for both datasets.

*  outperforms , which can be attributed to the fact that BIGCLAM was originally designed for community detection, whereas MLP fails to precisely capture the structure–community relationship.

*  achieves remarkable gains over  (i.e., our prior work [15]), which implies that the network inference step is essential in achieving more accurate community detection results. Compared to ,  leverages the structural information acquired from network exploration to the maximum, resulting in superior community detection performance.

legend columns=6,
legend entries=,RS,DFS,
legend to name=named,
xlabel= (a) Facebook, ylabel = $N_{ex}$,  width = 3.7cm, height = 3.7cm,

+[color=black] coordinates(0.1, 191)(0.2, 215)(0.3, 223)(0.4, 225);
+[color=orange] coordinates(0.1, 177)(0.2, 201)(0.3, 212)(0.4, 218);
+[color=purple] coordinates(0.1, 156)(0.2, 189)(0.3, 196)(0.4, 199);

xlabel=(b) Engineering, ylabel = $N_{ex}$,  width = 3.7cm, height = 3.7cm,

+[color=black] coordinates(0.1, 7153)(0.2, 10470)(0.3, 12872)(0.4, 14285);
+[color=orange] coordinates(0.1, 6656)(0.2, 10312)(0.3, 12340)(0.4, 13465);
+[color=purple] coordinates(0.1, 5766)(0.2, 8311)(0.3, 10085)(0.4, 11436);

The number of explored nodes, $N_\text{ex}$, according to different percentages (%) of queried nodes among $N$ nodes on Facebook and Engineering.

§.§.§ Growth of Explored Subnetworks (RQ3)
To empirically validate the effectiveness of our node query strategy, we conduct experiments on Facebook and Engineering by plotting the number of explored nodes, denoted as $N_\text{ex}$, versus the percentages of queried nodes in Fig. <ref>. We compare our query strategy with two cases in which two sampling strategies (i.e., RS and DFS) are employed for network exploration in  rather than the strategy proposed in (<ref>). Our findings are as follows:

* Our query strategy based on the discovered community affiliations is consistently more beneficial compared to other samplings as it leads to the faster exploration of the unknown parts of the underlying network.

* The growth rate of $N_\text{ex}$ for RS is even higher than that for DFS since querying nodes away from explored subnetworks via RS (instead of expanding the explored subnetwork via DFS) is more effective as the number of queried nodes increases.

The AUC score between the inferred network $\mathcal{G}^{(t)}$ in both  and  and the underlying network $\mathcal{G}$.

Dataset     Queried percentage              Gain

10%     0.6015    0.6823    13.43%

20%     0.6681    0.7304    9.32%

30%     0.7310    0.7864    7.57%

40%     0.7799    0.8302     6.44%

10%     0.5744    0.6220    8.28%

20%     0.6408    0.6794    6.02%

30%     0.6907    0.7308    4.89%

40%     0.7495    0.7771     3.68%

§.§.§ Convergence of the Inferred Network (RQ4)
It is worth analyzing the convergence of the inferred network to the underlying true network, which is crucial for finding more precise community-affiliation embeddings through iterations. In Table <ref>, we present the area under the curve (AUC) score to measure the similarity between the inferred network $\mathcal{G}^{(t)}$ in both  (mentioned in Section 5.5.2) and  and the underlying network $\mathcal{G}$ for different percentages of queried nodes when the Facebook and Engineering datasets are used. The AUC score between $\mathcal{G}^{(t)}$ and $\mathcal{G}$ can be computed by comparing the two corresponding adjacency matrices, where the adjacency matrices from $\mathcal{G}^{(t)}$ and $\mathcal{G}$ can be seen as the predicted outcome and the true label, respectively. A higher AUC indicates a greater similarity between the two networks being compared. Our findings are as follows:

* The performance gap between  and  is largest when the Facebook dataset is used; the maximum improvement rate of 13.43% is achieved in terms of AUC score when 10% of nodes are queried.

* The AUC score between $\mathcal{G}^{\left( t \right)} $ and $\mathcal{G}$ tends to increase as the percentage of node queries grows. This suggests that EC-SiamNet is effective in accurately inferring edges, leading to a fast convergence of the inferred network to the underlying true network, as noted in Remark 1.

§.§.§ Effect of Hyperparameters (RQ5)

Figs. <ref> and <ref> illustrate the impact of two key hyperparameters, $\eta$ and $\lambda$, on the performance of  in terms of the NMI when the Facebook and Engineering datasets are used. When a hyperparameter varies so that its effect is clearly revealed, another parameter is set to the pivot value addressed in Section 5.4. Our findings are as follows.

* The effect of $\eta $: From Fig <ref>, the maximum NMI is achieved at $\eta = 1.5$ and $\eta = 1.0$ on Facebook and Engineering, respectively. When $\eta  = 0 $, our loss function in (<ref>) boils down to the case in [7], which only takes into account the structure–community relationship without node metadata, leading to unsatisfactory performance. On the other hand, setting $\eta$ to a high value leads to relatively low performance for both datasets since the metadata–community relationship is over-emphasized during training. Hence, it is crucial to suitably determine the value of $\eta$ in guaranteeing satisfactory performance.

* The effect of $\lambda $: From Fig <ref>, the maximum NMI is achieved at $\lambda = 2.0$ and $\lambda = 3.0$ on Facebook and Engineering, respectively. When $\lambda = 0 $, our node query strategy in (<ref>) focuses only on selecting nodes belonging to more communities. In contrast, setting $\lambda$ to a high value leads to a negative effect on performance because it over-emphasizes the selection of nodes distributed over diverse communities. Thus, it is important to appropriately determine the value of $\lambda$ depending on the dataset.

legend columns=6,
legend entries=10%,20%,30%,40%,
legend to name=named,
xlabel= (a) Facebook, ylabel = NMI,  width = 3.7cm, height = 3.7cm,
+[color=fig_6_color_1] coordinates(0, 0.2584)(0.5, 0.2606)(1.0, 0.2647)(1.5, 0.2680)(2.0, 0.2676)(2.5, 0.2546);
+[color=fig_6_color_2] coordinates(0, 0.2025)(0.5, 0.2091)(1.0, 0.2185)(1.5, 0.2234)(2.0, 0.2217)(2.5, 0.2106);
+[color=fig_6_color_3] coordinates(0, 0.1665)(0.5, 0.1700)(1.0, 0.1737)(1.5, 0.1778)(2.0, 0.1753)(2.5, 0.1690);
+[color=fig_6_color_4] coordinates(0, 0.0913)(0.5, 0.0963)(1.0, 0.1003)(1.5, 0.1022)(2.0, 0.0992)(2.5, 0.0981);

xlabel=(b) Engneering, ylabel = NMI,  width = 3.7cm, height = 3.7cm,
+[color=fig_6_color_1] coordinates(0, 0.3091)(0.5, 0.3168)(1.0, 0.3224)(1.5, 0.3186)(2.0, 0.3177)(2.5, 0.3104);
+[color=fig_6_color_2] coordinates(0, 0.2859)(0.5, 0.3036)(1.0, 0.3091)(1.5, 0.3066)(2.0, 0.3047)(2.5, 0.3015);
+[color=fig_6_color_3] coordinates(0, 0.26099)(0.5, 0.26316)(1.0, 0.26849)(1.5, 0.26720)(2.0, 0.26348)(2.5, 0.26289);
+[color=fig_6_color_4] coordinates(0, 0.1925)(0.5, 0.1979)(1.0, 0.2064)(1.5, 0.2041)(2.0, 0.2010)(2.5, 0.1993);

NMI according to different $\eta$'s in  on Facebook and Engineering when different percentages of nodes are queried.

legend columns=6,
legend entries=10%,20%,30%,40%,
legend to name=named,
xlabel= (a) Facebook, ylabel = NMI,  width = 3.7cm, height = 3.7cm,
+[color=fig_7_color_1] coordinates(0, 0.24114)(1, 0.24816)(2, 0.25337)(3, 0.24562)(4, 0.23032);
+[color=fig_7_color_2] coordinates(0, 0.1925)(1, 0.20773)(2, 0.21507)(3, 0.2084)(4, 0.19456);
+[color=fig_7_color_3] coordinates(0, 0.1600)(1, 0.16288)(2, 0.16920)(3, 0.16328)(4, 0.15811);
+[color=fig_7_color_4] coordinates(0, 0.0913)(1, 0.09704)(2, 0.09801)(3, 0.09760)(4, 0.08909);

xlabel=(b) Engineering, ylabel = NMI,  width = 3.7cm, height = 3.7cm,
+[color=fig_7_color_1] coordinates(0, 0.3143)(1, 0.3196)(2, 0.3221)(3, 0.3288)(4, 0.3197);
+[color=fig_7_color_2] coordinates(0, 0.2925)(1, 0.3077)(2, 0.3084)(3, 0.3150)(4, 0.29456);
+[color=fig_7_color_3] coordinates(0, 0.2600)(1, 0.26288)(2, 0.26328)(3, 0.26920)(4, 0.25811);
+[color=fig_7_color_4] coordinates(0, 0.1943)(1, 0.1996)(2, 0.2037)(3, 0.2072)(4, 0.1997);

NMI according to different $\lambda$'s in  on Facebook and Engineering when different percentages of nodes are queried.

§.§.§ Computational Complexity (RQ6)
To empirically validate the scalability of our  method, we measure the execution time on synthetic networks generated using the Erdős–Rényi model [65] with a fixed number of nodes and a varying number of edges. The Erdős–Rényi model $G\left( {n,q} \right) $ can generate various networks by creating edges between two nodes with probabilitiy $q$. We generate a set of networks with $n = 2000 $ and $q = \left\{ {0.002,0.003,0.006,0.008,0.01,0.02,0.03,0.04} \right\} $. Fig. <ref> illustrates the execution time (in seconds) of one iteration of , including the training time of the GNN and MLP models and query node selection, as the number of edges increases. The dashed line indicates a linear scaling in $\left| \mathcal{E} \right| $, derived from Theorem 4.3. It can be seen that our empirical evaluation concurs with the theoretical analysis.

[        xlabel=$|\mathcal{E}|$,        ylabel= Execution time (s), grid=major, grid style=dashed,  width = 5.95cm, height = 4.25cm , legend style=at=(0.39,0.2),anchor=west]
[color=fig_8_color_1, mark=square, legend = ]
(1734, 197.2833)(3487, 224.2517)(7021, 276.9718)(10187, 304.2664)(13745, 348.728)(17231, 404.77)(26873, 515.596)(33317, 601.8297)(36206, 629.718)(48505, 796.292)(57380, 890.4584)(62948, 945.412)
[ dashed, color=red,        mark=triangle, legend = $O(|\mathcal{E}|)$ ]
(1000,188) (11000,310) (21000,433) (31000,554) (41000, 677) (51000,799) (65000,970)

The computational complexity of , where the plot of the execution time versus $|\mathcal{E}|$ is shown.

§ CONCLUDING REMARKS

In this paper, we solved the unexplored problem of overlapping community detection in networks with unknown topology. To tackle this challenge, we introduced , a novel unified framework for overlapping community detection, which iteratively performs the following three steps: 1) community-affiliation embedding, 2) network exploration via node queries, 3) network inference. Through extensive experiments on five real-world datasets, we demonstrated (a) the superiority of  over state-of-the-art overlapping community detection methods, achieving dramatic gains up to 65.55% in terms of NMI compared to the best existing competitor, (b) the impact of each module in , (c) the effectiveness of our node query strategy by analyzing the growth of the explored subnetworks, (d) the convergence of the inferred network to the underlying true network, (e) the effect of key hyperparameters, including $\eta$ and $\lambda$, and (f) the scalability of . Our theoretical analyses also uncovered (a) the effect of the proposed node query strategy and (b) the scalability of .

Potential avenues of future research include the design of a more sophisticated GNN architecture  for overlapping community detection in our uncertain network setting, which will improve the expressiveness of node-level community affiliation embeddings.

§ ACKNOWLEDGMENTS

§ ACKNOWLEDGMENT

The work of Won-Yong Shin was supported by the National Research Foundation of Korea (NRF) grant funded by the Korea government (MSIT) (No. 2021R1A2C3004345, No. RS-2023-00220762). Ming Li acknowledged the supports from the Key R&D Program of Zhejiang Province (No. 2024C03262) and the National Natural Science Foundation of China (No. 62172370, No. U21A20473). The material in this paper was presented in part at the ACM International Conference on Information and Knowledge Management, Atlanta, GA, October 2022 [15].

[1]
X. Su, S. Xue, F. Liu, J. Wu, J. Yang, C. Zhou, W. Hu, C. Paris, S. Nepal, D. Jin et al., “A comprehensive survey on community detection with deep learning,” IEEE Trans. Neural Networks Learn. Syst., pp. 1–21, Mar. 2022.

[2]
E. Abbe, “Community detection and stochastic block models: Recent developments,” J. Mach. Learn. Res., vol. 18, no. 1, pp. 6446–6531, Apr. 2017.

[3]
G. Palla, I. Derényi, I. Farkas, and T. Vicsek, “Uncovering the overlapping community structure of complex networks in nature and society,” Nature, vol. 435, no. 7043, pp. 814–818, June 2005.

[4]
V. Nicosia, G. Mangioni, V. Carchiolo, and M. Malgeri, “Extending the definition of modularity to directed graphs with overlapping communities,” J. Statistical Mechanics: Theory and Experiment, vol. 2009, no. 03, p. P03024, Mar. 2009.

[5]
J. Yang and J. Leskovec, “Overlapping community detection at scale: A nonnegative matrix factorization approach,” in Proc. WSDM, 2013, pp. 587–596.

[6]
F. Ye, C. Chen, and Z. Zheng, “Deep autoencoder-like nonnegative matrix factorization for community detection,” in Proc. CIKM, 2018, pp. 1393–1402.

[7]
O. Shchur and S. Günnemann, “Overlapping community detection with graph neural networks,” in Proc. 25th ACM SIGKDD Workshop on Deep Learning on Graphs: Methods and Applications, 2019.

[8]
N. Mehta, L. C. Duke, and P. Rai, “Stochastic blockmodels meet graph neural networks,” in Proc. ICML, 2019, pp. 4466–4474.

[9]
T. W. Valente and P. Pumpuang, “Identifying opinion leaders to promote behavior change,” Health Educ. & Behav., vol. 34, no. 6, pp. 881–896, Dec. 2007.

[10]
R. Dey, Z. Jelveh, and K. Ross, “Facebook users have become much more private: A large-scale study,” in Proc. 10th IEEE Int. Conf. Pervasive Comput. Commun. Workshops, 2012, pp. 346–352.

[11]
M. S. Granovetter, “The strength of weak ties,” Amer. J. Sociology, vol. 78, no. 6, pp. 1360–1380, May 1973.

[12]
M. Kim and J. Leskovec, “The network completion problem: Inferring missing nodes and edges in networks,” in Proc. 11th SIAM Int. Conf. Data Mining, 2011, pp. 47–58.

[13]
C. Tran, W.-Y. Shin, A. Spitz, and M. Gertz, “DeepNC: Deep generative network completion,” IEEE Trans. Pattern Anal. Mach. Intell., vol. 44, no. 4, pp. 1837–1852, Apr. 2020.

[14]
C. Tran, W.-Y. Shin, and A. Spitz, “Community detection in partially observable social networks,” ACM Trans. Knowl. Discovery Data, vol. 16, no. 2, pp. 1–24, July 2021.

[15]
Y. Hou, C. Tran, and W.-Y. Shin, “META-CODE: Community detection via exploratory learning in topologically unknown networks,” in Proc. CIKM, 2022, pp. 4034–4038.

[16]
B. Wilder, L. Onasch-Vera, J. Hudson, J. Luna, N. Wilson, R. Petering, D. Woo, M. Tambe, and E. Rice, “End-to-end influence maximization in the field,” in Proc. AAMAS, 2018, pp. 1414–1422.

[17]
H. Kamarthi, P. Vijayan, B. Wilder, B. Ravindran, and M. Tambe, “Influence maximization in unknown social networks: Learning policies for effective graph sampling,” in Proc. AAMAS, 2020, pp. 575–583.

[18]
C. Tran, W.-Y. Shin, and A. Spitz, “IM-META: Influence maximization using node metadata in networks with unknown topology,” IEEE Transactions on Network Science and Engineering, 2024.

[19]
B. Yan and S. Gregory, “Finding missing edges and communities in incomplete networks,” J. Phys. A: Mathematical and Theor., vol. 44, no. 49, p. 495102, Nov. 2011.

[20]
J. Yang and J. Leskovec, “Community-affiliation graph model for overlapping network community detection,” in Proc. ICDM, 2012, pp. 1170–1175.

[21]
F.-Y. Sun, M. Qu, J. Hoffmann, C.-W. Huang, and J. Tang, “vGraph: A generative model for joint community detection and node representation learning,” in Proc. NeurIPS, 2019, pp. 512–522.

[22]
J. Yang, J. McAuley, and J. Leskovec, “Community detection in networks with node attributes,” in Proc. ICDM, 2013, pp. 1151–1156.

[23]
M. Zhou, “Infinite edge partition models for overlapping community detection and link prediction,” in Proc. AISTATS, 2015, pp. 1135–1143.

[24]
V. Leroy, B. B. Cambazoglu, and F. Bonchi, “Cold start link prediction,” in Proc. KDD, 2010, pp. 393–402.

[25]
M. Kosinski, D. Stillwell, and T. Graepel, “Private traits and attributes are predictable from digital records of human behavior,” Proc. Nat. Acad. Sci., vol. 110, no. 15, pp. 5802–5805, Mar. 2013.

[26]
E. Rice, E. Tulbert, J. Cederbaum, A. Barman Adhikari, and N. G. Milburn, “Mobilizing homeless youth for hiv prevention: a social network analysis of the acceptability of a face-to-face and online social networking intervention,” Health education research, vol. 27, no. 2, pp. 226–236, 2012.

[27]
T. N. Kipf and M. Welling, “Semi-supervised classification with graph convolutional networks,” in Proc. ICLR (Poster), 2017.

[28]
P. Veličković, G. Cucurull, A. Casanova, A. Romero, P. Lio, and Y. Bengio, “Graph attention networks,” in Proc. ICLR (Poster), 2018.

[29]
B. Wilder, N. Immorlica, E. Rice, and M. Tambe, “Maximizing influence in an unknown social network,” in Proc. AAAI, 2018, pp. 4743–4750.

[30]
J. Mcauley and J. Leskovec, “Discovering social circles in ego networks,” ACM Trans. Knowl. Discovery Data, vol. 8, no. 1, pp. 1–28, Feb. 2014.

[31]
J. Leskovec and J. Mcauley, “Learning to discover social circles in ego networks,” in Proc. NeurIPS, 2012, pp. 539–547.

[32]
X. Zhang, H. Liu, Q. Li, and X.-M. Wu, “Attributed graph clustering via adaptive graph convolution,” in Proc. IJCAI, 2019, pp. 4327–4333.

[33]
X. Wang, J. Li, L. Yang, and H. Mi, “Unsupervised learning for community detection in attributed networks based on graph convolutional network,” Neurocomputing, vol. 456, pp. 147–155, May 2021.

[34]
C. Park, D. Kim, J. Han, and H. Yu, “Unsupervised attributed multiplex network embedding,” in Proc. AAAI, 2020, pp. 5371–5378.

[35]
X. Fu, J. Zhang, Z. Meng, and I. King, “MAGNN: Metapath aggregated graph neural network for heterogeneous graph embedding,” in Proc. WWW, 2020, pp. 2331–2341.

[36]
J. J. Choong, X. Liu, and T. Murata, “Learning community structure with variational autoencoder,” in Proc. ICDM, 2018, pp. 69–78.

[37]
D. He, Y. Song, D. Jin, Z. Feng, B. Zhang, Z. Yu, and W. Zhang, “Community-centric graph convolutional network for unsupervised community detection,” in Proc. IJCAI, 2021, pp. 3515–3521.

[38]
J. Sun, W. Zheng, Q. Zhang, and Z. Xu, “Graph neural network encoding for community detection in attribute networks,” IEEE Trans. Cybernetics, vol. 52, no. 8, pp. 7791–7804, Feb. 2021.

[39]
B. Yan and S. Gregory, “Detecting community structure in networks using edge prediction methods,” J. Statistical Mechanics: Theory and Experiment, vol. 2012, no. 09, p. P09008, Sept. 2012.

[40]
N. Barbieri, F. Bonchi, and G. Manco, “Efficient methods for influence-based network-oblivious community detection,” ACM Trans. Intell. Syst. Technol., vol. 8, no. 2, pp. 1–31, Dec. 2016.

[41]
T. Hoffmann, L. Peel, R. Lambiotte, and N. S. Jones, “Community detection in networks without observing edges,” Sci. Advances, vol. 6, no. 4, p. eaav1478, Jan. 2020.

[42]
M. Brautbar and M. J. Kearns, “Local algorithms for finding interesting individuals in large networks,” in Proc. Innov. Comput. Sci. (ICS), 2010, pp. 188–199.

[43]
Y. Higashikawa, N. Katoh, S. Langerman, and S.-i. Tanigawa, “Online graph exploration algorithms for cycles and trees by multiple searchers,” J. Combinatorial Optim., vol. 28, no. 2, pp. 480–495, Dec. 2014.

[44]
B. Settles, “Active learning literature survey,” 2009.

[45]
A. J. Joshi, F. Porikli, and N. P. Papanikolopoulos, “Scalable active learning for multiclass image classification,” IEEE Trans. Pattern Anal. Mach. Intell., vol. 34, no. 11, pp. 2259–2273, Jan. 2012.

[46]
A. Yadav, H. Chan, A. X. Jiang, H. Xu, E. Rice, and M. Tambe, “Using social networks to aid homeless shelters: Dynamic influence maximization under uncertainty.” in Proc. AAMAS, 2016, pp. 740–748.

[47]
J. Bromley, I. Guyon, Y. LeCun, E. Säckinger, and R. Shah, “Signature verification using a “Siamese” time delay neural network,” in Proc. NeurIPS, 1993, pp. 737–744.

[48]
S. Chopra, R. Hadsell, and Y. LeCun, “Learning a similarity metric discriminatively, with application to face verification,” in Proc. CVPR, 2005, pp. 539–546.

[49]
X. Liu, J. Van De Weijer, and A. D. Bagdanov, “Exploiting unlabeled data in cnns by self-supervised learning to rank,” IEEE Trans. Pattern Anal. Mach. Intell., vol. 41, no. 8, pp. 1862–1878, Feb. 2019.

[50]
Y. Qi, S. Zhang, L. Qin, Q. Huang, H. Yao, J. Lim, and M.-H. Yang, “Hedging deep features for visual tracking,” IEEE Trans. Pattern Anal. Mach. Intell., vol. 41, no. 5, pp. 1116–1130, Apr. 2018.

[51]
A. P. Streich, M. Frank, D. Basin, and J. M. Buhmann, “Multi-assignment clustering for Boolean data,” in Proc. ICML, 2009, pp. 969–976.

[52]
J. Tang, H. Gao, X. Hu, and H. Liu, “Exploiting homophily effect for trust prediction,” in Proc. WSDM, 2013, pp. 53–62.

[53]
Z. Wang, C. Chen, and W. Li, “Predictive network representation learning for link prediction,” in Proc. SIGIR, 2017, pp. 969–972.

[54]
R. Hadsell, S. Chopra, and Y. LeCun, “Dimensionality reduction by learning an invariant mapping,” in Proc. CVPR, 2006, pp. 1735–1742.

[55]
M. Armandpour, P. Ding, J. Huang, and X. Hu, “Robust negative sampling for network embedding,” in Proc. AAAI, 2019, pp. 3191–3198.

[56]
M. Girvan and M. E. Newman, “Community structure in social and biological networks,” Proc. Nat. Acad. Sci., vol. 99, no. 12, pp. 7821–7826, Apr. 2002.

[57]
Z. Wu, S. Pan, F. Chen, G. Long, C. Zhang, and S. Y. Philip, “A comprehensive survey on graph neural networks,” IEEE Trans. Neural Netw. Learn. Syst., vol. 32, no. 1, pp. 4–24, Mar. 2021.

[58]
F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay, “Scikit-learn: Machine learning in Python,” J. Mach. Learn. Res., vol. 12, pp. 2825–2830, Oct. 2011, <https://scikit-learn.org/stable/modules/neural_networks_supervised.html>.

[59]
Microsoft, “Announcing the microsoft academic graph: Let the research begin!” 2015, <https://www.microsoft.com/en-us/research/blog/announcing-the-microsoft-academic-graph-let-the-research-begin/>.

[60]
X. Wu, Y. Xiong, Y. Zhang, Y. Jiao, C. Shan, Y. Sun, Y. Zhu, and P. S. Yu, “CLARE: A semi-supervised community detection algorithm,” in Proc. KDD, 2022, pp. 2059–2069.

[61]
A. Tsitsulin, J. Palowitch, B. Perozzi, and E. Müller, “Graph clustering with graph neural networks,” Journal of Machine Learning Research, vol. 24, no. 127, pp. 1–21, 2023.

[62]
A. F. McDaid, D. Greene, and N. Hurley, “Normalized mutual information to evaluate overlapping community finding algorithms,” arXiv preprint arXiv:1110.2515, 2011.

[63]
M. Fey and J. E. Lenssen, “Fast graph representation learning with pytorch geometric,” in Proc. 7th ICLR Workshop Representation Learn. Graphs and Manifolds, 2019.

[64]
D. P. Kingma and J. Ba, “Adam: A method for stochastic optimization,” in Proc. ICLR (Poster), 2015.

[65]
P. Erdős, A. Rényi et al., “On the evolution of random graphs,” Publ. Math. Inst. Hung. Acad. Sci, vol. 5, no. 1, pp. 17–60, 1960.