# MGTCOM: Community Detection in Multimodal Graphs

Egor Dmitriev<EMAIL_ADDRESS>Utrecht UniversityUtrechtThe
Netherlands ,  Mel Chekol<EMAIL_ADDRESS>Utrecht UniversityUtrechtThe
Netherlands and  Shihan Wang<EMAIL_ADDRESS>Utrecht UniversityUtrechtThe
Netherlands

###### Abstract.

Community detection is the task of discovering groups of nodes sharing similar
patterns within a network. With recent advancements in deep learning, methods
utilizing graph representation learning and deep clustering have shown great
results in community detection. However, these methods often rely on the
topology of networks (i) ignoring important features such as network
heterogeneity, temporality, multimodality and other possibly relevant
features. Besides, (ii) the number of communities is not known a priori and is
often left to model selection. In addition, (iii) in multimodal networks all
nodes are assumed to be symmetrical in their features; while true for
homogeneous networks, most of the real-world networks are heterogeneous where
feature availability often varies. In this paper, we propose a novel framework
(named MGTCOM) that overcomes the above challenges (i)–(iii). MGTCOM
identifies communities through multimodal feature learning by leveraging a new
sampling technique for unsupervised learning of temporal embeddings.
Importantly, MGTCOM is an end-to-end framework optimizing network embeddings,
communities, and the number of communities in tandem. In order to assess its
performance, we carried out an extensive evaluation on a number of multimodal
networks. We found out that our method is competitive against state-of-the-art
and performs well in inductive inference.

##  1\. Introduction

Various systems can be modelled as complex networks such as social (Hagen et
al., 2018), citation (Sen et al., 2008), biological (Gosak et al., 2018) and
transaction (Pryke, 2004) networks. The task of identifying patterns of nodes
with common properties, in such networks, is known as community detection.
There is an abundant number of community detection methods in literature that
approach this problem through modularity optimization (Schuetz and Caflisch,
2008), clique identification (Kumpula et al., 2008), and spectral optimization
(He et al., 2011). With recent advancements in graph representation learning a
new type of methods have emerged which utilize context-based learning
techniques (e.g., DeepWalk (Perozzi et al., 2014) or Node2Vec (Grover and
Leskovec, 2016)) to obtain topology-aware node embeddings. These embeddings
are either combined with existing clustering methods (Xue et al., 2019) or are
jointly optimized with found clusters (Jia et al., 2019) to obtain
communities.

In the above studies, the multimodal characteristics of real-world networks
are overlooked. These characteristics can manifest as meta-topological
features (node and relation types) (Cao et al., 2021), temporal features, and
contentual features (e.g., text and image attributes). Introduction of
multimodality contrasts homophily assumed by previous methods as heterophily
and can play an essential role in detecting communities in multimodal
networks, as connected nodes may belong to different communities when multiple
feature types are considered (Zhu et al., 2020). While it is common for causal
links to be present between these features, it cannot be assumed without
extensive domain knowledge. Various algorithms have been devised to address
the issue of temporality and multimodality (Luo et al., 2021; Li et al., 2018;
Fani et al., 2020), though as far as we are aware none of the methods are able
to address the lossless setting where all the features are incorporated.

Another challenge is information variance present in heterogeneous real-world
networks. Different node or relation types may have different feature subsets
and/or dimensionality. For instance, consider the Twitter dataset (SDS) we use
in our experiments. This network consists of users, tweets, hashtags, and
various relations. Tweets have content as textual features and post dates as
temporal features, while users only have biography as textual features, and
hashtags have neither. Similarly, users can form a directed follower relation
link, while multiple relations may be present between tweets such as retweet,
mention or quote. This shows that real-world networks can be incomplete and
the goal is to devise a model that works under such circumstances.

Overall, we would like to address some of the open problems in community
detection (as pointed out in (Su et al., 2021)). In particular, detecting
communities when: networks are multimodal, some nodes have incomplete features
(incompleteness constraints), the number of communities is not known a priori,
and learning node embeddings as well as finding communities in an end-to-end
manner. Hence, we propose a novel community detection framework (MGTCOM) that
is able to address these problems. MGTCOM discovers communities through
multimodal feature learning and unsupervised learning with a new temporal
sampling technique. In particular, our key contributions include:

  * (i)

A robust method for unsupervised inductive representation learning on
multimodal networks.

  * (ii)

A new sampling technique, namely ballroom walk, for unsupervised learning of
temporal embeddings.

  * (iii)

An end-to-end framework optimizing network embeddings, communities, and number
of communities in tandem.

  * (iv)

Extensive evaluation on the quality of various features in multimodal
networks.

  * (v)

We compare MGTCOM with state-of-the-art methods and demonstrate its robustness
on inference tasks.

##  2\. Related Work

A comparison of MGTCOM with the state-of-the-art is given in Table 1. These
methods are chosen based on their popularity within the literature, recency
and relevance to our task. From these methods we select several comparable
ones as the baseline in our experiments. As can be seen, MGTCOM is able to
generate: (i) node, (ii) meta-topology, (iii) content, and (iv) temporal
embeddings as well as (v) is able to infer the number of communities $(K)$. By
contrast, state-of-the-art methods (such as GraphSAGE and ComE) are able to
produce either two or three of the above. A commonality of all the methods is
that they all utilize topological features. Similarly, we focus on
representation based community detection methods in contrast to traditional
link-based methods. We provide a brief introduction of these methods below. We
refer the reader to the survey (Su et al., 2021) for a detailed discussion.
Throughout the paper we will use the terms network and graph interchangeably.

Table 1.  A comparison of MGTCOM with state-of-the-art.

|  topology |  meta-topology |  content |  temporal |  infers $K$
---|---|---|---|---|---
GraphSAGE (Hamilton et al., 2017) |  $\bullet$ |  |  $\bullet$ |  |
SageDy (Wu et al., 2021) |  $\bullet$ |  |  $\bullet$ |  $\bullet$ |
CTDNE (Nguyen et al., 2018) |  $\bullet$ |  |  |  $\bullet$ |
Metapath2Vec (Dong et al., 2017) |  $\bullet$ |  $\bullet$ |  |  |
HGT (Hu et al., 2020) |  $\bullet$ |  $\bullet$ |  $\bullet$ |  |
ComE (Cavallari et al., 2017) |  $\bullet$ |  |  |  |
GEMSEC (Rozemberczki et al., 2019) |  $\bullet$ |  |  |  |
GRACE (Yang et al., 2017) |  $\bullet$ |  |  $\bullet$ |  |
Fani et al. (Fani et al., 2020) |  $\bullet$ |  |  $\bullet$ |  $\bullet$ |
CP-GNN (Luo et al., 2021) |  $\bullet$ |  $\bullet$ |  |  |
MGTCOM |  $\bullet$ |  $\bullet$ |  $\bullet$ |  $\bullet$ |  $\bullet$

Graph Embedding. Graph representation learning approaches such as DeepWalk and
Node2Vec utilize random walks as a means to generate context and adopt the
Skip-gram (Mikolov et al., 2013) model to directly learn the node embeddings
methods. By defining a trade-off between first- and higher-order proximity
they provide a way to fine-tune the learned topological representations for
the task at hand. Depth-first search sampling strategies (higher-order
proximity) encourage network communities while breadth-first search (first-
order proximity) encourages structural similarity as the local neighborhood is
more thoroughly explored (Grover and Leskovec, 2016).

The above methods mainly work on homogeneous networks in which all nodes and
edges belong to the same types. Heterogeneous networks contain meta-
topological information that characterizes various relationships between
different types of nodes/entities. One way to address meta-topological
features is by using meta-path constrained random walks to capture semantic
and structural relations between different node/entity types. An example of
such a model is Metapath2Vec (Dong et al., 2017). Meta-path describes a
sequence of entity and relation types. Other methods utilize a representation-
based approach (Bordes et al., 2013) to explicitly capture meta-topological
features by defining relations as translations between different node types.
This approach is further utilized in graph convolutional networks (GCN)-based
methods, such as GraphSAGE (Hamilton et al., 2017) and HGT (Hu et al., 2020),
to apply them in an inductive setting. Furthermore, HGT improves the
neighborhood sampling algorithm by introducing a type-based budget for
unbiased sampling.

Temporal graph embedding approaches are mainly split into two categories.
Snapshot-based approaches operate by temporally splitting the graph into
multiple snapshots or subgraphs and applying (modifying) existing graph
embedding methods by temporally smoothing between the snapshots (Pareja et
al., 2020). The second category are the continuous temporal representation
approaches which attempt to capture temporal information within the learned
embeddings. Generally, these methods look at the temporal progression of
individual nodes rather than utilizing predefined snapshots. The techniques
vary; for instance CTDNE introduces biased temporal random walks (Nguyen et
al., 2018); and SageDy introduces a neighborhood sampling technique to filter
for temporal neighborhood (Wu et al., 2021).

