Search

The main results of this paper provide an Efficient Polynomial-Time Approximation Scheme (EPTAS) for approximating the genus (and non-orientable genus) of dense graphs. By dense we mean that \(|E(G)|\ge \alpha \, |V(G)|^2\) for some fixed \(\alpha \gt 0\). While a constant-factor approximation is trivial for this class of graphs, approximations with factor arbitrarily close to 1 need a sophisticated algorithm and complicated mathematical justification. More precisely, we provide an algorithm that for a given (dense) graph G of order n and given \(\varepsilon \gt 0\) , returns an integer g such that G has an embedding in a surface of genus g, and this is ɛ-close to a minimum genus embedding in the sense that the minimum genus \(\mathsf {g}(G)\) of G satisfies: \(\mathsf {g}(G)\le g\le (1+\varepsilon)\mathsf {g}(G)\). The running time of the algorithm is \(O(f(\varepsilon)\,n^2)\) , where \(f(\cdot)\) is an explicit function. Next, we extend this algorithm to also output an embedding (rotation system) whose genus is g. This second algorithm is an Efficient Polynomial-time Randomized Approximation Scheme (EPRAS) and runs in time \(O(f_1(\varepsilon)\,n^2)\). Our algorithms are based on the analysis of minimum genus embeddings of quasirandom graphs. We use a general notion of quasirandom graphs [25]. We start with a regular partition obtained via an algorithmic version of the Szemerédi Regularity Lemma (due to Frieze and Kannan [17] and to Fox, Lovász, and Zhao [14, 15]). We then partition the input graph into a bounded number of quasirandom subgraphs, which are preselected in such a way that they admit embeddings using as many triangles and quadrangles as faces as possible. Here we provide an ɛ-approximation \(\nu (G)\) for the maximum number of edge-disjoint triangles in G. The value \(\nu (G)\) can be computed by solving a linear program whose size is bounded by certain value \(f_2(\varepsilon)\) depending only on ɛ. After solving the linear program, the genus can be approximated (see Corollary 1.7). The proof of this result is long and will be of independent interest in topological graph theory. [ABSTRACT FROM AUTHOR]

The unsupervised attribute graph embedding technique aims to learn low-dimensional node embedding using neighborhood topology and attribute information under unlabeled data. Current unsupervised models are mostly based on graph self-encoders, but full-batch training limits the scalability of the model and ignores attribute integrity when reconstructing the topology. In order to solve the above problems while considering the unsupervised learning of the model and full use of node information, this paper proposes a graph neural network architecture based on a graph self-encoder to capture the nonlinearity of the attribute graph data, and an attribute graph embedding algorithm that explicitly models the influence of neighborhood information using a multi-level attention mechanism. Specifically, the proposed algorithm fuses topology information and attribute information using a lightweight sampling strategy, constructs an unbiased graph self-encoder on the sampled graph, implements topology aggregation and attribute aggregation, respectively, models the correlation between topology embedding and attribute embedding, and considers multi-level loss terms. [ABSTRACT FROM AUTHOR]

In some machine learning applications, graphs tend to be composed of a large number of tiny almost constant sub-structures. The current embedding methods are not prepared for this type of graphs and thus, their representational power tends to be very low. Our aim is to define a new graph embedding that considers this specific type of graphs. We present GraphFingerprint, which is a new embedding method that specifically considers the fact that graphs are composed of millions of almost constant sub-structures. The three-dimensional characterisation of a chemical metal-oxide nanocompound easily fits in these types of graphs, which nodes are atoms and edges are their bonds. Our graph embedding method has been used to predict the toxicity of these nanocompounds, achieving a high accuracy compared to other embedding methods. The representational power of the current embedding methods do not properly satisfy the requirements of some machine learning applications based on graphs, for this reason, a new embedding method has been defined and heuristically demonstrated that achieves good accuracy. [ABSTRACT FROM AUTHOR]

While encryption enhances data security, it also presents significant challenges for network traffic analysis, especially in detecting malicious activities. To tackle this challenge, this paper introduces combined Attention-aware Feature Fusion and Communication Graph Embedding Learning (AFF_CGE), an advanced representation learning framework designed for detecting encrypted malicious traffic. By leveraging an attention mechanism and graph neural networks, AFF_CGE extracts rich semantic information from encrypted traffic and captures complex relations between communicating nodes. Experimental results reveal that AFF_CGE substantially outperforms traditional methods, improving F1-scores by 5.3% through 22.8%. The framework achieves F1-scores ranging from 0.903 to 0.929 across various classifiers, exceeding the performance of state-of-the-art techniques. These results underscore the effectiveness and robustness of AFF_CGE in detecting encrypted malicious traffic, demonstrating its superior performance. [ABSTRACT FROM AUTHOR]

With the strong capability of heterogeneous graphs in accurately modeling various types of nodes and their interactions, they have gradually become a research hotspot, promoting the rapid development of the field of heterogeneous graph neural networks (HGNNs). However, most existing HGNN models rely on meta−paths for feature extraction, which can only utilize part of the data from the graph for training and learning. This not only limits the data generalization ability of deep learning models but also affects the application effect of data−driven adaptive technologies. In response to this challenge, this study proposes a new model—heterogeneous graph neural network based on regional feature extraction (HGNN−BRFE). This model enhances performance through an "extraction−fusion" strategy in three key aspects: first, it efficiently extracts features of neighboring nodes of the same type according to specific regions; second, it effectively fuses information from different regions and hierarchical neighbors using attention mechanisms; third, it specially designs a process for feature extraction and fusion targeting heterogeneous type nodes, ensuring that the rich semantic and heterogeneity information within the heterogeneous graph is retained while maintaining the node's own characteristics during the node embedding process to prevent the loss of its own features and potential over−smoothing issues. Experimental results show that HGNN−BRFE achieves a performance improvement of 1–3% over existing methods on classification tasks across multiple real−world datasets. [ABSTRACT FROM AUTHOR]

Unexpected faults in rotating machinery can lead to cascading disruptions of the entire work process, emphasizing the importance of early detection of performance degradation and identification of the current state. To accurately assess the health of a machine, this study introduces an FFT‐based raw vibration data preprocessing and graph representation technique, which analyses changes in frequency bands to detect early degradation trends in vibration data that may appear normal. The approach proposes a methodology that utilizes a graph convolutional autoencoder trained using only normal data to extract health indicators using the differences in the vectors as degradation progresses. This approach has the advantage of using only normal data to detect subtle performance degradation early and effectively represent health indicators accordingly. [ABSTRACT FROM AUTHOR]

Copyright of Journal of Jilin University (Science Edition) / Jilin Daxue Xuebao (Lixue Ban) is the property of Zhongguo Xue shu qi Kan (Guang Pan Ban) Dian zi Za zhi She 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.)

