Search

As Internet users interacting with their different friends in different social networks, the de-anonymization problem has been raising improving concern. Since the assailants may de-anonymize a social network by matching it with a correlated sanitized network and identifying anonymized user identities, multifarious arts study on the theoretical conditions or practical algorithms for correctly de-anonymizing a social network. Except for the structural information of these social networks, there has also been bounteous works taking advantage of some pre-identied seed nodes for reference in the anonymized network. In this paper, we systematically probe the theoretical conditions and algorithmic approaches for correctly matching two different-sized social networks by leveraging the multi-hop neighborhood relationships. A limited number of seeds are also taken into consideration as auxiliary information. To this end, we introduce the de-anonymization problem with the aid of the collectiveness and the collective adjacency disagreements, which are the collection of disagreements of different multi-hop adjacency matrices. We theoretically demonstrate that minimizing the collective adjacency disagreements can help match two social networks even in a very sparse circumstance, as it signicantly enlarges the difference between the mismatched node pairs and the correctly matched pairs. The seeds is proved to bring positive inuence in accuracy.

The data-driven intelligent health state diagnosis strategy has been successfully applied in modern industrial equipments. However, many of existing researches suffer from two major deficiencies: Firstly, the sample independence assumption is widely adopted, so the influences of the relationship between samples on the overall performances are not explored. Secondly, most of the above-mentioned application objects are typical key functional components (such as bearings, gearboxes, etc.), and researches on the intelligent health state diagnosis of planar parallel manipulator are rarely reported. To address these issues, a novel intelligent health state diagnosis method, termed multi-scale graph-guided convolutional network with node attention (MSGCN-NA), is proposed for a 3-PRR (P and R represent prismatic and revolute pairs respectively) planar parallel manipulator. Specifically, the developed MSGCN-NA model mainly contains two parts: a) the one is an unsupervised convolutional auto-encoder, which is employed for the extraction of deep representation features, and then combined with Pearson metric to establish the adjacency matrix. b) the other part is the constructed multi-scale graph convolutional network, in which the node attention mechanism is adopted to achieve cross-scale fusion of different neighborhood information. The effectiveness of the proposed MSGCN-NA method is fully verified based on the simulation and experimental scenarios, the results show that MSGCN-NA can achieve superior diagnosis performances.

Based on the fact that the traditional probability distribution entropy describing a local feature of the system cannot effectively capture the global topology variations of the network, some indicators constructed by the network adjacency matrix and Laplacian matrix come into being. Specifically, these measures are based on the eigenvalues of the scaled Laplace matrix, the eigenvalues of the network communicability matrix, and the spectral entropy based on information diffusion that has been proposed recently, respectively. In this article, we systematically study the dependence of these measures on the topological structure of the network. We prove from various aspects that spectral entropy has a better ability to identify the global topology than the traditional distribution entropy. Furthermore, the indicator based on the eigenvalues of the network communicability matrix achieves good results in some aspects while, overall, the spectral entropy is able to identify network topology variations from a global perspective.

Road traffic sensing is pivotal in all the imperative services offered by Intelligent Transportation Systems (ITS). Both static and probe based traffic sensing technologies aid in the acquisition of road traffic parameters, represented as spatio-temporal traffic data matrices. These matrices suffer from inevitable data losses, urging accurate matrix reconstruction. Many Low Rank Matrix Completion (LR-MC) approaches have been formulated in the literature, with varied optimization problems and solution methods. The subsequent approaches have exploited spatio-temporal constraints to further reduce the reconstruction error. In this paper, these formulations are modified to develop two new LR-MC approaches, the Augmented Lagrangian Sparsity Regularized Matrix Factorization (AL-SRMF) and the Constrained Low Rank (C-LR). AL-SRMF replaces the Alternating Least Squares (ALS) solution method of SRMF with an AL based method. Optimization in C-LR inherits its temporal constraint from the Temporal and Adaptive Spatial constrained Low Rank (TAS-LR) approach, while adopting its spatial constraint similar to SRMF. Spatial constraint in both C-LR and AL-SRMF is deduced by computing an adjacency matrix that leverages graph notion of the geographical road traffic network. For experimental validations of the proposed approaches, traffic matrices of Californian road network are obtained from PEMS database. Investigations reveal that for a signal integrity (SI) of 0.5, C-LR demonstrated a Normalized Mean Absolute Error (NMAE) of 3.4% and a Root Mean Square Error (RMSE) of 3.2. With a slight increase in computational time, the AL-SRMF rendered least values of NMAE and RMSE, 2.4% and 2.3 respectively, demonstrating significantly better performance than the state-of-the-art approaches.

Computing the number of loop-free k-hop paths is crucial for selecting services in social networks, for example a service consumer require to evaluate the trustworthiness of a service provider along the social trust paths, there are usually many social trust paths between two unconnected participants, we need know the number of loop-free k-hop trust propogation paths; other applications include the similarity computation for services recommendation, information diffusion, etc. Previously, the number of k-hop paths is roughly estimated by the elements in the k multiplications of the network adjacency matrix. This method calculates much more k-hop paths with loops, counted as loop-free k-hop paths, which may result in obvious errors in applications. Accurate mathematical formulas for counting loop-free paths are obtained in this paper for paths with 5 or less hops, an approximate method is provided for larger hops. Based on the proposed loop removing algorithm (LRA), the typical method for predicting trust between any two people is improved, the error rate is dramatically reduced; the traditional path based similarity indices are improved, which are much accurate than their antecedent counterparts; and a method for computing the spreading probability for information spreading in the famous independent cascade model is also obtained. To reveal the effectiveness of the proposed LRA, this paper also provide a traversal depth-first search algorithm (DFSA) for finding the true number of k-hop loop-free paths.

Big data analytics and mining have the potential to enable real-time decision-making and control in a range of Internet of Things (IoT) application domains, such as the Internet of Vehicles, the Internet of Wings and the Airport of Things. The prediction toward air mobility, which is essential to the studies of air traffic management, has been a challenging task due to the complex spatial and temporal dependencies in air traffic data with highly nonlinear and variational patterns. Existing works for air traffic prediction only focus on either modeling static traffic patterns of individual flight or temporal correlation, with no or limited addressing of the spatial impact, namely the propagation of traffic perturbation among airports. In this paper, we propose to leverage the concept of graph and model the airports as nodes with time-series features and conduct data mining on graph-structured data. To be specific, firstly, Airline On-Time Performance (AOTP) Data is preprocessed to generate a temporal graph dataset, which includes three features: the number, average delay, and average taxiing time of departure and arrival flights. Then a spatial-temporal graph neural networks model is implemented to forecast the mobility level at each airport over time, where a combination of graph convolution and time-dimensional convolution is used to capture the spatial and temporal correlation simultaneously. Experiments on the dataset demonstrate the advantage of the model on spatial-temporal air mobility prediction, together with the impact of different priors on adjacency matrices and the effectiveness of temporal attention mechanism. Finally, we analyze the prediction performance and discuss the capability of our model. The prediction framework proposed in this work has the potential to be generalized to other spatial-temporal tasks in IoT.