Community Detection. There is an abundance of work concerning the finding of
community structures by relying mainly on topological features (Fortunato,
2010). Recent community detection methods focus on exploiting feature-rich
information found in multimodal networks (Su et al., 2021). The focus has
shifted from link-based methods towards deep learning methods which combine
graph embedding methods with clustering algorithms (such as k-means or
spectral clustering) (Tian et al., 2014; Kozdoba and Mannor, 2015). For
instance, ComE (Cavallari et al., 2017) uses a Gaussian mixture model to learn
homogeneous graph embeddings and cluster parameters jointly while utilizing
random walk based context sampling. GEMSEC (Rozemberczki et al., 2019) uses
random walks to learn community structure and embeddings simultaneously on
homogeneous graphs. With the emergence of multimodal community detection
methods heterophily is important as similarity may not always be correlated
with topological features (homophily) (Zhu et al., 2020). In line with this,
various methods (Liu et al., 2014; Sun et al., 2012) modify the Latent
Dirichlet Allocation algorithm to incorporate attribute, topological and meta-
topological information. Cao et al. (Cao et al., 2018) and Yang et al. (Yang
et al., 2017) utilize autoencoders to jointly optimize graph embeddings on
content and topological information. Fani et al. (Fani et al., 2020) use topic
models to construct a user interest histogram over a time axis, which in turn
is used to learn temporal content-based node representations. These
representations are interpolated with topological representations, the
similarity along edges is computed, and fed as edge weight to the existing
link-based community detection algorithm (namely Louvain (Blondel et al.,
2008)). Meta-topological information can be used in various ways to assist in
community detection, for instance, Luo et al. (Luo et al., 2021) propose CP-
GNN which combines a heterogeneous graph transformer architecture with k-means
clustering to find communities in heterogeneous graphs.

Clustering. Bayesian non-parametric methods such as Dirichlet Process Mixture
(DPM) have had great results in clustering (Min et al., 2018) and community
detection tasks where the number of communities is unknown (Tonellato, 2020).
As these models can evaluate the likelihood of a set of cluster parameters
being drawn from a prior distribution, the task is transformed into a Markov
Chain Monte Carlo sampling problem. Since there are prohibitively many
possible parameter states, various hierarchical algorithms are proposed to
explore the most promising states efficiently (Chang and Fisher III, 2013).
Because these methods can be estimated using Expectation-Maximization (EM)
algorithms, the previously introduced embedding methods can be utilized to
learn representations and clusters in an end-to-end manner (Cavallari et al.,
2017; Ronen et al., 2022). MGTCOM takes advantage of this.

##  3\. Preliminaries

Figure 1. Overview of the MGTCOM framework.

###### Definition 3.1 (Heterogeneous graph).

A heterogeneous graph, denoted by
$G=(\mathcal{V},\mathcal{E},\mathcal{A},\mathcal{R})$, consists of a set of
nodes $\mathcal{V}$, a set of edges $\mathcal{E}$, and their associated type
mapping functions $\phi:\mathcal{V}\rightarrow\mathcal{A}$ and
$\psi:\mathcal{E}\rightarrow\mathcal{R}$. $\phi$ (resp. $\psi$) maps a node
(resp. edge) to its type. $\mathcal{A}$ and $\mathcal{R}$ denote sets of node
and edge types, respectively, where $|\mathcal{A}|>1$ and $|\mathcal{R}|>1$.
$G$ is a homogeneous if $|\mathcal{A}|=1$ and $|\mathcal{R}|=1$.

We define a multimodal information network by combining the notion of
heterogeneous, continuous-time, and contentual networks.

###### Definition 3.2 (Multimodal graph).

A multimodal graph is defined as
$G=(\mathcal{V},\mathcal{E},\mathcal{A},\mathcal{R},\mathcal{T},\mathcal{X})$
where $\mathcal{T}$ is a set of timestamps $t$ and $\mathcal{X}$ is a set of
type specific feature matrices $\mathcal{X}_{\phi(\cdot)}$. A feature matrix
is created by extracting and stacking feature vectors for each node given pre-
trained dense representations of their image, text, or categorical attributes.
Each node $v\in\mathcal{V}$ (resp. edge $e\in\mathcal{E}$) has a time range
$\tau(v)=[t_{s},t_{e}]$ (resp. $\tau(e)=[t_{s},t_{e}]$), indicating the time
period on which it is considered valid, where $t_{s},t_{e}\in\mathcal{T}$.
Moreover, each node $v$ has an attribute vector
$\mathbf{x}\in\mathcal{X}_{\phi(v)}$.

###### Definition 3.3 (Incompleteness constraints).

Real-world multimodal networks can be noisy, incomplete, and may change over
time. In order to represent this information we introduce additional indicator
functions to denote whether a node has a time interval
$\mathbf{1}_{\mathcal{T}}:\mathcal{V}\rightarrow\\{0,1\\}$, has a feature
vector $\mathbf{1}_{\mathcal{X}}:\mathcal{V}\rightarrow\\{0,1\\}$, or is
unseen during training
$\mathbf{1}_{\mathcal{V}}:\mathcal{V}\rightarrow\\{0,1\\}$. We refer to the
noisiness, incompleteness, and temporality as incompleteness constraints.

###### Definition 3.4 (Context window).

A context window connects nodes based on some predefined criteria. Two nodes
are context neighbors if they occur in the same context window. We use two
different kinds of context windows. The first is the topological context
window. It connects two nodes $v_{i}$ and $v_{j}$ if there exists a h-hop path
${p}^{\mathcal{E}}_{k}$ in graph $G$ through which they are connected. The
second is temporal context window ${p}^{\mathcal{T}}_{\omega}$. It connects
$v_{i}$ and $v_{j}$ if they occur within a given time window
$\omega=[t_{s},t_{e}]$. Going forward we use ${P}^{\mathcal{E}}_{k}$ and
${P}^{\mathcal{T}}_{\omega}$ to denote a fixed size sample of all possible
context windows. We use contexts for learning task based node embeddings.

###### Definition 3.5 (Heterogeneous Graph Transformer).

Classical GCNs focus mainly on homogeneous graphs (Hamilton et al., 2017). For
heterogeneous graphs, Heterogeneous Graph Transformer (HGT) (Hu et al., 2020)
adopts the transformer architecture (Vaswani et al., 2017) by calculating
mutual attention based on representation and meta-types of source nodes,
target nodes and relation information. We utilize HGT to generate the primary
embedding of a multimodal graph (Section 4.1).

Problem formulation. Given a multimodal graph $G$, our goal is to learn a node
embedding function $\zeta:G_{v}\rightarrow\mathbb{R}^{d}$ which given a
$h$-hop neighborhood subgraph $G_{v}$ of node $v$ produces a $d$-dimensional
embedding vector $Z_{v}$. The objective is to minimize the distance between
embedding $Z_{v}$ to other node embeddings, given that they are topological
and/or temporal context neighbors of node $v$. Taking into account
incompleteness constraints (3.3), $\zeta$ should work under any valuation of
$(\mathbf{1}_{\mathcal{X}(v)},\mathbf{1}_{\mathcal{T}(v)},\mathbf{1}_{\mathcal{V}(v)})$.
We also aim to find community parameters
$\mathbf{\theta}=\\{\mathcal{N}(\mu_{1},\Sigma_{1}),...,\mathcal{N}(\mu_{K},\Sigma_{K})\\}$
and node-to-community assignment
$\mathbf{z}\in\\{0,\ldots,K\\}^{|\mathcal{V}|}$ such that their members have a
low inter-proximity in contrast to other nodes. Finally, the found community
count $K$ should approximate the ground truth number of communities.

##  4\. The Proposed Approach