Graph embedding has gained significant popularity due to its ability to represent large-scale graph data by mapping nodes to a low-dimensional space. However, most of the existing research in this field has focused on transductive learning, where fixed node embeddings are generated by training the entire graph. This approach is not well-suited for temporal graphs that undergo continuous changes with the addition of new nodes and interactions. To address this limitation, we propose an inductive temporal graph embedding method called MIAN (Multi-angle Information Aggregation Network). The key focus of MIAN is to design an aggregation function that combines multi-angle information for generating node embeddings. Specifically, we divide the information into different angles, including neighborhood, temporal, and environment. Each angle of information is modeled and mined independently, and then fed into an improved gated recuttent unit (GRU) module to effectively combine them. To assess the performance of MIAN, we conduct extensive experiments on various real-world datasets and compare its results with several state-of-the-art baseline methods across diverse tasks. The experimental findings demonstrate that MIAN outperforms these methods. [ABSTRACT FROM AUTHOR]

Identifying the region's functionalities and what the specific Point-of-Interest (POI) needs is essential for effective urban planning. However, due to the diversified and ambiguity nature of urban regions, there are still some significant challenges to be resolved in urban POI demand analysis. To this end, we propose a novel framework, in which Region-of-Interest Demand Modeling is enhanced through the graph representation learning, namely Variational Multi-graph Auto-encoding Fusion, aiming to effectively predict the ROI demand from both the POI level and category level. Specifically, we first divide the urban area into spatially differentiated neighborhood regions, extract the corresponding multi-dimensional natures, and then generate the Spatial-Attributed Region Graph (SARG). After that, we introduce an unsupervised multi-graph based variational auto-encoder to map regional profiles of SARG into latent space, and further retrieve the dynamic latent representations through probabilistic sampling and global fusing. Additionally, during the training process, a spatio-temporal constrained Bayesian algorithm is adopted to infer the destination POIs. Finally, extensive experiments are conducted on real-world dataset, which demonstrate our model significantly outperforms state-of-the-art baselines. [ABSTRACT FROM AUTHOR]

Spatial models for areal data are often constructed such that all pairs of adjacent regions are assumed to have near‐identical spatial autocorrelation. In practice, data can exhibit dependence structures more complicated than can be represented under this assumption. In this article, we develop a new model for spatially correlated data observed on graphs, which can flexibly represented many types of spatial dependence patterns while retaining aspects of the original graph geometry. Our method implies an embedding of the graph into Euclidean space wherein covariance can be modeled using traditional covariance functions, such as those from the Matérn family. We parameterize our model using a class of graph metrics compatible with such covariance functions, and which characterize distance in terms of network flow, a property useful for understanding proximity in many ecological settings. By estimating the parameters underlying these metrics, we recover the "intrinsic distances" between graph nodes, which assist in the interpretation of the estimated covariance and allow us to better understand the relationship between the observed process and spatial domain. We compare our model to existing methods for spatially dependent graph data, primarily conditional autoregressive models and their variants, and illustrate advantages of our method over traditional approaches. We fit our model to bird abundance data for several species in North Carolina, and show how it provides insight into the interactions between species‐specific spatial distributions and geography. [ABSTRACT FROM AUTHOR]

We introduce new tools to support finding efficient graph embedding techniques for graph databases and to process their outputs using deep learning for classification scenarios. Accordingly, we investigate the possibility of creating an ensemble of different graph embedding methods to raise accuracy and present an interconnected neural network-based ensemble to increase the efficiency of the member classification algorithms. We also introduce a new convolutional neural network-based architecture that can be generally proposed to process vectorized graph data provided by various graph embedding methods and compare it with other architectures in the literature to show the competitiveness of our approach. We also exhibit a statistical-based inhomogeneity level estimation procedure to select the optimal embedding for a given graph database efficiently. The efficiency of our framework is exhaustively tested using several publicly available graph datasets and numerous state-of-the-art graph embedding techniques. Our experimental results for classification tasks have proved the competitiveness of our approach by outperforming the state-of-the-art frameworks. [ABSTRACT FROM AUTHOR]

Abstract Influence Maximization (IM) stands as a central challenge within the domain of complex network analysis, with the primary objective of identifying an optimal seed set of a predetermined size that maximizes the reach of influence propagation. Over time, numerous methodologies have been proposed to address the IM problem. However, one certain network referred to as Imbalanced Heterogeneous Networks (IHN), which widely used in social situation, urban and rural areas, and merchandising, presents challenges in achieving high-quality solutions. In this work, we introduce the Lightweight Reinforcement Learning algorithm with Prior knowledge (LRLP), which leverages the Struc2Vec graph embedding technique that captures the structural similarity of nodes to generate vector representations for nodes within the network. In details, LRLP incorporates prior knowledge based on a group of centralities, into the initial experience pool, which accelerates the reinforcement learning training for better solutions. Additionally, the node embedding vectors are input into a Deep Q Network (DQN) to commence the lightweight training process. Experimental evaluations conducted on synthetic and real networks showcase the effectiveness of the LRLP algorithm. Notably, the improvement seems to be more pronounced when the the scale of the network is larger. We also analyze the effect of different graph embedding algorithms and prior knowledge on algorithmic results. Moreover, we conduct an analysis about some parameters, such as number of seed set selections T, embedding dimension d and network update frequency C. It is significant that the reduction of number of seed set selections T not only keeps the quality of solutions, but lowers the algorithm’s computational cost.

Abstract Graph encoder embedding, a recent technique for graph data, offers speed and scalability in producing vertex-level representations from binary graphs. In this paper, we extend the applicability of this method to a general graph model, which includes weighted graphs, distance matrices, and kernel matrices. We prove that the encoder embedding satisfies the law of large numbers and the central limit theorem on a per-observation basis. Under certain condition, it achieves asymptotic normality on a per-class basis, enabling optimal classification through discriminant analysis. These theoretical findings are validated through a series of experiments involving weighted graphs, as well as text and image data transformed into general graph representations using appropriate distance metrics.

Interconnection networks, composed of numerous integrated circuits (ICs), form complex structures crucial to many parallel computing systems. The effectiveness of very large scale integration (VLSI) relies on various parameters that influence the design’s cost. In this article, one such crucial parameter, called wirelength, has been studied. Graph embedding is a tool used in the design of VLSI layouts. A graph’s optimal linear layout, also known as minimum linear arrangement (MinLA), is achieved by embedding its vertices onto a line topology. The network topology of (K 11 - C 11) n is significant due to its distinct structure when n = 1 . The study of the Cartesian product of graphs, whether considered as a guest graph (Bezrukov et al. in Ann Comb 4:153–169, 2000; Arockiaraj et al. in Theor Comput Sci 905:69–86, 2022), a host graph (Harper in J Soc Ind Appl Math 12:131–135, 1964; Arockiaraj et al. in Discret Appl Math 288:50–65, 2021), or in relation to solving its edge isoperimetric problem (EIP) (Bonnet and Sikora in Int J Found Comput Sci 27:771–774, 2016; Afiya and Rajesh in J Supercomput 79:12000–12012, 2023), has received considerable attention in recent years. This has also motivated the study of the cartesian product of (K 11 - C 11) . The paper focuses on computing the EIP of (K 11 - C 11) n and addresses the minimum linear arrangement and optimal wirelength of grid, triangular snake and certain tree structures. [ABSTRACT FROM AUTHOR]