Knowledge graphs have received intensive research interests. When the labels of most nodes or datapoints are missing, anchor graph and hierarchical anchor graph models can be employed. With an anchor graph or hierarchical anchor graph, we only need to optimize the labels of the coarsest anchors, and the labels of datapoints can be inferred from these anchors in a coarse-to-fine manner. The complexity of optimization is therefore reduced to a cubic cost with respect to the number of the coarsest anchors. However, to obtain a high accuracy when a data distribution is complex, the scale of this anchor set still needs to be large, which thus inevitably incurs an expensive computational burden. As such, a challenge in scaling up these models is how to efficiently estimate the labels of these anchors while keeping classification performance. To address this problem, we propose a novel approach that adds an anchor label predictor in the conventional anchor graph and hierarchical anchor graph models. In the proposed approach, the labels of the coarsest anchors are not directly optimized, and instead, we learn a label predictor which estimates the labels of these anchors with their spectral representations. The predictor is optimized with a regularization on all datapoints based on a hierarchical anchor graph, and we show that its solution only involves the inversion of a small-size matrix. Built upon the anchor hierarchy, we design a sparse intra-layer adjacency matrix over these anchors, which can simultaneously accelerate spectral embedding and enhance effectiveness. Our approach is named Faster Learning6 on Anchor Graph (FLAG) as it improves conventional anchor-graph-based methods in terms of efficiency. Experiments on a variety of publicly available datasets with sizes varying fromthousands to millions of Q1 samples demonstrate the effectiveness of our approach.

This paper addresses the task of detecting and recognizing human-object interactions (HOI) in images. Considering the intrinsic complexity and structural nature of the task, we introduce a cascaded parsing network (CP-HOI) for a multi-stage, structured HOI understanding. At each cascade stage, an instance detection module progressively refines HOI proposals and feeds them into a structured interaction reasoning module. Each of the two modules is also connected to its predecessor in the previous stage. The structured interaction reasoning module is built upon a graph parsing neural network (GPNN). In particular, GPNN infers a parse graph that i) interprets meaningful HOI structures by a learnable adjacency matrix, and ii) predicts action (edge) labels. Within an end-to-end, message-passing framework, GPNN blends learning and inference, iteratively parsing HOI structures and reasoning HOI representations (i.e., instance and relation features). Further beyond relation detection at a bounding-box level, we make our framework flexible to perform fine-grained pixel-wise relation segmentation; this provides a new glimpse into better relation modeling. A preliminary version of our CP-HOI model reached 1st place in the ICCV2019 Person in Context Challenge, on both relation detection and segmentation. Our CP-HOI shows promising results on two popular HOI recognition benchmarks, i.e., V-COCO and HICO-DET.

—In graph neural networks (GNNs), pooling operators compute local summaries of input graphs to capture their global properties, and they are fundamental for building deep GNNs that learn hierarchical representations. In this work, we propose the Node Decimation Pooling (NDP), a pooling operator for GNNs that generates coarser graphs while preserving the overall graph topology. During training, the GNN learns new node representations and fits them to a pyramid of coarsened graphs, which is computed offline in a pre-processing stage. NDP consists of three steps. First, a node decimation procedure selects the nodes belonging to one side of the partition identified by a spectral algorithm that approximates the MAXCUT solution. Afterwards, the selected nodes are connected with Kron reduction to form the coarsened graph. Finally, since the resulting graph is very dense, we apply a sparsification procedure that prunes the adjacency matrix of the coarsened graph to reduce the computational cost in the GNN. Notably, we show that it is possible to remove many edges without significantly altering the graph structure. Experimental results show that NDP is more efficient compared to state-of-the-art graph pooling operators while reaching, at the same time, competitive performance on a significant variety of graph classification tasks. submittedVersion

In view of most current studies on text sentiment classification focus on the deep learning model to obtain the sentimental characteristics of English text. Chinese text sentiment analysis is rarely involved, and only the context information of the statement is considered, but the syntax information of the statement is rarely considered. In this paper, a novel sentiment classification model is proposed (Dependency Tree Graph Convolutional Network, DTGCN) combined Chinese syntactically dependent tree with graph convolution. Firstly, the Bi-GRU (Bi-directional Gated Recurrent Unit) model is used to learn the contextual feature representation of a given text. Secondly, the syntax-dependent tree structure of a given text is constructed, then obtain its adjacency matrix according to the syntax-dependent tree, with the initial features extracted from the bidirectional gate control network, input into the graph convolutional neural network (GCN) to extract the sentimental features of the text; the obtained sentimental characteristics are then input into the classifier SoftMax for text sentimental polarity classification. Finally, the data set is compared with the mainstream neural network model. The experimental results show that the accuracy of the proposed DTGCN model proposed on the data set is 90.51% and the recall rate is 90.34%. Compared with the benchmark models (LSTM, CNN, TextCNN and Bi-GRU), the proposed DTGCN model shows a 4.45% advantage in accuracy. It shows that the proposed DTGCN model can effectively use the grammatical information of Chinese text to mine the hidden relationship in statements, it can improve the accuracy of Chinese text sentiment classification. In addition, the proposed DTGCN model not only improves the performance of sentiment classification in the essay, it also provides a new research method for social network public opinion identification.

Heterogeneous information network (HIN) embedding aims at learning the low-dimensional representation of nodes while preserving structure and semantics in an HIN. Existing methods mainly focus on static networks, while a real HIN usually evolves over time with the addition (deletion) of multiple types of nodes and edges. Because even a tiny change can influence the whole structure and semantics, the conventional HIN embedding methods need to be retrained to get the updated embeddings, which is time-consuming and unrealistic. In this paper, we investigate the problem of dynamic HIN embedding and propose a novel Dynamic HIN Embedding model (DyHNE) with meta-path based proximity. Specifically, we introduce the meta-path based first- and second-order proximities to preserve structure and semantics in HINs. As the HIN evolves over time, we naturally capture changes with the perturbation of meta-path augmented adjacency matrices. Thereafter, we learn the node embeddings by solving generalized eigenvalue problem effectively and employ eigenvalue perturbation to derive the updated embeddings efficiently without retraining. Experiments show that DyHNE outperforms the state-of-the-arts in terms of effectiveness and efficiency.

Link weight prediction is an important subject in network science and machine learning. Its applications to social network analysis, network modeling, and bioinformatics are ubiquitous. Although this subject has attracted considerable attention recently, the performance and interpretability of existing prediction models have not been well balanced. This article focuses on an unsupervised mixed strategy for link weight prediction. Here, the target attribute is the link weight, which represents the correlation or strength of the interaction between a pair of nodes. The input of the model is the weighted adjacency matrix without any preprocessing, as widely adopted in the existing models. Extensive observations on a large number of networks show that the new scheme is competitive to the state-of-the-art algorithms concerning both root-mean-square error and Pearson correlation coefficient metrics. Analytic and simulation results suggest that combining the weight consistency of the network and the link weight-associated latent factors of the nodes is a very effective way to solve the link weight prediction problem.

