Search

Anomaly detection on attributed graphs is a crucial topic for practical applications. Existing methods suffer from semantic mixture and imbalance issue because they commonly optimize the model based on the loss function for anomaly discrimination, mainly focusing on anomaly discrimination and ignoring representation learning. Graph Neural networks based techniques usually tend to map adjacent nodes into close semantic space. However, anomalous nodes commonly connect with numerous normal nodes directly, conflicting with the assortativity assumption. Additionally, there are far fewer anomalous nodes than normal nodes, leading to the imbalance problem. To address these challenges, a unique algorithm, decoupled self-supervised learning for anomaly detection (DSLAD), is proposed in this paper. DSLAD is a self-supervised method with anomaly discrimination and representation learning decoupled for anomaly detection. DSLAD employs bilinear pooling and masked autoencoder as the anomaly discriminators. By decoupling anomaly discrimination and representation learning, a balanced feature space is constructed, in which nodes are more semantically discriminative, as well as imbalance issue can be resolved. Experiments conducted on various six benchmark datasets reveal the effectiveness of DSLAD. [ABSTRACT FROM AUTHOR]

This survey article presents a comprehensive and conceptual overview of anomaly detection (AD) using dynamic graphs. We focus on existing graph-based AD techniques and their applications to dynamic networks. The contributions of this survey article include the following: (i) a comparative study of existing surveys on AD; (ii) a Dynamic Graph-based anomaly detection (DGAD) review framework in which approaches for detecting anomalies in dynamic graphs are grouped based on traditional machine learning models, matrix transformations, probabilistic approaches, and deep learning approaches; (iii) a discussion of graphically representing both discrete and dynamic networks; and (iv) a discussion of the advantages of graph-based techniques for capturing the relational structure and complex interactions in dynamic graph data. Finally, this work identifies the potential challenges and future directions for detecting anomalies in dynamic networks. This DGAD survey approach aims to provide a valuable resource for researchers and practitioners by summarizing the strengths and limitations of each approach, highlighting current research trends, and identifying open challenges. In doing so, it can guide future research efforts and promote advancements in AD in dynamic graphs. [ABSTRACT FROM AUTHOR]

Applications of graph mining have proliferated across the research spectrum in recent years. Mining data to retrieve information is a big deal as data are unstructured and huge in size, volume and in different data-types as internet is available to everyone and anywhere. Therefore data is so rapidly increased and for that point this mining concept came. In graph mining, analysis of graph base data is considered. In different research fields use graph base mining as it give quick and efficient result of large datasets. Here we consider biological data which are very complex to describe and analyse to extract useful information, so now researchers use computational tools to mine the large datasets, graphs are the most efficiently used. We consider amino acid network to do graph mining and extract some useful patterns from the network. Amino Acid Networks (AANs) are undirected graphs where amino acids are act like vertices and their relationships connect two vertices in protein structures. Every amino acid exhibits different physico-chemical properties. The shift in R groups affects various characteristics of the amino acids. The shift in R groups affects the various characteristics of the amino acids. In this paper we have construct a graph of amino acids based on property similarity and discussed different measures of centrality. We have also investigated the correlation coefficients between different measures of centrality.

As a universal computational model in quantum computing, the quantum walk is employed in secure communication, quick query, similar calculation, graph mining, etc. At present, researchers have paid limited attention to the design, development, and relationship between models and algorithms of the quantum walk. Further, the theoreticals advantages of the quantum walk on graphs in graph computing are neglected. Aiming at the quantum walk model and algorithms for graph data, firstly, the core design strategy and theoretical advantages of quantum walks are analyzed, the construction form of significant operators and spatial dimension characteristics of relevant algorithms are summarized, and the logical relationship between model and algorithm is clarified. Secondly, according to the classification of discrete-time and continuous-time, the research advances and design difficulties of the quantum walk model are summarized, and the evolutionary trend of quantum walk extending from regular graphs to irregular graphs is concluded. Furthermore, around the similarity calculation of graphs, spatial search, and graph mining, the research progress of quantum walk algorithms is reviewed, and the technical characteristics, advantages and shortcomings of relevant algorithms are analyzed. Finally, from the perspectives of efficiency optimization, accuracy improvement, unitary constraints, and graph reconstruction, the future research directions of the quantum walk models and algorithms are prospected.