Influence Maximization (IM) stands as a central challenge within the domain of complex network analysis, with the primary objective of identifying an optimal seed set of a predetermined size that maximizes the reach of influence propagation. Over time, numerous methodologies have been proposed to address the IM problem. However, one certain network referred to as Imbalanced Heterogeneous Networks (IHN), which widely used in social situation, urban and rural areas, and merchandising, presents challenges in achieving high-quality solutions. In this work, we introduce the Lightweight Reinforcement Learning algorithm with Prior knowledge (LRLP), which leverages the Struc2Vec graph embedding technique that captures the structural similarity of nodes to generate vector representations for nodes within the network. In details, LRLP incorporates prior knowledge based on a group of centralities, into the initial experience pool, which accelerates the reinforcement learning training for better solutions. Additionally, the node embedding vectors are input into a Deep Q Network (DQN) to commence the lightweight training process. Experimental evaluations conducted on synthetic and real networks showcase the effectiveness of the LRLP algorithm. Notably, the improvement seems to be more pronounced when the the scale of the network is larger. We also analyze the effect of different graph embedding algorithms and prior knowledge on algorithmic results. Moreover, we conduct an analysis about some parameters, such as number of seed set selections T, embedding dimension d and network update frequency C. It is significant that the reduction of number of seed set selections T not only keeps the quality of solutions, but lowers the algorithm’s computational cost. [ABSTRACT FROM AUTHOR]

The Industrial Internet of Things (IIoT) provides a foundation for the development of emerging digital servitization paradigm in smart manufacturing. The deep integration of massive heterogeneous IIOT data plays a critical role in realising manufacturing digital servitization. However, there is a knowledge gap between different manufacturing fields, which brings a challenge for efficient integration and leverage of industrial big data. For this purpose, a Framework of Manufacturing Knowledge Graph (FMKG) is proposed, which is used to extracts industry knowledge triples from multi-source heterogeneous data to integrate domain knowledge. Also, an attention-based graph embedding model (ABGE) is proposed to discover and complement the implicit missing relationships in the knowledge graph to obtain a complete industrial knowledge graph. The effectiveness of the ABGE model has been verified on several knowledge graph data sets. And an aerospace enterprise production process was taken as an example to establish a product quality knowledge graph, which proved the feasibility of the proposed method. [ABSTRACT FROM AUTHOR]

Studying gene regulatory networks (GRNs) is paramount for unraveling the complexities of biological processes and their associated disorders, such as diabetes, cancer, and Alzheimer’s disease. Recent advancements in computational biology have aimed to enhance the inference of GRNs from gene expression data, a non-trivial task given the networks’ intricate nature. The challenge lies in accurately identifying the myriad interactions among transcription factors and target genes, which govern cellular functions. This research introduces a cutting-edge technique, EGRC (Effective GRN Inference applying Graph Convolution with Self-Attention Graph Pooling), which innovatively conceptualizes GRN reconstruction as a graph classification problem, where the task is to discern the links within subgraphs that encapsulate pairs of nodes. By leveraging Spearman’s correlation, we generate potential subgraphs that bring nonlinear associations between transcription factors and their targets to light. We use mutual information to enhance this, capturing a broader spectrum of gene interactions. Our methodology bifurcates these subgraphs into ‘Positive’ and ‘Negative’ categories. ‘Positive’ subgraphs are those where a transcription factor and its target gene are connected, including interactions among their neighbors. ‘Negative’ subgraphs, conversely, denote pairs without a direct connection. EGRC utilizes dual graph convolution network (GCN) models that exploit node attributes from gene expression profiles and graph embedding techniques to classify these. The performance of EGRC is substantiated by comprehensive evaluations using the DREAM5 datasets. Notably, EGRC attained an AUROC of 0.856 and an AUPR of 0.841 on the E. coli dataset. In contrast, the in silico dataset achieved an AUROC of 0.5058 and an AUPR of 0.958. Furthermore, on the S. cerevisiae dataset, EGRC recorded an AUROC of 0.823 and an AUPR of 0.822. These results underscore the robustness of EGRC in accurately inferring GRNs across various organisms. The advanced performance of EGRC represents a substantial advancement in the field, promising to deepen our comprehension of the intricate biological processes and their implications in both health and disease.

Summary: Knowledge graphs contain a large amount of entity and relational data, and graph neural networks, as a class of efficient graph representation techniques based on deep learning, excel in knowledge graph modeling. However, previous neural network architectures for the most part only learn node representations and do not fully consider the heterogeneity of data. In this article, we innovatively propose a privacy attack framework based on IoT, PAFI, which is able to classify entities and relations, learn embedding representations in multi‐relational graphs, and can be applied to some existing neural network algorithms. Based on this, a fine‐grained privacy attack model, FPM, is proposed, which can perform attack operations on multiple targets, achieve selectivity of target tasks, and greatly improve the generalization ability of the attack model. In this article, the effectiveness of PAFI and FPM is demonstrated by real network datasets, and compared with previous attack methods, both of which achieve good results. [ABSTRACT FROM AUTHOR]

Recently, the analysis of heterogeneous networks has become more popular due to the growing number of social networks. These networks are capable of covering a variety of nodes and edges. The members of these networks usually have metadata whose analysis can lead to the discovery of knowledge. One way to analyze such data is clustered where high-quality clustering requires effective similarity calculation. Most of the existing clustering methods do not pay attention to the use of metadata or the characteristics of network members. On the other hand, they are only able to process small and medium-sized networks due to the amount of memory and execution speed. This paper presents a hybrid approach for heterogeneous network clustering to overcome these problems. The structural similarity in this approach is calculated by the graph embedding method, which we call learning-based. Attribute similarity is calculated by a scoring method that we call similarity-based. In the experimental study, we compared the proposed method with collaborative approaches based on similarity on the real-world networks. The experimental findings demonstrate the superiority of the proposed method in terms of entropy, memory consumption, execution time, and density in certain cases. [ABSTRACT FROM AUTHOR]

