Clustering in Networks with Time-varying Nodal Attributes

Yik Lun Kei, Oscar Hernan Madrid Padilla, Rebecca Killick, James Wilson, Xi Chen, Robert Lund · 2025

Read Clustering in Networks with Time-varying Nodal Attributes by Yik Lun Kei, Oscar Hernan Madrid Padilla, Rebecca Killick, James Wilson, Xi Chen, Robert Lund (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-04859.txt.

Introduction

Yik Lun Kei leads six authors clustering nodes in attributed graphs with a decoder-only design. Each node carries several measured attributes alongside its graph links. Low-dimensional node representations get node-specific priors in their framework.

A neural decoder bridges those latent variables back to the observed attributes. A graph-fused LASSO penalty on the prior means pulls linked nodes toward shared clusters. Alternating direction optimization fits the model, with Langevin dynamics for posterior sampling. Tests on grid graphs and messy real data show the clustering works, using structure and attributes together rather than either alone.

Catalog record

CREATORYik Lun Kei, Oscar Hernan Madrid Padilla, Rebecca Killick, James Wilson, Xi Chen, Robert Lund
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE60 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2511-04859

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Clustering in Networks with Time-varying Nodal Attributes Yik Lun Kei, Oscar Hernan Madrid Padilla, Rebecca Killick, James Wilson, Xi Chen, Robert Lund Abstract This manuscript studies nodal clustering in graphs having a time series at each node. The framework includes priors for low-dimensional representations and a decoder that bridges the latent representations and time series. The structural and temporal patterns are fused into representations that facilitate clustering, addressing the limitation that the evolution of nodal attributes is often overlooked. Parameters are learned via maximum approximate likelihood, with a graph-fused LASSO regularization imposed on prior parameters. The optimization problem is solved via alternating direction method of multipliers; Langevin dynamics are employed for posterior inference. Simulation studies on block and grid graphs with autoregressive dynamics, and applications to California county temperatures and a book word co-occurrence network demonstrate the effectiveness of the proposed method. Keywords: ADMM, LASSO, Latent Space Models, Representation Learning, Time Series. 1 Introduction Networks are used to describe relational phenomena, where entities are denoted by nodes and relations are delineated by edges between nodes. Such structures naturally arise in various domains, including social interactions ( 27 ) , neurology ( 32 ) , and finance ( 13 ) . A fundamental task in network analysis involves clustering nodes into disjoint sets, where node within a set are more connected than nodes in disjoint sets. Such clusters often provide structural insights into the network (see 25 for a collection of case studies). The majority of clustering methods focus on structural patterns ( 2 ) . However, many networks possess additional “nodal attributes”. This paper shows how to take advantage of nodal time series, providing clustering methods that account for both network structure and attribute dynamics. Section 4 uses the methods to identify climate regions in California by county. Here, both spatial proximities and temperatures of the counties are used to develop a realistic clustering. Clustering nodes of networks with nodal attributes relies on effectively combining graphical structures with the nodal information. Methods have been previously proposed for clustering attributed networks. 4 perform covariate-assisted spectral clustering by augmenting the Laplacian of the graph with pairwise similarities of the nodal covariates. 26 propose a Bayesian stochastic block model where nodal information is incorporated into prior distributions via a covariate-dependent random partition prior. 12 leverage individual and neighboring covariates with a node-specific weight matrix to improve clustering. Furthermore, the graph-fused LASSO regularizations in 6 and 19 have shown promising results, producing smoothed signals between neighboring nodes while preserving boundaries between regions having distinct signals. Following 9 and 34 , our framework also adapts graph-fused LASSO regularization to achieve similar filtering behavior. In many applications, nodal attributes progress in time, while the network structure remains fixed. Nodal time series can provide valuable clustering information, especially in cases with a non-informative graph. Some methods for clustering graphs nodes overlook the evolution of nodal features, eschewing an approach that merges temporal dynamics with structural patterns. A natural solution introduces a latent variable at each node. By compressing each nodal series into a low-dimensional latent representation, temporal dynamics can be summarized and integrated with structural patterns. In our approach, latent representations are managed by node-specific priors and empirical Bayes techniques. Simultaneously, the latent space is regularized by a graph-fused LASSO penalty to incorporate network information. The resulting low-dimensional representations preserve both neighbor information and attribute dynamics, promoting effective clustering. Latent space models bridge low-dimensional representations with the observed nodal series. 10 model nodes in a Euclidean space by assuming that edge probabilities are greater for node pairs that are closer in the latent space. 36 construct a latent space model with both attractive and repulsive nodes, thereby disentangling network polarization dynamics. In contrast, our framework models the nodal series, conditioning on its low-dimensional representations. Unlike a variational auto-encoder ( 15 ) , which encourages the approximate posterior to align with a zero-mean Gaussian prior, we focus on learning Gaussian prior means to facilitate clustering. With graph-fused LASSO regularization imposed on the differences between prior parameters over the edges, nodes having similar patterns are encouraged to have similar prior parameters. Consequently, a k -means algorithm that clusters via centroids is well-suited. This manuscript makes the following contributions: • A decoder-only latent space model is proposed to link the nodal series and latent variables. Anchored on the decoder, the latent variables are regarded as low-dimensional representations of the nodal series, while also capturing network structural patterns. The prior parameters are clustered via k -means method. • We show how to learn the Gaussian prior parameters in our latent representation. Specifically, our graph-fused LASSO regularization encourages sparsity in the multivariate parameters across edges. This produces similar parameters in neighboring nodes while preserving regions with disparate signals. • An alternating direction method of multipliers (ADMM) procedure is developed to solve our associated optimization problem; parameters are learned via posterior inference. Through simulations on block and grid graphs with autoregressive dynamics, and applications to California county temperatures and a word co-occurrence network, the effectiveness of the proposed framework is demonstrated. The rest of the manuscript is organized as follows. Section 2 describes our proposed framework. Section 3 presents an objective function with a graph-fused LASSO regularization and develops the ADMM procedure to solve the optimization problem. Section 4 illustrates the proposed method through simulations and real-data applications. Section 5 discusses limitations and ideas for future work. 2 Decoder-only Latent Space Models We consider an undirected graph \mathcal{G}=(\mathcal{V},\mathcal{E}) , where \mathcal{V} is the node set and \mathcal{E} is the edge set. For each node i\in\mathcal{V} , let \{Y_{t,i}\}_{t=1}^{n} denote a sequence of univariate random variables (the node i time series). The node i series is represented as \bm{Y}_{i}\coloneqq(Y_{1,i},Y_{2,i},\dots,Y_{n,i})^{\top}\in\mathbb{R}^{n} . For each \bm{Y}_{i}\in\mathbb{R}^{n} , we assume existence of a latent variable \bm{Z}_{i}\in\mathbb{R}^{d} such that \bm{Y}_{i} is generated from \bm{Z}_{i} with the following time series “decoder”: \bm{Y}_{i}|\bm{Z}_{i}\sim P_{\bm{\phi}}(\bm{Y}_{i}|\bm{Z}_{i})\stackrel{{\scriptstyle\cal D}}{{=}}\mathcal{N}\big(\bm{h}_{\bm{\phi}}(\bm{Z}_{i}),\bm{I}_{n}\big), where \bm{h}_{\bm{\phi}}:\mathbb{R}^{d}\rightarrow\mathbb{R}^{n} is a neural network parameterized by \bm{\phi} . Here, P_{\bm{\phi}}(\bm{Y}_{i}|\bm{Z}_{i}) is the conditional probability density function of \bm{Y}_{i} given \bm{Z}_{i} (which depends on the neural network parameters in \bm{\phi} ). We impose a prior distribution on the latent \bm{Z}_{i} via \bm{Z}_{i}\sim P_{\bm{\mu}_{i}}(\bm{Z}_{i})\stackrel{{\scriptstyle\cal D}}{{=}}\mathcal{N}(\bm{\mu}_{i},\bm{I}_{d}). The prior parameter, \bm{\mu}_{i}\in\mathbb{R}^{d} , is learned for each node i\in\mathcal{V} . For the decoder P_{\bm{\phi}}(\bm{Y}_{i}|\bm{Z}_{i}) , the latent variable \bm{Z}_{i}\in\mathbb{R}^{d} is a low-dimensional representation of \bm{Y}_{i}\in\mathbb{R}^{n} at node i . Here, the distribution of interest is P(\bm{Y}_{i}) , which may be complicated. Instead of directly imposing a parametric form on the marginal P(\bm{Y}_{i}) , our framework introduces an auxiliary latent variable \bm{Z}_{i}\in\mathbb{R}^{d} to model P(\bm{Y}_{i}) as a mixture: P(\bm{Y}_{i})=\int P_{\bm{\phi}}(\bm{Y}_{i}|\bm{Z}_{i})P_{\bm{\mu}_{i}}(\bm{Z}_{i})d\bm{Z}_{i}. While the flexibility of our framework allows \bm{Y}_{i} to be a vector of multivariate features, we regard \bm{Y}_{i}\in\mathbb{R}^{n} as a univariate series of length n . Two remarks follow. Remark 1 . The Gaussian assumption is placed on P(\bm{Y}_{i}|\bm{Z}_{i}) , not on the marginal P(\bm{Y}_{i}) . The induced distribution of P(\bm{Y}_{i}) can be highly non-Gaussian and depends on \bm{h}_{\bm{\phi}}(\bm{\cdot}) . Remark 2 . Our framework assumes that Y_{t,i} is independent in time conditional on \bm{Z}_{i} . Here, \bm{Z}_{i} serves as our low-dimensional representation that captures temporal relationships while retaining a flexible marginal for P(\bm{Y}_{i}) . In particular, the covariance of \bm{Y}_{i} is \displaystyle\mathrm{Cov}(\bm{Y}_{i}) \displaystyle=\mathbb{E}\big[\mathrm{Cov}(\bm{Y}_{i}|\bm{Z}_{i})\big]+\mathrm{Cov}\big[\mathbb{E}(\bm{Y}_{i}|\bm{Z}_{i})\big]=\bm{I}_{n}+\mathrm{Cov}\big[\bm{h}_{\bm{\phi}}(\bm{Z}_{i})\big] which depends on \bm{h}_{\bm{\phi}}(\bm{\cdot}) , thereby

Read the complete text