GCN-based weakly-supervised community detection with updated structure centres selection

Abstract

Community detection is a classic problem in network learning. Semi-supervised network learning requires a certain amount of known samples, while sample annotation is time-consuming and laborious. In particular, when the number of known samples is only very small, the learning ability of existing semi-supervised network learning models decreases sharply. In view of this, a weakly-supervised community detection method based on graph convolutional neural network (WC-GCN). Firstly, it introduces a genetic evolution strategy to select and update the structure centres, which enables the updating structure centre process to not get stuck in the local optima, and get the structural centres that are closer to the global best, solving the problem of centre dependence. Secondly, the structural centrality index Cstruct is proposed to measure the representativeness of a subgraph, learning more accurate network structure centres. Thirdly, a self-training method to expand the pseudo-labelled nodes for GCN training to further improve the model effect. The proposed method is evaluated on various real-world networks and shows that it outperforms the state-of-the-art community detection algorithms.

KEYWORDS:

• Weakly-supervised learning
• community detection
• structure centres
• graph convolutional network

1. Introduction

In recent years, complex systems have modelled data as networks in many cases, such as biological networks, social networks, citation networks, etc. (Girvan & Newman, 2002). Community is an important micro-structural feature of a complex network, as it is often associated with function and organisation modules of the underlying system (He et al., 2018; Lancichinetti et al., 2009). Community detection is helpful to reveal important hidden properties of complex networks from a microscopic perspective, and thus becomes one of the most important tasks to explore and understand how networks work (Girvan & Newman, 2002). Therefore, community detection in complex networks has received more and more attention (Rostami et al., 2023). How to effectively describe and discover communities in a network is one of the most challenging problems in community detection.

Currently, many algorithms for community detection have been proposed. These methods attempt to explore community structure characteristics in networks from various perspectives which are mainly divided into two categories, global algorithms and local algorithms. The global methods generally depend on prior knowledge of the entire network, such as the number of communities and network size. At present, many classical community detection methods have been proposed, including hierarchical clustering (Girvan & Newman, 2002), random block model (Fortunato & Hric, 2016), modular optimisation (Yang et al., 2016), spectral clustering (Raghavan et al., 2007), non-negative matrix factorisation (He et al., 2021; He et al., 2021; Sun & Yang, 2023). The global approach has certain limitations (Wang et al., 2017). On the one hand, the analysis from the division and clustering viewpoint, these methods require information on the entire network structure for the network to be processed. Global methods need the whole graph’s information to detect the structure of community; hence, they cannot be used for today’s dynamic and large-scale complex networks due to their high time complexity. On the other hand, only the topology of the network is considered in the calculation process, while the attribute information of the nodes in the network is ignored.

Local optimisation methods are mainly based on the local topological characteristics of the network to reveal the community structure of a local or whole network (Moradi et al., 2014). Compared with global community discovery methods, local-based methods can effectively discover communities without complete information about the network structure and have more advantages in terms of combining node attribute information to better mine local community characteristics (Wang et al., 2017). Many local approaches have been proposed, which are based purely on local information of nodes. Local methods based on various optimising strategies have been surveyed in a recent study (Li et al., 2015), where the local methods are empirically divided into label propagation algorithms (Raghavan et al., 2007), link clustering (Šubelj & Bajec, 2012) and local expansion optimisation methods (Huang et al., 2011). Among them, local expansion optimisation methods are widely used for local community detection in large networks, due to the advantages both in effectivity and accuracy. In the local methods, exploring such structural centres of a network is important to community detection.

However, as the problems that network methods try to solve and the network data that need to be analysed become more and more complex, new methods are proposed and developed. Deep learning techniques have recently been employed to process high-dimensional network data and learn low-dimensional representations of network structures. For example, Convolutional Neural Networks (CNN) (Zhou et al., 2020) utilise convolution and pooling operations to reduce the dimensionality of network data, thereby effectively discovering communities in the network. Graph Convolutional Network (GCN) (Kipf & Welling, 2017), inherits the advantages of CNN and directly operates on network structured data (Zhou et al., 2020). Graph Convolutional Network can not only effectively combine topology and attribute information, but also extract more attribute network features, so this is widely used in network analysis tasks (Lambiotte & RenaudPeel, 2020; Wang et al., 2021).

Although, some scholars have applied GCN to community detection and achieved good results in (He et al., 2020; Jin et al., 2019a), there are still great challenges. For example, on one hand, GCN models are semi-supervised learning models that require a certain amount of prior knowledge (labelled nodes) for graph learning. When there are very few known labelled nodes, the GCN model has limited propagation ability. On the other hand, the detected communities are highly dependent on the selected structure centres. The traditional structure-based centre selection method considers the extension process of node centrality guidance, but has a high dependence on the centre node of the initial structure of the network, and the extension process only considers the network topology information, leading to the poor community discovery effect. As shown in Figure 1, the first two abnormal points in the karate decision graph are the structure centres, but some networks have the same or similar values for a part of the outlier points, and it is difficult to choose the structure centres, which can result in an inaccurate structure centres, for example, the football decision graph.

Figure 1. Decision diagram of karate network and football network. (a) karate network. (b) football network.

To overcome the limitations, we propose a weakly-supervised community detection model based on GCN and the updated structural centres. The main contributions of this paper are as follows:

• Weakly-supervised community detection method based on graph convolutional neural network (WC-GCN) is proposed, which can use a very small number of known label samples to learn the network important nodes (structure centres), and further mine the network community after expanding the training set.

• The method of selecting structural centres uses a genetic evolution strategy, which enables the updating structure centre process to not get stuck with the local optima, and get the structural centres that are closer to the global best, solving the problem of centre dependence. In particular, the genetic evolution strategy has a high fault tolerance when a extremely small number of known labelled samples still have mislabelled samples.

• And the structural centrality index C struct is firstly proposed, which can well reflect the ability of a subgraph to represent the whole network and learn more accurate network structure centres.

• The self-training method is utilised to expand some nearby high-confidence nodes to establish a balanced training set for GCN training to further improve the model effect.

2. Related work

The graph convolutional networks (GCN) (Kipf & Welling, 2016) recently proposed by Kipf and Welling are an effective graph model for semi-supervised learning. This model, however, was originally designed to be learned with the presence of both training and test data. Over the past few years, several graph-based convolution network models emerged for addressing applications of graph-structured data.

In recent years, more and more scholars leverage deep learning methods to solve the problem of community detection on graphs and improve the effect of community detection (Zhou et al., 2020). Some scholars have applied GCN to community detection and achieved good results (He et al., 2020; Jin et al., 2019b). GCN can effectively combine topology and attribute information, so this is widely used in network analysis tasks (Wang et al., 2021). However, these methods still have some challenges. On one hand, the detected communities are highly dependent on the selected structure centres. Exploring such structural centres of a network is important to community detection. Lancichinetti et al. proposed a local optimisation algorithm based on a local fitness measure (Lancichinetti et al., 2009), which generates hierarchical community structure of the network by randomising the starting node. Lee et al. introduced a greedy clique expansion algorithm (Lee et al., 2010), which selects distinct cliques as starting seeds, and expands these seeds by greedy optimisation. These methods expand each community from the structural centre to the boundary with a local search procedure and accelerate the convergence to optimal solutions, which avoids the randomness of seed selection to improve its stability. However, if the structure centres are inaccurate, they will affect the result of community discovery.