We present our framework for Community Detection in Multimodal Graphs (MGTCOM)
that learns multimodal representation vectors for graph nodes and detects
communities in tandem. We achieve this by leveraging heterogeneous graph
transformers (Hu et al., 2020) to learn a primary node embedding function
$\zeta$. In order to handle the incompleteness constraints, we introduce an
auxiliary embedding vector $\mathbf{E}$ for known (or seen) nodes with missing
features. Next, we learn task-specific node representation for topological and
temporal information by combining primary embeddings with task-specific
transformation/attention and context sampling. As we utilize random walks for
topological context sampling, we introduce its analogue as an unbiased
temporal window sampling algorithm for temporal context collection. Finally,
we adopt DPMM (Dirichlet process mixture model) for community detection and
close the loop by introducing cluster-based loss to ensure the graph
embeddings are community-aware. The architecture of MGTCOM is given in Fig. 1.
In the embedding step primary embeddings are used in auxiliary tasks to
construct the multi-objective loss (Fig. 1(a)). (b) The clustering step
updates clustering by alternating between Expectation (E), Maximization (M),
and Proposal (P) steps. (c) In the topological (topo) embedding task, random
walk sampling and feature-wise attention minimize inter-node proximity. (d) In
the temporal (tempo) embedding task, ballroom walk sampling and feature-wise
attention minimize proximity between temporally related nodes. (e) Clustering
task adds community awareness to the embeddings by minimizing proximity
between nodes within the same cluster.

###  4.1. Primary embedding module

The central component of our framework is responsible for inferring the
primary representation vector $Z_{v}$ given a node $v\in\mathcal{V}$ in a
graph $G$. The basic idea is to learn node representation from its h-hop
heterogeneous neighborhood subgraph $G_{v}$ while handling edge cases
introduced by the incompleteness constraints (3.3). The learning starts by
sampling a subgraph $G_{\mathcal{B}}$ given a batch of central nodes
$\mathcal{B}$ using the budget sampling algorithm (Hu et al., 2020). The
budget sampling algorithm works by restricting sampled subgraph at each layer
given a per node type limit. In our case, we define this limit as multiple
$|\mathcal{B}|$ to avoid re-tuning its value for each dataset.

####  4.1.1. Incompleteness constraints

Once the graph is sampled we split the task of initial feature inference into
three cases to handle the incompleteness constraints (Eq. 1). (i) If a feature
vector ($\mathbf{x}_{v}$) is present, then it is linearly projected into the
representation space. (ii) If the node $v$ is in the training set while no
feature vector is present, then its representation is drawn from the auxiliary
embedding matrix $\operatorname{E}$. To avoid over reliance on the embeddings
in preference for feature vectors we apply dropout on the resulting
representation. (iii) Finally, if an unseen node without a feature vector is
encountered, the zero vector (denoted as $0_{d}$) is used, indicating that its
feature vector has zero weight during the aggregation step of the graph
convolution. Note that for large datasets, it may not be feasible to keep a
full auxiliary embedding matrix in memory.

(1) $\displaystyle H_{v}^{(0)}$
$\displaystyle=\begin{cases}\operatorname{Linear}(\mathbf{x_{v}})&\mathbf{1}_{\mathcal{X}}(v)=1\\\
\operatorname{Dropout}(\mathbf{E}_{s})&\mathbf{1}_{\mathcal{V}}(v)=1\\\
0_{d}&\text{otherwise}\end{cases}$ (2) $\displaystyle H^{(l)}$
$\displaystyle=\operatorname{GeLU}(\operatorname{HGT}(G_{\mathcal{B}},H^{(l-1)}))$

Next, given the subgraph $G_{\mathcal{B}}$ and the initial representation
vector $H^{(0)}$, $L$ layers of HGT graph convolutions are applied (Eq. 2).
Each layer uses the representation vector of the previous layer and feeds its
output through a $\operatorname{GeLU}$ (Hendrycks and Gimpel, 2020) activation
function (chosen based on our experiments in which it outperforms other
activation functions such as ReLU). Finally, the output vectors at the
$L^{\mathit{th}}$ layer are used as primary embeddings for each node in the
batch $Z_{\mathcal{B}}$.

Algorithm 1 provides a full overview of the primary embedding algorithm. The
basic idea is to learn node representation from its k-hop heterogeneous
neighborhood subgraph $G_{v}$ while handling edge cases introduced by the
incompleteness constraints (3.3). The learning starts by sampling a subgraph
$G_{\mathcal{B}}$ given a batch of central nodes using the budget sampling
algorithm on Algorithm 1. The budget sampling algorithm works by restricting
sampled subgraph at each layer given a per-node type limit. For our use case,
we define this limit as multiple $|\mathcal{B}|$ to avoid re-tuning its value
for each dataset.

Once the graph is sampled we split the task of initial feature inference into
three cases to handle the incompleteness constraints. (i) If a feature vector
is present, then it is simply projected into the representation space. (ii) If
the node is in the training set while no feature vector is present, then its
representation is drawn from the auxiliary embedding matrix $\mathbf{E}$. To
avoid overreliance on the embeddings in preference for feature vectors we
apply dropout on the resulting representation. (iii) Finally, if an unseen
node without a feature vector is encountered, the zero vector (denoted as
$0_{d}$) is used, indicating that its feature vector has zero weight during
the aggregation step of the graph convolution.

1

2 Procedure  _EmbedPrimary(__)_

Input: multimodal graph
$G=(\mathcal{V},\mathcal{E},\mathcal{A},\mathcal{R},\mathcal{X})$, mini-batch
$\mathcal{B}\subseteq\mathcal{V}$, auxiliary node embedding
$\mathbf{E}\in\mathbb{R}^{N_{\bar{\mathcal{X}}}\times d}$ where
$N_{\bar{\mathcal{X}}}=|\\{v|v\in\mathcal{V},\mathbf{1}_{\mathcal{X}}(v)=0\\}|$,
number of convolutional layers $L$

Output: The primary embedding $Z_{\mathcal{B}}$ for nodes in batch
$\mathcal{B}$

3
$G_{\mathcal{B}}(\mathcal{V}_{\mathcal{B}},\mathcal{E}_{\mathcal{B}},\mathcal{A}_{\mathcal{B}},\mathcal{R}_{\mathcal{B}},\mathcal{X}_{\mathcal{B}})\leftarrow\operatorname{HeteroSample}(G,\mathcal{B},L)$;

4 for  _$s\in\mathcal{V}_{\mathcal{B}}$_ do

5
$H_{s}^{(0)}=\begin{cases}\operatorname{Linear}(\mathbf{x_{s}})&\mathbf{1}_{\mathcal{X}}(s)=1\\\
\operatorname{Dropout}(\mathbf{E}_{s})&\mathbf{1}_{\mathcal{V}}(s)=1\\\
0_{d}&\text{otherwise}\end{cases}$;

6

7 end for

8 for  _$l=1$ to $L$_ do

9
$H^{(l)}=\operatorname{GeLU}(\operatorname{HeteroConv}(G_{\mathcal{B}},H^{(l-1)}))$;

10

11 end for

12 $Z_{\mathcal{B}}=\\{H^{(L)}_{t}|t\in\mathcal{B}\\}$;

13 return _$Z_{\mathcal{B}}$_

14

Algorithm 1 Batchwise primary node embedding

On Algorithm 1, given the subgraph $G_{\mathcal{B}}$ and the initial
representation vector $H^{(0)}$, $L$ layers of HGT graph convolutions are
applied. Each layer uses the representation vector of the previous layer and
feeds its output through a $\operatorname{GeLU}$ (Hendrycks and Gimpel, 2020)
activation function. Finally, the output vectors at the $L^{\mathit{th}}$
layer are used as primary representation vectors and output for each query
node in the batch on Algorithm 1.

###  4.2. Multi-task representation learning

During task-specific learning we focus on two main tasks capturing the
intricacies of multimodal networks. The topological task denoted by
$\mathcal{L}^{\mathcal{E}}$ focuses on minimizing the representation distance
between nodes that are proximate within the network (Fig. 1(b)). Analogously,
the temporal task $\mathcal{L}^{\mathcal{T}}$ focuses on minimizing the
distance between nodes that co-occur at the same time range (Fig. 1(b)). While
fundamentally different since the tasks are trained in parallel, they benefit
from weight sharing and from node sharing during primary embedding as the
subgraph batches are centered around the same nodes.

####  4.2.1. Task-based attention

An important observation is that while temporal and topological communities
are both important during analysis, they are not always correlated. In most of
the benchmarking datasets such as DBLP temporal features and topology show low
correlation. However, it is very rare that contentual features are completely
independent of topology and temporality. Given this observation, we admit that
it may not be possible to train a model that excels at both tasks. To work
around this issue while still capturing both tasks in a single embedding
vector we introduce task-based attention. The basic idea is that while primary
embedding extracts suitable features from the multimodal network, task-
specific attention selects the most relevant of these features for the task at
hand. Inspired by transformers (Vaswani et al., 2017) we define multi-head
attention $\operatorname{\textit{att}}^{task}$ to capture various feature
patterns Eq. 4. The task-based transformation function is defined as Eq. 3
where the primary representation vector is attended to using matrix
multiplication. We specialize this function for topological task as
$f^{\mathcal{E}}(\mathbf{Z})$ producing $\mathbf{Z}^{\mathcal{E}}$ and
temporal task $f^{\mathcal{T}}(\mathbf{Z})$ producing
$\mathbf{Z}^{\mathcal{T}}$.