Recommender system helps address information overload problem and satisfy consumers' personalized requirement in many applications such as e-commerce, social networks, and in-game store. However, existing approaches mainly focus on improving the accuracy of recommendation tasks but usually ignore how to improve the interpretability of recommendation, which is still a challenging and crucial task, especially for some complicated scenarios such as large-scale online games. A few previous attempts on explainable recommendation mostly depend on a large amount of a priori knowledge or user-provided review corpus, which is labor consuming as well as often suffers from data deficiency. To relieve this issue, we propose a Multi-source Heterogeneous Graph Attention Network for Explainable Recommendation (MHANER) for the case without enough a priori knowledge or corpus of user comments. Specifically, MHANER employs the attention mechanism to model players' preference to in-game store items as the support for the explanation of recommendation. Then a graph neural network–based method is designed to model players' multi-source heterogeneous information, including the players' historical behavior data, historical purchase data, and attributes of the player-controlled character, which is leveraged to recommend possible items for players to buy. Finally, the multi-level subgraph pattern mining is adopted to combine the characteristics of a recommendation list to generate corresponding explanations of items. Extensive experiments on three real-world datasets, two collected from JD and one from NetEase game, demonstrate that the proposed model MHANER outperforms state-of-the-art baselines. Moreover, the generated explanations are verified by human encoding comprised of hard-core game players and endorsed by experts from game developers. [ABSTRACT FROM AUTHOR]

A combination of tools and methods known as "graph mining" is used to evaluate real-world graphs, forecast the potential effects of a given graph's structure and properties for various applications, and build models that can yield actual graphs that closely resemble the structure seen in real-world graphs of interest. However, some graph mining approaches possess scalability and dynamic graph challenges, limiting practical applications. In machine learning and data mining, among the unique methods is graph embedding, known as network representation learning where representative methods suggest encoding the complicated graph structures into embedding by utilizing specific pre-defined metrics. Co-occurrence graphs and keyword searches are the foundation of search engine optimizations for diverse real-world applications. Current work on keyword searches on graphs is based on pre-established information retrieval search criteria and does not provide semantic linkages. Recent works on co-occurrence and keyword search methods function effectively on graphs with only one layer instead of many layers. However, the graph neural network has been utilized in recent years as a branch of graph model due to its excellent performance. This paper proposes an Effective Keyword Search Co-occurrence Multi-Layer Graph mining method by employing two core approaches: Multi-layer Graph Embedding and Graph Neural Networks. We conducted extensive tests using benchmarks on real-world data sets. Considering the experimental findings, the proposed method enhanced with the regularization approach is substantially excellent, with a 10% increment in precision, recall, and f1-score. [ABSTRACT FROM AUTHOR]

The growth in academic and scientific publications has increased very rapidly. Researchers must choose a representative and significant literature for their research, which has become challenging worldwide. Usually, the paper citation number indicates this paper's potential influence and importance. However, this standard metric of citation numbers is not suitable to assess the popularity and significance of recently published papers. To address this challenge, this study presents an effective prediction method called FutureCite to predict the future citation level of research articles. FutureCite integrates machine learning with text and graph mining techniques, leveraging their abilities in classification, datasets in-depth analysis, and feature extraction. FutureCite aims to predict future citation levels of research articles applying a multilabel classification approach. FutureCite can extract significant semantic features and capture the interconnection relationships found in scientific articles during feature extraction using textual content, citation networks, and metadata as feature resources. This study's objective is to contribute to the advancement of effective approaches impacting the citation counts in scientific publications by enhancing the precision of future citations. We conducted several experiments using a comprehensive publication dataset to evaluate our method and determine the impact of using a variety of machine learning algorithms. FutureCite demonstrated its robustness and efficiency and showed promising results based on different evaluation metrics. Using the FutureCite model has significant implications for improving the researchers' ability to determine targeted literature for their research and better understand the potential impact of research publications. [ABSTRACT FROM AUTHOR]

Finding the densest subgraph has tremendous potential in computer vision and social network research, among other domains. In computer vision, it can demonstrate essential structures, and in social network research, it aids in identifying closely associated communities. The densest subgraph problem is finding a subgraph with maximum mean density. However, most densest subgraph-finding algorithms are based on edge-weighted graphs, where edge weights can only represent a single value dimension, whereas practical applications involve multiple dimensions. To resolve the challenge, we propose two algorithms for resolving the densest subgraph problem in a vertex-weighted graph. First, we present an exact algorithm that builds upon Goldberg's original algorithm. Through theoretical exploration and analysis, we rigorously verify our proposed algorithm's correctness and confirm that it can efficiently run in polynomial time O(n(n + m)log2n) is its temporal complexity. Our approach can be applied to identify closely related subgroups demonstrating the maximum average density in real-life situations. Additionally, we consistently offer an approximation algorithm that guarantees an accurate approximation ratio of 2. In conclusion, our contributions enrich theoretical foundations for addressing the densest subgraph problem. [ABSTRACT FROM AUTHOR]

The article introduces a dual meta-learning (DML) technique to enhance semi-supervised text classification, improving both teacher and student classifiers iteratively. Topics include the challenge of noisy pseudo-labels in semi-supervised text classification, the proposed meta-learning methods for noise correction and pseudo supervision, and the experimental validation demonstrating the effectiveness of the DML framework.

