Search

Accurate forecasting of taxi demand has facilitated the rational allocation of urban public transport resources, reduced congestion in urban transport networks, and shortened passenger waiting time. However, virtual station discovery and modelling of the demand when forecasting through graph convolutional neural networks remains challenging. In this study, the virtual station discovery problem was addressed by using a two-stage clustering approach, which considers the geographical and load characteristics of taxi demand. Furthermore, a fusion model combining non-negative matrix decomposition and a graph convolutional neural network was proposed in order to extract the features of the nodes for dimension reduction and adaptive adjacency matrix computation. By the construction of a local processing structure, further extraction of the local characteristics of the demand was achieved. The experimental results show that the method in this study outperforms state-of-the-art methods in terms of the root mean square error and average absolute value error. Therefore, the model proposed in this study is able to achieve accurate forecasting of taxi demand. [ABSTRACT FROM AUTHOR]

In this article, we discuss the spectral properties of the general extended adjacency matrix for chain graphs. In particular, we discuss the eigenvalues of the general extended adjacency matrix of the chain graphs and obtain its general extended adjacency inertia. We obtain bounds for the largest and the smallest general extended adjacency eigenvalues and characterize the extremal graphs. We also obtain a lower bound for the spread of the general extended adjacency matrix. We characterize chain graphs with all the general extended adjacency eigenvalues being simple and chain graphs that are non-singular under the general extended adjacency matrix. Further, we determine the explicit formula for the determinant and the trace of the square of the general extended adjacency matrix of chain graphs. Finally, we discuss the energy of the general extended adjacency matrix and obtain some bounds for it. We characterize the extremal chain graphs attaining these bounds. [ABSTRACT FROM AUTHOR]

In the paper, we introduce the signless Laplacian A B C -matrix Q ̃ (G) = D ¯ (G) + A ̃ (G) , where D ¯ (G) is the diagonal matrix of A B C -degrees and A ̃ (G) is the A B C -matrix of G. The eigenvalues of the matrix Q ̃ (G) are the signless Laplacian A B C -eigenvalues of G. We give some basic properties of the matrix Q ̃ (G) , which includes relating independence number and clique number with signless Laplacian A B C -eigenvalues. For bipartite graphs, we show that the signless Laplacian A B C -spectrum and the Laplacian A B C -spectrum are the same. We characterize the graphs with exactly two distinct signless Laplacian A B C -eigenvalues. Also, we consider the problem of the characterization of the graphs with exactly three distinct signless Laplacian A B C -eigenvalues and solve it for bipartite graphs and, in some cases, for non-bipartite graphs. We also introduce the concept of the trace norm of the matrix Q ̃ (G) − t r (Q ̃ (G)) n I , called the signless Laplacian A B C -energy of G. We obtain some upper and lower bounds for signless Laplacian A B C -energy and characterize the extremal graphs attaining it. Further, for graphs of order at most 6, we compare the signless Laplacian energy and the A B C -energy with the signless Laplacian A B C -energy and found that the latter behaves well, as there is a single pair of graphs with the same signless Laplacian A B C -energy unlike the 26 pairs of graphs with same signless Laplacian energy and eight pairs of graphs with the same A B C -energy. [ABSTRACT FROM AUTHOR]

Let G be a graph with the adjacency matrix A (G) , and let D (G) be the diagonal matrix of the degrees of G. Nikiforov first defined the matrix A α (G) as A α (G) = α D (G) + (1 − α) A (G) , 0 ≤ α ≤ 1 , which shed new light on A (G) and Q (G) = D (G) + A (G) , and yielded some surprises. The α − adjacency energy E A α (G) of G is a new invariant that is calculated from the eigenvalues of A α (G) . In this work, by combining matrix theory and the graph structure properties, we provide some upper and lower bounds for E A α (G) in terms of graph parameters (the order n, the edge size m, etc.) and characterize the corresponding extremal graphs. In addition, we obtain some relations between E A α (G) and other energies such as the energy E (G) . Some results can be applied to appropriately estimate the α -adjacency energy using some given graph parameters rather than by performing some tedious calculations. [ABSTRACT FROM AUTHOR]

For a simple finite graph G, the generalized adjacency matrix is defined as A α (G) = α D (G) + (1 − α) A (G) , α ∈ [ 0 , 1 ] , where A (G) and D (G) are respectively the adjacency matrix and diagonal matrix of the vertex degrees. The A α -spread of a graph G is defined as the difference between the largest eigenvalue and the smallest eigenvalue of the A α (G) . In this paper, we answer the question posed in (Lin, Z.; Miao, L.; Guo, S. Bounds on the A α -spread of a graph. Electron. J. Linear Algebra2020, 36, 214–227). Furthermore, we show that the path graph, P n , has the smallest S (A α) among all trees of order n. We establish a relationship between S (A α) and S (A). We obtain several bounds for S (A α) . [ABSTRACT FROM AUTHOR]

We introduce a generalized adjacency matrix in order to distinguish cospectral graphs. Our reasoning is motivated by the work of Johnson and Newman and properties of p-adic numbers. Using a polynomial time algorithm, we comment on computer experiments with which we can distinguish cospectral (non-isomorphic) graphs. [ABSTRACT FROM AUTHOR]

The demand for accurate and reliable unsupervised image segmentation methods is high. Regardless of whether we are faced with a problem for which we do not have a usable training dataset, or whether it is not possible to obtain one, we still need to be able to extract the desired information from images. In such cases, we are usually gently pushed towards the best possible clustering method, as it is often more robust than simple traditional image processing methods. We investigate the usefulness of combining two clustering methods for unsupervised image segmentation. We use the mixture models to extract the color and spatial image features based on the obtained output segments. Then we construct a similarity matrix (adjacency matrix) based on these features to perform spectral clustering. In between, we propose a label noise correction using Markov random fields. We investigate the usefulness of our method on many hand-crafted images of different objects with different shapes, colorization, and noise. Compared to other clustering methods, our proposal performs better, with 10% higher accuracy. Compared to state-of-the-art supervised image segmentation methods based on deep convolutional neural networks, our proposal proves to be competitive. [ABSTRACT FROM AUTHOR]