Traffic forecasting problem remains a challenging task in the intelligent transportation system due to its spatio-temporal complexity. Although temporal dependency has been well studied and discussed, spatial dependency is relatively less explored due to its large variations, especially in the urban environment. In this study, a novel graph convolutional network model, Multi-Weight Traffic Graph Convolutional (MW-TGC) network, is proposed and applied to two urban networks with contrasting geometric constraints. The model conducts graph convolution operations on speed data with multi-weighted adjacency matrices to combine the features, including speed limit, distance, and angle. The spatially isolated dimension reduction operation is conducted on the combined features to learn the dependencies among the features and reduce the size of the output to a computationally feasible level. The output of multi-weight graph convolution is applied to the sequence-to-sequence model with Long Short-Term Memory units to learn temporal dependencies. When applied to two urban sites, urban-core and urban-mix, MW-TGC network not only outperformed the comparative models in both sites but also reduced variance in the heterogeneous urban-mix network. We conclude that MW-TGC network can provide a robust traffic forecasting performance across the variations in spatial complexity, which can be a strong advantage in urban traffic forecasting., Comment: 11 pages, 7 figures, Accepted to IEEE Transactions on Intelligent Transportation Systems (2020)

Clustering large hyperspectral images (HSIs) is a very challenging problem because large HSIs have high dimensionality, large spectral variability, and large computational and memory consumption. Recently, sparse subspace clustering (SSC) has achieved remarkable success in HSI clustering. However, most SSC-based methods suffer from the following bottlenecks for large HSIs: 1) high computational consumption and memory space during the construction of the similarity matrix and decomposition of the graph Laplacian matrix and 2) failure to capture the relationships among dictionary atoms, sparse coefficients, and hyperspectral pixels. To address these challenges, we propose a novel algorithm that extends SSC to cocluster large HSIs, called bipartite graph partition with graph nonnegative matrix factorization (BGP-GNMF). Specifically, to fully explore the characteristics of the spectral and spatial contexts in HSIs, we propose a novel superpixel and pixel coclustering framework with bipartite graph partitioning in the joint sparse representation domain, where superpixel-based dictionary atoms are defined as disjoint vertex sets of the bipartite graph and the joint sparsity representation is mapped into the adjacency matrix of the undirected bipartite graph. To overcome the challenges of high computational consumption and large memory space for large HSIs, the bipartite graph partition with orthonormal constrained nonnegative matrix factorization is proposed to simultaneously cluster the structured dictionary atoms and hyperspectral pixels with an indicator matrix. Finally, to exploit the intrinsic geometry of HSIs, we incorporate manifold regularization into the bipartite graph partition to improve final clustering accuracy. The effectiveness and efficiency of the proposed method are verified on three classical HSIs, and the experimental results illustrate the superiority of the proposed method compared with other state-of-the-art HSI clustering methods.

Convolutional neural networks (CNN) and graph representation learning are two common methods for hyperspectral image (HSI) classification. Recently, graph convolutional neural networks (GCN), a combination of CNN and graph representation learning, have shown great potential in HSI classification problem. However, the existing GCN-based methods have many problems, such as over dependence on the adjacency matrix, usage of a single modal feature, and lower accuracy than the mature CNN method. In this paper, we propose a feature fusion hypergraph convolutional neural network (F2HNN) for HSI classification. F2HNN first generates hyperedges from features of different modalities to construct a hypergraph representing multi-modal features in HSI. Then, the HSI and the extracted hypergraph are input into the hypergraph convolutional neural network for learning. In addition, we proposes three feature fusion strategies. The first strategy is the most basic spatial and spectral feature fusion. The second strategy fuses the spectral features extracted by a pre-trained multilayer perceptron (MLP) with the spatial features to reduce the redundant information of the original spectral features. The third strategy uses the fusion of CNN features, spectral features and spatial features to explore the capabilities of F2HNN. Sufficient experiments on four datasets have proved the effectiveness of F2HNN.

Road information from high-resolution remote sensing images is widely used in various fields, and deep-learning-based methods have effectively shown high road-extraction performance. However, for the detection of roads sealed with tarmac, or covered by trees in high-resolution remote sensing images, some challenges still limit the accuracy of extraction: 1) large intra-class differences between roads, and unclear inter-class differences between urban objects, especially roads and buildings; 2) roads occluded by trees, shadows, and buildings are difficult to extract; and 3) lack of high-precision remote-sensing datasets for roads. To increase the accuracy of road extraction from high-resolution remote-sensing images, we propose a split depth-wise (DW) separable graph convolutional network (SGCN). Firstly, we split DW-separable convolution to obtain channel and spatial features, to enhance the expression ability of road features. Thereafter, we present a graph convolutional network to capture global contextual road information in channel and spatial features. The Sobel gradient operator is used to construct an adjacency matrix of the feature graph. A total of thirteen deep-learning networks were used on the Massachusetts Roads Dataset and nine on our self-constructed mountain road dataset, for comparison with our proposed SGCN. Our model achieved a mean Intersection over Union (IOU) of 81.65% with an F1-score of 78.99% for the Massachusetts Roads dataset, and a mean IOU of 62.45% with an F1-score of 45.06% for our proposed dataset. The visualization results showed that SGCN performs better in extracting covered and tiny roads and is able to effectively extract roads from high-resolution remote-sensing images.

Undirected graphs are frequently used to model phenomena that deal with interacting objects, such as social networks, brain activity and communication networks. The topology of an undirected graph G can be captured by an adjacency matrix; this matrix in turn can be visualized directly to give insight into the graph structure. Which visual patterns appear in such a matrix visualization crucially depends on the ordering of its rows and columns. Formally defining the quality of an ordering and then automatically computing a high-quality ordering are both challenging problems; however, effective heuristics exist and are used in practice.Often, graphs do not exist in isolation but as part of a collection of graphs on the same set of vertices, for example, brain scans over time or of different people.To visualize such graph collections, we need a single ordering that works well for all matrices simultaneously.The current state-of-the-art solves this problem by taking a (weighted) union over all graphs and applying existing heuristics. However, this union leads to a loss of information, specifically in those parts of the graphs which are different. We propose a collection-aware approach to avoid this loss of information and apply it to two popular heuristic methods: leaf order and barycenter.The de-facto standard computational quality metrics for matrix ordering capture only block-diagonal patterns (cliques). Instead, we propose to use Moran's I, a spatial auto-correlation metric, which captures the full range of established patterns. Moran's I refines previously proposed stress measures. Furthermore, the popular leaf order method heuristically optimizes a similar measure which further supports the use of Moran's I in this context. An ordering that maximizes Moran's I can be computed via solutions to the Traveling Salesperson Problem (TSP); orderings that approximate the optimal ordering can be computed more efficiently, using any of the approximation algorithms for metric TSP.We evaluated our methods for simultaneous orderings on real-world datasets using Moran's I as the quality metric. Our results show that our collection-aware approach matches or improves performancecompared to the union approach, depending on the similarity of the graphs in the collection. Specifically, our Moran's I-based collection-aware leaf order implementation consistently outperforms other implementations.Our collection-aware implementations carry no significant additional computational costs.