Copyright of Journal of Frontiers of Computer Science & Technology is the property of Beijing Journal of Computer Engineering & Applications Journal Co Ltd. and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

Listing dense subgraphs is a fundamental task with a variety of network analytics applications. A lot of research has been done focusing on |$k$| -cliques, i.e. complete subgraphs on |$k$| nodes. However, requiring complete connectivity between the nodes of a subgraph may be too restrictive in many real applications. Hence, in this paper, we consider a natural relaxation of cliques, called |$k$| -diamonds and defined as cliques of size |$k$| with one missing edge. We first provide a sequential algorithm that, in |$O(nm^{(k-1)/2})$| time, counts and lists all the |$k$| -diamonds in large graphs, for any constant |$k \geq 4$|⁠. A parallel extension of the sequential algorithm is then proposed and analyzed in a MapReduce-style model, achieving the same local and total space usage of the state-of-the-art algorithms for |$k$| -cliques. The running time is optimal on dense graphs and |$O(\sqrt{m})$| larger than |$k$| -clique counting if the graph is sparse. Our algorithms compute induced diamonds by analyzing the structure of directed stars formed by the graph nodes and their neighbors. [ABSTRACT FROM AUTHOR]

Abstract Anomaly detection on attributed graphs is a crucial topic for practical applications. Existing methods suffer from semantic mixture and imbalance issue because they commonly optimize the model based on the loss function for anomaly discrimination, mainly focusing on anomaly discrimination and ignoring representation learning. Graph Neural networks based techniques usually tend to map adjacent nodes into close semantic space. However, anomalous nodes commonly connect with numerous normal nodes directly, conflicting with the assortativity assumption. Additionally, there are far fewer anomalous nodes than normal nodes, leading to the imbalance problem. To address these challenges, a unique algorithm, decoupled self-supervised learning for anomaly detection (DSLAD), is proposed in this paper. DSLAD is a self-supervised method with anomaly discrimination and representation learning decoupled for anomaly detection. DSLAD employs bilinear pooling and masked autoencoder as the anomaly discriminators. By decoupling anomaly discrimination and representation learning, a balanced feature space is constructed, in which nodes are more semantically discriminative, as well as imbalance issue can be resolved. Experiments conducted on various six benchmark datasets reveal the effectiveness of DSLAD.

Abstract As a knowledge representation method, knowledge graph is widely used in intelligent question answering systems and recommendation systems. At present, the research on knowledge graph mainly focuses on information query and retrieval based on knowledge graph. In some domain knowledge graphs, specific subgraph structures (patterns) have specific physical meanings. Aiming at this problem, this paper proposes a method and framework of knowledge graph pattern mining based on gat. Firstly, the patterns with specific physical meaning were transformed into subgraph structures containing topological structures and entity attributes. Secondly, the subgraph structure of the pattern is regarded as the query graph, and the knowledge graph is regarded as the data graph, so that the problem is transformed into an approximate subgraph matching problem. Then, the improved relational graph attention network is used to fuse the adaptive edge deletion mechanism to realize the approximate subgraph matching of subgraph structure and attribute, so as to obtain the best matching subgraph. The proposed method is trained in an end-to-end manner. The approximate subgraph matching is realized on the existing data set, and the research work of key pattern mining of complex geological structure knowledge graph is carried out.

As a knowledge representation method, knowledge graph is widely used in intelligent question answering systems and recommendation systems. At present, the research on knowledge graph mainly focuses on information query and retrieval based on knowledge graph. In some domain knowledge graphs, specific subgraph structures (patterns) have specific physical meanings. Aiming at this problem, this paper proposes a method and framework of knowledge graph pattern mining based on gat. Firstly, the patterns with specific physical meaning were transformed into subgraph structures containing topological structures and entity attributes. Secondly, the subgraph structure of the pattern is regarded as the query graph, and the knowledge graph is regarded as the data graph, so that the problem is transformed into an approximate subgraph matching problem. Then, the improved relational graph attention network is used to fuse the adaptive edge deletion mechanism to realize the approximate subgraph matching of subgraph structure and attribute, so as to obtain the best matching subgraph. The proposed method is trained in an end-to-end manner. The approximate subgraph matching is realized on the existing data set, and the research work of key pattern mining of complex geological structure knowledge graph is carried out. [ABSTRACT FROM AUTHOR]

Social networks such as Facebook, Twitter, etc. have dramatically increased in recent years. These databases are huge and their use is time consuming. In this work, we present an optimal calculation in graph mining for link prediction to reduce the runtime. For that purpose, we propose a novel approach that operates on the connected components of a network instead of the whole network. We show that thanks to this decomposition, the results of all link prediction algorithms using local and path-based similarity measure scan be achieved with much less amount of computations and hence within much shorter runtime. We show that this gain depends on the distribution of nodes in components and may be captured by the Gini and the variance measures. We propose a parallel architecture of the link prediction process based on the connected components decomposition. To validate this architecture, we have carried out an experimental study on a wide range of well-known datasets. The obtained results clearly confirm the efficiency of exploiting the decomposition of the network into connected components in link prediction. [ABSTRACT FROM AUTHOR]