The local expansion methods are highly dependent on the selected structure centres, affecting the effect of community detection. Structure centres-dependent demonstrates that the quality of initial structure centres directly affects the effect of community detection. For instance, a small community may disappear if no node in it is identified as one of the initial structure centres. A large community might be split into more than two fragments if more than two nodes are identified as initial structure centres. Therefore, after the initial structure centres are selected, the updating structure centres is a very necessary step for the effect of community detection.

On the other hand, when there are very few known labelled nodes, the GCN model has limited propagation ability, thus yielding unsatisfactory results. To overcome the problem, Li et al. (2018) proposed a joint training and self-training method for training GCNs with few labels. Furthermore, some researchers have designed self-supervised GCN to perform node clustering in complex networks (Kou et al., 2021; Xie et al., 2023). Sun et al. (2020) proposed a multi-stage self-supervised learning algorithm for graph convolutional networks with a small number of labelled nodes on the graph. Some scholars have also applied GCN to community detection and achieved good results (He et al., 2020; Jin et al., 2019a). Jin et al. (2019a) integrated GCN and MRF for semi-supervised community detection. The framework effectively incorporates local topological features and properties of nodes into the task of community detection, but does not consider mesoscopic community properties (Berahmand et al., 2018) such as structure centres.

3. Preliminaries

This section briefly introduces the preliminary knowledge of this work, including basic notations, problem statements and the core of graph convolutional networks. Table 1 lists the main symbols used in the paper.

Table 1. Main symbols and their definitions.

Symbol	Definition
G;V;E	in an undirected graph; the set of nodes; the set of edges;
${\mathcal{G}}_k$;${\mathcal{V}}_k$;${\mathcal{E}}_k$	subgraphs; the k-th initial structure centre; the set of vertices whose predicted label is k
A;X	the network topology; node attributes
$C_i$	a set of disjoint communities
SLP	Similarity based on Local Simple Paths;
$\mathcal{w}({\nu }_{\text{i}}|{\mathcal{G}}_{\text{k}})$	the local connectivity strength
$C_{struct}$	structural centrality
$S;|S|$	the structural centrality set; denotes the number of nodes in S.
I(i);I(j)	denotes the influence of node ${\nu }_i$; denotes the influence of node ${\nu }_j$.
$\overline{I}$; $\overline{d}$	denotes the average of the influence of all nodes of network G; denotes the average shortest distance of network G .
$S^{(0)}$;$S_k$;$S^{(r)}$	known label nodes; the pseudo-labelled set; the structure centres

3.1. Problem formulation

We are interested in the community detection task in an undirected graph $G=(V,E)$, where $V=\{v_1,v_2,\dots ,v_N\}$ denotes the set of nodes, and $E=\{e_1,e_2,\dots ,e_M\}$ denotes the set of edges. The topology of G can be represented by its adjacency matrix $A\in {\mathbb{R}}^{N\times N}$, where the i-th row, i.e. $x_i=X_{i\ast }$, is the feature vector for node $v_i$. If there are usually only a small amount of labels that indicate some nodes of the network belong to a certain community $k(\text{k}\in [1,C])$, which can be indexed by k sets of labels ${\mathcal{S}}^{(0)}=\{l_1,l_2,\dots \dots ,l_C\}$.

The community detection problem is regarded as a semi-supervised learning task where unlabelled nodes are assigned to the corresponding communities by training some of the labelled nodes.

However, it is often the case that there is only a few available label information in some complex networks. This means it’s a challenging problem to uncover underlying communities in these unlabelled networks. Here, we are interested in developing community detection methods that make full use of the known label information. So we require that method accepts networks of few labelled nodes, similarly as in weakly-supervised learning models. In this paper, we focus on the problem of non-overlapping community detection based on the network topology $A$ and node attributes $X$, which aims to partition the node set V into a set of disjoint communities $C=\{C_1,C_2,\dots ,C_K\}$, where $C_i\subseteq V$ for i = 1,2, … , K and ${\cup }_{i=1}^k{C}_i=V$.

3.2. Graph convolutional network

Graph Neural Networks (GNNs) are an effective framework for representation learning of graphs. Many GNN variants have been proposed and have achieved state-of-the-art results on both node and graph classification tasks, such as Graph Isomorphism Network (GIN) (Xu et al., 2018) and GCN (Kipf & Welling, 2017). To make full use of the network topology and node attributes, GCN is a basic module in our method. GCN (Kipf & Welling, 2017) is a multi-layer neural network that operates directly on a homogeneous graph and induces the embedding vector of a node based on the properties of its neighbours. The layer-wise propagation rule is as follows: (1) $H^{\text{(}l+1\text{)}}=\sigma \left({\tilde{D}}^{-\frac{1}{2}}\tilde{A}{\tilde{D}}^{-\frac{1}{2}}{H}^{(l)}{W}^{(l)}\right)$(1) It is a special form of localised filter – a linear combination of the feature vectors of adjacent neighbours. $\tilde{A}=A+I$, which added self-connections to the original adjacency matrix. $\tilde{D}$ is the degree matrix, where ${\tilde{D}}_{ii}=\sum _i{\tilde{A}}_{ij}$. $W^{(l)}$ is a layer-specific trainable transformation matrix. $\sigma (.)$ denotes an activation function such as ReLU. $H(l)$ denotes the hidden representations of nodes in the 1-th layer. Initially, $H(0)=X$. For non-attributed networks, X is initialised as one-hot representations of nodes in the graph.

Most GCNs (Jin et al., 2019b; Sun et al., 2020) are built on supervised or semi-supervised settings and require some high-quality node labels for efficient model optimisation. However, in real-world applications, it is difficult to obtain high-quality node labels. Therefore, unsupervised graph representation learning remains a challenging task.

4. Methodology

4.1. Overview

The overall framework of the model is shown in Figure 2. Firstly, we consider structural centre updating in the structural centre selection algorithm, and use the genetic evolution algorithm of roulette (Kochenderfer & Wheeler, 2019) to make the process of updating structural centres break the local optimum and get the structural centres that are closer to the global optimum, which solves the centre dependence problem. Secondly, the structural centrality index C_struct is firstly proposed, which can well reflect the ability of a subgraph to represent the whole network. Learning the GCN-based framework effectively incorporates network topology and attributes information, which naturally allows us to tackle the above challenges. Thirdly, a self-training method is used to extend some trusted nearest neighbour nodes to construct a balanced training set to further improve the model effect.

Figure 2. WC-GCN is comprised of three steps: (1) the structural centre selection; (2) constructing pseudo-labelled nodes; and (3) finally training the GCN model for community partition.

4.2. Selecting structure centres