Entity alignment is an important task in knowledge fusion, which aims to link entities that have the same real-world identity in two knowledge graphs. However, in the process of constructing a knowledge graph, some noise may inevitably be introduced, which must affect the results of the entity alignment tasks. The triple confidence calculation can quantify the correctness of the triples to reduce the impact of the noise on entity alignment. Therefore, we designed a method to calculate the confidence of the triples and applied it to the knowledge representation learning phase of entity alignment. The method calculates the triple confidence based on the pairing rates of the three angles between the entities and relations. Specifically, the method uses the pairing rates of the three angles as features, which are then fed into a feedforward neural network for training to obtain the triple confidence. Moreover, we introduced the triple confidence into the knowledge representation learning methods to improve their performance in entity alignment. For the graph neural network-based method GCN, we considered entity confidence when calculating the adjacency matrix, and for the translation-based method TransE, we proposed a strategy to dynamically adjust the margin value in the loss function based on confidence. These two methods were then applied to the entity alignment, and the experimental results demonstrate that compared with the knowledge representation learning methods without integrating confidence, the confidence-based knowledge representation learning methods achieved excellent performance in the entity alignment task. [ABSTRACT FROM AUTHOR]

This work surveys the use of directed weighted graphs in conducting comparative static analyses. The paper discusses the implementation of a computer-aided process for building spreadsheet-based graph models for inter- and intra-regional financial flows. The graph-theoretic techniques are programmed to enable the interactive visualization and analysis of financial data using Wolfram technologies (i.e., Mathematica software v. 11.3 or later, Wolfram player v. 12 or later). The paper describes the workflow for several interactive visualizations applicable to financial networks. The author provides four programs, written in the Wolfram language, that customize input–output financial models by combining the Manipulate command with built-in Mathematica functions and functions of the IGraph package (IGraph/M). The study is a tutorial article for the generation of a suite of visual schemes that provide patterns, practices, and roadmaps of the financial markets across the globe. [ABSTRACT FROM AUTHOR]

Community structure is a significant characteristic of complex networks, and community detection has valuable applications in network structure analysis. Non-negative matrix factorization (NMF) is a key set of algorithms used to solve the community detection issue. Nevertheless, the localization of feature vectors in the adjacency matrix, which represents the characteristics of complex network structures, frequently leads to the failure of NMF-based approaches when the data matrix has a low density. This paper presents a novel algorithm for detecting sparse network communities using non-negative matrix factorization (NMF). The algorithm utilizes local feature vectors to represent the original network topological features and learns regularization matrices. The resulting feature matrices effectively reveal the global structure of the data matrix, demonstrating enhanced feature expression capabilities. The regularized data matrix resolves the issue of localized feature vectors caused by sparsity or noise, in contrast to the adjacency matrix. The approach has superior accuracy in detecting community structures compared to standard NMF-based community detection algorithms, as evidenced by experimental findings on both simulated and real-world networks. [ABSTRACT FROM AUTHOR]

Related party transactions (RPTs) can serve as channels for the spread of credit risk events among blockchain firms. However, current credit risk-assessment models typically only consider a firm's individual characteristics, overlooking the impact of related parties in the blockchain. We suggest incorporating RPT network analysis to improve credit risk evaluation. Our approach begins by representing an RPT network using a weighted adjacency matrix. We then apply DANE, a deep network embedding algorithm, to generate condensed vector representations of the firms within the network. These representations are subsequently used as inputs for credit risk-evaluation models to predict the default distance. Following this, we employ SHAP (Shapley Additive Explanations) to analyze how the network information contributes to the prediction. Lastly, this study demonstrates the enhancing effect of using DANE-based integrated features in credit risk assessment. [ABSTRACT FROM AUTHOR]

Applying machine learning algorithms to graph-structured data has garnered significant attention in recent years due to the prevalence of inherent graph structures in real-life datasets. However, the direct application of traditional deep learning algorithms, such as Convolutional Neural Networks (CNNs), is limited as they are designed for regular Euclidean data like 2D grids and 1D sequences. In contrast, graph-structured data are in a non-Euclidean form. Graph Neural Networks (GNNs) are specifically designed to handle non-Euclidean data and make predictions based on connectivity rather than spatial structure. Real-life graph data can be broadly categorized into two types: spatially-invariant graphs, where the link structure between nodes is independent of their spatial positions, and spatially-variant graphs, where node positions provide additional information about the graph's properties. However, there is limited understanding of the effect of spatial variance on the performance of Graph Neural Networks. In this study, we aim to address this issue by comparing the performance of GNNs and CNNs on spatially-variant and spatially-invariant graph data. In the case of spatially-variant graphs, when represented as adjacency matrices, they can exhibit Euclidean-like spatial structure. Based on this distinction, we hypothesize that CNNs may outperform GNNs when working with spatially-variant graphs, while GNNs may excel on spatially-invariant graphs. To test this hypothesis, we compared the performance of CNNs and GNNs under two scenarios: (i) graphs in the training and test sets had the same connectivity pattern and spatial structure, and (ii) graphs in the training and test sets had the same connectivity pattern but different spatial structures. Our results confirmed that the presence of spatial structure in a graph allows for the effective use of CNNs, which may even outperform GNNs. Thus, our study contributes to the understanding of the effect of spatial graph structure on the performance of machine learning methods and allows for the selection of an appropriate algorithm based on the spatial properties of the real-life graph dataset. [ABSTRACT FROM AUTHOR]