Hyperspectral images (HSIs) have gained high spectral resolution due to recent advances in spectral imaging technologies. This incurs problems, such as an increased data scale and an increased number of bands for HSIs, which results in a complex correlation between different bands. In the applications of remote sensing and earth observation, ground objects represented by each HSI pixel are composed of physical and chemical non-Euclidean structures, and HSI classification (HIC) is becoming a more challenging task. To solve the above problems, we propose a framework based on a deep attention graph convolutional network (DAGCN). Specifically, we first integrate an attention mechanism into the spectral similarity measurement to aggregate similar spectra. Therefore, we propose a new similarity measurement method, i.e., the mixed measurement of a kernel spectral angle mapper and spectral information divergence (KSAM-SID), to aggregate similar spectra. Considering the non-Euclidean structural characteristics of HSIs, we design deep graph convolutional networks (DeepGCNs) as a feature extraction method to extract deep abstract features and explore the internal relationship between HSI data. Finally, we dynamically update the attention graph adjacency matrix to adapt to the changes in each feature graph. Experiments on three standard HSI data sets, namely, the Indian Pines, Pavia University, and Salinas data sets, demonstrate that the DAGCN outperforms the baselines in terms of various evaluation criteria. For example, on the Indian Pines data set, the overall accuracy of the proposed method achieves 98.61% when the training sample is 10%.

While many machine learning approaches have been widely applied to power system online dynamic stability assessment, how to sufficiently learn spatial-temporal correlations from system transients without losing the interpretability is still a challenging issue. In this paper, a novel networked time series shapelet learning approach is proposed to learn spatial-temporal correlations for transient stability assessment (TSA) in an interpretable manner. Specifically, a network impedance-based adjacency matrix is first introduced to characterize spatial networked correlations. Based on graph structural regularization, this matrix is effectively incorporated into the subsequent learning procedure as spatial constraints. Taking time series trajectories acquired from multiple buses as the inputs, networked shapelet learning is heuristically performed to learn critical sequential features, i.e., networked shapelets, for TSA model derivation. With the learning procedure strategically guided by inherent spatial-temporal correlations of the system, the obtained data-driven TSA model is able to perform highly reliable and interpretable online TSA. Numerical test results on the IEEE 39-bus test system and the realistic GD Power Grid in China verify the superior performances of the proposed approach.

Lossless compression of dynamic 2-D+t and 3-D+t medical data is challenging regarding the huge amount of data, the characteristics of the inherent noise, and the high bit depth. Beyond that, a scalable representation is often required in telemedicine applications. Motion Compensated Temporal Filtering works well for lossless compression of medical volume data and additionally provides temporal, spatial, and quality scalability features. To achieve a high quality lowpass subband, which shall be used as a downscaled representative of the original data, graph-based motion compensation was recently introduced to this framework. However, encoding the motion information, which is stored in adjacency matrices, is not well investigated so far. This work focuses on coding these adjacency matrices to make the graph-based motion compensation feasible for data compression. We propose a novel coding scheme based on constructing so-called motion maps. This allows for the first time to compare the performance of graph-based motion compensation to traditional block-and mesh-based approaches. For high quality lowpass subbands our method is able to outperform the block-and mesh-based approaches by increasing the visual quality in terms of PSNR by 0.53 dB and 0.28 dB for CT data, as well as 1.04 dB and 1.90 dB for MR data, respectively, while the bit rate is reduced at the same time.

In this paper, we propose a new measure of communication performance of linear network systems, the information gain, and we show that this measure is strongly affected by the degree of non-normality of the networks adjacency matrix. Specifically, we prove that the numerical abscissa of the networks adjacency matrix, a well-known indicator of matrix non-normality, regulates the behavior of the information gain. Further, we establish a lower bound on the information gain of positive networks, i.e., weighted networks with positive weights. This bound reveals that the information gain may exhibit an exponential dependence on the graphical distance between the transmitter and the receiver nodes. Finally, we present a design methodology which provably enhances the information gain while keeping the networks weights bounded in magnitude. We illustrate and validate our theoretical findings by means of examples with structured and random networks.

Hyperspectral image (HSI) clustering is extremely challenging because of the complexity of the image structure. Recently, the subspace clustering algorithms have achieved competitive performance for HSIs. However, these methods generally are computationally complex and time-and-memory-consuming, given their reliance on large-scale adjacency matrix learning and graph segmentation, which limits their application to large HSIs and reduces their attractiveness in real applications. In this article, in view of this, two novel sparsity-based clustering algorithms are proposed for large HSIs, named sparse coding-based clustering (SCC) and joint SCC (JSCC). To the best of our knowledge, we are the first to use the sparse representation recovery residual to cluster HSIs. Based on a structured dictionary constructed by k-means and k-nearest neighbor (KNN), an SCC model is constructed to cluster HSIs according to the recovery residual minimization criterion. By dealing with a pixel-wise sparse recovery problem instead of the large-scale graph optimization problem of the whole image, the computational complexity and the time-and-memory cost are reduced to a large degree, which makes sense for practical applications. Then, by introducing the super-pixel neighborhood, a JSCC model is constructed to better explore the interpixel correlation of HSIs and further improve the clustering performance. The proposed algorithms were verified on three widely used HSIs. All the three experiments confirm the effectiveness of the proposed algorithms, which can be considered as competitive tools for use with large HSIs.

Wind speed accurate forecasting plays an important role in preserving the stability of offshore wind power. Most of current predictions are based on a single wind node. It is difficult for this methods to capture wind high dimensional features and latent spatio-temporal dependencies. In this paper, we propose a general graph optimization neural network specifically for multi-node offshore wind speed prediction named spatio-temporal correlation graph neural network. The proposed model firstly employs graph convolution, which performs Laplace transforms instead of the traditional convolution, to capture the potential spatial dependencies from the nodes' relationship and historical time series better. The channel-wise attention makes the original concentrated weights within a region constructed by adjacency matrix disperse to all input nodes, which distinguishes the nodes’ contributions and generates high dimensional spatial features. Long short-term memory is applied to extract temporal correlation from the high dimensional spatial features. The model has ability to excavate the full potential of spatial-temporal dependencies from multiple wind nodes to the utmost. Experiments select 120 wind nodes in the China sea for prediction. The results show that the proposed model can be very competitive with state-of-the-art methods and holds great performance on multi-node and multi-step wind speed forecasting.

Federated learning has been applied to various tasks in intelligent transportation systems to protect data privacy through decentralized training schemes. The majority of the state-of-the-art models in intelligent transportation systems (ITS) are graph neural networks (GNN)-based for spatial information learning. When applying federated learning to the ITS tasks with GNN-based models, the existing frameworks can only protect the data privacy; however, ignore the one of topological information of transportation networks. In this article, we propose a novel federated learning framework to tackle this problem. Specifically, we introduce a differential privacy-based adjacency matrix preserving approach for protecting the topological information. We also propose an adjacency matrix aggregation approach to allow local GNN-based models to access the global network for a better training effect. Furthermore, we propose a GNN-based model named attention-based spatial-temporal graph neural networks (ASTGNN) for traffic speed forecasting. We integrate the proposed federated learning framework and ASTGNN as FASTGNN for traffic speed forecasting. Extensive case studies on a real-world dataset demonstrate that FASTGNN can develop accurate forecasting under the privacy preservation constraint.