The selection of initial structure centres is particularly important. They act as carriers for the initial labelling and to some extent influence the resulting community. In the following, the set of known label nodes ${\mathcal{S}}^{(0)}=\{l_1,l_2,\dots \dots ,l_C\}$ is as the initial set of structure centres. To reduce the adverse effect of inappropriate structure centres, we suggests using graph topology and node attributes to select more appropriate structure centre nodes. Specifically, a two-layer GCN is trained under the set of structure centres ${\mathcal{S}}^{(0)}$ (Kipf & Welling, 2017). The GCN takes as input the graph adjacency matrix A and node attribute matrix X. The output is denoted as $\mathcal{Z}\in {\mathbb{R}}^{N\times K}$, which is computed as (2) $Z=f(X,A)=softmax(\hat{A}ReLU(\hat{A}X{W}^{(0)})W^{(1)})$(2) $\hat{A}={\tilde{D}}^{-\frac{1}{2}}\tilde{A}{\tilde{D}}^{-\frac{1}{2}}$, which is the normalised adjacency matrix with self-connection. $W^{(0)}\in {\mathbb{R}}^{F\times D}$ and $W^{(1)}\in {\mathbb{R}}^{D\times K}$ are the weight parameters for the two graph convolution layers. $ReLU(x)=max(0,x)$, and $softmax(x_i)=\frac{exp(x_i)}{{\sum }_{i^{\mathrm{\prime }}}exp(x_{i^{\mathrm{\prime }}})}$, which are the activation functions for the first and second GCN layer. Let $z_{i,k}$ the entry denote $v_i$ the affiliation strength of node to the k-th community. Then the predicted community label for an unlabelled node $v_i$ is (3) $\widehat{y_i}=\underset{k\in [1,2,\dots ,K]}{argmax}{z}_{i,k}$(3)

Based on the predicted community labels, we can obtain a temporary partition of the nodes $\mathrm{\Omega }=\{{\mathcal{V}}_1,{\mathcal{V}}_2,\dots ,{\mathcal{V}}_K\}$, where ${\mathcal{V}}_K=\{{\nu }_i|\widehat{y_i}=k\}$ . Then K subgraphs can be induced: ${\mathcal{G}}_k=({\mathcal{V}}_k,{\mathcal{E}}_k)$, where ${\mathcal{E}}_k=\{\{({\nu }_i,{\nu }_j)|{\nu }_i\in {\mathcal{V}}_k,{\nu }_j\in {\mathcal{V}}_k,({\nu }_i,{\nu }_j)\in \mathcal{E}\}\}$, $k=1,2,\dots ,K$. Some inaccurate structure centres may emerge now: the k-th initial structure centre, i.e. $c_k^{(0)}$, may locate on the periphery of subgraph ${\mathcal{G}}_k$ or even in another subgraph ${\mathcal{G}}_{{\mathrm{k}}^{\mathrm{\prime }}}$. To find the structure centres of ${\mathcal{G}}_{\text{k}}$, we compute the local structure importance for each node in ${\mathcal{G}}_{\text{k}}$, which is calculated from the perspective of the shortest path (Zheng et al., 2020), to get to the set of structure centres ${\mathcal{S}}^{(1)}$. On this basis, in order to make the structural centre more accurate, we propose the structural centrality refinement structural centres. Formally speaking, we introduce the following definitions.

Definition 1

Similarity based on Local Simple Paths, SLP

