This study focuses on detecting dependency changes in multivariate time series. This is a practically important issue because, for example, changes in the relationships between several stocks may lead to early warning of critical economic events. The corresponding change detection methods should be feasible for addressing high-dimensional cases online. We use the Gaussian graphical model (GGM) to represent the conditional dependencies in multivariate and reduce our issue to change detection in GGM and consider the cases with the size of the graphical model significantly larger than the sample size as high-dimensional. Although there are several studies on GGM change detection, adequately controlling the sparsity of the model to handle high-dimensional data remains a significant challenge. To address this problem, we introduce new change statistics based on the luckiness normalized maximum likelihood (LNML) code length and minimum description length (MDL) adapted for sparse modeling. We demonstrate how to efficiently calculate the LNML-based change statistics and provide a theoretical guarantee in terms of Type I and Type II error probabilities. We expand the methodology to include cases in which missing values exist. We compare the effectiveness of our methodology with that of conventional methods through experiments using synthetic and real-world datasets.

Abstract Graph data augmentation (GDA), which manipulates graph structure and/or attributes, has been demonstrated as an effective method for improving the generalization of graph neural networks on semi-supervised node classification. As a data augmentation technique, label preservation is critical, that is, node labels should not change after data manipulation. However, most existing methods overlook the label preservation requirements. Determining the label-preserving nature of a GDA method is highly challenging, owing to the non-Euclidean nature of the graph structure. In this study, for the first time, we formulate a label-preserving problem (LPP) in the context of GDA. The LPP is formulated as an optimization problem in which, given a fixed augmentation budget, the objective is to find an augmented graph with minimal difference in data distribution compared to the original graph. To solve the LPP problem, we propose GMMDA, a generative data augmentation (DA) method based on Gaussian mixture modeling (GMM) of a graph in a latent space. We designed a novel learning objective that jointly learns a low-dimensional graph representation and estimates the GMM. The learning is followed by sampling from the GMM, and the samples are converted back to the graph as additional nodes. To uphold label preservation, we designed a minimum description length (MDL)-based method to select a set of samples that produces the minimum shift in the data distribution captured by the GMM. Through experiments, we demonstrate that GMMDA can improve the performance of graph convolutional network on Cora , Citeseer and Pubmed by as much as $$7.75\%$$ 7.75 % , $$8.75\%$$ 8.75 % and $$5.87\%$$ 5.87 % , respectively, significantly outperforming the state-of-the-art methods.

Graph data augmentation (GDA), which manipulates graph structure and/or attributes, has been demonstrated as an effective method for improving the generalization of graph neural networks on semi-supervised node classification. As a data augmentation technique, label-preservation is critical, that is, node labels should not change after data manipulation. However, most existing methods overlook the label-preservation requirements. Determining the label-preserving nature of a GDA method is highly challenging, owing to the non-Euclidean nature of the graph structure. In this study, for the first time, we formulate a label-preserving problem (LPP) in the context of GDA. The LPP is formulated as an optimization problem in which, given a fixed augmentation budget, the objective is to find an augmented graph with minimal difference in data distribution compared to the original graph. To solve the LPP problem, we propose GMMDA, a generative data augmentation (DA) method based on Gaussian mixture modeling (GMM) of a graph in a latent space. The proposed GMMDA has three phases. First, a novel objective is designed to jointly learn a low-dimensional graph representation and estimate the GMM. The learning is followed by sampling from the GMM, and then the samples are converted back to the graph as additional nodes. To uphold label preservation, we designed a minimum description length (MDL)-based method to select a set of samples that produces the minimum shift in the data distribution. Through experiments, we demonstrate that GMMDA can improve the performance of graph convolutional network on CORA, CITESEER and PUBMED by as much as 7.75% 8.75% and 5.87%, respectively, significantly outperforming the state-of-the-art methods.

The detection of network changes over time is based on identifying deviations of the network structure. The challenge mainly lies in designing a good summary or descriptor of the network structure for facilitating the measure of deviations. In particular, a network may have a huge number of nodes and edges. Moreover, there can exist complicated dependences among edges, e.g., the existence of some edges may be because of others. Therefore, it is non-trivial to measure the contribution of each node and each edge to the deviation of the entire network structure. Existing descriptors are designed to have factors less than the number of nodes and edges. They also model edge dependences, but can only achieve partial modeling. In this paper, we propose a novel type of descriptor. We first obtain node coordinates or positions in a latent space where nodes connected by edges have close positions by network embedding. Node positions are low-dimensional. More importantly, node positions can fully model edge dependences. We then design the descriptor based on random walk on the node positions. We conducted extensive experiments on synthetic datasets and three real-world datasets to demonstrate the effectiveness of our proposed change detection framework with the descriptor.