Trip purpose is a meaningful aspect of travel behaviour for the understanding of urban mobility. However, it is non-trivial to automatically obtain trip purposes. On one hand, trip purposes are naturally diverse and complicated, but the available predictive data sources are limited in real-world scenarios. On the other hand, since trip purpose labeling is costly and the development levels of cities are unbalanced, it is infeasible to access large-scale labeled data in less developed cities to train advanced prediction models. To narrow the gaps, this article presents A new Graph Embedding Network and active Domain Adaptation based framework (AGENDA) that only requires open data sources and is capable of predicting in both label-rich cities and label-scarce cities. Specifically, in label-rich source cities, we first use the vehicle's GPS trajectory and open POI check-ins to augment trip contexts. Then we establish a supervised graph embedding network with two attention mechanisms to extract the passenger's latent activity semantics and a classifier to predict trip purpose. To enable the prediction in label-scarce target cities, we further devise an active domain adaptation framework, in which adversarial domain adaptation is used to transfer the source-learned knowledge, and active learning is used to integrate human intelligence in the model training. A group of experiments are conducted with real-world datasets in Beijing and Shanghai. Evaluation results demonstrate that the proposed framework significantly outperforms existing trip purpose prediction algorithms, and could make accurate trip purpose prediction in label-scarce cities with much fewer labeling efforts. [ABSTRACT FROM AUTHOR]

Studying gene regulatory networks (GRNs) is paramount for unraveling the complexities of biological processes and their associated disorders, such as diabetes, cancer, and Alzheimer's disease. Recent advancements in computational biology have aimed to enhance the inference of GRNs from gene expression data, a non-trivial task given the networks' intricate nature. The challenge lies in accurately identifying the myriad interactions among transcription factors and target genes, which govern cellular functions. This research introduces a cutting-edge technique, EGRC (Effective GRN Inference applying Graph Convolution with Self-Attention Graph Pooling), which innovatively conceptualizes GRN reconstruction as a graph classification problem, where the task is to discern the links within subgraphs that encapsulate pairs of nodes. By leveraging Spearman's correlation, we generate potential subgraphs that bring nonlinear associations between transcription factors and their targets to light. We use mutual information to enhance this, capturing a broader spectrum of gene interactions. Our methodology bifurcates these subgraphs into 'Positive' and 'Negative' categories. 'Positive' subgraphs are those where a transcription factor and its target gene are connected, including interactions among their neighbors. 'Negative' subgraphs, conversely, denote pairs without a direct connection. EGRC utilizes dual graph convolution network (GCN) models that exploit node attributes from gene expression profiles and graph embedding techniques to classify these. The performance of EGRC is substantiated by comprehensive evaluations using the DREAM5 datasets. Notably, EGRC attained an AUROC of 0.856 and an AUPR of 0.841 on the E. coli dataset. In contrast, the in silico dataset achieved an AUROC of 0.5058 and an AUPR of 0.958. Furthermore, on the S. cerevisiae dataset, EGRC recorded an AUROC of 0.823 and an AUPR of 0.822. These results underscore the robustness of EGRC in accurately inferring GRNs across various organisms. The advanced performance of EGRC represents a substantial advancement in the field, promising to deepen our comprehension of the intricate biological processes and their implications in both health and disease. [ABSTRACT FROM AUTHOR]

Copyright of Journal of Computer Engineering & Applications 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.)

A tissue sample is a valuable resource for understanding a patient's symptoms and health status in relation to tumor growth. Recent research seeks to establish a connection between tissue-specific tumor samples and genetic markers (genes). This breakthrough has paved the way for personalized cancer therapies. With this motivation, the proposed model constructs a heterogeneous network based on tumor sample-gene relation data and gene-gene interaction data. This network also incorporates tissue-specific gene expression and primary site-based gene counts as features, enabling tissue-specific predictions. Graph neural networks (GNNs) have proven effective in modeling complex interactions and predicting links within this network. The proposed model has successfully predicted tumor-gene associations by leveraging sampling-based GNNs and link layer embedding. The model's performance metrics, such as AUC-ROC scores, reached approximately 94%, demonstrating the potential of this heterogeneous network in predicting tissue-specific tumor sample-gene links. This paper's findings highlight the importance of tissue-specific associations in cancer research. Overview of our proposed work [ABSTRACT FROM AUTHOR]

Core patents are the most important in a specific technological field. Forecasting core patents is crucial to understanding the development of technology trends. Traditional approaches are based on structured/unstructured features or patent relationships. However, most previous methods focused on specific aspects of patents. We propose a novel framework based on the potential relationships to forecast core patents. An event study approach is applied to analyze the short-term impact of core patents' granting events on the stock market. We apply three methods to build framework: a baseline model using traditional features and two graph embeddings. Finally, a classification model is used to predict and compare the effectiveness of different inputs: the traditional patent feature index, and the feature vectors output by the Node2vec and GraphSAGE models. We verify the method with data from the communications and biomedical industries and investigate its application to the stock market. Results demonstrate that the graph-embedding features based on the network are superior to traditional patent features. The graph neural network effectively fuses the two sets of information, and forecasting is improved in all models. And we find that the cumulative abnormal returns from core patents' granting events outweigh those for non-core (ordinary) patents. [ABSTRACT FROM AUTHOR]

With the rise of Internet-of-Things devices, the analysis of sensor-generated energy time series data has become increasingly important. This is especially crucial for detecting rare events like unusual electricity usage or water leakages in residential and commercial buildings, which is essential for optimizing energy efficiency and reducing costs. However, existing detection methods on large-scale data may fail to correctly detect rare events when they do not behave significantly differently from standard events or when their attributes are non-stationary. Additionally, the capacity of computational resources to analyze all time series data generated by an increasing number of sensors becomes a challenge. This situation creates an emergent demand for a workload-bounded strategy. To ensure both effectiveness and efficiency in detecting rare events in massive energy time series, we propose a heuristic-based framework called HALE. This framework utilizes an explore–exploit selection process that is specifically designed to recognize potential features of rare events in energy time series. HALE involves constructing an attribute-aware graph to preserve the attribute information of rare events. A heuristic-based random walk is then derived based on partial labels received at each time period to discover the non-stationarity of rare events. Potential rare event data are selected from the attribute-aware graph, and existing detection models are applied for final confirmation. Our study, which was conducted on three actual energy datasets, demonstrates that the HALE framework is both effective and efficient in its detection capabilities. This underscores its practicality in delivering cost-effective energy monitoring services. [ABSTRACT FROM AUTHOR]

