Network motifs, as a fundamental higher-order structure in large-scale networks, have received significant attention over recent years. Particularly in heterogeneous networks, motifs offer a higher capacity to uncover diverse information compared to homogeneous networks. However, the structural complexity and heterogeneity pose challenges in coding, counting, and profiling heterogeneous motifs. This work addresses these challenges by first introducing a novel heterogeneous motif coding method, adaptable to homogeneous motifs as well. Building upon this coding framework, we then propose GIFT, a heterogeneous network motif counting algorithm. GIFT effectively leverages combined structures of heterogeneous motifs through three key procedures: neighborhood searching, motif combination, and redundant motif filtering. We apply GIFT to count three-order and four-order motifs across eight distinct heterogeneous networks. Subsequently, we profile these detected motifs using four classical motif-based indicators. Experimental results demonstrate that by appropriately selecting motifs tailored to specific networks, heterogeneous motifs emerge as significant features in characterizing the underlying network structure.

Data explosion in the information society drives people to develop more effective ways to extract meaningful information. Extracting semantic information and relational information has emerged as a key mining primitive in a wide variety of practical applications. Existing research on relation mining has primarily focused on explicit connections and ignored underlying information, e.g., the latent entity relations. Exploring such information (defined as implicit relationships in this article) provides an opportunity to reveal connotative knowledge and potential rules. In this article, we propose a novel research topic, i.e., how to identify implicit relationships across heterogeneous networks. Specially, we first give a clear and generic definition of implicit relationships. Then, we formalize the problem and propose an efficient solution, namely MIRROR, a graph convolutional network (GCN) model to infer implicit ties under explicit connections. MIRROR captures rich information in learning node-level representations by incorporating attributes from heterogeneous neighbors. Furthermore, MIRROR is tolerant of missing node attribute information because it is able to utilize network structure. We empirically evaluate MIRROR on four different genres of networks, achieving state-of-the-art performance for target relations mining. The underlying information revealed by MIRROR contributes to enriching existing knowledge and leading to novel domain insights.

Discovering causal relationships among observed variables is an important research focus in data mining. Existing causal discovery approaches are mainly based on constraint-based methods and functional causal models (FCMs). However, the constraint-based method cannot identify the Markov equivalence class and the functional causal models cannot identify the complex interrelationships when multiple variables affect one variable. To address the two aforementioned problems, we propose a new graph structure Causal Star Graph (CSG) and a corresponding framework Causal Discovery via Causal Star Graphs (CD-CSG) to divide a causal directed acyclic graph into multiple CSGs for causal discovery. In this framework, we also propose a generalized learning in CSGs based on a variational approach to learn the representative intermediate variable of CSG’s non-central variables. Through the generalized learning in CSGs, the asymmetry in the forward and backward model of CD-CSG can be found to identify the causal directions in the directed acyclic graphs. We further divide the CSGs into three categories and provide the causal identification principle under each category in our proposed framework. Experiments using synthetic data show that the causal relationships between variables can be effectively identified with CD-CSG and the accuracy of CD-CSG is higher than the best existing model. By applying CD-CSG to real-world data, our proposed method can greatly augment the applicability and effectiveness of causal discovery.

Discovering causal relationships among observed variables is a new research focus in the area of data mining. Methods based on the additive noise model have been proved to be efficient in the identification of cause-effect pairs. However, when trying to determine many-to-one causality, additive noise models often fail to identify the causal direction due to the complex interrelationships and interactions even though the generation of each causal relation follows the additive noise model, and become unreliable in practical applications. In this work, to identify the causal direction, we propose a Hierarchical Additive Noise Model (HANM) to convert many-to-one causality into an approximate one-to-one causality by generalizing multiple factors into an intermediate variable with a variational approach, and use asymmetry in the forward model and backward model of HANM to identify causal direction. Experiments using synthetic data show that many-to-one causality can be effectively identified through asymmetry with our proposed HANM and the accuracy of HANM is higher than the best existing model. By applying the model to real-world data, it can be seen that HANM can greatly augment the application scope of functional causal models for causal discovery.

Anomaly detection from graph data has drawn much attention due to its practical significance in many critical applications including cybersecurity, finance, and social networks. Existing data mining and machine learning methods are either shallow methods that could not effectively capture the complex interdependency of graph data or graph autoencoder methods that could not fully exploit the contextual information as supervision signals for effective anomaly detection. To overcome these challenges, in this paper, we propose a novel method, Self-Supervised Learning for Graph Anomaly Detection (SL-GAD). Our method constructs different contextual subgraphs (views) based on a target node and employs two modules,generative attribute regressionandmulti-view contrastive learningfor anomaly detection. While thegenerative attribute regressionmodule allows us to capture the anomalies in the attribute space, themulti-view contrastive learningmodule can exploit richer structure information from multiple subgraphs, thus abling to capture the anomalies in the structure space, mixing of structure, and attribute information. We conduct extensive experiments on six benchmark datasets and the results demonstrate that our method outperforms state-of-the-art methods by a large margin.