Computational color naming (CCN) aims to learn a mapping from pixels into semantic color names, e.g., red, green and blue. CCN has wide applications including color vision deficiency assistance and color image retrieval. Existing research on CCN mainly studies pixels collected under laboratory settings or studies images collected from the web. However, laboratory pixels are very limited such that the learned mapping may not generalize well on unseen pixels, and the mapping discovered from images is usually data-specific. In this paper, we aim to learn a universal mapping by studying pixels collected from the web. To this end, we formulate a novel classification problem that incorporates both the pixels and the RGB color model. The RGB color model is beneficial for learning the mapping because it characterizes the production of colors, e.g., the addition of red and green produces yellow. However, the characterization is rather qualitative. To solve this problem, we propose ColorMLP, which is a multilayer perceptron (MLP) embedded with graph attention networks (GATs). Here, the GATs are designed to capture color relations that we construct by referring to the RGB color model. In this way, the parameters of the MLP can be regularized to comply with the RGB model. We conduct comprehensive experiments to demonstrate the superiority of ColorMLP to alternative methods.To expand the application of CCN, we design a novel data augmentation method named partial color jitter (PCJ), which performs color jitter (CJ) on a subset of pixels belonging to the same color of an image. In this way, PCJ partially changes the color properties of images, thereby significantly increasing images’ diversity. We conduct extensive experiments on CIFAR10/100 and ImageNet datasets, showing that PCJ can consistently improve the classification performance. Our data and software can be found at https://https://github.com/yanzipei/CCN_and_ItsApp.

Knowledge Graph (KG) errors introduce non-negligible noise, severely affecting KG-related downstream tasks. Detecting errors in KGs is challenging since the patterns of errors are unknown and diverse, while ground-truth labels are rare or even unavailable. A traditional solution is to construct logical rules to verify triples, but it is not generalizable since different KGs have distinct rules with domain knowledge involved. Recent studies focus on designing tailored detectors or ranking triples based on KG embedding loss. However, they all rely on negative samples for training, which are generated by randomly replacing the head or tail entity of existing triples. Such a negative sampling strategy is not enough for prototyping practical KG errors, e.g., (Bruce_Lee, place_of_birth, China), in which the three elements are often relevant, although mismatched. We desire a more effective unsupervised learning mechanism tailored for KG error detection. To this end, we propose a novel framework - ContrAstive knowledge Graph Error Detection (CAGED). It introduces contrastive learning into KG learning and provides a novel way of modeling KG. Instead of following the traditional setting, i.e., considering entities as nodes and relations as semantic edges, CAGED augments a KG into different hyper-views, by regarding each relational triple as a node. After joint training with KG embedding and contrastive learning loss, CAGED assesses the trustworthiness of each triple based on two learning signals, i.e., the consistency of triple representations across multi-views and the self-consistency within the triple. Extensive experiments on three real-world KGs show that CAGED outperforms state-of-the-art methods in KG error detection. Our codes and datasets are available at https://github.com/Qing145/CAGED.git.

Glaucoma, which can cause irreversible damage to the sight of human eyes, is conventionally diagnosed by visual field (VF) sensitivity. However, it is labor-intensive and time-consuming to measure VF. Recently, optical coherence tomography (OCT) has been adopted to measure retinal layers thickness (RT) for assisting the diagnosis because glaucoma makes structural changes to RT and it is much less costly to obtain RT. In particular, RT can assist in mainly two manners. One is to estimate a VF from an RT such that clinical doctors only need to obtain an RT of a patient and then convert it to a VF for the diagnosis. The other is to predict future VFs by utilizing both past VFs and RTs, i.e., the prediction of progression of VF over time. The two computational tasks are performed as two data mining tasks because currently there is no knowledge about the exact form of the computations involved. In this paper, we study a novel problem which is the integration of the two data mining tasks. The motivation is that both the two data mining tasks deal with transforming information from the RT domain to the VF domain such that the knowledge discovered in one task can be useful for another. The integration is non-trivial because the two tasks do not share the way of transformation. To address this issue, we design a progression-agnostic and mode-independent (PAMI) module which facilitates cross-task knowledge utilization. We empirically demonstrate that our proposed method outperforms the state-of-the-art method for the estimation by 6.33% in terms of mean of the root mean square error on a real dataset, and outperforms the state-of-the-art method for the progression prediction by 3.49% for the best case.