In recommender systems, sequence information is crucial. Sequence data contains user preferences and reflects the evolution of user interests over time. Therefore, how to utilize sequence information to capture dynamic user interests is a critical issue in sequential recommender systems (SRSs). Attention-based methods are commonly used in SRSs and achieve state-of-the-art results. However, attention mechanisms lack the ability to represent the temporal dimension and cannot use sequence order effectively. To this end, this paper proposes a novel model structure called Long-Short Interest Network (LSIN), which fuses Long Short Term Memory (LSTM) and Transformer encoder. We use two LSTM layers to capture the user's long-term and short-term interests, respectively. Furthermore, adding the LSTM can help the self-attention mechanism better model the sequential relationship between items. In addition, most embedding models generate embedding vectors based on individual items without considering the connection between items and users. This will be an obstacle and bring difficulty for later models to capture the evolution of user interests. Therefore, we use a heterogeneous graph to model the interactions between users and items. And design a weight-based graph embedding for generating embedding vectors, which can encode higher-order structural information by propagating on the graph. Finally, we propose LSRec, a framework that unites the above two structures to achieve more accurate recommendations. The new model yielded significant benefits. The experiments on four benchmark data sets demonstrate the effectiveness of LSRec, which achieves almost 5 % improvement in NDCG@10 compared with Self-Attention based Sequential Recommendation model (SASRec). [ABSTRACT FROM AUTHOR]

Summary: Unsupervised person re‐identification based on video sequences can be applied to surveillance systems and is attracting much more attention. It aims to spot specific person in other scenes captured by different cameras. This work explores an innovative strategy, namely, learning to cluster unlabeled person in the videos through graph convolutional networks. In this article, we find that the possibility of inter‐frame linkage can be inferred from context. Therefore, a pose‐guided topology linkage clustering framework is proposed. Our framework consists of three modules: (i) a pose‐guided representation module; (ii) a pose‐guided embedding module; (iii) a link prediction module. First, the representation coding alone is performed at the level of relational induction bias, embedding the implicit pose structure information in image features. Then, based on the consideration of the topology relationship between adjacent and cross‐frame, graph convolutional network is introduced to infer the likelihood of linkage between frame nodes. Experiments show that the proposed method demonstrates excellent scalability in addition to being an effective response to person clustering in case of changes, and does not need the number of clusters as a prior. [ABSTRACT FROM AUTHOR]

Accurate and reliable wind speed prediction is conducive to improving the power generation efficiency of electrical systems. Due to the lack of adequate consideration of spatial feature extraction, the existing wind speed prediction models have certain limitations in capturing the rich neighborhood information of multiple sites. To address the previously mentioned constraints, our study introduces a graph isomorphism-based gated recurrent unit (GIN-GRU). Initially, the model utilizes a hybrid mechanism of random forest and principal component analysis (PCA-RF) to discuss the feature data from different sites. This process not only preserves the primary features but also extracts critical information by performing dimensionality reduction on the residual features. Subsequently, the model constructs graph networks by integrating graph embedding techniques with the Mahalanobis distance metric to synthesize the correlation information among features from multiple sites. This approach effectively consolidates the interrelated feature data and captures the complex interactions across multiple sites. Ultimately, the graph isomorphism network (GIN) delves into the intrinsic relationships within the graph networks and the gated recurrent unit (GRU) integrates these relationships with temporal correlations to address the challenges of wind speed prediction effectively. The experiments conducted on wind farm datasets for offshore California in 2019 have demonstrated that the proposed model has higher prediction accuracy compared to the comparative model such as CNN-LSTM and GAT-LSTM. Specifically, by modifying the network layers, we achieved higher precision, with the mean square error (MSE) and root mean square error (RMSE) of wind speed at a height of 10 m being 0.8457 m/s and 0.9196 m/s, respectively. [ABSTRACT FROM AUTHOR]

Link prediction is a key technique for connecting entities and relationships in a graph reasoning field. It leverages known information about the graph structure data to predict missing factual information. Previous studies have either focused on the semantic representation of a single triplet or on the graph structure data built on triples. The former ignores the association between different triples, and the latter ignores the true meaning of the node itself. Furthermore, common graph-structured datasets inherently face challenges, such as missing information and incompleteness. In light of this challenge, we present a novel model called Multi-source Information Graph Embedding with Ensemble Learning for Link Prediction (EMGE), which can effectively improve the reasoning of link prediction. Ensemble learning is systematically applied throughout the model training process. At the data level, this approach enhances entity embeddings by integrating structured graph information and unstructured textual data as multi-source information inputs. The fusion of these inputs is effectively addressed by introducing an attention mechanism. During the training phase, the principle of ensemble learning is employed to extract semantic features from multiple neural network models, facilitating the interaction of enriched information. To ensure effective model learning, a novel loss function based on contrastive learning is devised, effectively minimizing the discrepancy between predicted values and the ground truth. Moreover, to enhance the semantic representation of graph nodes in link prediction, two rules are introduced during the aggregation of graph structure information. These rules incorporate the concept of spreading activation, enabling a more comprehensive understanding of the relationships between nodes and edges in the graph. During the testing phase, the EMGE model is validated on three datasets, including WN18RR, FB15k-237, and a private Chinese financial dataset. The experimental results demonstrate a reduction in the mean rank (MR) by 0.2 times, an improvement in the mean reciprocal rank (MRR) by 5.9%, and an increase in the Hit@1 by 12.9% compared to the baseline model. [ABSTRACT FROM AUTHOR]

Neurodegeneration measured through volumetry in MRI is recognized as a potential Alzheimer's Disease (AD) biomarker, but its utility is limited by lack of specificity. Quantifying spatial patterns of neurodegeneration on a whole brain scale rather than locally may help address this. In this work, we turn to network based analyses and extend a graph embedding algorithm to study morphometric connectivity from volume-change correlations measured with structural MRI on the timescale of years. We model our data with the multiple random eigengraphs framework, as well as modify and implement a multigraph embedding algorithm proposed earlier to estimate a low dimensional embedding of the networks. Our version of the algorithm guarantees meaningful finite-sample results and estimates maximum likelihood edge probabilities from population-specific network modes and subject-specific loadings. Furthermore, we propose and implement a novel statistical testing procedure to analyze group differences after accounting for confounders and locate significant structures during AD neurodegeneration. Family-wise error rate is controlled at 5% using permutation testing on the maximum statistic. We show that results from our analysis reveal networks dominated by known structures associated to AD neurodegeneration, indicating the framework has promise for studying AD. Furthermore, we find network-structure tuples that are not found with traditional methods in the field.

ABSTRACTSpatial interaction imputation aims to compensate for missing stable connections in geographical space, bolstering interaction network integrity and accuracy. Graph neural networks excel in graph-structured interaction data. However, existing research often focuses on homogeneous networks, neglecting the impact of heterogeneous interaction relationships influenced by distance decay on interaction imputation. Neglecting edge heterogeneity constrains the ability to effectively model the network structure, consequently leading to suboptimal performance in interaction imputation. This study introduces an interaction imputation graph convolutional network model. It constructs a heterogeneous interaction network with multi-distance relationships, considering distance decay. The model performs graph embedding based on interaction relationships between nodes. It comprehensively incorporates multiple interaction modes, topological structures, and node attributes to enhance spatial interaction imputation accuracy. Empirically validated using Beijing taxi travel data, our model outperforms existing models, improving imputation accuracy by approximately 8.70%. Our model consistently maintains superior accuracy in interaction networks of various sizes, demonstrating the stable superiority of our model. We also demonstrated that the variation in the number of interaction relationships affects imputation accuracy. A reasonable number of relationships and a larger feature dimension of geographical units yield better interaction imputation results.