(3) $\displaystyle f^{task}(\mathbf{Z})$
$\displaystyle=\mathbf{Z}\cdot\operatorname{\textit{att}}^{task}(\mathbf{Z})$
(4) $\displaystyle\operatorname{\textit{att}}^{task}(\mathbf{Z})$
$\displaystyle=\underset{i\in[1..h]}{\|}\sigma\left[\operatorname{Linear}_{i}^{task}(\mathbf{Z})\right]$

where $\|$ denotes concatenation operation, $h$ is the number of attention
heads, and $\sigma$ denotes nonlinearity (sigmoid function).

####  4.2.2. Objective function

In order to learn model parameters in an unsupervised way, we define
contrastive loss. Task-specific positive context sample $P$ and a negative
context sample $\bar{P}$, both sharing a central query node $q$ are used to
construct positive $(q,p)$ and negative $(q,n)$ node pairs respectively. We
define an objective function based on max-margin (Hinge loss) (Eq. 5) which
aims to maximize the inner product similarity between the query and positive
examples. On the other hand, the inner product of query and negative samples
is minimized to be smaller than that of the positive samples by some
predefined value of $\Delta$ (we performed hyperparameter analysis to find the
best). To smoothen out the noise caused by context sampling, we average
similarity over negative samples within the max loop (Eq. 6).

(5) $\displaystyle\operatorname{MM-Loss}(\mathbf{Z},P,\bar{P},q)$
$\displaystyle=\max_{n\in\bar{P}}\left\\{0,\mathbf{Z}_{q}\mathbf{Z}_{n}-\widetilde{\mathbf{Z}_{q}\mathbf{Z}_{p}}+\Delta\right\\}$
(6) $\displaystyle\widetilde{\mathbf{Z}_{q}\mathbf{Z}_{p}}$
$\displaystyle=\frac{1}{|P|}\sum_{p\in{P}}\left(\mathbf{Z}_{q}\mathbf{Z}_{p}\right)$

Figure 2.  Visual overview of the Ballroom Walk temporal sampling algorithm.

1

2 Algorithm  _BallroomWalk(__)_

Input: multimodal graph
$G=(\mathcal{V},\mathcal{E},\mathcal{A},\mathcal{R},\mathcal{X})$, relative
temporal window $\omega$, walks per node $n$, walk length $l$, center node
$v$,

Output: Temporal $n$ random walks $P_{l}$

3 Initialize $C$;

4 $t_{v}=\begin{cases}t_{v}\sim\tau(v)&\mathbf{1}_{\mathcal{T}}(v)=1\\\
\textnormal{{TemporalRW(}}\textnormal{\emph{$v$,
$(-\infty,\infty)$}}\textnormal{{)}}&\text{otherwise}\end{cases}$;

5 $N(v)=\\{u|u\in\mathcal{V},\tau(u)\cap\omega+t_{v}\neq\emptyset\\}$;

6 for  _$i=1$ to $n$_ do

7 $m\sim\mathcal{N}$;

8 $C=C\cup\textnormal{{TemporalRW(}}\textnormal{\emph{$m$,
$\omega+v_{t}$}}\textnormal{{)}}$;

9

10 end for

11 RandomPermute($C$);

12

13 for  _$i=1$ to $n$_ do

14 $P_{l}=\\{C_{j}|i\cdot l\leq j<i\cdot l+l\\}$;

15 return $P_{l}$;

16

17 end for

18

19

20

Algorithm 2 Ballroom walk sampling

Topological context window sampler. The objective of task-specific learning is
mainly defined by the context (window) sampling method. As our method allows
for inference of primary and task-specific representations for unseen nodes,
we assume that topological, meta-topological and contentual features contain
enough information or are correlated with the objectives of the tasks. To
gather the topological context $P^{\mathcal{E}}$, Node2Vec biased random-walk
algorithm is utilized (Grover and Leskovec, 2016). By choosing a low value for
its control parameter $q$ we discourage structural/topological equivalence
representation in favor of larger neighborhood exploration (depth-first
strategy) which is useful for community representation. In our framework, the
query nodes and negative contexts are shared across both tasks. In order to
collect temporal context $P^{\mathcal{T}}$ of size $l$, we introduce ballroom
walk sampling below.

####  4.2.3. Two temporal context samplers

Temporal features are often not correlated with network topology. We propose a
separate context sampling method that, given a query node and an interval
window $\omega$, returns other nodes occurring within the same time window.
$\omega$ is determined by using the dataset statistics as a fraction of the
complete time range $\mathcal{T}$. By picking a small enough interval window,
a fine-grained continuous-time representation vector can be learned. This is
because additional granularity is achieved by centering the sample around the
query node. Edge cases arising from the incompleteness constraints need to be
handled where the nodes are missing timestamps $\mathbf{1}_{\mathcal{T}}=1$.
While the usual semantic approach is to consider these nodes omnipresent
(static), the naive window sampling methods quickly get congested with static
to static context pairs. Our aim is to alleviate this issue using biased
sampling in favor of non-static pairs.

Temporal random walk context sampler. We start by introducing the temporal
random walk procedure which enforces standard random walks over the network to
stay within a predetermined time window $\omega$. Here random walk of size $l$
is constructed by picking a randomly connected node to the current head node
within a window. If no such node is present, then the random walk is restarted
from any already picked node. The walk is extended with a new head node until
it reaches the desired length.

Ballroom walk context sampling. Since temporal random walk looks naively for
only adjacent temporal neighbors, we propose a more complex sampling method
called ballroom walk that searches for temporal neighbors which may not
necessarily be connected. The outline of the proposed method is shown in
Algorithm 2. It starts by inferring the sampling timestamp $t_{v}$ picking a
random timestamp in which the center/query node $v$ occurs in. If the node is
static, the timestamp of its nearest neighbor reachable through temporal
random walk ($\operatorname{TemporalRW()}$) is selected (Algorithm 2). In
order to reliably sample the temporal neighborhood, $n$ root nodes are picked
occurring in the time-window relative to the sampling timestamp (Algorithm 2).
Temporal context $C$ is constructed by collecting temporal random walks
starting from root nodes $m$ given a relative time window $\omega+t_{v}$
(Algorithm 2). Finally, $l$ long context paths are created as random subsets
of $C$. Note that because a sampled context is valid for all member nodes,
random walk-like throughput optimization can be used by setting a larger
window length than context size (Perozzi et al., 2014). An example of ballroom
walk sampling is given in Fig. 2. In Fig. 2(a) the sampling timestamp $t_{v}$
for query node $v$ is inferred given the nearest neighbor if the node is
static (blue). The relative time window is determined as $\omega+t_{v}$. (b)
The root context nodes are sampled from the relative time window (red). (c)
Context is extended with temporal random walks from the root nodes (yellow).
(d) The context path is sampled from the collected context (green).

Due to timestamp inference, the first- and second-order proximity static to
static pairs are ignored. By only passively sampling omnipresent nodes we
mitigate the over-saturation issue while still being fair. Most importantly
the neighborhood of central nodes is being sampled independently of their
topology. By sampling within a temporal window, we avoid not relying on the
correlation of temporality with topology.

###  4.3. Community detection with unknown $K$

For community detection, we adopt the DPMM split/merge algorithm proposed by
Chang and Fisher III (Chang and Fisher III, 2013). In our implementation, we
use Normal Wishart (NW) as a conjugate prior and use variational lower bound
in our convergence criteria. Specifically, we monitor the log sum of the
variational lower bound for the supercluster and subcluster models. The
variational lower bound is computed as the product of variational distribution
$q(\mathbf{z})$, the normalizing constant of the Dirichlet distribution
$B(\alpha_{0})$, and the normalizing constant of the Normal Wishart
distribution $C(W,\nu)$. Once its monitored value starts oscillating, then the
model has converged and is moved into the proposal state. If the model
parameters remain unchanged during the proposal stage (no split or merge is
accepted), then the clustering is complete. The only parameters relevant for
our clustering method are the prior hyperparameters. Most of the other
parameters (i.e. $\alpha$, $\kappa$, and $\nu$) are not very relevant if they
are much smaller than the sample count. We use the $\Sigma_{scale}$ parameter
to scale the dataset covariance for more effective control over the strength
of the data-bound prior parameters $\mu_{0}$ and $\Sigma_{0}$. To fit the
clustering model we use primary embedding to calculate assignment and
posterior parameters as it contains features relevant for both temporal and
topological tasks. It is worth noting that it is not necessary to have all the
embeddings in memory as exact posterior parameters depend on data $\mu$ and
$\Sigma$ which can be calculated over multiple batches.