Ontologies are domain-specific metadata that describe relationships between a specific field's properties, sample data of this field, and properties developed for many different purposes. Also, ontologies can be defined by other names within the same domain. Ontology matching algorithms eliminate definition differences and find similarities between existing ontologies. Ontology matching algorithms are used especially for information management, data integration, information extraction, etc. In this study, a graph-based framework is proposed to match large ontologies. This framework is aimed to divide the large ontologies into small pieces and then matches them using sub-graph mining algorithms. Karger algorithm and CP (clique percolation and nearest neighbor) algorithm are used to divide large ontologies. Both algorithms were applied to ontologies for the first time. In the next step, these obtained sub-parts are matched by using sub-graph mining algorithms. GraMi and gSpan algorithms were selected and were used for the first time in the field of ontology matching. We validated our framework using Anatomy and Conference data sets. Also, the proposed framework is compared with widely used in the literature AML and Falcon-AO matching algorithms. According to obtained the results, it is seen that GraMi is better than matching algorithms. [ABSTRACT FROM AUTHOR]

Detecting misbehavior in social networks is essential for maintaining trust and reliability in online communities. Traditional methods of identification often rely on individual attributes or structural network properties, which may overlook subtle or complex misbehavior patterns. This paper introduces a novel approach called OCMLMD that leverages network overlapping community structure and machine learning techniques to detect misbehavior. Our method combines graph-based analyses of network topology with state-of-theart machine learning algorithms to identify suspicious behavior indicative of misbehavior. Specifically, we target nodes that belong to multiple communities or exhibit weak connections within their community, utilizing a novel metric for selecting overlapping nodes. Additionally, we develop a machine learning model trained on relevant attributes extracted from social network data to detect misbehavior accurately. Extensive experiments on synthetic and real-world social network datasets demonstrate the superior performance of OCMLMD compared to baseline methods. Overall, our proposed approach offers a promising solution to the challenge of detecting misbehavior in social networks.

We have developed a classification method that segments a large group of Amazon or TikTok users into distinct categories, or “genres,” based on their shared purchasing behaviors, such as preferences for consumer electronics or household items. Our approach uses a geometry-based feature selection strategy to accurately capture each user’s buying patterns, which are characterized by a range of features, including those learned under weak supervision. These features are then refined through two feature selection processes tailored to different application needs. We also use a probabilistic model to represent each user’s buying preferences as a distribution within a hidden feature space. To map the purchasing connections between users, we construct a graph and apply a specialized algorithm to identify tightly connected subgroups. These subgroups reflect shared purchasing habits, allowing us to categorize users into specific genres. Finally, a ranking model is used to recommend products to users based on these genres. We validated the effectiveness of our recommendation system using a dataset of over one million Amazon users, showing that it accurately identifies and classifies distinct purchasing genres.

Investigating credit risk in contemporary entrepreneurial debt analysis is the key for maintaining financial stability. Entrepreneurial debt management, facilitated by innovative financing models, is significant in fostering economic as well as social development. However, due to certain imperfections in these financial systems, this model is exposed to considerable risks. To precisely predict the risk level of each entrepreneurial debt, this paper presents a novel methodology combining a massive-scale affinity graph construction and efficient subgraph mining for categorizing each entrepreneurial debt into one of the multiple debt-level subgraphs. This approach marks a substantial contribution to the advancement and generalization of entrepreneurial debt management systems. For extensively testifying our approach, we collected a huge data set containing entrepreneurial debt information from nearly 1.41 million company with different sizes throughout the world. Our experimental results showed that our designed method achieves an impressive 97.93% accuracy in predict different risk levels in entrepreneurial debt management, highlighting its efficacy and potential for broad implementation.

The explosive growth of cyber attacks today, such as malware, spam, and intrusions, has caused severe consequences on society. Securing cyberspace has become a great concern for organizations and governments. Traditional machine learning based methods are extensively used in detecting cyber threats, but they hardly model the correlations between real-world cyber entities. In recent years, with the proliferation of graph mining techniques, many researchers have investigated these techniques for capturing correlations between cyber entities and achieving high performance. It is imperative to summarize existing graph-based cybersecurity solutions to provide a guide for future studies. Therefore, as a key contribution of this work, we provide a comprehensive review of graph mining for cybersecurity, including an overview of cybersecurity tasks, the typical graph mining techniques, and the general process of applying them to cybersecurity, as well as various solutions for different cybersecurity tasks. For each task, we probe into relevant methods and highlight the graph types, graph approaches, and task levels in their modeling. Furthermore, we collect open datasets and toolkits for graph-based cybersecurity. Finally, we present an outlook on the potential directions of this field for future research. [ABSTRACT FROM AUTHOR]