Graph embedding has gained significant popularity due to its ability to represent large-scale graph data by mapping nodes to a low-dimensional space. However, most of the existing research in this field has focused on transductive learning, where fixed node embeddings are generated by training the entire graph. This approach is not well-suited for temporal graphs that undergo continuous changes with the addition of new nodes and interactions. To address this limitation, we propose an inductive temporal graph embedding method called MIAN (Multi-angle Information Aggregation Network). The key focus of MIAN is to design an aggregation function that combines multi-angle information for generating node embeddings. Specifically, we divide the information into different angles, including neighborhood, temporal, and environment. Each angle of information is modeled and mined independently, and then fed into an improved gated recuttent unit (GRU) module to effectively combine them. To assess the performance of MIAN, we conduct extensive experiments on various real-world datasets and compare its results with several state-of-the-art baseline methods across diverse tasks. The experimental findings demonstrate that MIAN outperforms these methods.

Federated learning has been widely employed in many applications to protect the data privacy of participating clients. Although the dataset is decentralized among training devices in federated learning, the model parameters are usually stored in a centralized manner. Centralized federated learning is easy to implement; however, a centralized scheme causes a communication bottleneck at the central server, which may significantly slow down the training process. To improve training efficiency, we investigate the decentralized federated learning scheme. The decentralized scheme has become feasible with the rapid development of device-to-device communication techniques under 5G. Nevertheless, the convergence rate of learning models in the decentralized scheme depends on the network topology design. We propose optimizing the topology design to improve training efficiency for decentralized federated learning, which is a non-trivial problem, especially when considering data heterogeneity. In this paper, we first demonstrate the advantage of hypercube topology and present a hypercube graph construction method to reduce data heterogeneity by carefully selecting neighbors of each training device—a process that resembles classic graph embedding. In addition, we propose a heuristic method for generating torus graphs. Moreover, we have explored the communication patterns in hypercube topology and propose a sequential synchronization scheme to reduce communication cost during training. A batch synchronization scheme is presented to fine-tune the communication pattern for hypercube topology. Experiments on real-world datasets show that our proposed graph construction methods can accelerate the training process, and our sequential synchronization scheme can significantly reduce the overall communication traffic during training.

In maritime logistics optimization, considerable research efforts are focused on the extraction of deep behavioral characteristics from comprehensive shipping data to discern patterns in maritime vessel behavior. The effective linkage of these characteristics with maritime infrastructure, such as berths, is critical for the enhancement of ship navigation systems. This endeavor is paramount not only as a research focus within maritime information science but also for the progression of intelligent maritime systems. Traditional methodologies have primarily emphasized the analysis of navigational paths of vessels without an extensive consideration of the geographical dynamics between ships and port infrastructure. However, the introduction of knowledge graphs has enabled the integration of disparate data sources, facilitating new insights that propel the development of intelligent maritime systems. This manuscript presents a novel framework using knowledge graph technology for profound analysis of maritime data. Utilizing automatic identification system (AIS) data alongside spatial information from port facilities, the framework forms semantic triplet connections among ships, anchorages, berths, and waterways. This enables the semantic modeling of maritime behaviors, offering precise identification of ships through their diverse semantic information. Moreover, by exploiting the semantic relations between ships and berths, a reverse semantic knowledge graph for berths is constructed, which is specifically tailored to ship type, size, and category. The manuscript critically evaluates a range of graph embedding techniques, dimensionality reduction methods, and classification strategies through experimental frameworks to determine the most efficacious methodologies. The findings reveal that the maritime knowledge graph significantly enhances the semantic understanding of unmanned maritime equipment, thereby improving decision-making capabilities. Additionally, it establishes a semantic foundation for the development of expansive maritime models, illustrating the potential of knowledge graph technology in advancing intelligent maritime systems. [ABSTRACT FROM AUTHOR]

Knowledge graphs are widely used and semantically rich data representations, which is increasingly becoming a crucial technology in the field of knowledge engineering. However, real-world knowledge graphs often suffer from incompleteness and ambiguity, hindering their application performance. Knowledge graph completion techniques aim to enrich the content of knowledge graphs by predicting missing entities or relations, has been a hot research topic in recent years. In particular, embedding-based approaches have made remarkable progress in knowledge graph completion tasks. It reviews recent embedding- based static knowledge graph completion methods, categorizing them based on approaches such as translation- based models, tensor factorization, neural network models, and pre- trained language models. These methods achieve an improved semantic representation and inferential capabilities by embedding entity relations into continuous vector spaces. At the same time, it has potential advantages in capturing complex relationships between entities and utilizing graph structural information. [ABSTRACT FROM AUTHOR]

In the last decade, graph embedding-based dimensionality reduction for multi-view data has been extensively studied. However, constructing a high-quality graph for dimensionality reduction is still a significant challenge. Herein, we propose a new algorithm, named multi-view low-rank graph optimization for dimensionality reduction (MvLRGO), which integrates graph optimization with dimensionality reduction into one objective function in order to simultaneously determine the optimal subspace and graph. The subspace learning of each view is conducted independently by the general graph embedding framework. For graph construction, we exploit low-rank representation (LRR) to obtain reconstruction relationships as the affinity weight of the graph. Subsequently, the learned graph of each view is further optimized throughout the learning process to obtain the ideal assignment of relations. Moreover, to integrate information from multiple views, MvLRGO regularizes each of the view-specific optimal graphs such that they align with one another. Benefiting from this term, MvLRGO can achieve flexible multi-view communication without constraining the subspaces of all views to be the same. Various experimental results obtained with different datasets show that the proposed method outperforms many state-of-the-art multi-view and single-view dimensionality reduction algorithms. [ABSTRACT FROM AUTHOR]

Graph clustering, an essential unsupervised learning task in data mining, has garnered significant attention in recent years. With the advent of deep learning, considerable progress has been made in this field. However, existing methods present several limitations: (1) Most encoder models employ Graph Convolutional Networks (GCNs) as encoders. However, GCNs assign equal weight to each neighboring node and have been shown to be oversmoothing, thereby impacting clustering performance. (2) Most algorithms do not fully utilize the original graph content and structural information, leading to incomplete embedding features. (3) These methods do not account for the specific distribution of clustering of embedding features and the enhancement of staged pseudo-labels on clustering tasks.In this study,we propose a novel end-to-end graph clustering model that leverages graph attention encoders. Specifically, we initially employ a graph attention encoder to extract the inherent information from the original graph. This process assigns varying weights to different nodes, thereby avoiding excessive smoothing. We also fully utilize the guidance of periodic pseudo-labels to facilitate the learning of potential features that are beneficial for clustering. In addition, to improve the model’s clustering performance, we introduce a regularization term that distributes the node features of different classifications across distinct low-dimensional spaces. Furthermore, to prevent the embedding features from straying from the original graph features, we design an information consistency module. Experimental results on the node graph datasets show that our model outperforms other state-of-the-art algorithms. [ABSTRACT FROM AUTHOR]