Simple graph convolution (SGC) achieves competitive classification accuracy to graph convolutional networks (GCNs) in various tasks while being computationally more efficient and fitting fewer parameters. However, the width of SGC is narrow due to the over-smoothing of SGC with higher power, which limits the learning ability of graph representations. Here, we propose AdjMix, a simple and attentional graph convolutional model, that is scalable to wider structure and captures more nodes features information, by simultaneously mixing the adjacency matrices of different powers. We point out that the key factor of over-smoothing is the mismatched weights of adjacency matrices, and design AdjMix to address the over-smoothing of SGC and GCNs by adjusting the weights to matching values. Experiments on citation networks including Pubmed, Citeseer, and Cora show that our AdjMix improves over SGC by 2.4%, 2.2%, and 3.2%, respectively, while achieving same performance in terms of parameters and complexity, and obtains better performance in terms of classification accuracy, parameters, and complexity, compared to other baselines.

A plane kinematic chain inversion refers to a plane kinematic chain with one link fixed (assigned as the ground link). In the creative design of mechanisms, it is important to select proper ground links. The structural synthesis of plane kinematic chain inversions is helpful for improving the efficiency of mechanism design. However, the existing structural synthesis methods involve isomorphism detection, which is cumbersome. This paper proposes a simple and efficient structural synthesis method for plane kinematic chain inversions without detecting isomorphism. The fifth power of the adjacency matrix is applied to recognize similar vertices, and non-isomorphic kinematic chain inversions are directly derived according to non-similar vertices. This method is used to automatically synthesize 6-link 1-degree-of-freedom (DOF), 8-link 1-DOF, 8-link 3-DOF, 9-link 2-DOF, 9-link 4-DOF, 10-link 1-DOF, 10-link 3-DOF and 10-link 5-DOF plane kinematic chain inversions. All the synthesis results are consistent with those reported in literature. Our method is also suitable for other kinds of kinematic chains.

In person search task, it is hard to retrieve the query persons undergoing large visual changes. To tackle this problem, we propose to exploit the context information to rectify the original individual similarity for better retrieval. To this end, we propose to model a query frame and a gallery frame as a graph pair, and then design the Siamese Residual Graph Convolutional Networks (SR-GCN) to aggregate context information to generate graph similarity as a complement of the original similarity. To model the relationships between context persons, we define the joint similarity adjacency matrix which assigns the proposed joint similarity as the edge weight to measure the contributions a context person makes to the aggregation. Therefore, the context node with a higher possibility to be a co-traveler of the target node makes more contributions to the matching of the target node. To further enhance the discriminative power of individual features, we also design a Random Proxy Center loss which explicitly constrains the intra-class variations to be smaller than the inter-class variations in the feature space and could make use of unlabeled samples. Experimental results on two public datasets show that our approach performs favorably against the state-of-the-art methods.

miRNAs significantly affect multifarious biological processes involving human disease. Biological experiments always need enormous financial support and time cost. Taking expense and difficulty into consideration, to predict the potential miRNA-disease associations, a lot of high-efficiency computational methods by computer have been developed, based on a network generated by miRNA-disease association dataset. However, there exist many challenges. Firstly, the association between miRNAs and diseases is intricate. These methods should consider the influence of the neighborhoods of each node from the network. Secondly, how to measure whether there is an association between two nodes of the network is also an important problem. In our study, we innovatively integrate graph node embedding with a multilayer perceptron and propose a method DEMLP. To begin with, we construct a miRNA-disease network by miRNA-disease adjacency matrix (MDA). Then, low-dimensional embedding representation vectors of nodes are learned from the miRNA-disease network by DeepWalk. Finally, we use these low-dimensional embedding representation vectors as input to train the multilayer perceptron. Experiments show that our proposed method that only utilized the miRNA–disease association information can effectively predict miRNA-disease associations. To evaluate the effectiveness of DEMLP in a miRNA-disease network from HMDD v3.2, we apply fivefold crossvalidation in our study. The ROC-AUC computed result value of DEMLP is 0.943, and the PR-AUC value of DEMLP is 0.937. Compared with other state-of-the-art methods, our method shows good performance using only the miRNA-disease interaction network.

Community detection has been a significant and long-standing task in network analysis . While existing methods tend to focus on the assortative structure where communities are densely connected internally, in reality other kinds of network structure (e.g., disassortative) also exist. In addition, previous methods often have difficulties in dealing with noise and redundant information in the network topology . To address these problems, we develop a novel Bayesian probabilistic model for identifying the generalized communities, regardless of whether the network structure is assortative, disassortative, or otherwise. Specifically, the model combines the original adjacency matrix representation with the network embedding (the dense and continuous vector representations of nodes in a low-dimensional space). The two parts are connected and generated jointly via the community memberships of nodes learned from the model. Finally, we take a Bayesian treatment for model parameters and develop an efficient variational inference algorithm to detect communities. Experimental results demonstrate the outstanding performance of the new approach both on synthetic networks and on real-world networks, while case studies validate the ability of the proposed approach to describe generalized communities meaningfully.

To quantitatively measure the connectedness robustness of a complex network, a sequence of values that record the remaining connectedness of the network after a sequence of node- or edge-removal attacks can be used. However, it is computationally time-consuming to measure the network connectedness robustness by attack simulations for large-scale networked systems. In the present paper, an efficient method based on convolutional neural network (CNN) is proposed to train for estimating the network connectedness robustness. The new approach is motivated by the facts that 1) the adjacency matrix of a network can be converted to a gray-scale image and CNN is very powerful for image processing, and 2) CNN has proved very effective in predicting the controllability robustness of complex networks. Extensive experimental studies on directed and undirected, as well as synthetic and real-world networks suggest that: 1) the proposed CNN-based methodology performs excellently in the prediction of the connectedness robustness of complex networks as a process; 2) it performs fairly well as the indicator for the connectedness robustness, compared to other predictive measures.

It has been shown that brain functional networks constructed from electroencephalographic signals (EEG) continuously change topology as brain fatigue increases, and extracting the topological properties of the network can characterize the degree of brain fatigue. However, the traditional brain function network construction process often selects only the amplitude or phase components of the signal to measure the relationship between brain regions, and the use of a single component of the signal to construct a brain function network for analysis is rather one-sided. Therefore, we propose a method of functional synchronization analysis of brain regions. This method takes the EEG signal based on empirical modal decomposition (EMD) to obtain multiple intrinsic modal components (IMF) and inputs them into the Hilbert transform to obtain the instantaneous amplitude, and then calculates the amplitude locking value (ALV) to measure the synchronization relationship between all pairs of channels. The topological properties of the brain functional network are extracted to classify awake and fatigue states. The brain functional network is constructed based on the adjacency matrix of each waveform obtained from the ALV between all pairs of channels to realize the synchronization analysis between brain regions. Moreover, we achieved a satisfactory classification accuracy (82.84%) using the discriminative connection features in the Alpha band. In this study, we analyzed the functional network of ALV brain in fatigue and awake state, and the results showed that the connections between brain regions in fatigue state were significantly increased, and the connections between brain regions in the awake state were significantly decreased, and the information interaction between brain regions was more orderly and efficient.

