CS-TGN: Community Search via Temporal Graph Neural Networks
Searching for local communities is an important research challenge that
allows for personalized community discovery and supports advanced data analysis
in various complex networks, such as the World Wide Web, social networks, and
brain networks. The evolution of these networks over time has motivated several
recent studies to identify local communities in temporal networks. Given any
query nodes, Community Search aims to find a densely connected subgraph
containing query nodes. However, existing community search approaches in
temporal networks have two main limitations: (1) they adopt pre-defined
subgraph patterns to model communities, which cannot find communities that do
not conform to these patterns in real-world networks, and (2) they only use the
aggregation of disjoint structural information to measure quality, missing the
dynamic of connections and temporal properties. In this paper, we propose a
query-driven Temporal Graph Convolutional Network (CS-TGN) that can capture
flexible community structures by learning from the ground-truth communities in
a data-driven manner. CS-TGN first combines the local query-dependent structure
and the global graph embedding in each snapshot of the network and then uses a
GRU cell with contextual attention to learn the dynamics of interactions and
update node embeddings over time. We demonstrate how this model can be used for
interactive community search in an online setting, allowing users to evaluate
the found communities and provide feedback. Experiments on real-world temporal
graphs with ground-truth communities validate the superior quality of the
solutions obtained and the efficiency of our model in both temporal and
interactive static settings.
Farnoosh Hashemi, Ali Behrouz, Milad Rezaei Hajidehi
# CS-TGN: Community Search via Temporal Graph Neural Networks

###### Abstract.

Searching for local communities is an important research challenge that allows for personalized community discovery and supports advanced data analysis in various complex networks, such as the World Wide Web, social networks, and brain networks. The evolution of these networks over time has motivated several recent studies to identify local communities in temporal networks. Given any query nodes, Community Search aims to find a densely connected subgraph containing query nodes. However, existing community search approaches in temporal networks have two main limitations: (1) they adopt pre-defined subgraph patterns to model communities, which cannot find communities that do not conform to these patterns in real-world networks, and (2) they only use the aggregation of disjoint structural information to measure quality, missing the dynamic of connections and temporal properties. In this paper, we propose a query-driven Temporal Graph Convolutional Network (CS-TGN) that can capture flexible community structures by learning from the ground-truth communities in a data-driven manner. CS-TGN first combines the local query-dependent structure and the global graph embedding in each snapshot of the network and then uses a GRU cell with contextual attention to learn the dynamics of interactions and update node embeddings over time. We demonstrate how this model can be used for interactive community search in an online setting, allowing users to evaluate the found communities and provide feedback. Experiments on real-world temporal graphs with ground-truth communities validate the superior quality of the solutions obtained and the efficiency of our model in both temporal and interactive static settings.

community search, temporal networks, graph neural networks +
Footnote †: 10.05