###  4.4. End-to-end framework

Given a graph embedding, it is straightforward to find communities by
performing the embedding and clustering tasks sequentially. This approach
lacks a unified objective, thus, the node embeddings may not be optimized for
community detection. We extend the objective with cluster-based loss
calculated as the distance between a node embedding and its assigned cluster
$z_{v}$ Eq. 7. This introduces a feedback loop that encourages the model to
reinforce community structures while optimizing the topological and temporal
objectives Eq. 10. The influence of three objectives can be controlled using
hyperparameters $\beta^{\mathcal{E}}$, $\beta^{\mathcal{T}}$, and
$\beta^{\mathcal{C}}$.

(7) $\displaystyle\mathcal{L}^{C}$
$\displaystyle=\left\|Z_{v}-\mu_{z_{v}}\right\|^{2}_{\ell 2}$ (8)
$\displaystyle\mathcal{L}^{\mathcal{E}}$ $\displaystyle=\operatorname{MM-
Loss}(\mathbf{Z},P^{\mathcal{E}},\bar{P},v)$ (9)
$\displaystyle\mathcal{L}^{\mathcal{T}}$ $\displaystyle=\operatorname{MM-
Loss}(\mathbf{Z},P^{\mathcal{T}},\bar{P},v)$ (10) $\displaystyle\mathcal{L}$
$\displaystyle=\beta^{\mathcal{E}}\mathcal{L}^{\mathcal{E}}+\beta^{\mathcal{T}}\mathcal{L}^{\mathcal{T}}+\beta^{\mathcal{C}}\mathcal{L}^{\mathcal{C}}$

With this closed feedback loop, the training procedure consists of two
alternating stages (See Fig. 1(a) and (b)). See Algorithm 3 for a detailed
overview. The embedding optimization stage (Algorithm 3), is responsible for
optimizing the graph embedding function parameters while keeping cluster
parameters $\theta$ fixed (Algorithm 3). Once the graph embeddings are updated
we run $I_{c}$ clustering/EM steps to optimize cluster parameters $\theta$
while keeping node representations fixed. Note that the representation
optimization stage is run until convergence as part of pretraining beforehand
to ensure the clusters are initialized properly.

Input: multimodal graph
$G=(\mathcal{V},\mathcal{E},\mathcal{A},\mathcal{R},\mathcal{X})$, number of
convolutional layers $L$

Output: Embedding $Z$ for nodes in $G$ and clusters parameters $\theta$

1 for  _$subiter=1$ to $I$_ do

2 for  _$v\in\mathcal{V}$_ do

/* Gather context samples */

3 $P^{\mathcal{E}}=\texttt{Node2VecRandomWalk}(G,l,v)$;

4 $P^{\mathcal{T}}=\texttt{BallroomWalk}(G,\omega,l,v)$;

5 $\overline{P}\stackrel{{\scriptstyle l}}{{\sim}}\mathcal{V}$ Negative
sampling;

6 $\mathcal{B}=P_{l}^{\mathcal{E}}\cup P_{l}^{\mathcal{T}}\cup\bar{P}_{l}$;

7 $\mathbf{Z}=\texttt{PrimaryEmbed}(G,\mathcal{B})$;

8 Compute task embeddings $Z^{\mathcal{E}}$, $Z^{\mathcal{T}}$ using Eq. 3;

9 Compute loss $\mathcal{L}^{\mathcal{E}}$, $\mathcal{L}^{\mathcal{T}}$,
$\mathcal{L}^{\mathcal{C}}$, $\mathcal{L}$ using Eqs. 7, 8, 9 and 10 given
respective context $P^{\mathcal{E}}$, $P^{\mathcal{T}}$;

10

11 end for

12 for  _$iter=1$ to $I_{c}$_ do

13 if  _$i=1$_ then

14 Initialize $\theta$ using K-means

15 end if

16 Update $\theta$ using EM given $Z$

17 end for

18

19 end for

Algorithm 3 MGTCOM learning pipeline

##  5\. Experiments

Table 2.  Dataset statistics.

Dataset | Node type | # Nodes | Edge type | # Edges | Temporal | Labelled
---|---|---|---|---|---|---
DBLP | Author (A) | 5,162 | A - Authored - P | 11,022 | $\bullet$ | $\bullet$
Paper (P) | 5,511 | P - Published In - V | 5,511
Venue (V) | 14 |  |
IMDB | Person (P) | 8,491 | P - Directed - M | 4,939 | $\bullet$ |
Movie (M) | 5,043 | P - Acted In - M | 15,086
Genre (G) | 26 | M - Tagged - G | 14,504
SDS | User (U) | 34,919 | U - Tweeted - T | 56,173 | $\bullet$ |
Hashtag (H) | 2,341 | T - Reply To - U | 21,769
Tweet (T) | 56,173 | T - Reply To - T | 4,296
|  | T - Quote - T | 882
|  | T - Mention - U | 70,367
|  | T - Mention - H | 12,313
|  | U - Follows - U | 5,649,098
ICEWS | Entity (E) | 10,463 | 123 different types | 915,028 | $\bullet$ |

Table 3.  Comparison of performance of baselines on multimodal graph learning
tasks. (”-” means no data available, for example metapaths are not available
for ICEWS). The calculated metrics are the link prediction accuracy
($LP_{ACC}$), predictive accuracy on ground truth communities $CF_{ACC}$
$L_{y}$, timestamp predictive accuracy $CF_{ACC}$ $L_{\mathcal{T}}$, NMI score
of detected communities ($COM_{NMI}$) given predefined communities ($L_{y}$,
$L_{\mathcal{T}}$, $L_{G}$) and Modularity.

Dataset |  | GraphSAGE | Node2Vec | Metapath2Vec | ComE | GEMSEC | CTDNE | CP-GNN | MGTCOM | MGTCOMT | MGTCOME
---|---|---|---|---|---|---|---|---|---|---|---
DBLP | $LP_{ACC}$ | 0.624 | 0.710 | 0.624 | 0.735 | 0.544 | 0.701 | 0.522 | 0.743 | 0.634 | 0.794
$CF_{ACC}$ $L_{y}$ | 0.315 | 0.832 | 0.696 | 0.842 | 0.831 | 0.809 | 0.506 | 0.896 | 0.330 | 0.884
$CF_{ACC}$ $L_{\mathcal{T}}$ | 0.309 | 0.308 | 0.296 | 0.328 | 0.324 | 0.488 | 0.313 | 0.758 | 0.508 | 0.320
$COM_{NMI}$ $L_{y}$ | 0.051 | 0.549 | 0.508 | 0.463 | 0.385 | 0.537 | 0.209 | 0.465 | 0.059 | 0.492
$COM_{NMI}$ $L_{\mathcal{T}}$ | 0.006 | 0.033 | 0.024 | 0.025 | 0.022 | 0.059 | 0.022 | 0.209 | 0.168 | 0.026
$COM_{NMI}$ $L_{G}$ | 0.040 | 0.425 | 0.413 | 0.470 | 0.314 | 0.401 | 0.107 | 0.336 | 0.039 | 0.371
Modularity | 0.028 | 0.662 | 0.583 | 0.636 | 0.492 | 0.642 | -0.035 | 0.427 | 0.137 | 0.514
ICEWS | $LP_{ACC}$ | 0.525 | 0.936 | - | 0.880 | 0.768 | 0.921 | 0.709 | 0.903 | 0.896 | 0.945
$CF_{ACC}$ $L_{\mathcal{T}}$ | 0.294 | 0.301 | - | 0.264 | 0.310 | 0.285 | 0.273 | 0.316 | 0.318 | 0.313
$COM_{NMI}$ $L_{\mathcal{T}}$ | 0.018 | 0.040 | - | 0.015 | 0.022 | 0.022 | 0.013 | 0.057 | 0.002 | 0.011
$COM_{NMI}$ $L_{G}$ | 0.227 | 0.354 | - | 0.548 | 0.309 | 0.347 | 0.204 | 0.119 | 0.001 | 0.447
Modularity | 0.218 | 0.215 | - | 0.483 | 0.311 | 0.239 | 0.199 | 0.007 | 0.001 | 0.390
IMDB | $LP_{ACC}$ | 0.714 | 0.757 | 0.642 | 0.666 | 0.637 | 0.728 | 0.598 | 0.721 | 0.724 | 0.773
$CF_{ACC}$ $L_{\mathcal{T}}$ | 0.346 | 0.373 | 0.309 | 0.394 | 0.380 | 0.488 | 0.316 | 0.659 | 0.556 | 0.377
$COM_{NMI}$ $L_{\mathcal{T}}$ | 0.022 | 0.025 | 0.008 | 0.031 | 0.013 | 0.065 | 0.004 | 0.239 | 0.231 | 0.026
$COM_{NMI}$ $L_{G}$ | 0.039 | 0.181 | 0.038 | 0.197 | 0.094 | 0.160 | 0.033 | 0.107 | 0.031 | 0.158
Modularity | -0.172 | 0.190 | 0.070 | 0.395 | 0.073 | 0.196 | 0.053 | 0.119 | 0.114 | 0.286
SDS | $LP_{ACC}$ | 0.922 | 0.953 | 0.853 | 0.758 | 0.878 | 0.955 | - | 0.934 | 0.616 | 0.956
$CF_{ACC}$ $L_{\mathcal{T}}$ | 0.521 | 0.445 | 0.399 | 0.386 | 0.384 | 0.447 | - | 0.523 | 0.887 | 0.492
$COM_{NMI}$ $L_{\mathcal{T}}$ | 0.250 | 0.149 | 0.018 | 0.117 | 0.015 | 0.161 | - | 0.204 | 0.536 | 0.044
$COM_{NMI}$ $L_{G}$ | 0.186 | 0.277 | 0.024 | 0.346 | 0.117 | 0.233 | - | 0.120 | 0.043 | 0.389
Modularity | 0.088 | 0.163 | -0.003 | 0.301 | 0.037 | 0.016 | - | 0.015 | 0.005 | 0.374

