Semi-supervised approaches to Community Detection (CD) in graphs aim to detect communities closely related to a few labeled ones. State-of-the-art semi-supervised algorithms adopt a three-step process, which entails (1) Generating candidate communities based solely on the network structure; (2) Selecting the candidates that are most similar to the labeled communities; (3) Refining the selected communities shortlisted at Step (2). However, existing approaches are unsuited to handle the dynamics in labeled communities and their relations with time-varying graph structures. In this work, we formulate the new task of semi-supervised CD from dynamic graphs, which is relevant to real-world time-evolving scenarios. To avoid executing the previous pipeline independently at every time step and potentially missing relevant temporal community-level relations, we envisage a new approach relying on time-aware strategies for both dynamic graph embedding and community selection and refinement. We leverage a latent graph representation incorporating nodeand subgraph-level temporal relations neglected by static approaches. Then, supervised community refinements are propagated across consecutive time steps to capture time-evolving trends. After adapting static CD models to the dynamic scenario, we conduct extensive comparisons of the methods on datasets with varying characteristics in the novel task of dynamic semi-supervised CD. The proposed approach shows remarkable improvements in low-modularity and low-stability dynamic graphs.
Communities in graphs are groups of nodes with distinctive
features or connections [
To deeply explore the network graph structure,
unsupervised approaches to CD have attempted to use a
variety of classical data mining or Deep Learning techniques
such as clustering [
Since real-world communities are naturally
timeevolving, there is an increasing need to extend existing CD
solutions suited to static graphs towards dynamic scenarios.
Recent approaches to CD capture time-evolving trends in
dynamic graphs by learning temporal graph embeddings.
They either learn temporal relations in sequences of graph
snapshots [
We first introduce the preliminary concepts and related notation and then formalize the newly proposed Semi-Supervised Dynamic Community Detection (SS-DCD) task.
Let G =( ,) be a graph where and are the
corresponding sets of nodes and edges, respectively. A
community c detected from G is a subset of the nodes with
peculiar characteristics in terms of either network graph
structure or node properties. Given a graph G , the
Unsupervised Community Detection (U-CD) task has the goal of
extracting the set C of all its communities without any
prior knowledge on the community properties, i.e., U-CD
exclusively relies on the network graph structure. When,
instead, the extraction process is guided by a given set C^
of labeled communities in G , the task is commonly
denoted by Supervised Community Detection (S-CD). The key
idea behind S-CD is to detect communities in graphs that
are closely related to the labeled ones by learning a model
that automatically captures similarities among subgraphs.
Importantly, S-CD is not necessarily based on the network
structure solely but might consider functional properties of
nodes or edges as well [
We aim to model the temporal variations of a graph structure and its underlying communities within a reference time period. Without loss of generality, we assume that the reference period is divided into discrete consecutive time steps (i.e., ∈ {1, 2, . . . , }).
Dynamic Community Detection (DCD) aims to detect all communities from sequences of graph snapshots = {G }=1. Unsupervised approaches to DCD extract communities from G for every ∈ {1, 2, . . . , } in the absence of labeled communities. Conversely, Supervised DCD (S-DCD) leverages the set C^ of labeled communities occurring in each time step . However, similar to the time-invariant case, the set of labeled communities is likely incomplete due to the lack of human annotations or reliable community descriptors. To tackle the above issue, we formalize the new task of Semi-Supervised Dynamic Community Detection (SS-DCD, in short). The twofold aims are, on the one hand, to make SS-CD time-aware by leveraging CD semisupervision and, on the other hand, to enrich Unsupervised DCD with a combined analysis of the properties of both the network structure and the labeled communities across diferent snapshots.
SS-DCD task formulation Given a sequence of graph snapshots and a partial set C^ of labeled communities occurring at every time step ∈ {1, 2, . . . , }, the SS-DCD task aims is to extract the sequence = {C }=1 of community sets C 1, . . . , C .
The classical SS-CD pipeline entails the following steps: 1. Candidate community generation, aimed to extract candidate communities based on the structure of the network graph. 2. Supervised candidate selection, which reduces the set of candidates generated at the previous step according to their similarity with the labeled communities. 3. Community refinement , aimed to revise the generated communities, e.g., by dropping or adding nodes or edges.
However, all the above-mentioned steps ignore the temporal evolution of both graph structure and communities which is peculiar to the newly proposed SS-DCD task.
Figure 1 shows how to naively use the classical SS-CD pipeline in an SS-DCD task. For the sake of simplicity, we exemplify the CD process across two consecutive time steps only, namely − 1 and . The temporal graph snapshots G − 1 and G are separately embedded to generate the candidate communities. Next, the candidate selection and reifnement processes are executed independently for every time step. This existing pipeline has two main drawbacks: • The process of generation of the candidate communities disregards the temporal relations among graph snapshots and related communities. Consequently, the next supervised candidate selection step could be biased. • The community refinement step is unaware of the outcomes of the supervised community detection and refinement steps. Hence, it potentially disregards all past (labeled or detected) community updates as well as the temporal relations with the surrounding network.
Let us consider, for example, the labeled community ˆ− 1 at time step − 1 consisting of nodes 1 and 3 (ˆ− 1 = {1, 3}). The path connecting 1 and 3 changes at time step by including also node 4. Knowing both the past community composition and the new network structure allows the CD algorithm to learn the temporal relation with its updated version ˆ = {1, 3, 4}. Analogously, the exclusion of node 2 from ˆ − 1 is a valuable hint for the definition of its updated version at time step .
To overcome the aforesaid limitations, we propose a new SS-DCD pipeline (see Figure 2). Compared to the standard pipeline, we incorporate the following two additional features making the SS-CD pipeline end-to-end time-aware.
independent embedding matrices for every snapshot in , we compute a time-aware embedding representation H of the previous graph snapshots G 1, . . ., G capturing time-varying properties of the network graph structure. The embedding representation is incrementally updated at each time step and, importantly, is directly fed to the supervised candidate selection step to allow time-aware semi-supervision (see the time-aware supervised candidate selection step in Figure 2).
The designed SS-DCD pipeline is agnostic to the encoder
used to compute the embedding matrix. For incremental
learning of node embeddings, our current implementation
leverages the ROLAND node embeddings [
Ct-1 Community refinement
Selected be the subset of G nodes belonging to the neighborhood of . We define the initial state of the RL as the union of the community with its neighborhood ( ∪ ). The state representation consists of the time-aware embeddings of the composing nodes, i.e., H∪
Similar to CLARE [
The ExpMLP network returns the probabilities of adding to a new node from the community neighborhood , whereas ReductMLP estimates the likelihood of removing any node from . To make the community refinement process time-aware, both networks are fed with the timeaware embeddings. The action probability distributions are defined as follows. (action=reduction of ) = softmax ReductMLP(H∪ ) (action=expansion of ) = softmax ExpMLP(H∪ )
The aforesaid probabilities distributions are propagated to the supervised community selection stage to initialize the CD process at the next time step (see the refinements’ feedforward propagation arrow in Figure 2).
In this section, we introduce the generator used to create dynamic graphs with time-evolving labeled communities and the datasets used in the experiments.
CD algorithms are commonly tested on both real-world
and synthetic data [
To bridge the gap, we extend a synthetic generator of
dynamic graphs [
networks with ground-truth communities retrieved from
SNAP [
Injection of network dynamics We extend the real
static graphs and ground-truth communities under two
different dynamic settings, i.e., low or high stability. In
compliance with [
dynamic graphs whose snapshots have diferent sizes, i.e., Syn_Const shows a roughly constant number of nodes per snapshot, in Syn_Growth the number of nodes per snapshot increases over time, whereas in Syn_Shrink shows an opposite trend.
All the experiments were conducted on a single NVIDIA Tesla V100 SXM2 GPU with 32 GB memory.
We evaluate SS-CD performance using the following three established metrics: F1 score, Jaccard score, and Overlapping Normalized Mutual Information (ONMI, in short). In all cases, we use a set of labelled test communities ˆ, with no intersection with the training ones ˆ. To cope with dynamic scenarios all the scores are averaged over all snapshots.
The F1 and Jaccard scores are metrics for comparing test
ground-truth and predicted communities in SS-CD [
As baseline methods, we consider the following four
state-ofthe-art DCD approaches extended to successfully cope with
dynamic graphs: DynGEM [
We test our approach by varying (1) The node
embedding strategy (we test Node2Vec [
For the baseline methods, we adapt the source code released by the papers’ authors. All the DCD baselines are trained for 50 epochs, whereas we train CLARE for 30 epochs to perform candidate generation and for 1000 epochs to perform community rewriting. We always use 16-dimension embeddings for DCD models and 64-dimension order embeddings for CLARE.
For all methods, we set the number of expected communities, whenever requested as input parameter, to the number of labeled communities in the training data.
To compute the statistics on the network graphs we use
the NetworkX library [
Table 2 reports the F1, Jaccard, ONMI Scores achieved by our approach and the baseline methods on the test communities. Among the tested baselines, CLARE performs averagely best on the analyzed datasets and settings confirming the beneifts of adopting the complete SS-CD pipeline. Our approach outperforms all the tested baselines, including CLARE, on the YouTube and the synthetic dynamic graphs, it performs best on email-Eu-core in four out of six dataset-metric combinations, whereas ranked second behind CLARE on the Amazon dataset. On average, it shows superior performance on graphs with low modularity (e.g., YouTube) and better suitability for fairly low-stability settings. The reason is that the time-aware approach provides clear benefits when graph snapshots and labeled communities are dynamic (i.e., low stability values) as long as the strength of the dynamics does not invalidate the relevance of the temporal graph relations. For instance, on the same dataset (email-Eu-core) the average F1 Score of our approach soars from 0.1931 to 0.3213 moving from a high-stability setting to a low-stability one. Conversely, on datasets like Amazon where the modularity is high, CD based on the analysis of the network structure is already quite efective. Therefore, the benefits achieved by semi-supervision turn out to be limited.
Figure 3 graphically shows the correlation between
average graph modularity and per-dataset F1-score gaps
between our approach and CLARE. The result confirms the
1We omit the comparisons with MARS [
email_1 0.2 0.3 0.4 0.8 0.9
1.0 0.5 0.6 0.7
Average Modularity negative correlation between modularity and usefulness of the time-aware community refinement step. A quantitative comparison in terms of Weighted F1- and Jaccard scores on low-modularity datasets confirms our previous findings (e.g., on YouTube our average Weighted F1-Score is 1.89 vs. 0.9 of CLARE). The achieved results indicate that the time-aware approach turns out to be particularly helpful when the community-level information conveyed by the network graph solely is not enough.
We carry out an ablation study to quantify the efect of the
choice of the node embedding strategy on dynamic graphs
characterized by variable modularity and stability levels. To
this end, we compare two alternative state-of-the-art
strategies for temporal graph embeddings, i.e., ROLAND [
The plots in Figure 4 show the F1-score gaps observed in our approach between the variants with ROLAND and CTGCN graph embeddings. They respectively show the separate influence of graph modularity (plot on the left) and stability (right) on the results of the ablation study. Thanks to the use of hierarchical node states, ROLAND embeddings turn out to be more efective than CTGCN in capturing dynamic graph and community relations. It has shown to be averagely more robust to graphs with low/medium modularity. On datasets with extremely high values of modularity or stability, CTGCN outperforms ROLAND. However, as discussed in Section 5.4, in those extreme cases adopting time-aware approaches to tackle the SS-DCD task is less appealing.
In this paper, we formulated a new Community Detection task combining Semi-Supervision and dynamic graphs. We extend the existing pipeline for SS-CD by leveraging temporal graph embeddings to capture temporal dynamics in the candidate community generation, selection, and refinement stages. We also propagate the outcomes of two policy networks used in the refinement stage across the subsequent time steps, thus making the supervision aware of the 0.5 0.6 0.7
Average Modularity temporal relations of communities with the past, partially labeled, graph snapshots. The main takeaways from the empirical analysis are: (i) the efectiveness of the proposed pipeline on low-modularity graphs and low-stability graphs, (ii) the importance of the community refinement stage as in the classical SS-CD task, and (iii) the little influence of the number of nodes on computational time of the community refinement stage, suggesting to optimize the cost of graph embedding to eficiently adopt time-aware strategies in large networks.
Our future research agenda will encompass: (i) the extension to network graphs with node attributes, which might also change over time, (ii) the study of scalable approaches to SS-DCD in the steps of graph embedding, candidate community generation, but also the community refinement stage, and (iii), and the adoption of Contrastive Learning architectures to generate input embeddings (replacing Graph Neural Networks), thus limiting the complexity and need for large sets of annotations.
This work has been partially supported by the Spoke 1 "FutureHPC & BigData" of ICSC - Centro Nazionale di Ricerca in High-Performance-Computing, Big Data and Quantum Computing, funded by European Union - NextGenerationEU.