+
Footnote †: 10.05: _Journal of the ACM Web Conference 2023 (WWW '23 Companion), April 30-May 4, 2023, Austin, TX, USA_

+
Footnote †: 10.05: _Journal of the ACM Web Conference 2023 (WWW '23 Companion), April 30-May 4, 2023, Austin, TX, USA_

+
Footnote †: 10.05: _Journal of the ACM Web Conference 2023 (WWW '23 Companion), April 30-May 4, 2023, Austin, TX, USA_

+
Footnote †: 10.05: _Journal of the ACM Web Conference 2023 (WWW '23 Companion), April 30-May 4, 2023, Austin, TX, USA_

+
Footnote †: 10.05: _Journal of the ACM Web Conference 2023 (WWW '23 Companion), April 30-May 4, 2023, Austin, TX, USA_

+
Footnote †: 10.05: _Journal of the ACM Web Conference 2023 (WWW '23 Companion), April 30-May 4, 2023, Austin, TX, USA_

+
Footnote †: 10.05: _Journal of the ACM Web Conference 2023 (WWW '23 Companion), April 30-May 4, 2023, Austin, TX, USA_

+
Footnote †: 10.05: _Journal of the ACM Web Conference 2023 (WWW '23 Companion), April 30-May 4, 2023, Austin, TX, USA_

+
Footnote †: 10.05: _Journal of the ACM Web Conference 2023 (WWW '23 Companion), April 30-May 4, 2023, Austin, TX, USA_

+
Footnote †: 10.05: _Journal of the ACM Web Conference 2023 (WWW '23 Companion), April 30-May 4, 2023, Austin, TX, USA_

+
Footnote †: 10.05: _Journal of the ACM Web Conference 2023 (WWW '23 Companion), April 30-May 4, 2023, Austin, TX, USA_

+
Footnote †: 10.05: _Journal of the ACM Web Conference 2023 (WWW '23 Companion), April 30-May 4, 2023, Austin, TX, USA_

+
Footnote †: 10.05: _Journal of the ACM Web Conference 2023 (WWW '23 Companion), April 30-May 4, 2023, Austin, TX, USA_

+
Footnote †: 10.05: _Journal of the ACM Web Conference 2023 (WWW '23 Companion), April 30-May 4, 2023, Austin, TX, USA_

+
Footnote †: 10.05: _Journal of the ACM Web Conference 2023 (WWW '23 Companion), April 30-May 4, 2023, Austin, TX, USA_

+
Footnote †: 10.05: _Journal of the ACM Web Conference 2023 (WWW '23 Companion), April 30-May 4, 2023, Austin, TX, USA_

+
Footnote †: 10.05: _Journal of the ACM Web Conference 2023 (WWW '23 Companion), April 30-May 4, 2023, Austin, TX, USA_

+
Footnote †: 10.05: _Journal of the ACM Web Conference 2023 (WWW '23 Companion), April 30-May 4, 2023, Austin, TX, USA_

+
Footnote †: 10.05: _Journal of the ACM Web Conference 2023 (WWW '23 Companion), April 30-May 4, 2023, Austin, TX, USA_

+
Footnote †: 10.05: _Journal of the ACM Web Conference 2023 (WWW '23 Companion), April 30-May 4, 2023, Austin, TX, USA_

+
Footnote †: 10.05: _Journal of the ACM Web Conference 2023 (WWW '23 Companion), April 30-May 4, 2023, Austin, TX, USA_

+
Footnote †: 10.05: _Journal of the ACM Web Conference 2023 (WWW '23 Companion), April 30-May 4, 2023, Austin, TX, USA_

+
Footnote †: 10.05: _Journal of the ACM Web Conference 2023 (WWW '23 Companion), April 30-May 4, 2023, Austin, TX, USA_

+
Footnote †: 10.05: _Journal of the ACM Web Conference 2023 (WWW '23 Companion), April 30-May 4, 2023, Austin, TX, USA_

+
Footnote †: 10.05: _Journal of the ACM Web Conference 2023 (WWW '23 Companion), April 30-May 4, 2023, Austin, TX, USA_

+
Footnote †: 10.05: _Journal of the ACM Web Conference 2023 (WWW '23 Companion), April 30-May 4, 2023, Austin, TX, USA_

+
Footnote †: 10.05: _Journal of the ACM Web Conference 2023 (WWW '23 Companion), April 30-May 4, 2023, Austin, TX, USA_

+
Footnote †: 10.05: _Journal of the ACM Web Conference 2023 (WWW '23 Companion), April 30-May 4, 2023, Austin, TX, USA_

+
Footnote †: 10.05: _Journal of the ACM Web Conference 2023 (WWW '23 Companion), April 30-May 4, 2023, Austin, TX, USA_

+
Footnote †: 10.05: _Journal of the ACM Web Conference 2023 (WWW '23 Companion), April 30-May 4, 2023, Austin, TX, USA_

+
Footnote †: 10.05: _Journal of the ACM Web Conference 2023 (WWW '23 Companion), April 30-May 4, 2023, Austin, TX, USA_

+
Footnote †: 10.05: _Journal of the ACM Web Conference 2023 (WWW '23 Companion), April 30-May 4, 2023, Austin, TX, USA_

+
Footnote †: 10.05: _Journal of the ACM Web Conference 2023 (WWW '23 Companion), April 30-May 4, 2023, Austin, TX, USA_

+
Footnote †: 10.05: _Journal of the ACM Web Conference 2023 (WWW '23 Companion), April 30-May 4, 2023, Austin, TX, USA_

+
Footnote †: 10.05: _Journal of the ACM Web Conference 2023 (WWW '23 Companion), April 30-May 4, 2023, Austin, TX, USA_

+
Footnote †: 10.05: _Journal of the ACM Web Conference 2023 (WWW '23 Companion), April 30-May 4, 2023, Austin, TX, USA_

+
Footnote †: 10.05: _Journal of the ACM Web Conference 2023 (WWW '23 Companion), April 30-May 4, 2023, Austin, TX, USA_

+
Footnote †: 10.05: _Journal of the ACM Web Conference 2023 (WWW '23 Companion), April 30-May 4, 2023, Austin, TX, USA_

+
Footnote †: 10.05: _Journal of the ACM Web Conference 2023 (WWW '23 Companion), April 30-May 4, 2023, Austin, TX, USA_

+
Footnote †: 10.05: _Journal of the ACM Web Conference 2023 (WWW '23 Companion), April 30-May 4, 2023, Austin, TX, USA_

+
Footnote †: 10.05: _Journal of the ACM Web Conference 2023 (WWW '23 Companion), April 30-May 4, 2023, Austin, TX, USA_

+
Footnote †: 10.05: _Journal of the ACM Web Conference 2023 (WWW '23 Companion), April 30-May 4, 2023, Austin, TX, USA_

+
Footnote †: 10.05: _Journal of the ACM Web Conference 2023 (WWW '23 Companion), April 30-May 4, 2023, Austin, TX, USA_

+
Footnote †: 10.05: _Journal of the ACM Web Conference 2023 (WWW '23 Companion), April 30-May 4, 2023, Austin, TX, USA_

+
Footnote †: 10.05: _Journal of the ACM Web Conference 2023 (WWW '23 Companion), April 30-May 4, 2023, Austin, TX, USA_

+
Footnote †: 10.05: _Journal of the ACM Web Conference 2023 (WWW '23 Companion), April 30-May 4, 2023, Austin, TX, USA_

+
Footnote †: 10.05: _Journal of the ACM Web Conference 2023 (WWW '23 Companion), April 30-May 4, 2023, Austin, TX, USA_

+
Footnote †: 10.05: _Journal of the ACM Web Conference 2023 (WWW '23 Companion), April 30-May 4, 2023, Austin, TX, USA_

+
Footnote †: 10.05: _Journal of the ACM Web Conference 2023 (WWW '23 Companion), April 30-May 4, 2023, Austin, TX, USA_

+
Footnote †: 10.05: _Journal of the ACM Web Conference 2023 (WWW '23 Companion), April 30-May 4, 2023, Austin, TX, USA_

+
Footnote †: 10.05: _Journal of the ACM Web Conference 2023 (WWW '23 Companion), April 30-May 4, 2023, Austin, TX, USA_

+
Footnote †: 10.05: _Journalournal of the ACM Web Conference 2023 (WWW '23 Companion), April 30-May 4, 2023, Austin, TX, USA
candidate set of nodes based on user input and lacks the ability to learn the dynamics of user queries to adjust the results accordingly. To mitigate the aforementioned limitations, we design a query-driven temporal graph convolutional neural network, called CS-TGN. To address structure inflexibility, we design two encoders: **(1)**_Query Encoder_ to encode the structural information from query nodes and capture the local topology around the queries in each snapshot of the network, and **(2)**_Snapshot Encoder_ to learn the query-independent node embeddings by combining the global structure and attributes of vertices in each snapshot of the network. To take advantage of node attributes, structural properties, and their dynamics in different snapshots of the network, CS-TGN employs Gated Recurrent Unit (GRU) cells (Gat et al., 2017) and extends the idea of hierarchical node states (Song et al., 2019) by using a contextual attention mechanism that can combine the hidden states for long-term patterns and the window information containing the short-term patterns. Next, we showcase the applicability of CS-TGN in interactive community search and propose a meta-learning framework. Within this framework, each query of the user is treated as an input of the _Query Encoder_ in a snapshot of the underlying network. We then consider the identification of communities based on user queries as distinct tasks. This design enables the model to **(1)** learn the dynamics of the network and better adapt to different user queries, and **(2)** learn the dynamic of user queries, resulting in better performance.

To summarize, We make the following contributions:

* We present CS-TGN, a query-driven temporal graph convolutional neural network that integrates the local query-dependent structure and global node embeddings at each timestamp. CS-TGN represents the local query-dependent and global node embeddings as hierarchical node states at different GCN layers and uses attention-based GRU cells to capture the network dynamics and update query-dependent and global embeddings over time.
* We demonstrate how CS-TGN can be utilized for interactive community search. Specifically, we approach interactive community search as a meta-learning problem over temporal networks, treating the network in each user-model interaction as one snapshot in CS-TGN framework. We then consider identifying communities based on queries from different users as distinct tasks.
* By conducting extensive experiments on real-world temporal and static networks with ground-truth communities, we demonstrate that our method is capable of efficiently and effectively discovering communities in both online and interactive settings.

## 2. Related Work

**Community Search.** The concept of community search, which aims to find query-dependent communities in a graph, was first introduced by Sozio and Gionis (Sozio and Gionis, 2018). Since then, various community models have been proposed based on different pre-defined dense subgraphs (Song et al., 2019), including \(k\)-core (Song et al., 2019; Song et al., 2019), \(k\)-truss (Song et al., 2019; Song et al., 2019), quasi-clique (Song et al., 2019), \(k\)-plex (Song et al., 2019), and densest subgraph (Song et al., 2019). Recently, community search has also been explored in directed (Song et al., 2019; Song et al., 2019), weighted (Song et al., 2019), geo-social (Song et al., 2019; Song et al., 2019), multilayer (Song et al., 2019; Song et al., 2019; Song et al., 2019), multi-valued (Song et al., 2019), and labeled (Song et al., 2019) graphs. Inspired by the success of Graph Neural Networks (GNNs), recently, several GNN-based approaches have been proposed for community search, such as (Song et al., 2019; Song et al., 2019; Song et al., 2019). However, these models only focus on static networks and do not capture the dynamics of interactions and temporal properties.

**Community Search in Dynamic Networks.** CS in temporal networks recently has attracted attention and several community models have been proposed (Song et al., 2019; Song et al., 2019; Song et al., 2019; Song et al., 2019; Song et al., 2019). Li et al. (Li et al., 2019) have defined the persistent community search as the maximal \(k\)-core, where each vertex's cumulative degree satisfies the \(k\)-core requirement within a specified time interval. Qin et al. (Qi et al., 2019) have proposed stable communities by first selecting centroid vertices with a certain number of neighbors having the desired similarity and a star-shaped structure of the centroid vertex and its neighbors existing frequently over a period of time, followed by clustering network vertices into stable groups based on the selected centroids. Similarly, Lin et al. (Lin et al., 2019) have defined frequency-based dense subgraphs that satisfy the quasi-clique structure with at least \(\theta\) vertices, and each vertex has a degree more than a given threshold. Finally, Tang et al. (Tang et al., 2019) have introduced the Reliable CS problem based on \(k\)-core structure and the duration of interactions. These methods differ from our approach, as they are based on pre-defined patterns.

**Temporal Graph Learning.** Many approaches have been proposed in the literature to address the problem of learning from temporal networks (Song et al., 2019; Song et al., 2019; Song et al., 2019; Song et al., 2019; Song et al., 2019; Song et al., 2019). One group of methods u Recurrent Neural Networks (RNN) and replace the linear layer with a graph convolution layer (Song et al., 2019; Song et al., 2019). Another group deploys a GNN as a feature encoder and a sequence model on top of the GNN to capture temporal properties (Song et al., 2019; Song et al., 2019; Song et al., 2019). However, these models have limitations in both their design and training strategies (Song et al., 2019). To overcome these limitations, recent frameworks such as ROLAND and its variants (Song et al., 2019; Song et al., 2019) have been proposed to re-purpose static GNNs for dynamic graphs. However, these approaches only incorporate node embeddings from the previous snapshot in the GRU cell, failing to capture short-term patterns. In contrast, our proposed framework extends ROLAND by incorporating both long-term and short-term patterns using a contextual attention mechanism. Notably, our framework is designed for the CS problem and can capture query-dependent structural properties, which is not addressed by previous approaches.

## 3. Problem Formulation

We first precisely define temporal networks, and then we formalize the problem of community search in temporal graphs. Let \(\mathcal{G}=(\mathcal{V},\mathcal{E},\mathcal{X})=\{\mathcal{G}^{t}\}_{t=1}^{T}\) denote a temporal network, where \(\mathcal{G}^{t}=(\mathcal{V}^{t},\mathcal{E}^{t},\mathcal{X}^{t})\) represents the \(t\)-th snapshot of the network, \(\mathcal{V}=\bigcup_{t=1}^{T}\mathcal{V}^{t}\) is the set of nodes, \(\mathcal{E}=\bigcup_{t=1}^{T}\mathcal{E}^{t}\) is the set of edges, and \(\mathcal{X}=\mathcal{X}^{T}\in\mathbb{R}^{|\mathcal{V}|\times f}\) is a matrix that encodes node attribute information for nodes in \(\mathcal{V}\). Given attribute matrix \(\mathcal{X},\mathcal{X}^{t}_{w}\) represents the attribute set of vertex \(v\in\mathcal{V}^{t}\) at timestamp \(t\). We denote the set of vertices in the neighborhood of \(u\in\mathcal{V}\) in \(t\)-th snapshot as \(\mathcal{N}^{t}(u)\). Each edge \(e=(u,v)\in\mathcal{E}\) is associated with a timestamp \(\tau_{e}\), and each node \(v\in\mathcal{V}\) is associated with a timestamp \(\tau_{v}\).

Problem 1 (Community Search in Temporal Networks).: _Given a temporal network \(\mathcal{G}=\left\{\mathcal{G}^{1},\dots,\mathcal{G}^{t}\right\}=(\mathcal{V },\mathcal{E},\mathcal{X})\), and a vertex
query set \(\mathcal{V}_{q}\subseteq\mathcal{V}\), the problem of Community Search in Temporal Networks (CST) is to find the query-dependent community \(\mathcal{C}_{q}\subseteq\mathcal{V}\) that is connected and has a cohesive structure._

In this paper, we formulate the problem as a binary classification task. Given a set of query vertices \(\mathcal{V}_{q}\subseteq\mathcal{V}\), we classify the nodes in \(\mathcal{V}\) into: **1**: being a part of the community \(\mathcal{C}_{q}\), **0**: not being a part of it. We use a one-hot vector \(\mathbf{c}_{q}^{\text{out}}\in\{0,1\}^{|\mathcal{V}|}\) to represent the output community \(\mathcal{C}_{q}\) produced by model \(\mathcal{M}\). Accordingly, if \(\mathbf{c}_{q_{o}}^{\text{out}}=1\), vertex \(v\) is a part of the predicted community \(\mathcal{C}_{q}\) by \(\mathcal{M}\).

## 4. CS-TGN Framework

This section presents our proposed framework for Community Search (CS) in temporal networks. The framework consists of two main stages: offline training and online query, as illustrated in Figure 1. In the offline training stage, we train a model denoted as \(\mathcal{M}\) to predict the membership of each vertex to the corresponding community of query vertices. Specifically, \(\mathcal{M}\) learns to capture the flexible community structures and the dynamic temporal properties of the network from ground-truth communities. In the online query stage, given a query vertex set \(\mathcal{V}_{q}\), we utilize the trained model \(\mathcal{M}\) to identify the corresponding community of \(\mathcal{V}_{q}\).

### Architecture

In our framework, given a timestamp \(t\), we begin by utilizing GCN layers to encode both the graph structure and the features of the nodes present in the recent snapshot \(\mathcal{G}^{t}=(\mathcal{V}^{t},\mathcal{E}^{t},\mathcal{X}^{t})\). We then use GCN layers and the query vector \(\mathbf{c}_{q}^{t}\) as the features of nodes to better capture the local query structure information. This part, called _Query Encoder_, propagates from the query vertices to its surrounding nodes, allowing for query-centered structural propagation. We then use a contextual attention-based model with GRU cells to capture both short-term and long-term patterns of nodes and update the node embeddings over time. Accordingly, we incorporate the historical and temporal properties of the network. Finally, a feedforward neural network (FNN) is employed for classification. The architectures of _Snapshot Encoder_ and _Query Encoder_ are illustrated in Figure 1(a). Next, we explain each part in detail.

**Snapshot Encoder.** Given a timestamp \(t\) and a snapshot of the network \(\mathcal{G}^{t}=(\mathcal{V}^{t},\mathcal{E}^{t},\mathcal{X}^{t})\), _Snapshot Encoder_ captures the structural properties as well as attributes of vertices at timestamp \(t\). To this end, it employs the layer-wise forward propagation of GCN with self-feature modeling as:

\[\hat{h}_{u}^{t\,(\ell+1)}=\text{Dr}\left\{\sigma\Bigg{(}\hat{h}_{u}^{t\,( \ell)}\text{W}_{s}^{(\ell+1)}+\sum_{v\in\mathcal{N}^{t}(u)}[\frac{h_{v}^{t\,( \ell)}}{\sqrt{p_{u}^{t\,p_{u}^{t}}}}\text{W}^{(\ell+1)}+\text{b}^{(\ell+1)}] \Bigg{)}\right\}, \tag{1}\]

where at timestamp \(t\), \(h_{u}^{t\,(\ell+1)}\in\mathbb{R}_{\ell^{\prime}}^{d^{(\ell+1)}}\) is the learned new features of node \(u\) in the \((\ell+1)\)-th GCN layer, \(h_{u}^{t\,(\ell)}\in\mathbb{R}_{\ell^{\prime}}^{d^{(\ell)}}\) is the hidden feature of \(u\) in \(\ell\)-th GCN layer, and \(\text{W}_{s}^{(\ell+1)},\text{W}^{(\ell+1)}\in\mathbb{R}^{d^{(\ell)}\times d ^{(\ell+1)}}\), and \(\text{b}^{(\ell+1)}\in\mathbb{R}^{d^{(\ell+1)}}\) are trainable weights. \(\sigma(.)\) is a nonlinearity, e.g., ReLU, and \(\text{Dr}(.)\) is the dropout method (Krizhevsky et al., 2015) to avoid overfitting. Given a vertex \(u\in\mathcal{V}\), \(p_{u}^{t}\) denotes the degree of node \(u\) plus one at timestamp \(t\), i.e., \(p_{u}^{t}=|\mathcal{N}^{t}(u)|+1\). The input feature of node \(u\) in the first layer, \(h_{u}^{r\,(0)}\in\mathbb{R}^{d}\), is the normalized feature vector \(\mathcal{X}_{u}^{t}\).

**Query Encoder.** At the time \(t\), we transform a set of query vertices, denoted as \(\mathcal{V}_{q}^{t}\), into a one-hot vector representation, called \(\mathbf{c}_{q}^{t}\). That is, if a vertex \(u\) is in the query set, then the value of \(\mathbf{c}_{q_{u}}^{t}\) is set to \(1\), otherwise it is \(0\). Next, we apply the propagation function defined in Equation 1 to each vertex \(u\in\mathcal{V}^{t}\). We denote the query-dependent hidden features of vertex \(u\) at \(\ell\)-th layer as \(h_{Q_{u}}^{t\,(\ell)}\), and use trainable query-dependent weights denoted by \(\text{W}_{Q}^{(\ell+1)}\)s, \(\text{W}_{Q}^{(\ell+1)}\), and \(\text{b}_{Q}^{(\ell+1)}\). Unlike _Snapshot Encoder_, where the input feature for vertex \(u\) in the first layer is the node feature vector, in _Query Encoder_, we use the one-hot query vector \(\mathbf{c}_{q_{u}}^{t}\) as the input for the first GCN layer. As shown in Figure 1(a), we combine the output of each layer in both _Snapshot Encoder_ and _Query Encoder_ and use it as the input for the next layer of _Query Encoder_. This enables us to provide a stable and reliable knowledge of the graph's structure and node features that is independent of the query.

**Attention-based Update Module.** In order to capture the short-term patterns of nodes, inspired by (Krizhevsky et al., 2015), we employ a contextual attention-based mechanism proposed by (Krizhevsky et al., 2015). Specifically, for a given local window size \(w\), we construct the short state of the

Figure 1. The design of CS-TGN framework.
window as follows:

(2) \[C_{u}^{t\,(\ell)} =\left[h_{u}^{t-\text{w}^{t\,(\ell)}},\dots,h_{u}^{t-1\,(\ell)}\right],\] (3) \[E_{u}^{t\,(\ell)} =\operatorname{softmax}\left(\mathbf{r}^{t\,(\ell)}\tanh\left( \mathbf{Q}^{t\,(\ell)}\left(C_{u}^{t\,(\ell)}\right)^{T}\right)\right),\] (4) \[\operatorname{short}_{u}^{t^{\prime}\,(\ell)} =\left(E_{u}^{t\,(\ell)}C_{u}^{t\,(\ell)}\right)^{T},\] (5)

where \(h_{u}^{t^{\prime}\,(\ell)}\) is the node embedding of vertex \(u\) at time \(t^{\prime}\) and after the \(\ell\)-th GCN layer, and \(\mathbf{r}^{t\,(\ell)}\) and \(\mathbf{Q}^{t\,(\ell)}\) are trainable weights. Next, we use a GRU cell (Chen et al., 2017) and update node embeddings:

\[\zeta_{u}^{t\,(\ell)}=\operatorname{GRU}\left(h_{u}^{t^{\prime}\,(\ell)}, \operatorname{short}_{u}^{t\,(\ell+1)}\right). \tag{6}\]

Note that the formulation of the _Update Module_ for _Query Encoder_ is the same as above, while we replace \(h_{u}^{t^{\prime}\,(\ell)}\) with \(h_{u}^{t^{\prime}\,(\ell)}\). In this case, we denote the output as \(\zeta_{uQ}^{t\,(\ell)}\). This process is illustrated in Figure 1(b).

**FNN Layer.** Finally, a feedforward neural network is used to classify nodes based on the concatenation of the obtained embedding from the previous part:

\[\psi_{u}^{t\,(L)}=\operatorname{FNN}\left(\zeta_{u}^{t\,(L)}\parallel\zeta_{uQ }^{t\,(L)}\right), \tag{7}\]

where \(L\) is the number of GCN layers.

**Loss Function.** As discussed, the CS problem is treated as a binary classification task, where the output of model \(\mathcal{M}\) is \(\psi_{q}^{t}\in\mathbb{R}^{|\mathcal{V}^{t}|}\), representing the probability of each vertex \(u\in\mathcal{V}^{t}\) being a member of the community \(\mathcal{C}_{q}^{t}\). Ground-truth labels \(y_{q_{u}}^{t}\) are defined for each vertex \(u\) based on the community structure of the query set \(\mathcal{V}_{q}^{t}\), and Binary Cross Entropy (BCE) is used as the loss function. The query-dependent loss function \(\mathcal{L}_{q}^{t}\) is defined as:

\[\mathcal{L}_{q}^{t}=\frac{1}{|\mathcal{V}^{t}|}\sum_{u\in\mathcal{V}^{t}}- \left(\psi_{q_{u}}^{t}\log(\psi_{q_{u}}^{t})+(1-\psi_{q_{u}}^{t})\log(1-\psi_ {q_{u}}^{t})\right). \tag{8}\]

By minimizing \(\mathcal{L}_{q}^{t}\), the model learns to detect the community structure of the network by classifying vertices into their respective communities.

Remark 1 ().: _Communities in real-world networks are known to be dynamic, with nodes joining or leaving communities over time. The proposed formulation allows for the adaptation of the model in scenarios where the ground-truth communities evolve over time. Consequently, during the training phase, the model can learn to capture the dynamics of the evolving ground-truth communities._

### Training and Online Query

**Training.** We begin with a given set of query vertex sets denoted as \(Q_{\text{train}}=\{q_{1},q_{2},\dots,q_{n}\}\) along with their respective ground-truth communities \(\mathcal{C}_{\text{train}}=\{C_{1},\dots,C_{n}\}\). First, we encode all query inputs as one-hot vectors. Then, at each time \(t\), we repeatedly feed a query \(q\) from \(\mathcal{Q}_{\text{train}}\) into a model \(\mathcal{M}\). The output \(\psi_{q}^{t}\) from \(\mathcal{M}\) is used to compute the loss and gradients of the model parameters. The updated parameters are then used for the next iteration, where \(\mathcal{M}\) receives another query \(q^{\prime}\in\mathcal{Q}_{\text{train}}\) as input. This process continues until all queries in \(\mathcal{Q}_{\text{train}}\) have been processed. The overall loss function is the sum of all query-dependent loss functions:

\[\mathcal{L}^{t}=\sum_{q\in\mathcal{Q}_{\text{train}}}\mathcal{L}_{q}^{t} \tag{9}\]

**Online Query.** Next, we describe the process of utilizing the pre-trained model \(\mathcal{M}\) at time \(t\) to identify the community \(\mathcal{C}_{q}^{t}\) of an online query \(\mathcal{V}_{q}^{t}\) without the need for re-training \(\mathcal{M}\). First, we construct a representative one-hot vector for \(\mathcal{V}_{q}^{t}\) and refer to \(\mathcal{M}\). The output of \(\mathcal{M}\) is denoted as \(\psi_{q}^{t}\in\mathbb{R}^{|\mathcal{V}^{t}|}\), where \(\psi_{q_{u}}^{t}\in[0,1]\) represents the probability of vertex \(u\) belonging to \(\mathcal{C}_{q}^{t}\) at time \(t\). The online query stage is presented in Algorithm 1, where a threshold \(\eta\in[0,1]\) is utilized to identify the vertices in \(\mathcal{C}_{q}^{t}\) as those with \(\psi_{q_{u}}^{t}\geq\eta\). Since communities are known to be connected, we use Breadth-First Search (BFS) traversal starting from query vertices to ensure connectivity.

**Time Complexity.** In Algorithm 1, the time complexity of GCN inferring (line 2) depends on the number of layers and the architecture of GCNs. BFS traversal (lines 3-7) takes \(\mathcal{O}(|\mathcal{E}^{t}|)\) time. Accordingly, the time complexity is dominated by GCN inferring (line 2).

```
1:A snapshot of a temporal network \(\mathcal{G}^{t}=(\mathcal{V}^{t},\mathcal{E}^{t},\mathcal{X}^{t})\), a query vertex set \(\mathcal{V}_{q}\), a trained model \(\mathcal{M}\), and a threshold \(\eta\)
2:A temporal community \(\mathcal{C}_{q}\)
3:\(\mathcal{Q},\mathcal{C}_{q}\leftarrow\mathcal{V}_{q}\);
4:\(\mathcal{V}_{q}\gets\) feed \(\mathcal{V}_{q}\) into \(\mathcal{M}\);
5:while\(\mathcal{Q}\) is not empty do
6: pick and remove a vertex \(u\) from \(Q\);
7:for\(v\in N^{t}(u)\) and \(\psi_{q_{u}}\geq\eta\)do
8:\(\mathcal{Q}\gets\mathcal{Q}\cup\{v\}\);
9:\(\mathcal{C}_{q}\leftarrow\mathcal{C}_{q}\cup\{v\}\); return\(\mathcal{C}_{q}\)
```

**Algorithm 1** Temporal Community Identification

### Interactive Community Search

The majority of community search methods in static and dynamic graphs utilize a progressive approach to identify the community (Han et al., 2017). Nonetheless, to obtain a high-quality outcome that meets the user's expectations, the user may need to adjust their query, choose representative features, and modify the size of the community, based on each presented result for a given set of queries. In this section, we propose a meta-learning framework, where each query submitted by the user is considered an input to the _Query Encoder_ in a snapshot of the underlying network. We view the identification of communities based on user queries as separate tasks.

In this work, we consider a scenario where each user query is treated as a new snapshot of the underlying network, which can be either temporal or static. We aim to improve the performance of the model and user satisfaction by allowing the user to provide feedback on the output community, label data, and query new nodes. To update the model based on the user's feedback, we propose a meta-learning framework that uses a meta-model \(\mathcal{M}^{(meta)}\) as a good initialization for deriving specialized models for future unseen user queries.

To achieve this, we draw inspiration from previous work (Zhu et al., 2019) and adopt the Reptile algorithm (Rapid et al., 2019). Specifically, for each user, we
first initialize the model \(\mathcal{M}\) using \(\mathcal{M}^{(meta)}\) and fine-tune it using back-propagation. We then update the meta-model by computing the moving average of the trained model:

\[\mathcal{M}^{(meta)}=(1-\alpha)\mathcal{M}^{(meta)}+\alpha\mathcal{M},\]

where \(\alpha\in[0,1]\) is the smoothing factor. It is worth noting that always fine-tuning the previous model may not be optimal, as the dynamics of each user's query can be different. Therefore, our proposal of finding a meta-model \(\mathcal{M}^{(meta)}\) as a good initialization can lead to better specialized models. The process is presented in Algorithm 2 and is illustrated in Figure 1(c).

```
0: A (temporal) network \(\mathcal{G}=(\mathcal{V},\mathcal{E},\mathcal{X})\), #epochs, a meta-model \(\mathcal{M}^{(meta)}\), smoothing factor \(\alpha\), and a threshold \(\eta\)
0: A temporal community \(\mathcal{C}_{q}\), and updated meta-model \(\mathcal{M}^{(meta)}\)
1:\(\mathcal{M}\leftarrow\mathcal{M}^{(meta)}\);
2:while user query vertex set \(\mathcal{V}_{q}\) is not empty do
3:\(\mathcal{C}_{q}\gets \text{feed }\mathcal{V}_{q}\) into \(\mathcal{M}\) and find a community; \(\triangleright\) Algorithm 1
4:\(y_{q}\leftarrow\text{user provides feedback on }\mathcal{C}_{q}\) (labels data);
5:for epoch = 1,..., #epochs do
6: Update \(\mathcal{M}\) via backprop based on \(\mathcal{V}_{q}\), \(y_{q}\), and \(\mathcal{G}^{\prime}\);
7: user terminates or inputs a new query vertex set \(\mathcal{V}_{q}\leftarrow\mathcal{V}_{q}^{(new)}\);
8:\(\mathcal{M}^{(meta)}\leftarrow(1-\alpha)\mathcal{M}^{(meta)}+\alpha\mathcal{M}\);
9:return\(\mathcal{M}^{(meta)}\)
```

**Algorithm 2** Interactive Community Identification

## 5. Experiments

**Datasets.** We evaluate the performance of our proposed model using five real-world networks with ground-truth communities [1; 4; 20; 22; 50], from diverse domains, including social, communication, co-authorship, and brain networks. The statistics of these networks can be found in Table 1. Notably, the ground-truth communities in the _brain_ dataset correspond to functional systems in the human brain, making it a valuable demonstration of the effectiveness of our approach in identifying such systems. We conduct experiments using 100 query-community pairs for the smaller _football_ and _brain_ networks, and 350 query-community pairs for the other networks. We divide the queries into training, validation, and test sets, with a ratio of 40% for training, 30% for validation, and 30% for testing. We use these sets to train the model, perform early stopping and hyperparameter tuning, and evaluate the end-to-end performance of our model, respectively.

**Setup.** Our models are implemented in Python 3.7 with _PyTorch_ and _torch-geometric_ libraries. The encoders consist of two GCN layers and a GRU unit with \(h\) neurons. We fine-tuned the optimal value of \(h\in\{32,64,128,256\}\). In the ablation study, the effect of varying \(h\) on the quality is evaluated.

The reported times for the training and inference are based on the experiments on a Linux machine with _nvidia A4000_ GPU with 16GB of memory. We train the model for 100 epochs with a learning rate of 0.01. We used ReLU as the activation function and a dropout rate of 0.5. When dealing with large datasets, we follow the approach outlined in [3; 18; 25] and choose nodes within 2-hops of query nodes as possible subgraphs for each query. The model is then trained on these subgraphs to predict communities. Our code repository ([https://github.com/joint-em/CS-TGN](https://github.com/joint-em/CS-TGN)) contains more information about the implementation of our framework.

**Baselines.** We compare our CS-TGN with state-of-the-art temporal and static community search (CS) methods. Reliable [44] is a \(k\)-core-based approach in temporal networks that finds a weighted \(k\)-core containing query nodes. Truss [49] is an approach based on \(k\)-truss structure in temporal networks. MLGCN [3] is a learning-based CS method in multiplex networks that leverages an attention mechanism to incorporate the information of different relation types. FTCS [4] finds the connected FirmTruss containing query nodes with the minimum diameter. In multiplex methods, each snapshot of the network is treated as one layer or view. Finally, we compare our approach with a state-of-the-art learning-based method in static graphs, QD-GNN [25]. In the interactive setting, we compare our method with ICS-GNN [18], a GNN-based interactive community search model that requires re-training for each query.

**Queries and Evaluation Metrics.** The performance of all algorithms is evaluated using varying numbers of query nodes. We generated the queries randomly with a size between 1 to 10. The quality of the found communities \(C\) is assessed through their F1-score, which measures the alignment with the ground truth \(\tilde{C}\). The F1 score is defined as \(F1(C,\tilde{C})=\frac{2pre(C,\tilde{C})rec(C,\tilde{C})}{pre(C,\tilde{C})+rec(C, \tilde{C})}\), where \(pre(C,\tilde{C})=\frac{|C\cap\tilde{C}|}{|C|}\) and \(rec(C,\tilde{C})=\frac{|C\cap\tilde{C}|}{|C|}\).

**Quality Evaluation.** The average F1-scores of our CS-TGN and the baselines on datasets with the ground-truth community are presented in Figure 2. Our CS-TGN outperforms all baselines on all networks, with an average improvement of 12.6%. This can be attributed to two factors. Firstly, the flexible nature of community structures is not well-captured by approaches that rely on pre-defined subgraph patterns, such as Reliable, Truss, \(k\)-core, and FTCS, resulting in inaccuracies for communities lacking such patterns. Secondly, while other learning-based methods neglect the temporal and historical properties of datasets, our approach can learn the community structure from the data and employs GRU cells with an attention mechanism to capture both short-term and long-term patterns in the network, thereby utilizing all the structural, temporal, and historical properties of the data.

**Query Efficiency.** The efficiency of query processing for CS-TGN is evaluated in the test set. Figure 3 presents the average query processing time of all methods for test queries. Our approach, CS-TGN, demonstrates a query time that is comparable to that of QD-GNN and surpasses other baselines in terms of efficiency. Notably, this finding is achieved by our method while also exhibiting superior performance compared to the baselines in quality evaluation.

\begin{table}
\begin{tabular}{l|c c c c c} \hline \hline Dataset & _football_ & _brain_ & _email_ & _dblp_ & _youtube_ \\ \hline \hline \(|\mathcal{V}|\) & 114 & 190 & 1005 & 472K & 1.1M \\ \(|\mathcal{E}|\) & 613 & 720 & 25.5K & 1M & 2.9M \\ \# Snapshots & 5 & 4 & 6 & 8 & 4 \\ \# Communities & 12 & 15 & 42 & 5000 & 5000 \\ \hline \hline \end{tabular}
\end{table}
Table 1. Network Statistics
**Effect of Temporal Learning.** We conduct the following experiments to test our main hypothesis, that learning community structure over time is beneficial. First, we report the performance of the same architecture but without the GRU unit on the same networks and set of queries to quantify the quality difference and overhead caused by GRU units. Following that, we demonstrate how the number of snapshots affects the quality of results produced by the CS-TGN architecture.

Table 2 presents a comparative analysis of the performance of CS-TGN against two of its variants that share the same architecture, albeit without the GRU cells. The first variant, referred to as the GRU-less version, is no longer temporal and is trained on the last snapshot of the network. The second variant, denoted as SUM-CS-TGN, employs a simple summation method to update node embeddings over time instead of using the GRU cell. In order to ensure a fair comparison, all test queries and answers are based on the last snapshot. Our experimental results demonstrate that CS-TGN outperforms both of its variants on all datasets in terms of F1-score, suggesting that capturing the community structure over time is beneficial for achieving superior performance.

To investigate the impact of the number of snapshots on the performance of CS-TGN, we conduct experiments by varying the number of snapshots on different versions of the DBLP dataset. As shown in Figure 4, increasing the number of snapshots leads to a significant improvement in performance. This result demonstrates the effectiveness of the attention-based update mechanism and the architecture of CS-TGN.

**Effects of Hyperparameters.** We evaluate the effect of hyperparameters on the quality of our proposed model: **(1)**Number of neurons in the hidden layer (hidden dimension of GCN and GRU units) **(2)** threshold \(\eta\). We demonstrated the effect of these hyperparameters for three datasets- _email_, _youtube_, and _brain_-in Figure 4. Grid search techniques can be used to tune these hyperparameters according to the dataset. Based on these results, the optimal threshold value \(\eta\) is between 0.4 and 0.6, and the optimal hidden dimension is correlated with network size.

**Interactive Community Search on Brain Networks.** Detecting and monitoring functional systems in the human brain is an important and fundamental task in neuroscience (Beng et al., 2017; Wang et al., 2018). A brain network is represented as a graph, where nodes correspond to the brain regions and edges depict co-activation between regions. To identify the functional systems of each brain region, a community search method can be used. However, health-related domains are sensitive and require expert supervision. In this experiment, we apply two interactive community search methods on the _brain_ datasets while varying the size of the query vertex set. The results are presented in Table 3. Our proposed CS-TGN outperforms the ICS-GNN model at any stage and number of interactions, thereby highlighting its effectiveness for interactive community search.

## 6. Conclusion

In this paper, we propose a novel approach for community search in temporal networks called CS-TGN. Our approach is a query-driven temporal graph convolutional neural network that takes a data-driven approach to capture flexible community structures and incorporates dynamic temporal properties from ground-truth communities. To achieve this, CS-TGN employs two encoders to encode the local query-dependent structure and global query-independent graph structure. To capture both short-term and long-term patterns and update node embeddings over time, CS-TGN uses a contextual attention mechanism and GRU cells. Additionally, we show how CS-TGN can be used for interactive community search and formulate the problem as a meta-learning approach over temporal networks. We evaluate our model on several real-world datasets with ground-truth communities and demonstrated its superior performance compared to existing state-of-the-art methods in terms of accuracy and efficiency.

\begin{table}
\begin{tabular}{l|c c c} \hline \hline Dataset & CS-TGN & CS-TGN w/o GRU & SUM-CS-TGN \\ \hline \hline _brain_ & **0.51** & 0.39 & 0.44 \\ _football_ & **0.93** & 0.84 & 0.89 \\ _email_ & **0.63** & 0.50 & 0.51 \\ _youtube_ & **0.74** & 0.47 & 0.57 \\ _dblp_ & **0.94** & 0.66 & 0.83 \\ \hline \hline \end{tabular}
\end{table}
Table 2. The effect of GRU cells on F1-score

Figure 4. Effects of #Snapshots (DBLP dataset) and Hyperparameters on F1-score.

\begin{table}
\begin{tabular}{l|c c c c c c c c} \hline \hline \#interactions & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ \hline \hline CS-TGN & **0.33** & **0.35** & **0.39** & **0.41** & **0.38** & **0.47** & **0.55** & **0.56** \\ ICS-GNN & 0.24 & 0.27 & 0.29 & 0.35 & 0.31 & 0.36 & 0.4 & 0.42 \\ \hline \hline \end{tabular}
\end{table}
Table 3. Interactive community search on brain networks

Figure 3. Query Efficiency.

Figure 2. Quality evaluation.