For the sake of space, we only report some key results and do not report our
extensive ablation study. Our code repository is available at
https://github.com/EgorDm/MGTCOM and all the datasets can be accessed at
https://zenodo.org/record/7273761.

We investigate the effectiveness of MGTCOM by evaluating its performance on
auxiliary tasks related to multimodal networks. In order to measure predictive
performance over distinct aspects of our data, we first identify the following
labels, then describe the auxiliary tasks (§5.1). We have three labels: ground
truth labels ($L_{y}$), node timestamps $L_{\mathcal{T}}$ (we split the nodes
evenly into snapshot labels given the timestamp of their first occurrences),
and Link-based communities $L_{G}$. For the $L_{G}$, we first identify
community labels using the Louvain method (Blondel et al., 2008). Then we use
those labels to assess the quality of individual node embeddings for community
detection. As the Louvain method greedily approximates optimal communities, we
don’t use this label for formal comparison.

###  5.1. Evaluation metrics

There are no measures that can assess the quality of communities in multimodal
networks. Therefore, we evaluate our model component-wise by defining related
auxiliary tasks. On a high level, these tasks evaluate the efficiency of
topological and temporal node embeddings and found communities.

  * •

Classification (CF). Given a set of node embeddings and their respective
ground truth labels, we train a logistic regression model to predict node
labels. For the predicted node labels, we calculate the average classification
accuracy.

  * •

Link prediction (LP). Given a set of positive and negative node pairs, binary
classification is used to predict whether an edge exists within the graph. We
use a held-out positive and randomly sampled negative sets of edges to train a
logistic regression model. The inner-product similarity between a pair of node
embeddings is used as input for the model. By repeating this process three
times, the average accuracy is calculated.

  * •

Link-based community quality. We use modularity to measure the quality of
topological communities (Girvan and Newman, 2002).

  * •

Ground-truth community quality (COM). To asses the quality of detected
communities for specific tasks, we measure the Normalized Mutual Information
(NMI) score given a task-based label.

###  5.2. Experimental setup

As shown in Table 1, there are no directly comparable methods to ours in terms
of features. For a fair and coherent comparison, we define three variants of
MGTCOM. In addition to the complete end-to-end model MGTCOM, we split our
framework into a temporal model MGTCOMT and topological model MGTCOME, by
removing $\mathcal{L}_{\mathcal{T}}$ and $\mathcal{L}_{\mathcal{E}}$ from the
objective respectively.

(a) $MGTCOM$ \+ $L_{y}$

(b) $MGTCOM$ \+ $L_{\mathcal{T}}$

(c) $ComE$ \+ $L_{y}$

(d) $ComE$ \+ $L_{\mathcal{T}}$

(e) $Node2Vec$ \+ $L_{y}$

(f) $Node2Vec$ \+ $L_{\mathcal{T}}$

(g) $CTDNE$ \+ $L_{y}$

(h) $CTDNE$ \+ $L_{\mathcal{T}}$

(I)

(II)

Figure 3.  (I) T-SNE plot of trained embeddings against ground truth ($L_{y}$)
and timestamp labels ($L_{\mathcal{T}}$), and (II) inductive inference results
for MGTCOM variants on the DBLP dataset.

Hyperparameters. The hyperparameters for MGTCOM model can be attributed to
either network architecture, topological random walk, temporal random walk or
clustering. The most important hyperparameters are specified below. For
primary embedding, we use two HGT layers with neighborhood sampling sizes of 8
and 4. All the hidden dimensions are equal to the representation dimension,
which is 64 ($d=64$). For temporal and topological context sampling we use
walk length $l=10$ (10 walks per node). Node2Vec is configured to use $q=0.5$
to favor neighborhood exploration. The temporal sampling window $\omega$ for
ballroom walk is determined for each dataset by splitting $\mathcal{T}$ into
20 even partitions. For the clustering module we set prior parameters as
$\nu=d+1,\kappa=1,\alpha=10$ and $\Sigma_{scale}=0.05$. We set trade-off
parameters as $\beta^{\mathcal{E}}=1,\beta^{\mathcal{T}}=1,\beta^{C}=0.01$.
For max-margin loss we set $\Delta$ to $0.1$.

Baselines. As baselines, we use various graph embedding and community
detection algorithms, namely, ComE, GEMSEC, CP-GNN, CTDNE, GraphSAGE, Node2Vec
and Matepath2Vec. We use the hyperparameters reported in their respective
papers. To keep the results comparable, we use representation dimension $d=64$
for all.

Datasets. We use four real-world multimodal datasets for evaluation, namely,
DBLP (Yang and Leskovec, 2012), IMDB (Zhang, 2017), SDS (Wang et al., 2020a),
and ICEWS (García-Durán et al., 2018). These datasets are of different types
and contain information on various modalities. We extracted a subset of the
multimodal SDS graph from Twitter and applied additional preprocessing on the
IMDB, DBLP, and ICEWS datasets to include the multimodal features present in
the datasets but often not included in the graph due to sparsity of temporal
or content-based features. Textual features are transformed using a pre-
trained language model (Wang et al., 2020b) and categorical features are
encoded as one-hot feature vectors. See Table 2 for a detailed comparison of
node features. For evaluation, we split the network edges into disjoint
training (80%), validation (10%), and testing (10%) sets. During link
prediction, we exclusively use links in the respective set as positive pairs.
Negative pairs are sampled given the full set of edges. Similarly, the
clustering is computed on the training embeddings while cluster-based metrics
are calculated using test and validation sets. During the calculation of
predictive metrics such as link prediction and classification, we run logistic
regression three times and average the results.

###  5.3. Performance comparison

We evaluate the performance of learned node embeddings and detected clusters.
In particular, we evaluate the predictive quality of embeddings using
classification and link prediction, i.e., link prediction accuracy $LP_{ACC}$,
temporal $L_{\mathcal{T}}$ and ground truth $L_{y}$ label classification
accuracy $CF_{ACC}$. We evaluate the quality of detected clusters by
calculating their NMI score based on predefined ground-truth communities
$L_{y}$, $L_{\mathcal{T}}$, $L_{G}$. This tells us whether detected clusters
approximate user-defined communities $L_{y}$, temporal partitioning
$L_{\mathcal{T}}$ or the topology $L_{G}$. Additionally, we calculate
community quality scores for the learned community assignments using the
modularity metric.

The embeddings obtained from non-community detection methods (GraphSAGE,
Node2Vec and Metapath2Vec) were clustered using k-means clustering with
$K=20$. Similarly, we use $K=20$ for community detection methods (ComE,
GEMSEC, CP-GNN) that assume a predefined cluster count. The results are
reported in Table 3. It can be seen that while MGTCOM is competitive on task-
specific measures such as link prediction and timestamp prediction, the
community detection methods still have an edge on link-based modularity
measures. A possible explanation for this would be the fact that the DPMM
process is more prone to getting stuck in local minima as the clusters split
and merge. Another possibility is that node features do not contain enough
information to model very specific network features such as modularity.