Recently, graph convolutional networks (GCN) have made substantial progress in semi-supervised learning (SSL). However, established GCN-based methods have two major limitations. First, GCN-based methods are restricted by the oversmoothing issue that limits their ability to extract knowledge from distant but informative nodes. Second, most available GCN-based methods exploit only the feature information of unlabeled nodes, and the pseudo-labels of unlabeled nodes, which contain important information about the data distribution, are not fully utilized. To address these issues, we propose a novel end-to-end ensemble framework, which is named mixed-order graph convolutional networks (MOGCN). MOGCN consists of two modules. (1) It constructs multiple simple GCN learners with multi-order adjacency matrices, which can directly capture the high-order connectivity among the nodes to alleviate the problem of oversmoothing. (2) To efficiently combine the results from multiple GCN learners, MOGCN employs a novel ensemble module, in which the pseudo-labels of unlabeled nodes from various GCN learners are used to augment the diversity among the learners. We conduct experiments on three public benchmark datasets to evaluate the performance of MOGCN on semi-supervised node classification tasks. The experimental results demonstrate that MOGCN consistently outperforms state-of-the-art methods.

Anaerobic digestion technology is an effective way to solve the problem of urban kitchen waste. Volatile fatty acid (VFA) is an essential intermediate product in the anaerobic digestion process. Real-time monitoring of the concentration of VFA cannot only directly reflect the anaerobic digestion process and improve resource conversion efficiency but also effectively avoid the reactor operation failure caused by acidification. Traditional soft sensors of VFA cannot adapt to the dynamic characteristics of industrial process. In this paper, a dynamic soft sensor based on spatiotemporal graph convolution network is developed. The spatial and temporal information of the anaerobic digestion process is extracted through graph convolutional network (GCN) and gated recurrent unit (GRU) respectively. With the purpose of further improving the prediction accuracy and generalization ability of the model, the adaptive adjacency matrix and graph attention mechanism are introduced into the model to solve the over-smoothing problem of GCN, and the semi-supervised learning mechanism based on manifold regularization is introduced to fully mine data information of unlabeled samples. Then, the gated unit is used to realize the information fusion of different dimensional features and the selection of model depth. At last, a dynamic soft sensor based on the semi-supervised gated spatiotemporal graph attention network is established to estimate the concentration of VFA in real time. Compared with baseline models such as GCN and GRU, the root mean square error of this model is reduced by 17.34% and 15.54%, respectively.

As an effective method for mining latent information between labels, label correlation is widely adopted by many scholars to model multi-label learning algorithms. Most existing multi-label algorithms usually ignore that the correlation between labels may be asymmetric while asymmetry correlation commonly exists in the real-world scenario. To tackle this problem, a multi-label learning algorithm with asymmetry label correlation (ACML, Asymmetry Label Correlation for Multi-Label Learning) is proposed in this paper. First, measure the adjacency between labels to construct the label adjacency matrix. Then, cosine similarity is utilized to construct the label correlation matrix. Finally, we constrain the label correlation matrix with the label adjacency matrix. Thus, asymmetry label correlation is modeled for multi-label learning. Experiments on multiple multi-label benchmark datasets show that the ACML algorithm has certain advantages over other comparison algorithms. The results of statistical hypothesis testing further illustrate the effectiveness of the proposed algorithm.

The maximum likelihood estimation is a probabilistic inferencing model of community connectivity in large networks. In general, only the adjacency matrix is utilized to perform community structure parameter inference. Although there are recent examples that combine connectivity and attribute information for community detection, our model is an enhanced overlapping community detection model that combines adjacency spectral embedding with maximum likelihood estimation. This provides the flexibility of complex networks to increase connectivity information through measurements from attribute embedding. The attribute information can be effectively captured and transformed by attribute embedding to encode the combination with structure information. Then, the link strength among communities is designed to adjust the impact of these structural information on community generation based on the contribution of the structure to the clusters, and the node assignment allow for the nature of the real network (overlapping and outliers). Experiments highlight attributed networks in which attributed community detection task provides satisfactory performance.

Graph convolutional networks (GCNs) have become the de facto approaches and achieved state-of-the-art results for circumventing many real-world problems on graph-structured data. However, these networks are usually shallow due to the over-smoothing of GCNs with many layers, which limits the expressive power of learning graph representations. The current methods of solving the limitations have the bottlenecks of high complexity and many parameters. Although Simple Graph Convolution (SGC) reduces the complexity and parameters, it fails to distinguish the feature information of neighboring nodes at different distances. To tackle the limits, we propose MulStepNET, a stronger multi-step graph convolutional network architecture, that can capture more global information, by simultaneously combining multi-step neighborhoods information. When compared to existing methods such as GCN and MixHop, MulStepNET aggregates neighborhoods information at more distant distances via multi-power adjacency matrix while fitting fewest parameters and being computationally more efficient. Experiments on citation networks including Pubmed, Cora, and Citeseer demonstrate that the proposed MulStepNET model improves over SGC by 2.8, 3.3, and 2.1% respectively while keeping similar stability, and achieves better performance in terms of accuracy and stability compared to other baselines.

The performance of graph-based learning techniques largely relies on the edges defined between the vertices of the graph. These edges that represent the affinity between vertices must be learned from data. In this paper, we propose statistical dependence as a measure of affinity for learning the structure of graphs from data. It is assumed that the data lies on a high-dimensional Riemannian manifold, but the neighborhood is not known. Due to unknown characteristics of the underlying manifold, Euclidean distance (ED) does not capture the affinity between the data points accurately and cannot be used to construct the adjacency matrix. A scalable Hilbert–Schmidt independence criterion (HSIC)-based affinity technique is proposed to learn the nonlinear dependence between the data points. The pairwise affinities are captured by dividing the data into small chunks, which also makes the technique scalable. Once the pairwise affinity between data points is computed using HSIC-based dependence, $$\mu$$ nearest neighboring points are determined to construct the graph. The data points represented by the graph lie on a high-dimensional Riemannian manifold with every data point having $$\mu$$ neighbors. Dimensionality reduction is performed, followed by classification. Experiments on both synthetic and real-world dataset give accurate low-dimensional representation with preservation of maximum local linear structures. The random walk illustration of both ED and proposed HSIC-based affinity shows that the proposed affinity measure is able to identify and link similar data points. The increase in kNN, SVM and decision tree classifiers’ accuracies on low-dimensional data achieved using graph Laplacian on HSIC-based affinity matrix proves the efficiency of the proposed affinity metric for graph-based learning.