Anomaly detection on graphs plays a significant role in various domains, including cybersecurity, e-commerce, and financial fraud detection. However, existing methods on graph anomaly detection usually consider the view in a single scale of graphs, which results in their limited capability to capture the anomalous patterns from different perspectives. Towards this end, we introduce a novel graph anomaly detection framework, namely ANEMONE, to simultaneously identify the anomalies in multiple graph scales. Concretely, ANEMONE first leverages a graph neural network backbone encoder with multi-scale contrastive learning objectives to capture the pattern distribution of graph data by learning the agreements between instances at the patch and context levels concurrently. Then, our method employs a statistical anomaly estimator to evaluate the abnormality of each node according to the degree of agreement from multiple perspectives. Experiments on three benchmark datasets demonstrate the superiority of our method.

In this work, we demonstrate a novel system, namely Web of Scholars, which integrates state-of-the-art mining techniques to search, mine, and visualize complex networks behind scholars in the field of Computer Science. Relying on the knowledge graph, it provides services for fast, accurate, and intelligent semantic querying as well as powerful recommendations. In addition, in order to realize information sharing, it provides open API to be served as the underlying architecture for advanced functions. Web of Scholars takes advantage of knowledge graph, which means that it will be able to access more knowledge if more search exist. It can be served as a useful and interoperable tool for scholars to conduct in-depth analysis within Science of Science.

There have been a number of approximate algorithms for text similarity computation, such as min-wise hashing, random projection, and feature hashing, which are based on the bag-of-words representation. A limitation of their “flat-set” representation is that context information and semantic hierarchy cannot be preserved. In this paper, we aim to fast compute similarities between texts while also preserving context information. To take into account semantic hierarchy, we consider a notion of “multi-level exchangeability” which can be applied at word-level, sentence-level, paragraph-level, etc. We employ a nested-set to represent a multi-level exchangeable object. To fingerprint nested-sets for fast comparison, we propose a Recursive Min-wise Hashing (RMH) algorithm at the same computational cost of the standard min-wise hashing algorithm. Theoretical study and bound analysis confirm that RMH is a highly-concentrated estimator. The empirical studies show that the proposed context-preserving hashing method can significantly outperform min-wise hashing and feature hashing in accuracy at the same (or less) computational cost.

Graph stream classification concerns building learning models from continuously growing graph data, in which an essential step is to explore subgraph features to represent graphs for effective learning and classification. When representing a graph using subgraph features, all existing methods employ coarse-grained feature representation, which only considers whether or not a subgraph feature appears in the graph. In this paper, we propose a fine-grained graph factorization approach for Fast Graph Stream Classification (FGSC). Our main idea is to find a set of cliques as feature base to represent each graph as a linear combination of the base cliques. To achieve this goal, we decompose each graph into a number of cliques and select discriminative cliques to generate a transfer matrix called Clique Set Matrix (M). By using M as the base for formulating graph factorization, each graph is represented in a vector space with each element denoting the degree of the corresponding subgraph feature related to the graph, so existing supervised learning algorithms can be applied to derive learning models for graph classification.

Most studies on graph classification focus on designing fast and effective kernels. Several fast subtree kernels have achieved a linear time-complexity w.r.t. the number of edges under the condition that a common feature space (e.g., a subtree pattern list) is needed to represent all graphs. This will be infeasible when graphs are presented in a stream with rapidly emerging subtree patterns. In this case, computing a kernel matrix for graphs over the entire stream is difficult since the graphs in the expired chunks cannot be projected onto the unlimitedly expanding feature space again. This leads to a big trouble for graph classification over streams -- Different portions of graphs have different feature spaces. In this paper, we aim to enable large-scale graph classification over streams using the classical ensemble learning framework, which requires the data in different chunks to be in the same feature space. To this end, we propose a Nested Subtree Hashing (NSH) algorithm to recursively project the multi-resolution subtree patterns of different chunks onto a set of common low-dimensional feature spaces. We theoretically analyze the derived NSH kernel and obtain a number of favorable properties: 1) The NSH kernel is an unbiased and highly concentrated estimator of the fast subtree kernel. 2) The bound of convergence rate tends to be tighter as the NSH algorithm steps into a higher resolution. 3) The NSH kernel is robust in tolerating concept drift between chunks over a stream. We also empirically test the NSH kernel on both a large-scale synthetic graph data set and a real-world chemical compounds data set for anticancer activity prediction. The experimental results validate that the NSH kernel is indeed efficient and robust for graph classification over streams.