Abstract Multi-label learning deals with data examples which are associated with multiple class labels simultaneously. Despite the success of existing approaches to multi-label learning, there is still a problem neglected by researchers, i.e., not only are some of the values of observed labels missing, but also some of the labels are completely unobserved for the training data. We refer to the problem asmulti-label learning with missing and completely unobserved labels, and argue that it is necessary to discover these completely unobserved labels in order to mine useful knowledge and make a deeper understanding of what is behind the data. In this paper, we propose a new approach named MCUL to solve multi-label learning with Missing and Completely Unobserved Labels. We try to discover the unobserved labels of a multi-label data set with a clustering based regularization term and describe the semantic meanings of them based on the label-specific features learned by MCUL, and overcome the problem of missing labels by exploiting label correlations. The proposed method MCUL can predict both the observed and newly discovered labels simultaneously for unseen data examples. Experimental results validated over ten benchmark datasets demonstrate that the proposed method can outperform other state-of-the-art approaches on observed labels and obtain an acceptable performance on the new discovered labels as well.

Heterogeneous information network (HIN) embedding is to encode network structure into node representations with the heterogeneous semantics of different node and edge types considered. However, since each HIN may have a unique nature, e.g., a unique set of node and edge types, a model designed for one type of networks may not be applicable to or effective on another type. In this article, we thus attempt to propose a framework for HINs with arbitrary number of node and edge types. The proposed framework constructs a novel mixture-split representation of an HIN, and hence is named as MixSp. The mixture sub-representation and the split sub-representation serve as two different views of the network. Compared with existing models which only learn from the original view, MixSp thus may exploit more comprehensive information. Node representations in each view are learned by embedding the respective network structure. Moreover, the node representations are further refined through cross-view co-regularization. The framework is instantiated in three models which differ from each other in the co-regularization. Extensive experiments on three real-world datasets show MixSp outperforms several recent models in both node classification and link prediction tasks even though MixSp is not designed for a particular type of HINs.

Network embedding has been widely employed in networked data mining applications as it can learn low-dimensional and dense node representations from the high-dimensional and sparse network structure. While most existing network embedding methods only model the proximity between two nodes regardless of the order of the proximity, this paper proposes to explicitly model multi-node proximities which can be widely observed in practice, e.g., multiple researchers coauthor a paper, and multiple genes co-express a protein. Explicitly modeling multi-node proximities is important because some two-node interactions may not come into existence without a third node. By proving that LINE(1st), a recent network embedding method, is equivalent to kernelized matrix factorization, this paper proposes coupled kernelized multi-dimensional array factorization (Cetera) which jointly factorizes multiple multi-dimensional arrays by enforcing a consensus representation for each node. In this way, node representations can be more comprehensive and effective, which is demonstrated on three real-world networks through link prediction and multi-label classification.

Prediction of glaucomatous visual field loss has significant clinical benefits because it can help with early detection of glaucoma as well as decision-making for treatments. Glaucomatous visual loss is conventionally captured through visual field sensitivity (VF ) measurement, which is costly and time-consuming. Thus, existing approaches mainly predict future VF utilizing limited VF data collected in the past. Recently, optical coherence tomography (OCT) has been adopted to measure retinal layers thickness (RT ) for considerably more low-cost treatment assistance. There then arises an important question in the context of ophthalmology: are RT measurements beneficial for VF prediction? In this paper, we propose a novel method to demonstrate the benefits provided by RT measurements. The challenge is management of the two heterogeneities of VF data and RT data as RT data are collected according to different clinical schedules and lie in a different space to VF data. To tackle these heterogeneities, we propose latent progression patterns (LPPs), a novel type of representations for glaucoma progression. Along with LPPs, we propose a method to transform VF series to an LPP based on matrix factorization and a method to transform RT series to an LPP based on deep neural networks. Partial VF and RT information is integrated in LPPs to provide accurate prediction. The proposed framework is named deeply-regularized latent-space linear regression (\em DLLR). We empirically demonstrate that our proposed method outperforms the state-of-the-art technique by 12% for the best case in terms of the mean of the root mean square error on a real dataset.

There are increasing interests in learning low-dimensional and dense node representations from the network structure which is usually high-dimensional and sparse. However, most existing methods fail to consider semantic meanings of links. Different links may have different semantic meanings because the similarities between two nodes can be different, e.g., two nodes share common neighbors and two nodes share similar interests which are demonstrated in node-generated content. In this paper, the former type of links are referred to as structure-close links while the latter type are referred to as content-close links. These two types of links naturally indicate there are two types of characteristics that nodes expose in a social network. Hence, we propose to learn two representations for each node, and render each representation responsible for encoding the corresponding type of node characteristics, which is achieved by jointly embedding the network structure and inferring the type of each link. In the experiments, the proposed method is demonstrated to be more effective than five recent methods on four social networks through applications including visualization, link prediction and multi-label classification.