Graph signal processing has recently emerged as a field with applications across a broad spectrum of fields including brain connectivity networks, logistics and supply chains, social media, computational aesthetics, and transportation networks. In this paradigm, signal processing methodologies are applied to the adjacency matrix, seen as a two-dimensional signal. Fundamental operations of this type include graph sampling, the graph Laplace transform, and graph spectrum estimation. In this context, topology similarity metrics allow meaningful and efficient comparisons between pairs of graphs or along evolving graph sequences. In turn, such metrics can be the algorithmic cornerstone of graph clustering schemes. Major advantages of relying on existing signal processing kernels include parallelism, scalability, and numerical stability. This work presents a scheme for training a tensor stack network to estimate the topological correlation coefficient between two graph adjacency matrices compressed with the two-dimensional discrete cosine transform, augmenting thus the indirect decompression with knowledge stored in the network. The results from three benchmark graph sequences are encouraging in terms of mean square error and complexity especially for graph sequences. An additional key point is the independence of the proposed method from the underlying domain semantics. This is primarily achieved by focusing on higher-order structural graph patterns.

Although graph convolutional networks (GCNs) that extend the convolution operation from images to graphs have led to competitive performance, the existing GCNs are still difficult to handle a variety of applications, especially cheminformatics problems. Recently multiple GCNs are applied to chemical compound structures which are represented by the hydrogen-depleted molecular graphs of different size. GCNs built for a binary adjacency matrix that reflects the connectivity among nodes in a graph do not account for the edge consistency in multiple molecular graphs, that is, chemical bonds (edges) in different molecular graphs can be similar due to the similar enthalpy and interatomic distance. In this paper, we propose a variant of GCN where a molecular graph is first decomposed into multiple views of the graph, each comprising a specific type of edges. In each view, an edge consistency constraint is enforced so that similar edges in different graphs can receive similar attention weights when passing information. Similarly to prior work, we prove that in each layer, our method corresponds to a spectral filter derived by the first order Chebyshev approximation of graph Laplacian. Extensive experiments demonstrate the substantial advantages of the proposed technique in quantitative structure-activity relationship prediction.

A recommendation system has been built for a web resource’s users that applies statistics about user activities to provide recommendations. The purpose of the system operation is to provide recommendations in the form of an orderly sequence of HTML pages of the resource suggested for the user. The ranking procedure uses statistical information about user transitions between web resource pages. The web resource model is represented in the form of a web graph; the user behavior model is shown as a graph of transitions between resource pages. The web graph is represented by an adjacency matrix; for the transition graph, a weighted matrix of probabilities of transitions between the vertices of the graph has been constructed. It was taken into consideration that user transitions between pages of a web resource may involve entering a URL in the address bar of a browser or by clicking on a link in the current page. The user’s transition between vertices in a finite graph according to probabilities determined by the weight of the graph’s edges is represented by a homogeneous Markov chain and is considered a process of random walk on the graph with the possibility of moving to a random vertex. Random Walk with Restarts was used to rank web resource pages for a particular user. Numerical analysis has been performed for an actual online store website. The initial data on user sessions are divided into training and test samples. According to the training sample, a weighted matrix of the probability of user transitions between web resource pages was constructed. To assess the quality of the built recommendation system, the accuracy, completeness, and Half-life Utility metrics were used. On the elements of the test sample, the accuracy value of 65‒68% was obtained, the optimal number of elements in the recommendation list was determined. The influence of model parameters on the quality of recommendation systems was investigated.

There are some interesting properties in quantum mechanics, such as quantum superposition and entanglement. We can use these features to solve some specific problems. Quantum computer has more advantages than classical computer in many problems. In this paper, we are interested in regular graph. A special case of graph structure destroyed is given. We present a search algorithm to find exceptional vertexes in the graph in this case. The algorithm uses the trick of amplitude amplification in quantum search algorithm. In the corresponding classical algorithm, the adjacency matrix may be used to store the information of vertex and edge of graph. It takes one time for the best and N times for the worst to find the target. Which means that N/2 times on average need to be conducted. In our quantum algorithm, nodes and vertexes are stored in quantum states, using quantum search to design algorithm. The search process can be accelerated in our quantum algorithm.

Purpose. At present, the computer networks of the information and telecommunication system (ITS) of railway transport use the OSPF protocol, which does not allow taking into account several metrics when determining the optimal route. Therefore, there is a need to study the possibility of organizing routing in computer networks of rail transport ITS using a two-colonial ant algorithm. Methodology. According to the Two-ACO software model, created in the Python language based on the two-colonial ant algorithm, the optimal route in a computer network was determined. Two-ACO model inputs: computer network parameters (network adjacency matrix, number of routers); parameters of the ant algorithm (number of iterations; number of ants in the colony; number of elite ants; initial pheromone level; evaporation rate; parameter for adjusting the amount of pheromone deposition). Findings. The results of the Two-ACO model are presented in the form of graphs depicting the optimal paths: the criterion of the total delay on the routers (for the first colony of ants) and the number of hops (for the second colony of ants). Originality. According to the created Two-ACO software model for a computer network of 7 routers and 17 channels, a study of the time for determining the optimal path in a computer network by the number of ordinary and elite ants, evaporation rate and deposited pheromone was conducted. It is determined that it is enough to use the number of ants equal to the number of routers and have 2 elite ants in the colony, with 1000 iterations, evaporation rate from 0.2 to 0.7, and pheromone deposition by ants close to one. Practical value. Created Two-ACO software model using two colonies of ants on the following criteria: the total delay on the routers (for the first colony of ants) and the number of hops that make up the route (for the second colony of ants) allows you to parallel determine the optimal routes in a computer network of railway transport. It is estimated that for a computer network of 15 routers and 17 channels, it is sufficient to have 30 agents (two ants on top), the value of the pheromone deposited by the agents is close to one, and the evaporation rate is 0.4.

Graph regularization has shown its effectiveness in multi-view subspace clustering methods. Many multi-view subspace clustering methods based on graph regularization build the adjacency matrix directly based on a simple similarity measure between data points for each view. However, these simply constructed graphs are sensitive to light corruptions and even generate misleading manifold. Considering this shortcoming, this paper presents a multi-view subspace clustering algorithm (CGMSC) with a well-defined locally consistent graph regularization. We formulate CGMSC by a two-stage procedure. In the first stage, an adaptive self-weighted multi-view local linear embedding (ASWMVLLE) method is proposed to build the locally consistent geometric relationship between instances. In the second stage, ASWMVLLE is introduced into CGMSC by defining a local graph regularization term about the consensus latent subspace representation, which can not only effectively keep the manifold structure of data, but also ensure the consistency across different views. Experiments on eight real-world datasets demonstrate that our method has good robustness and clustering performance.