For a simple graph with vertex set { v 1 , v 2 , ... , v n } with degree sequence d v i of vertex v i , i = 1 , 2 , ... , n , the inverse sum indeg matrix ( I S I -matrix) A I S I (G) = (a i j) n × n of G is defined by a i j = d v i d v j d v i + d v j , if v i is adjacent to v j , and zero, otherwise. The multiset of eigenvalues of A I S I (G) is the I S I -spectrum of G and the sum of their absolute values is the I S I -energy of G . In this paper, we modify the two results of (Li, Ye and Broersma, 2022), give the correct characterization of the extremal graphs and thereby obtain better bounds than the already known results. Moreover, we also discuss the QSPR analysis and carry the statistical modelling (linear, logarithmic and quadratic) of the physicochemical properties of anticancer drugs with the I S I -index (energy). [ABSTRACT FROM AUTHOR]

This paper defines the weighted super adjacency matrix based on the existing super adjacency matrix. This paper, for the first time, combines the trade network, competitive network, and complementary network to construct the trade multilayer network, and innovatively defines the interlayer connections. Based on this, we build trade multilayer networks for three major agricultural products in the western region along the "Belt and Road". The paper then proposes analytical methods, including a classification algorithm for local network relations and a comparative analysis of trade development priorities based on the local network relations. The former is used to identify and categorize key trading countries and potential trading countries for western agricultural products along the "Belt and Road". The latter is used to examine the western regions' order of priority in developing trade relations with the classified countries. According to the findings, category I agricultural trade has 37 key trading countries among the "Belt and Road" countries. Their local network relationships are classified into six groups, and their trade development priorities are classified into four levels. There are 49 key trading countries in category II agricultural trade. Their local network relations can be classified into three groups, and their trade development priorities can be classified into two levels. There are 62 key trading countries in category IV agricultural trade. Their local network relationships are classified into six groups, and their trade development priorities are classified into four levels. Furthermore, only Chile is a potential trading partner in category I agricultural trade. Finally, this paper offers policy recommendations for the development of agricultural trade along the "Belt and Road" in the western region. [ABSTRACT FROM AUTHOR]

Traffic flow forecasting is challenging for us to analyze intricate spatial–temporal dependencies and obtain incomplete information of spatial–temporal connection. Existing frameworks mostly construct spatial and temporal modeling based on a fixed graph structure and given time series. However, a fixed adjacency matrix is limited to learn effective spatial–temporal correlations of the network because it represents incomplete information for missing genuine relation. To solve the difficulty, we design a novel spatial–temporal adaptive fusion graph network (STFAGN) for traffic prediction. First, our model combines fusion convolution layers with a novel adaptive dependency matrix by end-to-end training to capture the hidden spatial-temporal dependency on the data to complete incomplete information. Second, STFAGN could, in parallel, acquire hidden spatial–temporal dependencies by a fusion operation and temporal trend by fast-DTW. Meanwhile, we use ReZero connection as a simple change of deep residual networks to facilitate deep signal propagation and faster converge. Lastly, we conduct comparative experiments on two public traffic network datasets, whose results demonstrate the superiority of our algorithm compared to state-of-the-art baseline types. Ablation experiments also prove the rationality of the framework of STFAGN. [ABSTRACT FROM AUTHOR]

Accurate predictions of parking occupancy are vital for navigation and autonomous transport systems. This research introduces a deep learning mode, AGCRU, which integrates Adaptive Graph Convolutional Networks (GCNs) with Gated Recurrent Units (GRUs) for predicting on-street parking occupancy. By leveraging real-world data from Melbourne, the proposed model utilizes on-street parking sensors to capture both temporal and spatial dynamics of parking behaviors. The AGCRU model is enhanced with the inclusion of Points of Interest (POIs) and housing data to refine its predictive accuracy based on spatial relationships and parking habits. Notably, the model demonstrates a mean absolute error (MAE) of 0.0156 at 15 min, 0.0330 at 30 min, and 0.0558 at 60 min; root mean square error (RMSE) values are 0.0244, 0.0665, and 0.1003 for these intervals, respectively. The mean absolute percentage error (MAPE) for these intervals is 1.5561%, 3.3071%, and 5.5810%. These metrics, considerably lower than those from traditional and competing models, indicate the high efficiency and accuracy of the AGCRU model in an urban setting. This demonstrates the model as a tool for enhancing urban parking management and planning strategies. [ABSTRACT FROM AUTHOR]