A Knowledge Graph-based Question Answering (KGQA) system attempts to answer a given natural language question using a knowledge graph (KG) rather than from text data. The current KGQA methods attempt to determine whether there is an explicit relationship between the entities in the question and a well-structured relationship between them in the KG. However, such strategies are difficult to build and train, limiting their consistency and versatility. The use of language models such as BERT has aided in the advancement of natural language question answering. In this paper, we present a novel Graph Neural Network(GNN) based approach with relevance scoring for improving KGQA. GNNs use the weight of nodes and edges to influence the information propagation while updating the node features in the network. The suggested method comprises subgraph construction, weighing of nodes and edges, and pruning processes to obtain meaningful answers. BERT-based GNN is used to build subgraph node embeddings. We tested the influence of weighting for both nodes and edges and observed that the system performs better for weighted graphs than unweighted graphs. Additionally, we experimented with several GNN convolutional layers and obtainined improved results by combining GENeralised Graph Convolution (GENConv) with node weights for simple questions. Extensive testing on benchmark datasets confirmed the effectiveness of the proposed model in comparison to state-of-the-art KGQA systems. [ABSTRACT FROM AUTHOR]

Due to the high heterogeneity of cancers, it is rather essential to explore driver modules with the help of gene mutation data as well as known interactions between genes/proteins. Unfortunately, latent false positive interactions are inevitable in the Protein-Protein Interaction (PPI) network. Hence in the presented method, a new weight evaluation index, based on the gene-microRNA network as well as somatic mutation profile, is introduced for weighting the PPI network first. Subsequently, the vertices in the weighted PPI network are hierarchically clustered by measuring the Mahalanobis distance of their feature vectors, extracted with the graph embedding method Node2vec. Finally, a heuristic process with dropping and extracting is conducted on the gene clusters to produce a group of gene modules. Numerous experiment results demonstrate that the proposed method exhibits superior performance to four cutting-edge identification methods in most cases regarding the capability of recognizing the acknowledged cancer-related genes, generating modules having relatively high coverage and mutual exclusivity, and are significantly enriched for specific types of cancers. The majority of the genes in the identified modules are involved in cancer-related signaling pathways, or have been reported to be carcinogenic in the literature. Furthermore, many cancer related genes detected by the proposed method are actually omitted by the four comparison methods, which has been verified in the experiments. [ABSTRACT FROM AUTHOR]

Increasing research findings suggest that circular RNA (circRNA) exerts a crucial function in the pathogenesis of complex human diseases by binding to miRNA. Identifying their potential interactions is of paramount importance for the diagnosis and treatment of diseases. However, long cycles, small scales, and time-consuming processes characterize previous biological wet experiments. Consequently, the use of an efficient computational model to forecast the interactions between circRNA and miRNA is gradually becoming mainstream. In this study, we present a new prediction model named BJLD-CMI. The model extracts circRNA sequence features and miRNA sequence features by applying Jaccard and Bert's method and organically integrates them to obtain CMI attribute features, and then uses the graph embedding method Line to extract CMI behavioral features based on the known circRNA-miRNA correlation graph information. And then we predict the potential circRNA-miRNA interactions by fusing the multi-angle feature information such as attribute and behavior through Autoencoder in Autoencoder Networks. BJLD-CMI attained 94.95% and 90.69% of the area under the ROC curve on the CMI-9589 and CMI-9905 datasets. When compared with existing models, the results indicate that BJLD-CMI exhibits the best overall competence. During the case study experiment, we conducted a PubMed literature search to confirm that out of the top 10 predicted CMIs, seven pairs did indeed exist. These results suggest that BJLD-CMI is an effective method for predicting interactions between circRNAs and miRNAs. It provides a valuable candidate for biological wet experiments and can reduce the burden of researchers. [ABSTRACT FROM AUTHOR]

Modelling size-realistic nanomaterials to analyse some of their properties, such as toxicity, solubility, or electronic structure, is a current challenge in computational and theoretical chemistry. The representation of the all-atom three-dimensional structure of a nanocompound would be ideal, as it could account explicitly for structural effects. However, the use of the whole structure is tedious due to the high data management and the structural complexity that accompanies the surface of the nanoparticle. Developing appropriate tools that enable a quantitative analysis of the structure, as well as the selection of regions of interest such as the core-shell, is a crucial step toward enabling the efficient analysis and processing of model nanostructures. The aim of this study was twofold. First, we defined the NanoFingerprint, which is a representation of a nanocompound in the form of a vector based on its 3D structure. The local relationship between atoms, i.e., their coordination within successive layers of neighbours, allows the characterisation of the local structure through the atom connectivity, maintaining the information of the three-dimensional structure but increasing the management ability. Second, we present a web server, called ATENA, to generate NanoFingerprints and other tools based on the 3D structure of the nanocompounds. A case study is reported to show the validity of our new fingerprint tool and the usefulness of our server. The scientific community and also private companies have a new tool based on a public web server for exploring the toxicity of nanocompounds. [ABSTRACT FROM AUTHOR]

Reliable cell type annotations are crucial for investigating cellular heterogeneity in single-cell omics data. Although various computational approaches have been proposed for single-cell RNA sequencing (scRNA-seq) annotation, high-quality cell labels are still lacking in single-cell sequencing assay for transposase-accessible chromatin (scATAC-seq) data, because of extreme sparsity and inconsistent chromatin accessibility between datasets. Here, we present a novel automated cell annotation method that transfers cell type information from a well-labeled scRNA-seq reference to an unlabeled scATAC-seq target, via a parallel graph neural network, in a semi-supervised manner. Unlike existing methods that utilize only gene expression or gene activity features, HyGAnno leverages genome-wide accessibility peak features to facilitate the training process. In addition, HyGAnno reconstructs a reference–target cell graph to detect cells with low prediction reliability, according to their specific graph connectivity patterns. HyGAnno was assessed across various datasets, showcasing its strengths in precise cell annotation, generating interpretable cell embeddings, robustness to noisy reference data and adaptability to tumor tissues. [ABSTRACT FROM AUTHOR]