Recent progress on human action recognition, fueled by the Graph Convolutional Network (GCN), has been substantial. However, two main problems are caused by the design strategy of graph convolution kernels: first, the partitioning strategy of neighbor set for graph vertices relies on the gravity center designed manually, which is limited in generalizability to diverse skeletons in action recognition; second, the existing GCN-based methods can only capture local physical dependencies among joints and result in missing implicit joint correlations due to over-smoothing. In this work, we present (1) a novel attention adjacency matrix (AAM) to design graph convolution kernels and (2) a dimension-attention block to improve the robustness of the model. Specifically, the proposed AAM is designed by a novel partitioning strategy for the neighbor set, through which an adjacency matrix is decomposed into several parametric matrices. Simultaneously, attention mechanism is introduced in the process to generate an attention matrix. Combining the matrix and the parametric matrices into an AAM through ResNet, we further exhibit the AAM based graph convolution network (AAM-GCN). The proposed dimension-attention block strengthens the important information in each dimension of skeleton data by extending the idea of channel-attention. Extensive experiments on two large-scale datasets, NTU-RGB+D and Kinetics, demonstrate that AAM-GCN achieves better performance than the state-of-the-art works.

In distributed and cooperative systems, the network structure is determinant to the success of the strategy adopted to solve complex tasks. Those systems are primarily governed by consensus protocols whose convergence is intrinsically dependent on the network topology. Most of the consensus algorithms deal with continuous values and perform average-based strategies to reach cohesion over the exchanged information. However, many problems demand distributed consensus over countable values, that cannot be handled by traditional protocols. In such a context, this work presents an approach based on semidefinite programming to design the optimal weights of a network adjacency matrix, in order to control the convergence of a distributed random consensus protocol for variables at the discrete-space domain, based on the voter model. As a second contribution, this work uses Markov theory and the biological inspiration of epidemics to find out a dynamical spreading model that can predict the information diffusion over this discrete consensus protocol. Also, convergence properties and equilibrium points of the proposed model are presented regarding the network topology. Finally, extensive numerical simulations evaluate the effectiveness of the proposed consensus algorithm, its spreading model, and the approach for optimal weight design.

There has been a rise in the popularity of algebraic methods for graph algorithms given the development of the GraphBLAS library and other sparse matrix methods. An exemplar for these approaches is Breadth-First Search (BFS). The algebraic BFS algorithm is simply a recurrence of matrix-vector multiplications with the $n \times n$ adjacency matrix, but the many redundant operations over nonzeros ultimately lead to suboptimal performance. Therefore an optimal algebraic BFS should be of keen interest especially if it is easily integrated with existing matrix methods. Current methods, notably in the GraphBLAS, use a Sparse Matrix masked-Sparse Vector (SpMmSpV) multiplication in which the input vector is kept in a sparse representation in each step of the BFS, and nonzeros in the vector are masked in subsequent steps. This has been an area of recent research in GraphBLAS and other libraries. While in theory these masking methods are asymptotically optimal on sparse graphs, many add work that leads to suboptimal runtime. We give a new optimal, algebraic BFS for sparse graphs, thus closing a gap in the literature. Our method multiplies progressively smaller submatrices of the adjacency matrix at each step. Let $n$ and $m$ refer to the number of vertices and edges, respectively. On a sparse graph, our method takes $O(n)$ algebraic operations as opposed to $O(m)$ operations needed by theoretically optimal sparse matrix approaches. Thus for sparse graphs it matches the bounds of the best-known sequential algorithm and on a Parallel Random Access Machine (PRAM) it is work-optimal. Our result holds for both directed and undirected graphs. Compared to a leading GraphBLAS library our method achieves up to 24x faster sequential time and for parallel computation it can be 17x faster on large graphs and 12x faster on large-diameter graphs., Will appear in ACM Transactions on Knowledge Discovery from Data, Vol. 15, No. 5, 2021

We present a novel transient fault detection and classification approach in power transmission lines based on graph convolutional neural network. Compared with the existing techniques, the proposed approach considers explicit spatial information in sampling sequences as prior knowledge and it has stronger feature extraction ability. On this basis, a framework for transient fault detection and classification is created. Graph structure is generated to provide topology information to the task. Our approach takes the adjacency matrix of topology graph and the bus voltage signals during a sampling period after transient faults as inputs, and outputs the predicted classification results rapidly. Furthermore, the proposed approach is tested in various situations and its generalization ability is verified by experimental results. The results show that the proposed approach can detect and classify transient faults more effectively than the existing techniques, and it is practical for online transmission line protection for its rapidness, high robustness and generalization ability.

We develop an empirical electrical-based framework to compare between centrality measures as to judge their ability to predict the vulnerability of smart grids and their elements under various attacks. The centrality measures considered are based on a weighted graph adjacency matrix representing the real power flows. The vulnerability is measured by the post-attack unsatisfied load (UL), which is determined through steady-state simulation using the MatPower v6.0. We introduce a generalized vulnerability curve as a plot of measures of electrical damage (e.g., the UL), versus physical damage. We consider various measures of physical damage such as the Fraction of Elements (FOE) removed and sums of centrality scores of elements removed. The area under the vulnerability curve (denoted as VPM) is shown to be a logical, reliable, and consistent indicator of the predictive power of a centrality measure. The VPM is simulated for several attacks including the Remove Most Central Elements First (RMCEF) attack. We show that degree centrality is the most predictive, when compared to eigenvector and betweenness centralities. Moreover, the degree-based RMCEF attack is the worst among the RMCEF and 5400 random attacks. The FOE-degree centrality VPM is the most predictive as well as the most computationally efficient.

The article examines the architecture of a networked knowledge base and the organizational structure of a complex military-purpose system, which is built when a group of troops (forces) is created and kept in a state where it is capable of solving the tasks assigned to it. This requires a deep study of issues not only of modern tactics regarding the preparation and conduct of hostilities, but also more complex issues of scientific substantiation of the architecture of a networked knowledge base and the structure of a complex military system with a networked knowledge base. The internal representation of knowledge in the knowledge base (formal programmatic and logical content) is advisable to implement in the form of an adjacency matrix, which displays the relationship and relationship between target settings; initial conditions; the resources of the grouping of troops (temporary, material, combat and quantitative composition), their costs and replenishment; rules for the use of resources and the choice of criteria for their distribution. The knowledge base synthesizes a mathematical network model for making decisions, which provides a change (correction) of the structure of target attitudes when replenishing the knowledge base. Tasks solved in the knowledge base: selection of vertices and relations when replenishing catalogs; making changes to the adjacency matrix in accordance with the identified or changed relationships between targets. A necessary element of the synthesis of a mathematical network model for making decisions on the preparation and conduct of hostilities is the construction of the structure of the target systems of the system for a specific situation. A feature of controlling the correctness of knowledge presented in the form of target attitudes is the need for a joint analysis of the entire set of target attitudes and initial conditions in their relationship. For this, the matrix of the relations of target attitudes and the matrix of the relations of initial conditions are combined. The control of the correctness of the knowledge base is carried out when replenishing the knowledge base, it includes: identification of contradictions in the structure of target attitudes when making changes to this structure; search and detection of contradictions in the graph of the semantic network according to available resources and time; checking the completeness of the graph of the mathematical network model; issuance of revealed contradictions to an expert and their elimination. A practical approach to building the architecture of a networked knowledge base and the organizational structure of a complex military system can be implemented during the substantiation of the components and elements of the system when creating a grouping of troops (forces).