In a certain class of graphs, a graph is called minimizing if the least eigenvalue of its adjacency matrix attains the minimum. A connected graph containing two or three cycles is called a bicyclic graph if its number of edges is equal to its number of vertices plus one. Let G1,nc and G2,ncbe the classes of the connected graphs of order n whose complements are bicyclic with exactly two and three cycles, respectively. In this paper, we characterize the unique minimizing graph among all the graphs which belong to Gnc= G1,nc [ G2,nc, a class of the connected graphs of order n whose complements are bicyclic. [ABSTRACT FROM AUTHOR]

Graph convolutional networks (GCNs) provide an advantage in node classification tasks for graph-related data structures. In this paper, we propose a GCN model for enhancing the performance of node classification tasks. We design a GCN layer by updating the aggregation function using an updated value of the weight coefficient. The adjacency matrix of the input graph and the identity matrix are used to calculate the aggregation function. To validate the proposed model, we performed extensive experimental studies with seven publicly available datasets. The proposed GCN layer achieves comparable results with the state-of-the-art methods. With one single layer, the proposed approach can achieve superior results. [ABSTRACT FROM AUTHOR]

Using the notions of clique partitions and edge clique covers of graphs, we consider the corresponding incidence structures. This connection furnishes lower bounds on the negative eigenvalues and their multiplicities associated with the adjacency matrix, bounds on the incidence energy, and on the signless Laplacian energy for graphs. For the more general and well-studied set S (G) of all real symmetric matrices associated with a graph G, we apply an extended version of an incidence matrix tied to an edge clique cover to establish several classes of graphs that allow two distinct eigenvalues. [ABSTRACT FROM AUTHOR]

The analysis of network structure is essential to many scientific areas ranging from biology to sociology. As the computational task of clustering these networks into partitions, i.e., solving the community detection problem, is generally NP-hard, heuristic solutions are indispensable. The exploration of expedient heuristics has led to the development of particularly promising approaches in the emerging technology of quantum computing. Motivated by the substantial hardware demands for all established quantum community detection approaches, we introduce a novel QUBO-based approach that only needs number-of-nodes qubits and is represented by a QUBO matrix as sparse as the input graph's adjacency matrix. The substantial improvement in the sparsity of the QUBO matrix, which is typically very dense in related work, is achieved through the novel concept of separation nodes. Instead of assigning every node to a community directly, this approach relies on the identification of a separation-node set, which, upon its removal from the graph, yields a set of connected components, representing the core components of the communities. Employing a greedy heuristic to assign the nodes from the separation-node sets to the identified community cores, subsequent experimental results yield a proof of concept by achieving an up to 95% optimal solution quality on three established real-world benchmark datasets. This work hence displays a promising approach to NISQ-ready quantum community detection, catalyzing the application of quantum computers for the network structure analysis of large-scale, real-world problem instances. [ABSTRACT FROM AUTHOR]

Relation extraction tasks aim to predict potential relations between entities in a target sentence. As entity mentions have ambiguity in sentences, some important contextual information can guide the semantic representation of entity mentions to improve the accuracy of relation extraction. However, most existing relation extraction models ignore the semantic guidance of contextual information to entity mentions and treat entity mentions in and the textual context of a sentence equally. This results in low-accuracy relation extractions. To address this problem, we propose a contextual semantic-guided entity-centric graph convolutional network (CEGCN) model that enables entity mentions to obtain semantic-guided contextual information for more accurate relational representations. This model develops a self-attention enhanced neural network to concentrate on the importance and relevance of different words to obtain semantic-guided contextual information. Then, we employ a dependency tree with entities as global nodes and add virtual edges to construct an entity-centric logical adjacency matrix (ELAM). This matrix can enable entities to aggregate the semantic-guided contextual information with a one-layer GCN calculation. The experimental results on the TACRED and SemEval-2010 Task 8 datasets show that our model can efficiently use semantic-guided contextual information to enrich semantic entity representations and outperform previous models. [ABSTRACT FROM AUTHOR]

Let G be a graph on n vertices. The Estrada index of G is an invariant that is calculated from the eigenvalues of the adjacency matrix of a graph. V. Nikiforov studied hybrids of A (G) and D (G) and defined the A α -matrix for every real α ∈ [ 0 , 1 ] as: A α (G) = α D (G) + (1 − α) A (G). In this paper, using a different demonstration technique, we present a way to compare the Estrada index of the A α -matrix with the Estrada index of the adjacency matrix of the graph G. Furthermore, lower bounds for the Estrada index are established. [ABSTRACT FROM AUTHOR]

The energy of a graph G as a chemical concept leading to HMO theory was introduced by Hückel in 1931 and developed into a mathematical interpretation many years later when Gutman in 1978 gave his famous definition of the graph energy as the sum of the absolute values of the eigenvalues of the adjacency matrix of G. One of the general requirements for any topological index is that similar molecules have close TI values, which is called smoothness. To explore this property, we consider two variants of structure sensitivity and abruptness as introduced by Furtula et al. in 2013 and 2019, for hydrocarbons with up to 20 carbon atoms. Finally, we investigate the relationships between graph energies of acyclic hydrocarbons compared to their cyclic versions. [ABSTRACT FROM AUTHOR]

Graph embedding plays an important role in the analysis and study of typical non-Euclidean data, such as graphs. Graph embedding aims to transform complex graph structures into vector representations for further machine learning or data mining tasks. It helps capture relationships and similarities between nodes, providing better representations for various tasks on graphs. Different orders of neighbors have different impacts on the generation of node embedding vectors. Therefore, this paper proposes a multi-order adjacency view encoder to fuse the feature information of neighbors at different orders. We generate different node views for different orders of neighbor information, consider different orders of neighbor information through different views, and then use attention mechanisms to integrate node embeddings from different views. Finally, we evaluate the effectiveness of our model through downstream tasks on the graph. Experimental results demonstrate that our model achieves improvements in attributed graph clustering and link prediction tasks compared to existing methods, indicating that the generated embedding representations have higher expressiveness. [ABSTRACT FROM AUTHOR]

Nowadays, graph representation learning methods, in particular graph neural network methods, have attracted great attention and performed well in many downstream tasks. However, most graph neural network methods have a single perspective since they start from the edges (or adjacency matrix) of graphs, ignoring the mesoscopic structure (high-order local structure). In this paper, we introduce HS-GCN (High-order Node Similarity Graph Convolutional Network), which can mine the potential structural features of graphs from different perspectives by combining multiple high-order node similarity methods. We analyze HS-GCN theoretically and show that it is a generalization of the convolution-based graph neural network methods from different normalization perspectives. A series of experiments have shown that by combining high-order node similarities, our method can capture and utilize the high-order structural information of the graph more effectively, resulting in better results. [ABSTRACT FROM AUTHOR]

The domain of Aspect Level Sentiment Classification, in which the sentiment toward a given aspect is analyzed, attracts much attention in NLP. Recently, the state-of-the-art Aspect Level Sentiment Classification methods are devised by using the Graph Convolutional Networks to deal with both the semantics and the syntax of the sentence. Generally, the parsing of syntactic structure inevitably incorporates irrelevant information toward the aspect. Besides, the syntactic and semantic alignment and uniformity that contribute to the sentiment delivery is currently neglected during processing. In this work, a Triplet Contrastive Learning Network is developed to coordinate the syntactic information and the semantic information. To start with, the aspect-oriented sub-tree is constructed to replace the syntactic adjacency matrix. Further, a sentence-level contrastive learning scheme is proposed to highlight the features of sentiment words. Based on The Triple Contrastive Learning, the syntactic information and the semantic information are thoroughly interacted and coordinated whilst the global semantics and syntax can be exploited. Extensive experiments are performed on three benchmark datasets and achieve accuracies (BERT-based) of 87.40, 82.80, 77.55 on Rest14, Lap14, and Twitter datasets, which demonstrate that our approach achieves state-of-the-art results in Aspect Level Sentiment Classification task. [ABSTRACT FROM AUTHOR]

The Estrada index of a graph G is defined as E E (G) = ∑ i = 1 n e λ i , where λ 1 , λ 2 , ... , λ n are the eigenvalues of the adjacency matrix of G. A unicyclic graph is a connected graph with a unique cycle. Let U (n , d) be the set of all unicyclic graphs with n vertices and diameter d. In this paper, we give some transformations which can be used to compare the Estrada indices of two graphs. Using these transformations, we determine the graphs with the maximum Estrada indices among U (n , d) . We characterize two candidate graphs with the maximum Estrada index if d is odd and three candidate graphs with the maximum Estrada index if d is even. [ABSTRACT FROM AUTHOR]

For α ∈ [ 0 , 1 ] , let A α (G σ) = α D (G) + (1 − α) A (G σ) , where G is a simple undirected graph, D (G) is the diagonal matrix of its vertex degrees and A (G σ) is the adjacency matrix of the signed graph G σ whose underlying graph is G. In this paper, basic properties of A α (G σ) are obtained, its positive semidefiniteness is studied and some bounds on its eigenvalues are derived—in particular, lower and upper bounds on its largest eigenvalue are obtained. [ABSTRACT FROM AUTHOR]

In recent years, graph convolutional neural networks (GCNs) have become a popular research topic due to their outstanding performance in various complex network data mining tasks. However, current research on graph neural networks lacks understanding of the high-order structural features of networks, focusing mostly on node features and first-order neighbor features. This article proposes two new models, MGAT and MGATv2, by introducing high-order structure motifs that frequently appear in networks and combining them with graph attention mechanisms. By introducing a mixed information matrix based on motifs, the generation process of graph attention coefficients is improved, allowing the model to capture higher-order structural features. Compared with the latest research on various graph neural networks, both MGAT and MGATv2 achieve good results in node classification tasks. Furthermore, through various experimental studies on real datasets, we demonstrate that the introduction of network structural motifs can effectively enhance the expressive power of graph neural networks, indicating that both high-order structural features and attribute features are important components of network feature learning. [ABSTRACT FROM AUTHOR]

Let G be a graph, for any real 0 ≤ α ≤ 1 , Nikiforov defines the matrix A α (G) as A α (G) = α D (G) + (1 − α) A (G) , where A (G) and D (G) are the adjacency matrix and diagonal matrix of degrees of the vertices of G. This paper presents some extremal results about the spectral radius ρ α (G) of the matrix A α (G) . In particular, we give a lower bound on the spectral radius ρ α (G) in terms of order and independence number. In addition, we obtain an upper bound for the spectral radius ρ α (G) in terms of order and minimal degree. Furthermore, for n > l > 0 and 1 ≤ p ≤ ⌊ n − l 2 ⌋ , let G p ≅ K l ∨ (K p ∪ K n − p − l) be the graph obtained from the graphs K l and K p ∪ K n − p − l and edges connecting each vertex of K l with every vertex of K p ∪ K n − p − l. We prove that ρ α (G p + 1) < ρ α (G p) for 1 ≤ p ≤ ⌊ n − l 2 ⌋ − 1 . [ABSTRACT FROM AUTHOR]

The ontology knowledge base (KB) can be divided into two parts: TBox and ABox, where the former models schema-level knowledge within the domain, and the latter is a set of statements of assertions or facts about instances. ABox reasoning is a process of discovering implicit knowledge in ABox based on the existing KB, which is of great value in KB applications. ABox reasoning is influenced by both the complexity of TBox and scale of ABox. The traditional logic-based ontology reasoning methods are usually designed to be provably sound and complete but suffer from long algorithm runtimes and do not scale well for ontology KB represented by OWL DL (Description Logic). In some application scenarios, the soundness and completeness of reasoning results are not the key constraints, and it is acceptable to sacrifice them in exchange for the improvement of reasoning efficiency to some extent. Based on this view, an approximate reasoning method for large-scale ABox in OWL DL KBs was proposed, which is named the ChunfyReasoner (CFR). The CFR introduces neural-symbolic learning into ABox reasoning and integrates the advantages of symbolic systems and neural networks (NNs). By training the NN model, the CFR approximately compiles the logic deduction process of ontology reasoning, which can greatly improve the reasoning speed while ensuring higher reasoning quality. In this paper, we state the basic idea, framework, and construction process of the CFR in detail, and we conduct experiments on two open-source ontologies built on OWL DL. The experimental results verify the effectiveness of our method and show that the CFR can support the applications of large-scale ABox reasoning of OWL DL KBs. [ABSTRACT FROM AUTHOR]

Accurate traffic flow prediction in road networks is essential for intelligent transportation systems (ITS). Since traffic data are collected from the road network with spatial topological and time series sequences, the traffic flow prediction is regarded as a spatial–temporal prediction task. With the powerful ability to model the non-Euclidean data, the graph convolutional network (GCN)-based models have become the mainstream framework for traffic forecasting. However, existing GCN-based models either use the manually predefined graph structure to capture the spatial features, ignoring the heterogeneity of road networks, or simply perform 1-D convolution with fixed kernel to capture the temporal dependencies of traffic data, resulting in insufficient long-term temporal feature extraction. To solve those issues, a spatial–temporal correlation constrained dynamic graph convolutional network (STC-DGCN) is proposed for traffic flow forecasting. In STC-DGCN, a spatial–temporal embedding encoder module (STEM) is first constructed to encode the dynamic spatial relationships for road networks at different time steps. Then, a temporal feature encoder module with heterogeneous time series correlation modeling (TFE-HCM) and a spatial feature encoder module with dynamic multi-graph modeling (SFE-DCM) are designed to generate dynamic graph structures for effectively capturing the dynamic spatial and temporal correlations. Finally, a spatial–temporal feature fusion module based on a gating fusion mechanism (STM-GM) is proposed to effectively learn and leverage the inherent spatial–temporal relationships for traffic flow forecasting. Experimental results from three real-world traffic flow datasets demonstrate the superior performance of the proposed STC-DGCN compared with state-of-the-art traffic flow forecasting models. [ABSTRACT FROM AUTHOR]

The logistics demands of industries represented by e-commerce have experienced explosive growth in recent years. Vehicle path-planning plays a crucial role in optimization systems for logistics and distribution. A path-planning scheme suitable for an actual scenario is the key to reducing costs and improving service efficiency in logistics industries. In complex application scenarios, however, it is difficult for conventional heuristic algorithms to ensure the quality of solutions for vehicle routing problems. This study proposes a joint approach based on the genetic algorithm and graph convolutional network for solving the capacitated vehicle routing problem with multiple distribution centers. First, we use the heuristic method to modularize the complex environment and encode each module based on the constraint conditions. Next, the graph convolutional network is adopted for feature embedding for the graph representation of the vehicle routing problem, and multiple decoders are used to increase the diversity of the solution space. Meanwhile, the REINFORCE algorithm with a baseline is employed to train the model, ensuring quick returns of high-quality solutions. Moreover, the fitness function is calculated based on the solution to each module, and the genetic algorithm is employed to seek the optimal solution on a global scale. Finally, the effectiveness of the proposed framework is validated through experiments at different scales and comparisons with other algorithms. The experimental results show that, compared to the single decoder GCN-based solving method, the method proposed in this paper improves the solving success rate to 100% across 15 generated instances. The average path length obtained is only 11% of the optimal solution produced by the GCN-based multi-decoder method. [ABSTRACT FROM AUTHOR]

This article investigates a class of multi-agent systems (MASs) with known dynamics external disturbances, where the communication graph is directed, and the followers have undirected connections. To eliminate the impacts of external disturbance, the technologies of disturbance observer-based control are introduced into the containment control problems. Additionally, to save communication costs and energy consumption, a distributed disturbance observer-based event-triggered controller is employed to achieve containment control and reject disturbance. Furthermore, designing the event-triggered function using an exponential function is beneficial for a time-dependent term while ensuring the exclusion of Zeno behavior. Finally, a numerical simulation is provided to validate the effectiveness of the theoretical analysis. [ABSTRACT FROM AUTHOR]

A streaming graph is a constantly growing sequence of edges, which forms a dynamic graph that changes with every edge in the stream. An anomalous behavior in a streaming graph can be modeled as an edge or a subgraph that is unusual compared to the rest of the graph. Identifying anomalous behaviors in real time is essential to the early warning of abnormal or notable events. Due to the complexity of the problem, little work has been reported so far to solve the problem. In this paper, we propose Finger-based Higher-order Graph Sketch (FHGS for short), which is an approximate data structure for streaming graphs with linear memory usage, high update speed, and high accuracy and supports both edge and subgraph anomaly detection. FHGS first maps each edge into a matrix based on hash functions, and then counts its frequency in a time window with unique fingerprints for detecting anomalies. Extensive experiments confirm that our approach generate high-quality results compared to baseline methods. [ABSTRACT FROM AUTHOR]

A hierarchical consensus control algorithm based on value function decomposition is proposed for hierarchical multi-agent systems. To implement the consensus control algorithm, the reward function of the multi-agent systems can be decomposed, and two value functions can be obtained by analyzing the communication content and the corresponding control objective of each layer in the hierarchical multi-agent systems. Therefore, for each agent in the systems, a dual-critic network and a single-actor network structure are applied to realize the objective of each layer. In addition, the target network is introduced to prevent overfitting in the critic network and improve the stability of the online learning process. During the updating of network parameters, a soft updating mechanism and experience replay buffer are introduced to slow down the update rate of the network and improve the utilization rate of training data. The convergence and stability of the consensus control algorithm with the soft updating mechanism are analyzed theoretically. Finally, the correctness of the theoretical analysis and the effectiveness of the algorithm were verified by two experiments. [ABSTRACT FROM AUTHOR]

The analysis of complex system reliability is an area of growing interest, particularly given the diverse and intricate nature of the subsystems and components these systems encompass. Tackling the reliability of such multifaceted systems presents challenges, including component wear, multiple failure modes, the cascading effects of these failures, and the associated uncertainties, which require careful consideration. While traditional studies have examined these elements, the dynamic interplay of information between subsystems and the overarching system has only recently begun to draw focus. A notably understudied aspect is the reliability analysis of complex real-time systems that must adapt to evolving operational conditions. This paper proposes a novel methodology for assessing the reliability of complex real-time systems. This method integrates complex network theory, thus capturing the intricate operational characteristics of these systems, with adjustments to several key complex network parameters to define the nuances of communication within the network framework. To showcase the efficacy and adaptability of our approach, we present case studies on railway and maritime systems. For the railway system, our analysis spans various operational scenarios: from single train operations to simultaneous operations across multiple or different radio block center regions, accounting for node and edge failures. In maritime systems, the case studies employing the VHF data exchange system under operational scenarios are subject to network reliability analysis, successfully pinpointing critical vulnerabilities and modules of high importance. The findings of our research are promising, demonstrating that the proposed method not only accurately evaluates the overall reliability of complex systems but also identifies the pivotal weak points—be it modules or links—warranting attention for system enhancement. [ABSTRACT FROM AUTHOR]

This paper investigates the problem of fixed-time event-triggered consensus control for a class of multi-agent systems with disturbed and non-linear dynamics. A fixed-time consensus protocol based on an event-triggered strategy is proposed, which can ensure a fixed-time event-triggered consensus, reduce energy consumption, and decrease the frequency of controller updates. The control protocol can also be applied to the case when the systems are free of disturbances; it solves the problem of high convergence time of the systems and reduces energy consumption of the systems. Sufficient conditions are proposed for the multi-agent systems with disturbed and non-linear dynamics to achieve the fixed-time event-triggered consensus by using algebraic graph theory, inequalities, fixed-time stability theory, and Lyapunov stability theory. Finally, simulation results show that the proposed control protocol has the advantages of both event-triggered and fixed-time convergence; compared to previous work, the convergence time of the new control protocol is greatly reduced (about 1.5 s) and the update times are also greatly reduced (less than 50 times), which is consistent with the theoretical results. [ABSTRACT FROM AUTHOR]

The shortest path problem is fundamental in graph theory and has been studied extensively due to its practical importance. Despite this aspect, finding the shortest path between two nodes remains a significant challenge in many applications, as it often becomes complex and time consuming. This complexity becomes even more challenging when constraints make the problem non-additive, thereby increasing the difficulty of finding the optimal path. The objective of this paper is to present a broad perspective on the conventional shortest path problem. It introduces a new method to classify cost functions associated with graphs by defining distinct sets of cost functions. This classification facilitates the exploration of line graphs and an understanding of the upper bounds on the transformation sizes for these types of graphs. Based on these foundations, the paper proposes a practical methodology for solving non-additive shortest path problems. It also provides a proof of optimality and establishes an upper bound on the algorithmic cost of the proposed methodology. This study not only expands the scope of traditional shortest path problems but also highlights their computational complexity and potential solutions. [ABSTRACT FROM AUTHOR]

Over the past few years, there has been a surge in research attention towards tasks involving graph data, largely due to the impressive performance demonstrated by graph neural networks (GNNs) in handling such information. Currently, out-of-distribution (OOD) detection in graphs is a hot research topic. The goal of graph OOD detection is to identify nodes or new graphs that differ from the training data distribution, primarily in terms of attributes and structures. OOD detection is crucial for enhancing the stability, security, and robustness of models. In various applications, such as biological networks and financial fraud, graph OOD detection can help models identify anomalies or unforeseen situations, thereby enabling appropriate responses. In node-level OOD detection, existing models typically only consider first-order neighbors. This paper introduces graph diffusion to the OOD detection task for the first time, proposing the HOOD model, a graph diffusion-based OOD node detection algorithm. Specifically, the original graph is processed through graph diffusion to obtain a new graph that can directly capture high-order neighbor information, overcoming the limitation that message passing must go through first-order neighbors. The new graph is then sparsified using a top-k approach. Based on entropy information, regularization is employed to ensure the uncertainty of OOD nodes, thereby giving these nodes higher scores and enabling the model to effectively detect OOD nodes while ensuring the accuracy of in-distribution node classification. Experimental results demonstrate that the HOOD model outperforms existing methods in both node classification and OOD detection tasks on multiple benchmarks, highlighting its robustness and effectiveness. [ABSTRACT FROM AUTHOR]

This paper focuses on the design of a continuous distributed observer for linear systems under multirate sampled output measurements involving multiple delays. It is mathematically proved that the continuous distributed observer can achieve estimation in a sensor network environment, where output measurements from each sensor are available at different sampling instants, whether these times are periodic or aperiodic, and despite the presence of multiple time-varying delays. Each sampled and delayed measurement represents a node of the network, necessitating a dedicated observer for each node, which has access to only part of the system's output and communicates with its neighbors according to a given network graph. The exponential convergence of the error dynamics is ensured by Lyapunov stability analysis, which accounts for the influence of the sampled and delayed measurements at each node. To demonstrate the effectiveness of the proposed observer, simulation tests were conducted on the tracking control of chasing satellites in low Earth orbit (LEO), encompassing both small and large sampling rates and delays. The continuous distributed observer with sampled output measurements exhibited convergence in scenarios with different sampling intervals, even in the presence of time-varying delays, achieving asymptotic omniscience, as demonstrated in the convergence analysis. [ABSTRACT FROM AUTHOR]

We consider the problem of finding the largest clique of a graph. This is an NP-hard problem and no exact algorithm to solve it exactly in polynomial time is known to exist. Several heuristic approaches have been proposed to find approximate solutions. Markov Chain Monte Carlo is one of these. In the context of Markov Chain Monte Carlo, we present a class of "parallel dynamics", known as Probabilistic Cellular Automata, which can be used in place of the more standard choice of sequential "single spin flip" to sample from a probability distribution concentrated on the largest cliques of the graph. We perform a numerical comparison between the two classes of chains both in terms of the quality of the solution and in terms of computational time. We show that the parallel dynamics are considerably faster than the sequential ones while providing solutions of comparable quality. [ABSTRACT FROM AUTHOR]

Stock index fluctuations are characterized by high noise and their accurate prediction is extremely challenging. To address this challenge, this study proposes a spatial–temporal–bidirectional long short-term memory (STBL) model, incorporating spatiotemporal attention mechanisms. The model enhances the analysis of temporal dependencies between data by introducing graph attention networks with multi-hop neighbor nodes while incorporating the temporal attention mechanism of long short-term memory (LSTM) to effectively address the potential interdependencies in the data structure. In addition, by assigning different learning weights to different neighbor nodes, the model can better integrate the correlation between node features. To verify the accuracy of the proposed model, this study utilized the closing prices of the Hong Kong Hang Seng Index (HSI) from 31 December 1986 to 31 December 2023 for analysis. By comparing it with nine other forecasting models, the experimental results show that the STBL model achieves more accurate predictions of the closing prices for short-term, medium-term, and long-term forecasts of the stock index. [ABSTRACT FROM AUTHOR]

The security of traditional public key cryptography algorithms depends on the difficulty of the underlying mathematical problems. Asymmetric topological encryption is a graph-dependent encryption algorithm produced to resist attacks by quantum computers on these mathematical problems. The security of this encryption algorithm depends on two types of NP-complete problems: subgraph isomorphism and graph coloring. Topological coding technology refers to the technology of generating key strings or topology signature strings through topological coding graphs. We take odd-graceful labeling and set-ordered odd-graceful labeling as limiting functions, and propose two kinds of topological coding generation technique, which we call the random leaf-adding operation and randomly adding edge-removing operation. Through these two techniques, graphs of the same scale and larger scales can be generated with the same type of labeling so as to derive more number strings, expand the key space, and analyze the topology and property of the generated graphs. [ABSTRACT FROM AUTHOR]

Moran's I is a spatial autocorrelation measure of univariate spatial data. Therefore, even if p spatial data exist, we can only obtain p values for Moran's I. In other words, Moran's I cannot measure the degree of spatial autocorrelation of multivariate spatial data as a single value. This paper addresses this issue. That is, we extend Moran's I so that it can measure the degree of spatial autocorrelation of multivariate spatial data as a single value. In addition, since the local version of Moran's I has the same problem, we extend it as well. Then, we establish their properties, which are fundamental for applied work. Numerical illustrations of the theoretical results obtained in the paper are also provided. [ABSTRACT FROM AUTHOR]

In network data analysis, one of the important problems is determining if two collections of networks are drawn from the same distribution. This problem can be modeled in the framework of two-sample hypothesis testing. Several graph-based two-sample tests have been studied. However, the methods mainly focus on binary graphs, and many real-world networks are weighted. In this paper, we apply empirical likelihood to test the difference in two populations of weighted networks. We derive the limiting distribution of the test statistic under the null hypothesis. We use simulation experiments to evaluate the power of the proposed method. The results show that the proposed test has satisfactory performance. Then, we apply the proposed method to a biological dataset. [ABSTRACT FROM AUTHOR]

The ABS (atom-bond sum-connectivity) index of a graph G is denoted by A B S (G) and is defined as ∑ x y ∈ E (G) (d x + d y) − 1 (d x + d y − 2) , where d x represents the degree of the vertex x in G. In this paper, we derive the best possible upper bounds on the ABS index for fixed-order trees possessing a given maximum degree, which provides a solution to the open problem proposed quite recently by Hussain, Liu and Hua. [ABSTRACT FROM AUTHOR]

This paper proposes a decentralized adaptive event-triggered fault-tolerant cooperative control (ET-FTCC) scheme for multiple unmanned aerial vehicles (UAVs) and unmanned ground vehicles (UGVs) with actuator faults and external disturbances under denial-of-service (DoS) attacks. The multiple UAVs and UGVs have a larger search radius, which is important in both the civilian and military domains. The different dynamics between UAVs and UGVs result in unbalanced interactions in the communication topologies, which increases the complexity of cooperative control. DoS attacks are conducted in both sensor and control channels. The dynamic models of UAVs and UGVs are introduced firstly, and the unified heterogeneous multiagent system model with actuator faults is established. The composite observer is designed to obtain the information of state and lumped disturbance, which is used to design the controller. In order to save the limited communication network resources, the event-triggered mechanism is introduced. The transformed error is presented by using the prescribed performance function (PPF). Then, the sliding-mode manifold is presented by combining the event-triggered control scheme to achieve the tracking purpose with actuator faults, external disturbances, and DoS attacks. Based on the Lyapunov function approach, the tracking errors are bounded within the prescribed boundary. Finally, the effectiveness of the proposed method is verified by qualitative analysis and quantitative analysis of the simulation results. This study can enhance the security and reliability of heterogeneous multiagent systems, providing technical support for the safe operation of unmanned systems. This paper mainly solves the FTCC problem of second-order nonlinear heterogeneous multiagent systems, and further research is needed for the FTCC problem of higher-order nonlinear heterogeneous multi-agent systems. In addition, the system may encounter multiple cyber attacks. As one of the future research works, we can extend the results of this paper to high-order nonlinear systems under multiple cyber attacks, which contain DoS attacks and deception attacks, and achieve fault-tolerant cooperative control of heterogeneous multiagent systems. [ABSTRACT FROM AUTHOR]

The incidence of edges on vertices is a cornerstone of graph theory, with profound implications for various graph properties and applications. Understanding degree distributions and their implications is crucial for analyzing and modeling real-world networks. This study investigates the impact of vertex degree distribution on the energy landscape of graphs in network theory. By analyzing how vertex connectivity influences graph energy, the research enhances the understanding of network structure and dynamics. It establishes important properties and sharp bounds related to degree spectra and degree energy. Furthermore, the study determines the degree spectra and degree energy for several key families of graphs, providing valuable insights with potential applications across various fields. [ABSTRACT FROM AUTHOR]

Causal structure learning plays a crucial role in the current field of artificial intelligence, yet existing causal structure learning methods are susceptible to interference from data sample noise and often become trapped in local optima. To address these challenges, this paper introduces a continuous optimization algorithm based on the curriculum learning framework: CL-NOTEARS. The model utilizes the curriculum loss function during training as a priority evaluation metric for curriculum selection and formulates the sample learning sequence of the model through task-level curricula, thereby enhancing the model's learning performance. A curriculum-based sample prioritization strategy is employed that dynamically adjusts the training sequence based on variations in loss function values across different samples throughout the training process. The results demonstrate a significant reduction in the impact of sample noise in the data, leading to improved model training performance. [ABSTRACT FROM AUTHOR]