For real-world graph data, the node class distribution is inherently imbalanced and long-tailed, which naturally leads to a few-shot learning scenario with limited nodes labeled for newly emerging classes. There are many carefully designed solutions for such a few-shot learning problem via methods such as data augmentation, learning transferable initialization, learning prototypes, and many more. However, most, if not all, of them are based on a strong assumption that all the test nodes exclusively come from novel classes, which is impractical in real-world applications. In this paper, we study a broader and more realistic problem named generalized few-shot node classification, where the test samples can be from both novel classes and base classes. Compared with the standard few-shot node classification, this new problem imposes several unique challenges, including asymmetric classification and inconsistent preference. To counter those challenges, we propose a shot-aware neural node classifier (Stager) equipped with an uncertainty-based weight assigner module for adaptive propagation. As the existing meta-learning solutions cannot handle this new problem, we propose a novel training paradigm named imbalanced episodic training to ensure the label distribution is consistent between the meta-training and meta-test scenarios. Comprehensive experiments on four real-world datasets demonstrate the effectiveness of our proposed model and training paradigm. [ABSTRACT FROM AUTHOR]

Graph mining has emerged as a significant field of research with applications spanning multiple domains, including marketing, corruption analysis, business, and politics. The exploration of knowledge within graphs has garnered considerable attention due to the exponential growth of graph-modeled data and its potential in applications where data relationships are a crucial component, and potentially being even more important than the data themselves. However, the increasing use of graphs for data storing and modeling presents unique challenges that have prompted advancements in graph mining algorithms, data modeling and storage, query languages for graph databases, and data visualization techniques. Despite there being various methodologies for data analysis, they predominantly focus on structured data and may not be optimally suited for highly connected data. Accordingly, this work introduces a novel methodology specifically tailored for knowledge discovery in labeled and heterogeneous graphs (KDG), and it presents three case studies demonstrating its successful application in addressing various challenges across different application domains. [ABSTRACT FROM AUTHOR]

Clustering is a very important method to analyze HIN. Thus, several HIN clustering algorithms have been proposed and all these algorithms are based on meta-paths. Meta-path can be used to describe the relationship of target objects. Even though the relationship of target objects are fully considered by these meta-path based algorithms, the directly connected neighbors of target objects are neglected by them. These neglected directly connected neighbors are not target objects, but they contain plenty of useful information for finding clusters of target objects. So, while performing clustering based on HIN, these neglected neighbors should be considered. To achieve the goal, in this paper, a new HIN clustering algorithm is proposed. The proposed algorithm tries to build a vector for each target object. The clustering task is fulfilled based on these vectors. During the vector building process, the neighbors of all the target objects are considered. As clustering result of HIN is affected by different factors, such as neighbors of target objects and different kinds of meta-paths, several similarity matrices are built in the proposed algorithm. Each matrix is corresponding to a specific factor. Besides, every matrix will be assigned a weight value. These weight values are used to represent the relative importance of factors. At the same time, in the proposed algorithm, a new training method is adopted to calculate the vectors and the weight values. [ABSTRACT FROM AUTHOR]

A hypergraph is a complex data structure capable of expressing associations among any number of data entities. Overcoming the limitations of traditional graphs, hypergraphs are useful to model real-life problems. Frequent pattern mining is one of the most popular problems in data mining with a lot of applications. To the best of our knowledge, there exists no flexible pattern mining framework for hypergraph databases decomposing associations among data entities. In this article, we propose a flexible and complete framework for mining frequent patterns from a collection of hypergraphs. To discover more interesting patterns beyond the traditional frequent patterns, we propose frameworks for weighted and uncertain hypergraph mining also. We develop three algorithms for mining frequent, weighted, and uncertain hypergraph patterns efficiently by introducing a canonical labeling technique for isomorphic hypergraphs. Extensive experiments have been conducted on real-life hypergraph databases to show both the effectiveness and efficiency of our proposed frameworks and algorithms. [ABSTRACT FROM AUTHOR]

Abstract Apart from nodes and links, for many networked systems, we have access to data on paths, i.e., collections of temporally ordered variable-length node sequences that are constrained by the system’s topology. Understanding the patterns in such data is key to advancing our understanding of the structure and dynamics of complex systems. Moreover, the ability to accurately model and predict paths is important for engineered systems, e.g., to optimise supply chains or provide smart mobility services. Here, we introduce MOGen, a generative modelling framework that enables both next-element and out-of-sample prediction in paths with high accuracy and consistency. It features a model selection approach that automatically determines the optimal model directly from data, effectively making MOGen parameter-free. Using empirical data, we show that our method outperforms state-of-the-art sequence modelling techniques. We further introduce a mathematical formalism that links higher-order models of paths to transition matrices of random walks in multi-layer networks.

