10 November 2022 in IEEE Transactions on Knowledge and Data Engineering
Most recent graph clustering methods have resorted to Graph Auto-Encoders (GAEs) to perform joint clustering and embedding learning. However, two critical issues have been overlooked. First, the accumulative error, inflicted by learning from noisy clustering assignments, degrades the effectiveness of the clustering model. This problem is called Feature Randomness. Second, reconstructing the adjacency matrix sets the model to learn irrelevant similarities for the clustering task. This problem is called Feature Drift. Furthermore, the theoretical relation between the aforementioned problems has not yet been investigated. We study these issues from two aspects: (1) there is a trade-off between Feature Randomness and Feature Drift when clustering and reconstruction are performed at the same level, and (2) the problem of Feature Drift is more pronounced for GAE models, compared with vanilla auto-encoder models. Thus, we reformulate the GAE-based clustering methodology. Our solution is two-fold. First, we propose a sampling operator $\Xi$ that triggers a protection mechanism against Feature Randomness. Second, we propose an operator $\Upsilon$ that triggers a correction mechanism against Feature Drift by gradually transforming the reconstructed graph into a clustering-oriented one. As principal advantages, our solution grants a considerable improvement in clustering effectiveness and can be easily tailored to GAE models.
26 May 2020 in IEEE Transactions on Knowledge and Data Engineering
To overcome the absence of concrete supervisory signals, deep clustering models construct their own labels based on self-supervision and pseudo-supervision. However, applying these techniques can cause Feature Randomness and Feature Drift. In this paper, we formally characterize these two new concepts. On one hand, Feature Randomness takes place when a considerable portion of the pseudo-labels is deemed to be random. In this regard, the trained model can learn non-representative features. On the other hand, Feature Drift takes place when the pseudo-supervised and the reconstruction losses are jointly minimized. While penalizing the reconstruction loss aims to preserve all the inherent data information, optimizing the embedded-clustering objective drops the latent between-cluster variances. Due to this compromise, the clustering-friendly representations can be easily drifted. In this context, we propose ADEC (Adversarial Deep Embedded Clustering) a novel autoencoder-based clustering model, which relies on a discriminator network to reduce random features while avoiding the drifting effect. Our new metrics $\Delta_{FR}$ and $\Delta_{FD}$ allows to, respectively, assess the level of Feature Randomness and Feature Drift. We empirically demonstrate the suitability of our model on handling these problems using benchmark real datasets. Experimental results validate that our model outperforms state-of-the-art autoencoder-based clustering methods.
29 June 2018 in IEEE Transactions on Knowledge and Data Engineering
As time evolves, communities in a social network may undergo various changes known as critical events. For instance, a community can either split into several other communities, expand into a larger community, shrink to a smaller community, remain stable or merge into another community. Prediction of critical events has attracted increasing attention in the recent literature. Learning the evolution of communities over time is a key step towards predicting the critical events the communities may undergo. This is an important and difficult issue in the study of social networks. In the work to date, there is a lack of formal approaches for modeling and predicting critical events over time. This motivates our effort to design a new statistical method for event prediction in order to make better use of histories of past changes. To this end, this paper proposes a sliding window analysis from which we develop a model that simultaneously exploits an autoregressive model and survival analysis techniques. The autoregressive model is employed here to simulate the evolution of the community structure, whereas the survival analysis techniques allow the prediction of future changes the community may undergo.
1 August 2013 in Data Mining and Knowledge Discovery
16 August 2023 in IEEE Transactions on Knowledge and Data Engineering
We investigate the problem of multiplex graph embedding, that is, graphs in which nodes interact through multiple types of relations (dimensions). In recent years, several methods have been developed to address this problem. However, the need for more effective and specialized approaches grows with the production of graph data with diverse characteristics. In particular, real-world multiplex graphs may exhibit a high number of dimensions, making it difficult to construct a single consensus representation. Furthermore, important information can be hidden in complex latent structures scattered in multiple dimensions. To address these issues, we propose HMGE, a novel embedding method based on hierarchical aggregation for high-dimensional multiplex graphs. Hierarchical aggregation consists in learning a hierarchical combination of the graph dimensions and refining the embeddings at each hierarchy level. Non-linear combinations are computed from previous ones, thus uncovering complex information and latent structures hidden in the multiplex graph dimensions. Moreover, we leverage mutual information maximization between local patches and global summaries to train the model without supervision. This allows to captures globally relevant information present in diverse locations of the graph. Detailed experiments on synthetic and real-world data illustrate the suitability of our approach on downstream supervised tasks, including link prediction and node classification.
28 June 2023 in ACM Transactions on Knowledge Discovery From Data
We investigate the problem of discovering and modeling regime shifts in an ecosystem comprising multiple time series known as co-evolving time series. Regime shifts refer to the changing behaviors exhibited by series at different time intervals. Learning these changing behaviors is a key step toward time series forecasting. While advances have been made, existing methods suffer from one or more of the following shortcomings: (1) failure to take relationships between time series into consideration for discovering regimes in multiple time series; (2) lack of an effective approach that models time-dependent behaviors exhibited by series; (3) difficulties in handling data discontinuities which may be informative. Most of the existing methods are unable to handle all of these three issues in a unified framework. This, therefore, motivates our effort to devise a principled approach for modeling interactions and time-dependency in co-evolving time series. Specifically, we model an ecosystem of multiple time series by summarizing the heavy ensemble of time series into a lighter and more meaningful structure called a mapping grid . By using the mapping grid, our model first learns time series behavioral dependencies through a dynamic network representation, then learns the regime transition mechanism via a full time-dependent Cox regression model. The originality of our approach lies in modeling interactions between time series in regime identification and in modeling time-dependent regime transition probabilities, usually assumed to be static in existing work.