In Part I of this series, all topologically possible 1‐periodic infinite graphs (chain graphs) representing chains of tetrahedra with up to 6–8 vertices (tetrahedra) per repeat unit were generated. This paper examines possible restraints on embedding these chain graphs into Euclidean space such that they are compatible with the metrics of chains of tetrahedra in observed crystal structures. Chain‐silicate minerals with T = Si4+ (plus P5+, V5+, As5+, Al3+, Fe3+, B3+, Be2+, Zn2+ and Mg2+) have a grand nearest‐neighbour ⟨T–T⟩ distance of 3.06±0.15 Å and a minimum T...T separation of 3.71 Å between non‐nearest‐neighbour tetrahedra, and in order for embedded chain graphs (called unit‐distance graphs) to be possible atomic arrangements in crystals, they must conform to these metrics, a process termed equalization. It is shown that equalization of all acyclic chain graphs is possible in 2D and 3D, and that equalization of most cyclic chain graphs is possible in 3D but not necessarily in 2D. All unique ways in which non‐isomorphic vertices may be moved are designated modes of geometric modification. If a mode (m) is applied to an equalized unit‐distance graph such that a new geometrically distinct unit‐distance graph is produced without changing the lengths of any edges, the mode is designated as valid (mv); if a new geometrically distinct unit‐distance graph cannot be produced, the mode is invalid (mi). The parameters mv and mi are used to define ranges of rigidity of the unit‐distance graphs, and are related to the edge‐to‐vertex ratio, e/n, of the parent chain graph. The program GraphT–T was developed to embed any chain graph into Euclidean space subject to the metric restraints on T–T and T...T. Embedding a selection of chain graphs with differing e/n ratios shows that the principal reason why many topologically possible chains cannot occur in crystal structures is due to violation of the requirement that T...T > 3.71 Å. Such a restraint becomes increasingly restrictive as e/n increases and indicates why chains with stoichiometry TO<2.5 do not occur in crystal structures. [ABSTRACT FROM AUTHOR]

Graphs that are critical (minimal excluded minors) for embeddability in surfaces are studied. In Part I, it was shown that graphs that are critical for embeddings into surfaces of Euler genus k or for embeddings into nonorientable surface of genus k are built from 3-connected components, called hoppers and cascades. In Part II, all cascades for Euler genus 2 are classified. As a consequence, the complete list of obstructions of connectivity 2 for embedding graphs into the Klein bottle is obtained. [ABSTRACT FROM AUTHOR]

In order to further optimize the overlapping community detection algorithm, this paper proposed a new definition of node importance based on degree and node clustering coefficient, and the nodes were updated in descending order of node importance, and the node update strategy was fixed to improve the stability of community detection. On this basis, this paper proposed an OCD-GEMPA. The algorithm combined the node2vec model to represent the nodes in a low-dimensional vector, constructed a matrix of weight values between nodes, calculated the label attribution coefficient according to the weight values, and selected labels accordingly, avoiding the problem of random selection. Experimental verification of the algorithm on real data sets and synthetic data sets shows that compared to other overlapping community detection algorithms, the OCD-GEMPA algorithm has significant improvements in both EQ and NMI indicators, with better accuracy and stability. [ABSTRACT FROM AUTHOR]

Graph clustering has been a hot research topic and is widely used in many fields, such as community detection in social networks. Lots of works combining auto-encoder and graph neural networks have been applied to clustering tasks by utilizing node attributes and graph structure. These works usually assumed the inherent parameters (i.e., size and variance) of different clusters in the latent embedding space are homogeneous, and hence the assigned probability is monotonous over the Euclidean distance between node embeddings and centroids. Unfortunately, this assumption usually does not hold since the size and concentration of different clusters can be quite different, which limits the clustering accuracy. In addition, the node embeddings in deep graph clustering methods are usually L2 normalized so that it lies on the surface of a unit hyper-sphere. To solve this problem, we proposed Deep Adaptive Graph Clustering via von Mises-Fisher distributions, namely DAGC. DAGC assumes the node embeddings H can be drawn from a von Mises-Fisher distribution and each cluster k is associated with cluster inherent parameters ρk which includes cluster center μ and cluster cohesion degree κ. Then we adopt an EM-like approach (i.e., (H|ρ) and (ρ|H), respectively) to learn the embedding and cluster inherent parameters alternately. Specifically, with the node embeddings, we proposed to update the cluster centers in an attraction-repulsion manner to make the cluster centers more separable. And given the cluster inherent parameters, a likelihood-based loss is proposed to make node embeddings more concentrated around cluster centers. Thus, DAGC can simultaneously improve the intra-cluster compactness and inter-cluster heterogeneity. Finally, extensive experiments conducted on four benchmark datasets have demonstrated that the proposed DAGC consistently outperforms the state-of-the-art methods, especially on imbalanced datasets. [ABSTRACT FROM AUTHOR]

For graphs F, G, and H, we write F → (G , H) if every red-blue coloring of the edges of F produces a red copy of G or a blue copy of H. The graph F is said to be (G, H)-minimal if it is subgraph-minimal with respect to this property. The characterization problem for Ramsey-minimal graphs is classically done for finite graphs. In 2021, Barrett and the second author generalized this problem to infinite graphs. They asked which pairs (G, H) admit a Ramsey-minimal graph and which ones do not. We show that any pair of star forests such that at least one of them involves an infinite-star component admits no Ramsey-minimal graph. Also, we construct a Ramsey-minimal graph for a finite star forest versus a subdivision graph. This paper builds upon the results of Burr et al. (Discrete Math 33:227–237, 1981) on Ramsey-minimal graphs for finite star forests. [ABSTRACT FROM AUTHOR]

In recent years, the growth of data has promoted the development of parallel and distributed systems. Graph embedding is of great importance in improving parallel and distributed system performance. The quality of an embedding can be measured by many important metrics, and wirelength is one of the critical metrics related to communication performance and layout costs of physical systems. The hierarchical cubic network is a well-performing interconnection network and the k -rooted complete binary tree is a data structure with a hierarchical relationship among its various elements in algorithms and programming. In this paper, we solve the problem of the embedding of hierarchical cubic networks into k -rooted complete binary trees with minimum wirelength. We first study the optimal set of the hierarchical cubic network, and propose algorithms to give embedding h e t which is an embedding scheme of hierarchical cubic networks into k -rooted complete binary trees with minimum wirelength. Moreover, we give the exact minimum wirelength of this embedding. Finally, we conduct comparative experiments to evaluate the performance of embedding h e t. [ABSTRACT FROM AUTHOR]

Many activities in the cybersecurity realm can be represented using graphs stream, such as call graphs. In this paper, we introduce an innovative method to detect Advanced Persistent Threats (APTs) from their onset. Unique to our approach is the ability to assimilate both structural and temporal aspects, crucial for differentiating between benign and malicious activities. To overcome challenges presented by streaming data processing, we leverage hashing techniques for a compact data representation. This method, when combined with a dynamic machine learning framework, facilitates swift, incremental detection and ensures minimal memory usage. Empirical evaluations underscore the efficacy of our approach, allowing a real-time response by pinpointing APTs at the initial stages of their activity [ABSTRACT FROM AUTHOR]