While CTDNE performs comparatively well in capturing the temporal aspect of a
given network, we see that it still yields inferior results on datasets where
temporal features are weakly correlated with topology. It is interesting to
note that algorithms that rely on pairwise loss measures such as GraphSAGE and
CP-GNN perform relatively well on classification-based measures while
performing very poorly on community quality measures modularity. A possible
explanation for such observation is that the combination of neighborhood
sampling and pairwise loss reinforces structural similarity despite having a
large receptive field. Our method successfully overcomes this issue by
modifying Hinge loss to work in a context path setting (see Section 4.2.2). We
also observe that the MGTCOM model performs well on both topology and temporal
prediction tasks in comparison to its task-specific counterparts.
Specifically, MGTCOM outperforms all the models, in all the metrics but
modularity, on the multimodal dataset SDS. Note that the modularity metric of
MGTCOM is inconclusive because it mainly measures the quality of topological
communities by looking at homophily. Heterophily commonly found in multimodal
networks is penalized. Additionally, it outperforms all the methods, on the
temporal task $L_{t}$, in all of the datasets.

###  5.4. Qualitative results

In this experiment, we further compare MGTCOM and the baseline models on the
DBLP network. We apply the T-SNE dimensionality reduction technique to
visualize the trained node embeddings in 2D space colored by the ground truth
label and the node timestamp (see Fig. 3-(I)). Since in this dataset the
timestamps are weakly correlated with its topology, we can see that topology
embedding (and community detection) methods such as ComE and Node2Vec do not
capture temporal relations of nodes. On contrary, we observe distinct patterns
emerge when looking at MGTCOM generated embeddings for both of the labels.
Similar to that of ComE the community structures are visible in the node
embeddings though they are not as distinct. Note that, in Fig. 3-(I), the
embeddings are calculated on the training dataset. Each of the plots contains
a blob of nodes that have no edges in the training set due to validation
split. None of the methods is equipped to handle disconnected nodes.

###  5.5. Inductive inference results

Since the MGTCOM model operates on sampled neighborhood subgraphs, in contrast
to other methods, it can operate in an inductive setting. Meaning that it is
not necessary to retrain the model to infer representation vectors for
previously unseen nodes. On the DBLP dataset, we evaluate the performance of
MGTCOM and its task-specific variants in an inductive setting by controlling
the ratio of nodes in the training set to the validation set. The test set
remains constant throughout the experiment to accurately assess performance on
inferred nodes. In Fig. 3-(II) we see the same measures ($LP_{ACC}$ and
$CF_{ACC}$) plotted with the training ratio on the x-axis. From Fig. 3-(II)
(a) we observe that varying training set size does not affect link-prediction
tasks as much as node classification tasks (b, c, d). In all the measures, we
can see that using only 75% of the data does not substantially affect the
results. Interestingly, we observe that the variance on the temporal
prediction task increases when more data is provided.

##  6\. Conclusion

In this paper, we introduce the MGTCOM framework for community detection in
multimodal graphs. It utilizes meta-topological, topological, content
features, and temporal information to detect communities. Moreover, we address
common issues in multimodal graphs such as information incompleteness, and
inference on unseen data by adopting a graph convolutional network
architecture that combines h-hop neighborhood sampling and random walk context
sampling. We devise a unified objective and an efficient temporal sampling
method to learn multimodal community-aware node embeddings in an unsupervised
manner. Consequently, we leverage a split/merge-based Dirichlet process
mixture model for community detection where the number of communities is not
known a priori. Our empirical evaluation shows that MGTCOM outperforms state-
of-the-art on the largest multimodal dataset with incomplete features (SDS).
It also achieves the best results on temporal tasks.