The growth in academic and scientific publications has increased very rapidly. Researchers must choose a representative and significant literature for their research, which has become challenging worldwide. Usually, the paper citation number indicates this paper’s potential influence and importance. However, this standard metric of citation numbers is not suitable to assess the popularity and significance of recently published papers. To address this challenge, this study presents an effective prediction method called FutureCite to predict the future citation level of research articles. FutureCite integrates machine learning with text and graph mining techniques, leveraging their abilities in classification, datasets in-depth analysis, and feature extraction. FutureCite aims to predict future citation levels of research articles applying a multilabel classification approach. FutureCite can extract significant semantic features and capture the interconnection relationships found in scientific articles during feature extraction using textual content, citation networks, and metadata as feature resources. This study’s objective is to contribute to the advancement of effective approaches impacting the citation counts in scientific publications by enhancing the precision of future citations. We conducted several experiments using a comprehensive publication dataset to evaluate our method and determine the impact of using a variety of machine learning algorithms. FutureCite demonstrated its robustness and efficiency and showed promising results based on different evaluation metrics. Using the FutureCite model has significant implications for improving the researchers’ ability to determine targeted literature for their research and better understand the potential impact of research publications.

Finding the densest subgraph has tremendous potential in computer vision and social network research, among other domains. In computer vision, it can demonstrate essential structures, and in social network research, it aids in identifying closely associated communities. The densest subgraph problem is finding a subgraph with maximum mean density. However, most densest subgraph-finding algorithms are based on edge-weighted graphs, where edge weights can only represent a single value dimension, whereas practical applications involve multiple dimensions. To resolve the challenge, we propose two algorithms for resolving the densest subgraph problem in a vertex-weighted graph. First, we present an exact algorithm that builds upon Goldberg’s original algorithm. Through theoretical exploration and analysis, we rigorously verify our proposed algorithm’s correctness and confirm that it can efficiently run in polynomial time O(n(n + m)log2n) is its temporal complexity. Our approach can be applied to identify closely related subgroups demonstrating the maximum average density in real-life situations. Additionally, we consistently offer an approximation algorithm that guarantees an accurate approximation ratio of 2. In conclusion, our contributions enrich theoretical foundations for addressing the densest subgraph problem.

Group interactions are prevalent in a variety of areas. Many of them, including email exchanges, chemical reactions, and bitcoin transactions, are directional, and thus they are naturally modeled as directed hypergraphs, where each hyperarc consists of the set of source nodes and the set of destination nodes. For directed graphs, which are a special case of directed hypergraphs, reciprocity has played a key role as a fundamental graph statistic in revealing organizing principles of graphs and in solving graph learning tasks. For general directed hypergraphs, however, even no systematic measure of reciprocity has been developed. In this work, we investigate the reciprocity of 11 real-world hypergraphs. To this end, we first introduce eight axioms that any reasonable measure of reciprocity should satisfy. Second, we propose HyperRec, a family of principled measures of hypergraph reciprocity that satisfy all the axioms. Third, we develop FastHyperRec, a fast and exact algorithm for computing the measures. Fourth, using them, we examine 11 real-world hypergraphs and discover patterns that distinguish them from random hypergraphs. Lastly, we propose ReDi, an intuitive generative model for directed hypergraphs exhibiting the patterns. [ABSTRACT FROM AUTHOR]

What are the relations between the edge weights and the topology in real-world graphs? Given only the topology of a graph, how can we assign realistic weights to its edges based on the relations? Several trials have been done for edge-weight prediction where some unknown edge weights are predicted with most edge weights known. There are also existing works on generating both topology and edge weights of weighted graphs. Differently, we are interested in generating edge weights that are realistic in a macroscopic scope, merely from the topology, which is unexplored and challenging. To this end, we explore and exploit the patterns involving edge weights and topology in real-world graphs. Specifically, we divide each graph into layers where each layer consists of the edges with weights at least a threshold. We observe consistent and surprising patterns appearing in multiple layers: the similarity between being adjacent and having high weights, and the nearly-linear growth of the fraction of edges having high weights with the number of common neighbors. We also observe a power-law pattern that connects the layers. Based on the observations, we propose PEAR, an algorithm assigning realistic edge weights to a given topology. The algorithm relies on only two parameters, preserves all the observed patterns, and produces more realistic weights than the baseline methods with more parameters. [ABSTRACT FROM AUTHOR]