As there are various data mining applications involving network analysis, network embedding is frequently employed to learn latent representations or embeddings that encode the network structure. However, existing network embedding models are only designed for a single network scenario. It is common that nodes can have multiple types of relationships in big data era, which results in multiple networks, e.g., multiple social networks and multiple gene regulatory networks. Jointly embedding multiple networks thus may make network-specific embeddings more comprehensive and complete as the same node may expose similar or complementary characteristics in different networks. In this paper, we thus propose an idea of multi-task network embedding (MTNE) to jointly learn multiple network-specific embeddings for each node via enforcing an extra information-sharing embedding. Moreover, we instantiate the idea in two models that are different in the mechanism for enforcing the information-sharing embedding. The first model enforces the information-sharing embedding as a common embedding shared by all tasks, which is similar to the concept of the common metric in multi-task metric learning while the second model enforces the information-sharing embedding as a consensus embedding on which all network-specific embeddings agree. We demonstrate through comprehensive experiments on three real-world datasets that the proposed models outperform state-of-the-art network embedding models in applications including visualization, link prediction, and multi-label classification.

Network embedding has been increasingly employed in networked data mining applications as it is effective to learn node embeddings that encode the network structure. Existing network models usually learn a single embedding for each node. In practice, a person may interact with others in different roles, such as interacting with schoolmates as a student, and with colleagues as an employee. Obviously, different roles exhibit different characteristics or features. Hence, only learning a single embedding responsible for all roles is not appropriate. In this paper, we thus introduce a concept of multiple social role (MSR) into social network embedding for the first time. The MSR models multiple roles people play in society, such as student and employee. To make the embedding more versatile, we thus propose a multiple social role embedding (MSRE) model to preserve both the network structure and social roles. Empirical evaluation on various real-world social networks demonstrates advantages of the proposed MSRE over the state-of-the-art embedding models in link prediction and multi-label classification.

Link prediction is an important and interesting application for social networks because it can infer potential links among network participants. Existing approaches basically work with the homophily principle, i.e., people of similar characteristics tend to befriend each other. In this way, however, they are not suitable for inferring negative links or hostile links, which usually take place among people with different characteristics. Moreover, negative links tend to couple with positive links to form signed networks. In this paper, we thus study the problem of disentangled link prediction (DLP) for signed networks, which includes two separate tasks, i.e., inferring positive links and inferring negative links. Recently, representation learning methods have been proposed to solve the link prediction problem because the entire network structure can be encoded in representations. For the DLP problem, we thus propose to disentangle a node representation into two representations, and use one for positive link prediction and another for negative link prediction. Experiments on three real-world signed networks demonstrate the proposed disentangled representation learning (DRL) method significantly outperforms alternatives in the DLP problem.

Network embedding is increasingly employed to assist network analysis as it is effective to learn latent features that encode linkage information. Various network embedding methods have been proposed, but they are only designed for a single network scenario. In the era of big data, different types of related information can be fused together to form a coupled heterogeneous network, which consists of two different but related sub-networks connected by inter-network edges. In this scenario, the inter-network edges can act as comple- mentary information in the presence of intra-network ones. This complementary information is important because it can make latent features more comprehensive and accurate. And it is more important when the intra-network edges are ab- sent, which can be referred to as the cold-start problem. In this paper, we thus propose a method named embedding of embedding (EOE) for coupled heterogeneous networks. In the EOE, latent features encode not only intra-network edges, but also inter-network ones. To tackle the challenge of heterogeneities of two networks, the EOE incorporates a harmonious embedding matrix to further embed the em- beddings that only encode intra-network edges. Empirical experiments on a variety of real-world datasets demonstrate the EOE outperforms consistently single network embedding methods in applications including visualization, link prediction multi-class classification, and multi-label classification.

Link Prediction has been an important task for social and information networks. Existing approaches usually assume the completeness of network structure. However, in many real-world networks, the links and node attributes can usually be partially observable. In this paper, we study the problem of Cross View Link Prediction (CVLP) on partially observable networks, where the focus is to recommend nodes with only links to nodes with only attributes (or vice versa). We aim to bridge the information gap by learning a robust consensus for link-based and attribute-based representations so that nodes become comparable in the latent space. Also, the link-based and attribute-based representations can lend strength to each other via this consensus learning. Moreover, attribute selection is performed jointly with the representation learning to alleviate the effect of noisy high-dimensional attributes. We present two instantiations of this framework with different loss functions and develop an alternating optimization framework to solve the problem. Experimental results on four real-world datasets show the proposed algorithm outperforms the baseline methods significantly for cross-view link prediction.