Given a network ${\mathcal{G}}_k=({\mathcal{V}}_k,{\mathcal{E}}_k)$, the SLP between nodes ${\nu }_i$ and ${\nu }_j$ is defined as: (4) $SLP({\nu }_i,{\nu }_j|{\mathcal{G}}_k)=\{\begin{array}{ll}{a}_1{\eta }_{i,j}^{(1)}+a_2{\eta }_{i,j}^{(2)}+a_3{\eta }_{i,j}^{(3)}& {\nu }_i\ne {\nu }_j\\ 0& {\nu }_i={\nu }_j\end{array}$(4) ${\eta }_{\text{i},\text{j}}^{(\text{l})}$ is the number of simple paths – paths with no repeated nodes – with length $l$ between nodes ${\nu }_i$ and ${\nu }_j$. α1, α2, α3 are non-negative weights that satisfy α1≥α2≥α3 and α1 + α2 + α3 = 1 . Intuitively, a higher value of $SLP({\nu }_i,{\nu }_j|{\mathcal{G}}_k)$ indicates that the two nodes ${\nu }_i$ and ${\nu }_{\text{j}}$ are better connected in the subgraph ${\mathcal{G}}_k$.

Definition 2

Local Structural Importance

Given a network ${\mathcal{G}}_k=({\mathcal{V}}_k,{\mathcal{E}}_k)$, the notion of local structural importance of node ${\nu }_i\in {\mathcal{V}}_k$ is defined as: (5) $\mathcal{w}({\nu }_i|{\mathcal{G}}_k)=\sum _{{\nu }_j\in {\mathcal{V}}_k}SLP({\nu }_i,{\nu }_j|{\mathcal{G}}_k)$(5) Since $SLP({\nu }_i,{\nu }_j|{\mathcal{G}}_k)$ measures the connectivity strength between nodes ${\nu }_i$ and ${\nu }_j$ from the perspective of the number of simple paths shorter than 3, $\mathcal{w}({\nu }_{\text{i}}|{\mathcal{G}}_{\text{k}})$ can indicate the local structure importance of node ${\nu }_{\text{i}}$ with respect to its surrounding nodes. A higher value of $\mathcal{w}({\nu }_i|{\mathcal{G}}_k)$ means that the node ${\nu }_i$ is closely connected to other nodes in the local neighbourhood and is more likely to be the centre of ${\mathcal{G}}_{\text{k}}$. Therefore, the node with the largest value of $\mathcal{w}({\nu }_{\text{i}}|{\mathcal{G}}_{\text{k}})$ is selected as the structure centre for the subgraph ${\mathcal{w}}^{{\mathcal{G}}^k}$. That is to say, (6) $c_h^{(r)}=arg\underset{{\nu }_i\in {\mathcal{V}}_k}{max}\mathcal{w}({\nu }_i|{\mathcal{G}}_k)$(6)

Definition 3

Structural centrality

Given a network $G=\{V,E\}$, with a set of nodes $S\subseteq V$, the importance of S in G is defined as follows: (7) $C_{struct}(S)=\frac{|S|\cdot {\sum }_{i,j\in S}I(i)\cdot I(j)\cdot d(i,j)}{C_{|s|}^2\cdot {\overline{I}}^2\cdot \overline{d}\cdot N},(|S|>1)$(7) S is the structural centrality set, |S| denotes the number of nodes in S. I(i) denotes the influence of node ${\nu }_i$. Metrics such as degree centrality, median centrality, proximity centrality, eigenvector centrality and so on, can denote the influence of a node. d(i,j) denotes the shortest distance between node ${\nu }_i$ and ${\nu }_j$, the $C_{|S|}^2=\frac{|S|\times (|S|-1)}{2}$, $\overline{I}$ denotes the average of the influence of all nodes of network G, $\overline{d}$ denotes the average shortest distance of network G, and N denotes the number of nodes of graph G.

When the network G is a complete graph, the structural centrality $C_{struct}(V)=1$ of G. That is, the network is best represented when the set of structural centres is the full set of nodes V of that network G. However, in practice, the size of the real network is getting higher and higher, and we choose a subset S to represent as much as possible the network G, for example in Figure 3 and Table 1. The nodes in S are characterised by a high local influence and are far away from each other. In weakly-supervised learning, the number of nodes in S is deterministic and equal to the number of classes, assuming that all classes are included in the training sample.

Figure 3. An example of structural centrality $C_{struct}$ function calculation.

In practice, considering the large size of the network, the complexity of calculating the influence of all nodes and the shortest distance between all nodes is high, and for a specific network, the value of its sum is fixed, so Equation (7) can be simplified as: (8) $C_{struct}(S)=\frac{{\sum }_{i,j\in S}I(i)\cdot I(j)\cdot d(i,j)}{2(|S|-1)\cdot N},(|S|>1)$(8) In this paper, node degree centrality is used to represent node influence. Figure 3 shows an example of structural centrality metric calculation and Table 2 shows the calculation process. In this example, $C_{struct}(S)$ = 2.67 in Figure 3 (NO. 4) is the largest value, so the three points a,b,c are more accurately chosen as the set of structure centre nodes for this graph.

Table 2. Structural centrality example calculation process.

No.	Structural centre set S	Structural centrality	Calculation process
1	{a,c}	2.13	4*4*4/(2*(2-1)*15)
2	{a,v}	1.60	4*4*3/(2*(2-1)*15)
3	{a,d,c}	1.87	(4*3*2 + 4*4*4 + 3*4*2)/(2*(3-1)*15)
4	{a,b,c}	2.67	(4*4*3 + 4*4*4 + 4*4*3)/(2*(3-1)*15)
5	{a,b,c,d}	2.44	(4*4*3 + 4*4*4 + 4*4*3 + 4*3*2 + 4*3*1 + 4*3*2)/(2*(4-1)*15)

According to the above calculations, when $\text{S}=\{\text{a},\text{b},\text{c}\}$, the value of structural centrality is large, it is an ideal set of structural centrality. K = 3 in this case.

The procedure for selecting initial structure centres is listed in algorithm 1, which selects the K nodes with largest centrality and assigns them with distinct community labels 1,2, …  … ,K, respectively. The output is denoted ${\text{S}}^{(0)}=\{\{{\text{c}}_1^{(0)}\},\{{\text{c}}_2^{(0)}\},\dots ,\{{\text{c}}_{\text{K}}^{(0)}\}\}$, where ${\text{c}}_{\text{K}}^{(0)}$ denotes the k-th structure centre and k is assigned a pseudo community label. The method in this paper is a weakly-supervised method where the number of communities k is determined by the number of known sample labels. The selecting structural centres algorithm not only considers the network topology information and node attribute information at the same time to obtain better structure centres iteratively, which solves the problem of structure centres dependence.

Table

Algorithm 1: Selecting structure centres algorithm
Input: The network $G=\{V,E\}$, adjacency matrix A, node feature matrix X, and the set of known label nodes ${\mathcal{S}}^{(0)}=\{l_1,l_2,\dots \dots ,l_C\}$, the maximum number of iterations iteraMax
Output: Structure centres $S^{(r)}$
1 $S={\mathcal{S}}^{(0)}$
2 while loop < =  iteraMax:
3 Train the GCN model under the supervision of S and get a graph partition $\mathrm{\Omega }=\{V_1,V_2,\dots \dots ,V_K\}$
4  for each $V_k$ do:
5   Build the induced subgraph $G_k=(V_k,E_k)$, where ${\text{V}}_{\text{k}}$ is the set of vertices whose predicted label is the k-th class and $E_k=\{\{({\nu }_i,{\nu }_j)|{\nu }_i\in V_k,{\nu }_j\in V_k,({\nu }_i,{\nu }_j)\in E\}\}$
6   Calculate the similarity $SLP({\nu }_i,{\nu }_j|G_k)$ for each pair of nodes in subgraph ${\mathcal{G}}_{\text{k}}$ according to Equation (4);
7   Calculate the local connectivity strengths $w({\nu }_i|G_k)$ for every node in $V_K$ according to Equation (5);
8  if loop%3 = =2:// Roulette is used in one of every three cycles.
9    $p_i=w({\nu }_i|G_k)/\sum w({\nu }_i|G_k)$
10   Select nodes $v_i$ to join in $S^{(1)}$ with probability $p_i$;
11   Else:
12   Select the node $v_i$ that corresponds to the maximum value $w({\nu }_i|G_k)$ to join $S^{(1)}$;
13  End for
14  Calculate the structural centrality $C_{struct}(S^{(1)})$ of the structural centre using Equation (8).
15  $S=S^{(1)}+S^{(0)}$
16  $S^{(1)}=\mathrm{\varnothing }$
17  End while
18  Select the greatest structure centrality ${\mathcal{S}}^{(\text{r})}$;
19 Return ${\mathcal{S}}^{(\text{r})}$

4.3. Constructing the balanced training set

Now we have obtained a set of refined structure centres, each of which is assigned a distinct pseudo community label. To realise community partition, a GCN can be trained to predict the community labels for other nodes in the graph by integrating the graph structure and node attributes. As known, GCN is a localised filter, hence it cannot effectively propagate the label information to the entire graph when only a limited amount of labelled nodes are available (Li et al., 2018). In order to train a better GCN for community detection, we propose to expand the pseudo-labelled set by the following process.

When the structure centres are iteratively updated in algorithm 1, a temporary graph partition $\mathrm{\Omega }=\{V_1,V_2,\dots \dots ,V_K\}$ is also returned: node ${\nu }_i$ is assigned to ${\mathcal{V}}_K$, if $k=argma{x}_{k^{\mathrm{\prime }}}{z}_{i,k^{\mathrm{\prime }}}$. For each node ${\nu }_x\in {\mathcal{V}}_k$, we compute the difference between its affiliation strength to the k-th community and that of $c_k^{(r)}$, i.e. $|z_{v_x,k}-z_{c_k^{(r)},k}|$. Then we construct the set of nodes $S_k$ with pseudo label k by selecting the $\tau$ nodes with the smallest affiliation strength difference to that of $c_k^{(r)}$ among $V_K$. (9) $S_k=arg\underset{{\nu }_x\in V_k}{max}(|z_{v_x,k}-z_{c_k^{(r)},k}|,\tau )$(9) where $argmin(.,\tau )$ is the function for selecting the $\tau$ nodes with smallest values. The lower bound of $\tau$ is estimated by solving $K\cdot \tau \cdot d^L\approx N$, where $d$ is the average degree of nodes in $\mathcal{G}$, and $\text{L}$ is the number of graph convolution layers which is 2 in our experiments. Note that the pseudo-label expansion process takes into account both the graph topology and node attributes, since the probability $z_{v_x,k}$ for node $\nu$ predicted by an $L$-layer GCN depends on the labels and attributes of its $L$-hop neighbours in the graph, as defined in Equation (2). In this way, we expand the set of refined structure centres $S^{(r)}=\{\{c_1^{(r)}\},\{c_2^{(r)}\},\dots ,\{c_K^{(r)}\}\}$ to a larger set of pseudo-labelled nodes $S=\{S_1,S_2,\dots ,S_K\}$. An alternative strategy is to select the $\tau$ nodes with the largest $z_{i,k}$ among all nodes in $\mathcal{V}$ (Li et al., 2018), i.e. (10) $S_k=arg\underset{{\nu }_x\in V_k}{max}(z_{v_x,k},\tau )$(10) We did not adopt this strategy, because it is sensitive to inappropriate structure centres. Besides, some nodes satisfying this criterion are ones of low degree which are located on the periphery of a certain community and far away from other communities. Although such nodes belong to the corresponding community with a high confidence, they have limited propagation ability.

4.4. Training GCN with expanded pseudo-labelled set

Under the supervision of the larger set of pseudo-labelled nodes, we can train a two-layer GCN with the same structure as defined by Equation (2). We minimise the cross-entropy loss over all pseudo-labelled nodes: (11) $T:=-\sum _{k=1}^K\sum _{v_i\in S_k}\log Z_{ik}$(11) where $S_k$ denotes the set of nodes with pseudo label, and $K$ is the output dimension of the softmax layer, which actually corresponds to the number of communities. The adam (Kingma & Ba, 2015) optimizer is used to update the model parameters ${\mathcal{W}}^{(0)}$ and ${\mathcal{W}}^{(1)}$. Once the GCN is trained to convergence, we can predict the community label using Equation (3) and obtain the final community partition $C=\{C_1,C_2,\dots ,C_K\}$, where (12) $C_k=\{v_i|\widehat{y_i}=k\}fork=1,2,\dots ,K$(12)

The whole process of our proposed method is shown in algorithm 2.

Table

Algorithm 2: The whole process of WC-GCN
Input: The network $G=\{V,E\}$, adjacency matrix A, node feature matrix X, and The set of known label nodes $S^{(0)}$, the maximum number of iterations iteraMax
Output: Community partition $C=\{C_1,C_2,\dots ,C_K\}$
1   // Phase 1: Selecting structure centres
2  Call algorithm 1 to select the structure centres $S^{(r)}$
3  // Phase 2: Expanding the pseudo-labelled set
4  Train the GCN model under the supervision of ${\text{S}}^{(\text{r})}$;
The hidden node representation $Z$ of all nodes obtained by Equation (2);
for $k\in [1,K]$ do
Construct the pseudo-labelled set $S_k$ using Equation (9);
5  // Phase 3: Community partition
6  Train the GCN model under the supervision of $S_k=\{S_1,S_2,\dots ,S_K\}$;
7  Predict the community label for all nodes according to Equation (10);
8  Obtain final community partition $C=\{C_1,C_2,\dots ,C_K\}$ according to Equation (12);
9 return $C$

4.5 Computational cost

In this paper, we try to solve an interesting problem, i.e. community detection with limited labelled nodes, iterating the process of training GCN, refining community centres, generating pseudo-labels of communities, to uncover underlying community structures with topology and attribute information.

Given a network G = (V, E) with N nodes and M edges, the time complexity of the algorithm mainly depends on the SLP process and the GCN model. The SLP algorithm takes linear time O(M) in the number of edges for each iteration. This process is repeated for a finite number of iterations and hence requires an overall near-linear time. In experiments, the runtime is negligible on networks with a few thousand nodes. In the GCN training phase, we follow Kinf and Welling’s setup with full-batch gradient descent, which scales linearly in the number of network edges. In our experiments, it generally converges fast with a few epochs as it propagates labels from expanded labelled nodes to the entire network effectively. Moreover, the computation of GCN can be further accelerated with mini-batch stochastic gradient descent. Therefore, the running time of our algorithm is comparable to GCN.

For GCNs, we follow the same hyper-parameters as Kipf and Welling (2017) with a learning rate 0.01, maximum epochs 200, dropout rate 0.5, L2 regularisation weight 5 × 10⁻⁴ and 16 hidden units. For each run, we randomly split labels into a small set for training, a large set for testing. According to the analysis and experiments (Jin et al., 2019a), GCN-based methods usually get the best performance with 5% training size on most datasets. We choose this labelling rate as the initial training size for easy comparison with other baselines. We adopt Adam optimizer to train the GCN-based models and run experiments on TensorFlow. All the experiments were conducted on a PC with a 2.6 GHz, i7-5600, Quad-core CPU and 12 GB of RAM.

5. Experiments

In this section, we validate the performance of the proposed community detection method on various real-world networks. We conduct extensive experiments with the aim of answering the following research questions:

• RQ-1: Whether the proposed WC-GCN helps to improve the community detection?

• RQ-2: Are both updating structure centre and pseudo-labelled set expansion essential for WC-GCN?

• RQ-3: Does the step of updating structure centres indeed yield better structure centres for later community detection?

• RQ-4: Why can constructing a pseudo-label training set improve the division effect of GCN?

5.1. Datasets

We conduct extensive experiments on the public network datasets, including Cora,¹ CiteSeer,² PubMed,³ Football⁴ and PolBlogs.⁴ Detailed statistics are shown in Table 3.

• Football (Girvan & Newman, 2002): The Football network is a network of American football games between Division IA colleges during regular season Fall 2000. In the network nodes denote the 115 teams that are divided into 12 conferences, and the edges represent 613 games.

• PolBlogs (Adamic & Glance, 2005): The PolBlogs dataset is a directed network of hyperlinks between political blogs collected during the 2004 US election. It includes 1490 nodes and 16,715 directed edges. The political orientation of each blog is either conservative or liberal.

• Cora (Sen et al., 2008): Cora is a citation network consisting of 2708 documents and 5,429 links (Zhang et al., 2023). Each document has a 1433-dimensional sparse bag-of-words feature vector. The Cora data set contains a number of machine learning papers divided into one of seven classes, including Case Based, Genetic Algorithms, Neural Networks, Probabilistic Methods, Reinforcement Learning, Rule Learning and Theory.

• CiteSeer (Sen et al., 2008): CiteSeer is a citation network consisting of 3327 scientific publications from six categories – agents, AI, databases, human–computer interaction, machine learning, and information retrieval, and a total of 4732 links.

• PubMed (Namata et al., 2012): PubMed is a citation network consisting of 19,717 nodes and 44,338 links. The dataset contains sparse bag-of-words feature vectors of length 500 for each document. The PubMed data set contains documents related to biomedical, health field and life sciences.

Table 3. Specific information of five network data sets.

Data set	Number of vertex	Number of edges	Reference community number
Football	115	613	12
PloBlogs	1490	16,715	2
Cora	2708	5429	7
Citeseer	3312	4732	6
Pubmed	19,729	44,338	3

5.2. Evaluation metrics

To evaluate the community detection performance of baselines and our method, we utilise four widely used performance metrics – Normalised Mutual Information (NMI) (Danon et al., 2005), Adjusted Rand Index (ARI) (Rand, 1971), F1 score (Bhattacharya et al., 2023; Jin et al., 2021a) and Accuracy (Bhattacharya et al., 2023; Liu et al., 2011). Accuracy to evaluate division performance from different perspectives.

$ACC()$ assesses cluster quality by measuring the agreement between the community partition predicted by an algorithm and the ground-truth community partition of a network. Let $P=\{P_1,P_2,\dots \dots ,P_A\}$ be the ground-truth community partition with A communities, and $C=\{C_1,C_2,\dots \dots ,C_K\}$ be the community partition detected by an algorithm. $ACC()$ is the ratio of the number of correctly predicted samples to whole samples, which is defined as given in Equation (13). (13) $ACC(P,C)=\frac{{\sum }_{i=1}^N\delta (P_i,map(C_i))}{N}$(13) where ${\text{P}}_{\text{i}}$ is the actual category label of the $i-th$ sample, $C_i$ is the predicted category label of the model on the $i-th$ sample. The $map()$ function facilitates each predicted category label to reach its optimal accurate category label. $\delta (\text{x},\text{y})$ denotes an indicator function defined as shown in Equation (14): (14) $\delta (x,y)=\{\begin{array}{ll}1,& x=y;\\ 0,& x\ne y.\end{array}$(14) F1 score: The F1 score (Bhattacharya et al., 2023; Jin et al., 2021a) for detecting communities has been defined as the harmonic mean of Precision and Recall, which may be expressed as follows: (15) $F1(P,C)=2\frac{Precision(P,C).Recall(P,C)}{Precision(P,C)+Recall(P,C)}$(15) where $P=\{P_1,P_2,\dots \dots ,P_A\}$ be the ground-truth community partition with A communities, and $C=\{C_1,C_2,\dots \dots ,C_K\}$ be the community partition detected by an algorithm.

Regarding the influence of the size of the training set on the GCN results, we also conducted related experiments with the NMI and ARI, and the experimental results are shown in the following Figure 4. They assess the community quality by measuring the agreement between the community partition predicted by an algorithm and the ground-truth community partition of the network. (15) $\text{NMI}(\text{P},\text{C})=\frac{2{\sum }_{\text{a}=1}^{\text{A}}{\sum }_{\text{b}=1}^{\text{K}}{\text{N}}_{\text{a},\text{b}}\log \frac{{\text{N}}_{\text{a},\text{b}}\text{N}}{{\text{N}}_{\text{a},.}{\text{N}}_{.,\text{b}}}}{-{\sum }_{\text{a}=1}^{\text{A}}{\text{N}}_{\text{a},.}\log \frac{{\text{N}}_{\text{a},.}}{\text{N}}-{\sum }_{\text{b}=1}^{\text{K}}{\text{N}}_{.,\text{b}}\log \frac{{\text{N}}_{.,\text{b}}}{\text{N}}}$(15) where $N_{a,b}=|P_a\cap P_b|$ is the number of nodes in common between the ground-truth community ${\text{P}}_{\text{a}}$ and detected community ${\text{C}}_{\text{b}}$, ${\text{N}}_{\text{a},.}=|{\text{P}}_{\text{a}}|=\sum _{\text{b}=1}^{\text{K}}{\text{N}}_{\text{a},\text{b}}$, ${\text{N}}_{.,\text{b}}=|{\text{C}}_{\text{b}}|=\sum _{\text{a}=1}^{\text{A}}{\text{N}}_{\text{a},\text{b}}$, and N is the total number of nodes in G. (16) $\text{ARI}(\text{P},\text{C})=\frac{{\sum }_{\text{a}=1}^{\text{A}}{\sum }_{\text{b}=1}^{\text{K}}\left(\begin{array}{c}{\text{N}}_{\text{a},\text{b}}\\ 2\end{array}\right)-\left[{\sum }_{\text{a}=1}^{\text{A}}\left(\begin{array}{c}{\text{N}}_{\text{a},.}\\ 2\end{array}\right){\sum }_{\text{b}=1}^{\text{K}}\left(\begin{array}{c}{\text{N}}_{.,\text{b}}\\ 2\end{array}\right)\right]/\left(\begin{array}{c}\text{N}\\ 2\end{array}\right)}{\frac{1}{2}\left[{\sum }_{\text{a}=1}^{\text{A}}\left(\begin{array}{c}{\text{N}}_{\text{a},.}\\ 2\end{array}\right)+{\sum }_{\text{b}=1}^{\text{K}}\left(\begin{array}{c}{\text{N}}_{.,\text{b}}\\ 2\end{array}\right)\right]-\left[{\sum }_{\text{a}=1}^{\text{A}}\left(\begin{array}{c}{\text{N}}_{\text{a},.}\\ 2\end{array}\right){\sum }_{\text{b}=1}^{\text{K}}\left(\begin{array}{c}{\text{N}}_{.,\text{b}}\\ 2\end{array}\right)\right]/\left(\begin{array}{c}\text{N}\\ 2\end{array}\right)}$(16)

Figure 4. The update process of the structure centres on the Football network when initialised randomly.

The range of NMI and ARI is [0, 1]. The value is equal to 1 only if the community partition detected by an algorithm is completely identical to the ground-truth community partition, and 0 for a random partition.

5.3. Baselines

We compare our method with 5 state-of-the-art methods on 3 widely used benchmark datasets. We mainly make a fair comparison between the models, which clearly presents the commonalities and differences between different models including ChebyNet, FastGCN, GAT, GCN, SimPGCN, PPR-GCN and Bet-GAT.

• ChebyNet (Defferrard et al., 2016): ChebyNet presents a formulation of CNNs in the context of spectral graph theory, which provides the necessary mathematical background and efficient numerical schemes to design fast localised convolutional filters on graphs.

• FastGCN (Chen et al., 2018): FastGCN, a fast improvement of the GCN model recently proposed by Kipf and Welling (2016) for learning graph embeddings. It generalises transductive training to an inductive manner and also addresses the memory bottleneck issue of GCN caused by recursive expansion of neighbourhoods.

• GAT (Velikovi et al., 2017): Graph attention networks (GATs), novel neural network architectures that operate on graph-structured data, leveraging masked self-attentional layers to address the shortcomings of prior methods based on graph convolutions or their approximations.

• GCN (Kipf & Welling, 2016): It is a semi-supervised classification on graph-structured data. GCN model uses an efficient layer-wise propagation rule that is based on a first-order approximation of spectral convolutions on graphs.

• SimPGCN (Jin et al., 2021b): There are many scenarios where node similarity plays a crucial role. Thus, it has motivated the proposed framework SimP-GCN that can effectively and adaptively balance the structure and feature information as well as capture pairwise node similarity via self-supervised learning.

• PPR-GCN (Zhang et al., 2023): A graph convolutional network based on personalised web page ranking algorithm (PPR-GCN) is proposed for community detection in attribute networks, which uses the strong characteristics of graph convolution algorithm for integrating node topology and attribute information, and combines with personalised web page ranking algorithm to decouple the prediction process and propagation process in the model.

• Bet-GAT (Verma et al., 2023): It is an efficient graph-attention-based semi-supervised classification method (Bet-GAT) where training nodes are selected based on betweenness centrality. The model essentially exploits the fact that GNN-based models rely on the aggregation of neighbourhood information. In a graph network, the structurally well-positioned nodes ensure good aggregation of information. This key idea is used to train the model.

5.4. Experimental results and analysis (RQ-1)

We compare the performance of our method (WC-GCN) with other state-of-the-art algorithms on Cora, CiteSeer, and PubMed real-world networks. The Cora, CiteSeer and PubMed datasets belong to the attributed network. All experiments take the average performance of the clustering results obtained by running the algorithm 30 times on each network, and the experimental results are shown in Tables 4–6.

Table 4. ACC results for Cora dataset with different labels selected in each class.

Input Methods	2*7	3*7	4*7	5*7	6*7	7*7	8*7	9*7	10*7
ChebyNet	0.3578	0.3922	0.4480	0.4690	0.4992	0.5165	0.5303	0.5427	0.5598
FastGCN	0.3794	0.4067	0.4674	0.4901	0.5329	0.5523	0.5625	0.5824	0.5881
GAT	0.5369	0.6268	0.6744	0.7004	0.7002	0.7486	0.7542	0.7778	0.7748
GCN	0.5265	0.6114	0.6635	0.7060	0.7062	0.7434	0.7498	0.7659	0.7784
SimPGCN	0.4866	0.5173	0.5541	0.5783	0.6088	0.6221	0.6397	0.6550	0.6562
PPR-GCN	0.6134	0.6323	0.6678	0.6754	0.6985	0.7023	0.7066	0.7144	0.7481
Bet-GAT	0.5468	0.6258	0.6841	0.7122	0.7164	0.7417	0.7496	0.7713	0.7906
SC-GCN	0.6638	0.6824	0.7335	0.7357	0.7534	0.7561	0.7595	0.7646	0.7939

Table 5. Citeseer dataset in each class selects different labels for ACC results.

Input Methods	2*6	3*6	4*6	5*6	6*6	7*6	8*6	9*6	10*6
ChebyNet	0.3323	0.3672	0.4048	0.4166	0.4315	0.4473	0.4774	0.4785	0.4797
FastGCN	0.3766	0.4186	0.4650	0.4739	0.4908	0.5029	0.5276	0.5264	0.5387
GAT	0.3684	0.4892	0.5562	0.5920	0.6006	0.6588	0.6516	0.6662	0.6590
GCN	0.3559	0.4417	0.4875	0.5505	0.5967	0.6330	0.6617	0.6775	0.6711
SimPGCN	0.4821	0.5428	0.5787	0.5694	0.5870	0.5875	0.6142	0.6187	0.6208
PPR-GCN	0.5316	0.6071	0.6213	0.6558	0.6643	0.6658	0.6743	0.6932	0.7027
Bet-GAT	0.4965	0.5579	0.5742	0.5974	0.6256	0.6641	0.6738	0.7953	0.7024
WC-GCN	0.5949	0.6582	0.6734	0.7071	0.7136	0.7169	0.7213	0.7445	0.7518

Table 6. ACC results for Pubmed dataset with different labels selected in each class.

Methods Input	2*3	3*3	4*3	5*3	6*3	7*3	8*3	9*3	10*3
ChebyNet	0.6040	0.6609	0.6540	0.6780	0.6864	0.7058	0.7296	0.7156	0.7335
FastGCN	0.5955	0.6468	0.6478	0.6719	0.6889	0.7104	0.7172	0.7272	0.7322
GAT	0.6245	0.6806	0.6823	0.6984	0.7092	0.7361	0.7426	0.7456	0.7505
GCN	0.6173	0.6625	0.6893	0.7025	0.7054	0.7099	0.7458	0.7371	0.7507
SimPGCN	0.6228	0.6785	0.6705	0.6906	0.7226	0.7386	0.7412	0.7354	0.7492
PPR-GCN	0.6023	0.6142	0.6184	0.6244	0.6423	0.6752	0.6842	0.6984	0.7130
Bet-GAT	0.6487	0.6877	0.7953	0.7054	0.713	0.7185	0.7289	0.7456	0.7648
WC-GCN	0.6580	0.6842	0.6966	0.7058	0.7286	0.7491	0.7611	0.7832	0.7941

The experimental parameters in this paper are consistent with the parameters $a_1$, $a_2$ and $a_3$ in the literature (Zheng et al., 2020). Experiments show that when $a_1\in [0.6,0.8]$, $a_2\in [0.15,0.35]$ and $a_3=1-a_1-a_2>0$, the algorithm WC-GCN will reach the optimal value in most cases, so $a_1$ = 0.6, $a_2$ = 0.35, $a_3$ = 0.05 for the unlabelled network. The experimental results are shown in Tables 4–6.

Table 4 is the experimental results on the Cora dataset. For different comparison methods, Cora has 7 communities and we selected 2,3,4,5,6,7,8,9 and 10 points for each community as input. From the experimental results in the table, we can intuitively see that when the less the known samples of the input, the accuracy of our model WC-GCN is higher than the other 5 methods. When the number of input points increases, the results of WC-GCN are still better than the other methods, but the accuracy is not obvious as the GAT. The reason is that GAT considers aggregation of neighbours based on their importance with respect to the node. This further improves the accuracy of the results and the quality of the learning process imparted to the model. At the same time, the learning framework WC-GCN should have certain fault tolerance, that is to say, when a very small number of samples with labelled errors in known samples, it can still learn the accurate network structure centre, which does not affect the accuracy of the network learning task.

In Tables 5 and 6, experiments on Citeseer and Pubmed datasets, there are 6 communities in Citeseer and the number of communities in Pubmed is 3. The trends in experimental results in Tables 5 and 6 are the same as those in Table 4. When the number of known samples is less, the accuracy of WC-GCN is higher than that of the other five methods; as the number of known samples increases, the results of WC-GCN are still better than other methods.

The F1 score is an indicative measure of the accuracy of the model. Furthermore, in the result of the F1 score index, a similar trend is seen for the various datasets, as illustrated in Tables 7–9. The F1 scores (calculated using different methods) for the three benchmark datasets were compared with the other state-of-the-art methods. The results of the WC-GCN model are more advantageous because the model is more advantageous when the number of known labels is small. In general, the algorithm WC-GCN proposed in this paper performs effectively in experiments, and its improvement is obvious compared with other comparison algorithms.

Table 7. F1 results for Cora dataset with different labels selected in each class.

Input Methods	2*7	3*7	4*7	5*7	6*7	7*7	8*7	9*7	10*7
ChebyNet	0.3191	0.3427	0.4221	0.4282	0.4636	0.4712	0.4919	0.5123	0.5164
FastGCN	0.3434	0.3721	0.4194	0.4559	0.4983	0.5189	0.5144	0.5567	0.5523
GAT	0.5009	0.5814	0.6258	0.6732	0.6741	0.7128	0.7079	0.7288	0.7275
GCN	0.4981	0.5694	0.6284	0.6696	0.6617	0.7004	0.7225	0.7394	0.7346
SimPGCN	0.4562	0.4706	0.5229	0.5530	0.5600	0.5905	0.6092	0.6202	0.6166
Bet-GAT	0.5161	0.5789	0.6429	0.6688	0.6770	0.7087	0.7068	0.7248	0.7511
WC-GCN	0.6236	0.6461	0.6902	0.7076	0.7058	0.7229	0.7241	0.7345	0.7532

Table 8. Citeseer dataset in each class selects different labels for F1 results.

Input Methods	2*6	3*6	4*6	5*6	6*6	7*6	8*6	9*6	10*6
ChebyNet	0.2840	0.3088	0.3488	0.3622	0.3722	0.3915	0.4284	0.4274	0.4364
FastGCN	0.3307	0.3595	0.4127	0.4150	0.4498	0.4459	0.4727	0.4688	0.4944
GAT	0.3258	0.4372	0.5014	0.5450	0.5494	0.5990	0.6033	0.6214	0.5998
GCN	0.3041	0.3913	0.4420	0.5077	0.5451	0.5873	0.6200	0.6350	0.6282
SimPGCN	0.4221	0.4912	0.5261	0.5214	0.5365	0.5331	0.5631	0.5635	0.5658
Bet-GAT	0.4435	0.5042	0.5282	0.5476	0.5705	0.6146	0.6204	0.6495	0.6595
WC-GCN	0.5448	0.6036	0.6185	0.6644	0.6605	0.6616	0.6761	0.6946	0.6933

Table 9. F1 results for Pubmed dataset with different labels selected in each class.

Methods Input	2*3	3*3	4*3	5*3	6*3	7*3	8*3	9*3	10*3
ChebyNet	0.5665	0.6227	0.5958	0.6374	0.6215	0.6417	0.6984	0.6721	0.6799
FastGCN	0.5276	0.5919	0.5984	0.6361	0.6317	0.6599	0.6796	0.6853	0.6787
GAT	0.5580	0.6143	0.6507	0.6542	0.6550	0.6877	0.7125	0.7077	0.7098
GCN	0.5606	0.6175	0.6386	0.6605	0.6607	0.6695	0.7000	0.6780	0.6865
SimPGCN	0.5534	0.6219	0.6237	0.6240	0.6630	0.7076	0.6854	0.6717	0.6835
Bet-GAT	0.5872	0.6233	0.6471	0.6604	0.6561	0.6761	0.6689	0.6930	0.7290
WC-GCN	0.5991	0.6315	0.6645	0.6664	0.6794	0.6845	0.7049	0.7499	0.7375

The experimental results show that the WC-GCN model uses a very small number of known samples to learn the important network nodes (network structure centre), further spread the influence of the structure centre nodes, construct the balanced training set and finally achieve the purpose of network learning. At the same time, the learning framework should have certain fault tolerance, that is to say, when a very small number of samples with labelled errors in known samples, it can still learn the accurate network structure centre, which does not affect the accuracy of the network learning task.

5.5. Ablation study (RQ-2)

Two key steps of WC-GCN are updating structure centre (UpSC) and pseudo-labelled set expansion (PLSet). To answer RQ2, we compare four variants of WC-GCN. (1) Variant 1 (w/o UpSC and PLSet) directly trains a GCN for community detection under the supervision of the initial structure centres identified, neither updating the structure centres nor constructing an expanded pseudo-labelled set. (2) Variant 2 (w/o UpSC) does not updates the initial structure centres, but construct a larger pseudo-labelled set based on these structure centres, which is used to train the final GCN for community detection. (3) Variant 3 (w/o PLSet) updates the initial structure centres, but does not expand the pseudo-labelled set before training the final GCN for community detection. (4) Variant 4 is the full model with both UpSC and PLSet. The results are shown in Table 10.

Table 10. ACC results for Comparison of four variants of WC-GCN.

	Methods
	1	2	3	4
Network	w/o UpSC&PLSet	w/o PLSet	w/o UpSC	Full model
Cora	0.5377	0.5745	0.7128	0.7381
CiteSeer	0.5274	0.5664	0.6537	0.6980
PubMed	0.5369	0.5574	0.6489	0.6980

For the ablation experiments, we calculated the average of the ACC results of the experiments with 9 different inputs. We can roughly obtain a rank of the four variants according to their performance: Variant 1 < Variant 2 < Variant 3 < Variant 4. (1) Variant 1 (w/o UpSC & PLSet) performs the worst. Since it neither updates the initial structure centres nor constructs an expanded pseudo-labelled set, when some of the initial structure centres are not good, training the GCN with a limited set containing inappropriate seeds will yield unsatisfactory community partition. (2) Variant 2 (w/o UpSC) achieves better performance than Variant 1, but still falls far behind the full model. Note that it expands the pseudo-labelled set on the basis of initial structure centres, without updating them in advance. On the one hand, training the final GCN with an expanded set of pseudo-labelled nodes improves its propagation ability when detecting communities. On the other hand, if inappropriate initial seeds are directly used for expanding pseudo-labelled set, it may mislead the model. (3) The performance of Variant 3 is better than that of Variant 1, but is still lower than the full model. It updates the initial structure centres, which provide high-quality seeds for local community detection. However, the final GCN has limited propagation ability, if it is trained with only the refined structure centres. GCN models are semi-supervised learning models that require a certain amount of prior knowledge (labelled nodes) for graph learning. When there are very few known labelled nodes, the GCN model has limited propagation ability. (4) The performance of Variant 2 is lower than that of Variant 3, indicating that refining the structure centres has a larger impact than expanding the pseudo-labelled set.

Based on the above analysis, we conclude that both updating structure centre and pseudo-labelled set expansion are essential for WC-GCN to achieve its best performance. By updating the initial structure centres, the former step obtains a set of high-quality seed nodes, which lay a good foundation for local community detection. By expanding the pseudo-labelled set, the latter prepares a larger amount of supervision information for training GCN, which helps to improve its label propagation ability.

5.6. Case study for updating structure centre (RQ-3)

To answer RQ3, we conduct case studies on the Football network, and visualise the process of structure centre refinement.

In Figure 4, we randomly select 12 initial structure centres, which are located in 6 communities as shown in Figure 4(b). After 11 iterations of updates, the refined 12 structure centres come from 11 communities, as shown in Figure 4(d). Therefore, no matter whether the initial structure centres are selected at random, they can be refined to a set of more representative seeds that are scattered in different communities by algorithm 1. That is to say, it can overcome the sensitivity to initial structure centres to some extent, and reduce the adverse effect of inappropriate structure centres on community detection.

5.7. The influence of the size of the training set on the GCN (RQ-4)

Regarding the influence of the size of the training set on the GCN results, we also conducted related experiments with the NMI and ARI on the dataset of PolBlogs, Cora, Citeseer and Pubmed, and investigated how their performance varies with respect to the number of expanded nodes per pseudo label (i.e. $\tau$).

The experimental results are shown in the following Figure 5. We can observe that when the training set is very small, the NMI and ARI values are not high. When the training set exceeds a large number, the index value basically does not change much. In all datasets, the community detection performance of WC-GCN with an expansion strategy generally improves as the number of expanded nodes per pseudo-label increases to a moderate size. The reason is that a larger set of pseudo-labelled nodes makes up for the lack of label propagation ability of local graph convolutional filter. The experiment shows that constructing a pseudo-label training set to train GCN can make up for the lack of the division ability of the GCN model trained with a small number of training sets, and improve the division effect of the GCN model.

Figure 5. Performance variation on each network dataset with the size of the training set.

6. Conclusion

This paper proposes a community detection method based on weakly-supervised graph convolutional neural network (WC-GCN) with updated structure centres selection. The structure-centre selection algorithm not only considers the topological structure and attribute information, but also compensates for the lack of structure-centre dependence. Secondly, the structural centrality index C_struct is proposed to measure the representativeness of a subgraph, learning more accurate network structure centres. Thirdly, the self-training method is used to expand some nearby nodes with high credibility to build a balanced training set to further improve the model effect. Finally, the proposed method is evaluated experimentally on various real-world networks. Experimental results show that the proposed method performs more effectively compared to the current state-of-the-art community detection algorithms.

In this study, some limitation is that the attributes of nodes are homogeneous. As a fact, attributes of nodes are heterogeneous. How to extend the proposed algorithm for networks with heterogeneous attributes, how to handle dynamic networks, heterogeneous networks, or networks with noisy or missing data, possible extensions of the proposed method are also promising.

Disclosure statement

No potential conflict of interest was reported by the author(s).

Additional information

Funding

This work was supported by National Natural Science Foundation of China [grant number 11702289]; Key Core Technology and Generic Technology R&D Project of Shanxi Province [grant number 2020XXX013].

Notes

1 https://linqs.org/datasets/#cora

2 https://linqs.org/datasets/#citeseer-doc-classification

3 https://linqs.org/datasets/#pubmed-diabetes

4 https://www.cc.gatech.edu/dimacs10/archive/clustering.shtml