The rapid development of large language models has significantly reduced the cost of producing rumors, which brings a tremendous challenge to the authenticity of content on social media. Therefore, it has become crucially important to identify and detect rumors. Existing deep learning methods usually require a large amount of labeled data, which leads to poor robustness in dealing with different types of rumor events. In addition, they neglect to fully utilize the structural information of rumors, resulting in a need to improve their identification and detection performance. In this article, we propose a new rumor detection framework based on bi-directional multi-level graph contrastive learning, BiMGCL, which models each rumor propagation structure as bi-directional graphs and performs self-supervised contrastive learning based on node-level and graph-level instances. In particular, BiMGCL models the structure of each rumor event with fine-grained bidirectional graphs that effectively consider the bi-directional structural characteristics of rumor propagation and dispersion. Moreover, BiMGCL designs three types of interpretable bi-directional graph data augmentation strategies and adopts both node-level and graph-level contrastive learning to capture the propagation characteristics of rumor events. Experimental results on real datasets demonstrate that our proposed BiMGCL achieves superior detection performance compared against the state-of-the-art rumor detection methods. [ABSTRACT FROM AUTHOR]

With the progressive improvements in the power, effectiveness, and reliability of AI solutions, more and more critical human problems are being handled by automated AI-based tools and systems. For more complex or particularly critical applications, the level of knowledge, not just information, must be handled by systems where explicit relationships among objects are represented and processed. For this purpose, the knowledge representation branch of AI proposes Knowledge Graphs, widely used in the Semantic Web, where different online applications may interact by understanding the meaning of the data they process and exchange. This paper describes a framework and online platform for the Internet-based knowledge graph definition, population, and exploitation based on the LPG graph model. Its main advantages are its efficiency and representational power and the wide range of functions that it provides to its users beyond traditional Semantic Web reasoning: network analysis, data mining, multistrategy reasoning, and knowledge browsing. Still, it can also be mapped onto the SW. [ABSTRACT FROM AUTHOR]

Nowadays, whereas the use of social networks and computer networks is increasing, the amount of associated complex data with graph structure and their applications, such as classification, clustering, link prediction, and recommender systems, has risen significantly. Because of security problems and societal concerns, anomaly detection is becoming a vital problem in most fields. Applications that use a heterogeneous graph, are confronted with many issues, such as different kinds of neighbors, different feature types, and differences in type and number of links. So, in this research, we employ the HetGNN model with some changes in loss functions and parameters for heterogeneous graph embedding to capture the whole graph features (structure and content) for anomaly detection, then pass it to a VAE to discover anomalous nodes based on reconstruction error. Our experiments on AMiner data set with many base-lines illustrate that our model outperforms state-of-the-arts methods in heterogeneous graphs while considering all types of attributes.

Circuit obfuscation is a recently proposed defense mechanism to protect the intellectual property (IP) of digital integrated circuits (ICs) from reverse engineering. There have been effective schemes, such as satisfiability (SAT)-checking based attacks that can potentially decrypt obfuscated circuits, which is called deobfuscation. Deobfuscation runtime could be days or years, depending on the layouts of the obfuscated ICs. Hence, accurately pre-estimating the deobfuscation runtime within a reasonable amount of time is crucial for IC designers to optimize their defense. However, it is challenging due to (1) the complexity of graph-structured circuit; (2) the varying-size topology of obfuscated circuits; (3) requirement on efficiency for deobfuscation method. This study proposes a framework that predicts the deobfuscation runtime based on graph deep learning techniques to address the challenges mentioned above. A conjunctive normal form (CNF) bipartite graph is utilized to characterize the complexity of this SAT problem by analyzing the SAT attack method. Multi-order information of the graph matrix is designed to identify the essential features and reduce the computational cost. To overcome the difficulty in capturing the dynamic size of the CNF graph, an energy-based kernel is proposed to aggregate dynamic features into an identical vector space. Then, we designed a framework, Deep Survival Analysis with Graph (DSAG), which integrates energy-based layers and predicts runtime inspired by censored regression in survival analysis. Integrating uncensored data with censored data, the proposed model improves the standard regression significantly. DSAG is an end-to-end framework that can automatically extract the determinant features for deobfuscation runtime. Extensive experiments on benchmarks demonstrate its effectiveness and efficiency.

Market research is an indispensable part of an organization's ability to understand market dynamics. Over the past 20 years, data collection and analysis through Knowledge Discovery through Databases (KDD) has arisen to supplement the traditional methods of surveys and focus groups. Market Basket Analysis is a discipline of KDD that identifies associations between commonly purchased items. As social media use has grown, link shortening companies help users share links in a constrained space environment and, in exchange, collect data about each user when a link is clicked. This research applies market basket analysis techniques with graph mining to shortened web link data to identify communities of co-visited websites to help analysts better understand web traffic for a geographic area during a time range. Patterns within clusters of web domains regarding hardware platforms, operating systems, or referral sources are then identified and used to gain a better understanding of a geographic area. [ABSTRACT FROM AUTHOR]