## References

  * (1)
  * Blondel et al. (2008) Vincent D. Blondel, Jean-Loup Guillaume, Renaud Lambiotte, and Etienne Lefebvre. 2008.  Fast Unfolding of Communities in Large Networks.  _Journal of Statistical Mechanics: Theory and Experiment_ 2008, 10 (Oct. 2008).
  * Bordes et al. (2013) Antoine Bordes, Nicolas Usunier, Alberto Garcia-Duran, Jason Weston, and Oksana Yakhnenko. 2013\.  Translating Embeddings for Modeling Multi-relational Data. In _Advances in Neural Information Processing Systems_ , Vol. 26.
  * Cao et al. (2018) Jinxin Cao, Di Jin, Liang Yang, and Jianwu Dang. 2018\.  Incorporating Network Structure with Node Contents for Community Detection on Large Networks Using Deep Learning.  _Neurocomputing_ 297 (July 2018).
  * Cao et al. (2021) Yuwei Cao, Hao Peng, Jia Wu, Yingtong Dou, Jianxin Li, and Philip Yu. 2021\.  Knowledge-Preserving Incremental Social Event Detection via Heterogeneous GNNs.
  * Cavallari et al. (2017) Sandro Cavallari, Vincent W. Zheng, Hongyun Cai, Kevin Chen-Chuan Chang, and Erik Cambria. 2017.  Learning Community Embedding with Community Detection and Node Embedding on Graphs. In _Proceedings of the 2017 ACM on Conference on Information and Knowledge Management_. ACM, Singapore.
  * Chang and Fisher III (2013) Jason Chang and John W Fisher III. 2013.  Parallel Sampling of DP Mixture Models Using Sub-Cluster Splits. In _Advances in Neural Information Processing Systems_ , Vol. 26. Curran Associates, Inc.
  * Dong et al. (2017) Yuxiao Dong, Nitesh V. Chawla, and Ananthram Swami. 2017\.  Metapath2vec: Scalable Representation Learning for Heterogeneous Networks. In _Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_ _(KDD ’17)_. Association for Computing Machinery, New York, NY, USA.
  * Fani et al. (2020) Hossein Fani, Eric Jiang, Ebrahim Bagheri, Feras Al-Obeidat, Weichang Du, and Mehdi Kargar. 2020\.  User Community Detection via Embedding of Social Network Structure and Temporal Content.  _Information Processing & Management_ 57, 2 (March 2020).
  * Fortunato (2010) Santo Fortunato. 2010\.  Community Detection in Graphs.  _Physics Reports_ 486, 3 (2010).
  * García-Durán et al. (2018) Alberto García-Durán, Sebastijan Dumančić, and Mathias Niepert. 2018.  Learning Sequence Encoders for Temporal Knowledge Graph Completion.  (2018).  arXiv:1809.03202 [cs.AI]
  * Girvan and Newman (2002) M. Girvan and M. E. J. Newman. 2002.  Community Structure in Social and Biological Networks.  _Proceedings of the National Academy of Sciences_ 99, 12 (June 2002).
  * Gosak et al. (2018) Marko Gosak, Rene Markovič, Jurij Dolenšek, Marjan Slak Rupnik, Marko Marhl, Andraž Stožer, and Matjaž Perc. 2018.  Network Science of Biological Systems at Different Scales: A Review.  _Physics of Life Reviews_ 24 (March 2018).
  * Grover and Leskovec (2016) Aditya Grover and Jure Leskovec. 2016.  Node2vec: Scalable Feature Learning for Networks. In _Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_ _(KDD ’16)_. Association for Computing Machinery, New York, NY, USA.
  * Hagen et al. (2018) Loni Hagen, Thomas Keller, Stephen Neely, Nic DePaula, and Claudia Robert-Cooperman. 2018\.  Crisis Communications in the Age of Social Media: A Network Analysis of Zika-Related Tweets.  _Social Science Computer Review_ 36, 5 (Oct. 2018).
  * Hamilton et al. (2017) William L. Hamilton, Rex Ying, and Jure Leskovec. 2017\.  Inductive Representation Learning on Large Graphs. In _Proceedings of the 31st International Conference on Neural Information Processing Systems_ _(NIPS’17)_. Curran Associates Inc., Red Hook, NY, USA.
  * He et al. (2011) Xiaofei He, Deng Cai, Yuanlong Shao, Hujun Bao, and Jiawei Han. 2011.  Laplacian Regularized Gaussian Mixture Model for Data Clustering.  _IEEE Trans. Knowl. Data Eng._ 23 (Sept. 2011).
  * Hendrycks and Gimpel (2020) Dan Hendrycks and Kevin Gimpel. 2020.  Gaussian Error Linear Units (GELUs).  arXiv:1606.08415 [cs]
  * Hu et al. (2020) Ziniu Hu, Yuxiao Dong, Kuansan Wang, and Yizhou Sun. 2020\.  Heterogeneous Graph Transformer. In _Proceedings of The Web Conference 2020_. ACM, Taipei Taiwan.
  * Jia et al. (2019) Yuting Jia, Qinqin Zhang, Weinan Zhang, and Xinbing Wang. 2019\.  CommunityGAN: Community Detection with Generative Adversarial Nets. In _The World Wide Web Conference_. ACM, San Francisco CA USA.
  * Kozdoba and Mannor (2015) Mark Kozdoba and Shie Mannor. 2015.  Community Detection via Measure Space Embedding. In _Advances in Neural Information Processing Systems_ , Vol. 28. Curran Associates, Inc.
  * Kumpula et al. (2008) Jussi M. Kumpula, Mikko Kivelä, Kimmo Kaski, and Jari Saramäki. 2008.  Sequential Algorithm for Fast Clique Percolation.  _Physical Review E_ 78, 2 (Aug. 2008).
  * Li et al. (2018) Ye Li, Chaofeng Sha, Xin Huang, and Yanchun Zhang. 2018\.  Community Detection in Attributed Graphs: An Embedding Approach.  _Proceedings of the AAAI Conference on Artificial Intelligence_ 32, 1 (April 2018).
  * Liu et al. (2014) Hongtao Liu, Hui Chen, Mao Lin, and Yu Wu. 2014\.  Community Detection Based on Topic Distance in Social Tagging Networks.  _Indonesian Journal of Electrical Engineering and Computer Science_ 12, 5 (May 2014).
  * Luo et al. (2021) Linhao Luo, Yixiang Fang, Xin Cao, Xiaofeng Zhang, and Wenjie Zhang. 2021.  Detecting Communities from Heterogeneous Graphs: A Context Path-based Graph Neural Network Model.  In _Proceedings of the 30th ACM International Conference on Information & Knowledge Management_. Association for Computing Machinery, New York, NY, USA.
  * Mikolov et al. (2013) Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg Corrado, and Jeffrey Dean. 2013.  Distributed Representations of Words and Phrases and Their Compositionality.  _arXiv:1310.4546_ (Oct. 2013).  arXiv:1310.4546 [cs, stat]
  * Min et al. (2018) Erxue Min, Xifeng Guo, Qiang Liu, Gen Zhang, Jianjing Cui, and Jun Long. 2018\.  A Survey of Clustering With Deep Learning: From the Perspective of Network Architecture.  _IEEE Access_ 6 (2018).
  * Nguyen et al. (2018) Giang Hoang Nguyen, John Boaz Lee, Ryan A. Rossi, Nesreen K. Ahmed, Eunyee Koh, and Sungchul Kim. 2018.  Continuous-Time Dynamic Network Embeddings. In _The Web Conference 2018 - WWW ’18_. ACM Press, Lyon, France.
  * Pareja et al. (2020) Aldo Pareja, Giacomo Domeniconi, Jie Chen, Tengfei Ma, Toyotaro Suzumura, Hiroki Kanezashi, Tim Kaler, Tao Schardl, and Charles Leiserson. 2020.  EvolveGCN: Evolving Graph Convolutional Networks for Dynamic Graphs.  _Proceedings of the AAAI Conference on Artificial Intelligence_ 34 (April 2020).
  * Perozzi et al. (2014) Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. 2014\.  DeepWalk: Online Learning of Social Representations. In _Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_ _(KDD ’14)_. Association for Computing Machinery, New York, NY, USA.
  * Pryke (2004) Stephen D. Pryke. 2004\.  Analysing Construction Project Coalitions: Exploring the Application of Social Network Analysis.  _Construction Management and Economics_ 22, 8 (Oct. 2004).
  * Ronen et al. (2022) Meitar Ronen, Shahaf E. Finder, and Oren Freifeld. 2022\.  DeepDPM: Deep Clustering With an Unknown Number of Clusters.  _arXiv:2203.14309_ (March 2022).  arXiv:2203.14309 [cs, stat]
  * Rozemberczki et al. (2019) Benedek Rozemberczki, Ryan Davies, Rik Sarkar, and Charles Sutton. 2019.  GEMSEC: Graph Embedding with Self Clustering. In _Proceedings of the 2019 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining_ _(ASONAM ’19)_. Association for Computing Machinery, New York, NY, USA.
  * Schuetz and Caflisch (2008) Philipp Schuetz and Amedeo Caflisch. 2008.  Multistep Greedy Algorithm Identifies Community Structure in Real-World and Computer-Generated Networks.  _Physical Review E_ 78, 2 (Aug. 2008).
  * Sen et al. (2008) Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad. 2008.  Collective Classification in Network Data.  _AI Magazine_ 29, 3 (Sept. 2008).
  * Su et al. (2021) Xing Su, Shan Xue, Fanzhen Liu, Jia Wu, Jian Yang, Chuan Zhou, Wenbin Hu, Cecile Paris, Surya Nepal, Di Jin, Quan Z. Sheng, and Philip S. Yu. 2021\.  A Comprehensive Survey on Community Detection with Deep Learning.  _arXiv:2105.12584 [cs]_ (May 2021).  arXiv:2105.12584 [cs]
  * Sun et al. (2012) Yizhou Sun, Charu Aggarwal, and Jiawei Han. 2012\.  Relation Strength-Aware Clustering of Heterogeneous Information Networks with Incomplete Attributes.  _Proceedings of the VLDB Endowment_ 5 (Jan. 2012).
  * Tian et al. (2014) Fei Tian, Bin Gao, Qing Cui, Enhong Chen, and Tie-Yan Liu. 2014.  Learning Deep Representations for Graph Clustering.  _Proceedings of the AAAI Conference on Artificial Intelligence_ 28, 1 (June 2014).
  * Tonellato (2020) Stefano F. Tonellato. 2020\.  Bayesian Nonparametric Clustering as a Community Detection Problem.  _Computational Statistics & Data Analysis_ 152 (Dec. 2020).
  * Vaswani et al. (2017) Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin. 2017.  Attention Is All You Need. In _Advances in Neural Information Processing Systems_ , Vol. 30. Curran Associates, Inc.
  * Wang et al. (2020a) Shihan Wang, Marijn Schraagen, Erik Tjong Kim Sang, and Mehdi Dastani. 2020a.  Public Sentiment on Governmental COVID-19 Measures in Dutch Social Media. In _Proceedings of the 1st Workshop on NLP for COVID-19 in Conference on Empirical Methods in Natural Language Processing (EMNLP 2020)_. Association for Computational Linguistics.
  * Wang et al. (2020b) Wenhui Wang, Furu Wei, Li Dong, Hangbo Bao, Nan Yang, and Ming Zhou. 2020b.  MiniLM: Deep Self-Attention Distillation for Task-Agnostic Compression of Pre-Trained Transformers.  arXiv:2002.10957 [cs]
  * Wu et al. (2021) Jiaming Wu, Meng Liu, Jiangting Fan, Yong Liu, and Meng Han. 2021.  SageDy: A Novel Sampling and Aggregating Based Representation Learning Approach for Dynamic Networks. In _Artificial Neural Networks and Machine Learning – ICANN 2021_ _(Lecture Notes in Computer Science)_ , Igor Farkaš, Paolo Masulli, Sebastian Otte, and Stefan Wermter (Eds.). Springer International Publishing, Cham.
  * Xue et al. (2019) Shan Xue, Jie Lu, and Guangquan Zhang. 2019.  Cross-Domain Network Representations.  _Pattern Recognition_ 94 (Oct. 2019).
  * Yang et al. (2017) Carl Yang, Mengxiong Liu, Zongyi Wang, Liyuan Liu, and Jiawei Han. 2017.  Graph Clustering with Dynamic Embedding.  _arXiv:1712.08249 [physics]_ (Dec. 2017).  arXiv:1712.08249 [physics]
  * Yang and Leskovec (2012) Jaewon Yang and Jure Leskovec. 2012.  Defining and Evaluating Network Communities Based on Ground-Truth. In _Proceedings of the ACM SIGKDD Workshop on Mining Data Semantics_ _(MDS ’12)_. Association for Computing Machinery, New York, NY, USA.
  * Zhang (2017) Yueming Zhang. 2017\.  IMDB 5000 Movie Dataset.  https://kaggle.com/carolzhangdc/imdb-5000-movie-dataset.
  * Zhu et al. (2020) Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. 2020\.  Beyond homophily in graph neural networks: Current limitations and effective designs.  _Advances in Neural Information Processing Systems_ 33 (2020), 7793–7804.