Graphs are used as a model of complex relationships among data in biological science since the advent of systems biology in the early 2000. In particular, graph data analysis and graph data mining play an important role in biology interaction networks, where recent techniques of artificial intelligence, usually employed in other type of networks (e.g., social, citations, and trademark networks) aim to implement various data mining tasks including classification, clustering, recommendation, anomaly detection, and link prediction. The commitment and efforts of artificial intelligence research in network biology are motivated by the fact that machine learning techniques are often prohibitively computational demanding, low parallelizable, and ultimately inapplicable, since biological network of realistic size is a large system, which is characterised by a high density of interactions and often with a non-linear dynamics and a non-Euclidean latent geometry. Currently, graph embedding emerges as the new learning paradigm that shifts the tasks of building complex models for classification, clustering, and link prediction to learning an informative representation of the graph data in a vector space so that many graph mining and learning tasks can be more easily performed by employing efficient non-iterative traditional models (e.g., a linear support vector machine for the classification task). The great potential of graph embedding is the main reason of the flourishing of studies in this area and, in particular, the artificial intelligence learning techniques. In this mini review, we give a comprehensive summary of the main graph embedding algorithms in light of the recent burgeoning interest in geometric deep learning.

Dynamic heterogeneous graphs can represent real-world networks. Predicting links in these graphs is more complicated than in static graphs. Until now, research interest of link prediction has focused on static heterogeneous graphs or dynamically homogeneous graphs. A link prediction technique combining temporal RNN and hierarchical attention has recently emerged, called DyHATR. This method is claimed to be able to work on dynamic heterogeneous graphs by testing them on four publicly available data sets (Twitter, Math-Overflow, Ecomm, and Alibaba). However, after further analysis, it turned out that the four data sets did not meet the criteria of dynamic heterogeneous graphs. In the present work, we evaluated the performance of DyHATR on dynamic heterogeneous graphs. We conducted experiments with DyHATR based on the Yelp data set represented as a dynamic heterogeneous graph consisting of homogeneous subgraphs. The results show that DyHATR can be applied to identify link prediction on dynamic heterogeneous graphs by simultaneously capturing heterogeneous information and evolutionary patterns, and then considering them to carry out link predicition. Compared to the baseline method, the accuracy achieved by DyHATR is competitive, although the results can still be improved.

Session-based travel packages recommendation aims to predict users' next click based on their current and historical sessions recorded by Online Travel Agencies (OTAs). Recently, an increasing number of studies attempted to apply Graph Neural Networks (GNNs) to the session-based recommendation and obtained promising results. However, most of them do not take full advantage of the explicit latent structure from attributes of items, making learned representations of items less effective and difficult to interpret. Moreover, they only combine historical sessions (long-term preferences) with a current session (short-term preference) to learn a unified representation of users, ignoring the effects of historical sessions for the current session. To this end, this article proposes a novel session-based model named STR-VGAE, which fills subtasks of the travel packages recommendation and variational graph auto-encoders simultaneously. STR-VGAE mainly consists of three components: travel packages encoder, users behaviors encoder, and interaction modeling. Specifically, the travel packages encoder module is used to learn a unified travel package representation from co-occurrence attribute graphs by using multi-view variational graph auto-encoders and a multi-view attention network. The users behaviors encoder module is used to encode user' historical and current sessions with a personalized GNN, which considers the effects of historical sessions on the current session, and coalesce these two kinds of session representations to learn the high-quality users' representations by exploiting a gated fusion approach. The interaction modeling module is used to calculate recommendation scores over all candidate travel packages. Extensive experiments on a real-life tourism e-commerce dataset from China show that STRVGAE yields significant performance advantages over several competitive methods, meanwhile provides an interpretation for the generated recommendation list. [ABSTRACT FROM AUTHOR]

The cover time of random walks on a graph has found wide practical applications in different fields of computer science, such as crawling and searching on the World Wide Web and query processing in sensor networks, with the application effects dependent on the behavior of the cover time: the smaller the cover time, the better the application performance. It was proved that over all graphs with N nodes, complete graphs have the minimum cover time N log N. However, complete graphs cannot mimic real-world networks with small average degree and scale-free small-world properties, for which the cover time has not been examined carefully, and its behavior is still not well understood. In this article, we first experimentally evaluate the cover time for various real-world networks with scale-free small-world properties, which scales as N log N. To better understand the behavior of the cover time for real-world networks, we then study the cover time of three scale-free small-world model networks by using the connection between cover time and resistance diameter. For all the three networks, their cover time also behaves as N log N. This work indicates that sparse networks with scale-free and small-world topology are favorable architectures with optimal scaling of cover time. Our results deepen understanding the behavior of cover time in real-world networks with scale-free small-world structure, and have potential implications in the design of efficient algorithms related to cover time. [ABSTRACT FROM AUTHOR]