Narrow Results

In recent years, knowledge graphs have had a significant impact across diverse domains. Notably, the power knowledge graph has garnered considerable attention as high-performance database. However, its untapped reasoning capabilities offer an enticing avenue for exploration. One of the main reasons is the sparsity of power grid datasets, especially electrical equipment knowledge graph. Because of the scarcity of high-risk records, there exists a large number of long tail entities and long tail relations. To address this challenge, we introduce a novel text-based model called GELMSP (Graph Embedding using Language Model with Self-learned Prompts). We employ a bi-encoder structure along with a contrastive learning strategy to expedite the training process. Additionally, our approach incorporates a self-learned prompt mechanism that generates prompts for specific situations without the need for any additional information, known as self-learning. This harnesses the power of pre-trained language models to comprehend the semantic nuances within the entities and relationships of the knowledge graph. Adopting this innovative method enables our model to effectively handle sparse datasets, leading to a comprehensive understanding of interconnectedness within the knowledge graph. Additionally, we demonstrate the efficacy of our model through extensive experiments and comparisons against baseline methods, reaffirming its potential in advancing the state-of-the-art in electrical equipment defect diagnosis.

Embedding an interconnection network into another network is one of the main problems in parallel processing and computing systems. Interconnection networks in multiprocessing systems facilitate effective communication among various system components. Obtaining the minimum cutwidth, congestion, and wirelength in graph embedding problems is of great significance for network design and architecture, where the minimum is taken over all embedding of guest graphs into host graphs, and addressing these issues can reduce time and cost in embedded design. This work aims to accurately calculate the minimum congestion and wirelength for the $K_4^n$ (the $n$th Cartesian product of $K_4$) layout into $1$-dimensional, $2$-dimensional, and $3$-dimensional grids by the optimal solution of edge isoperimetric problem on $K_4^n$.

Social media platforms share several emotions in the form of text, audio, and images, where the text-shared data are less convincing to understand the emotions. The classification of the sentiments should be accurate to achieve a better understanding of the values in the commercial industry. Twitter has proven to be an effective instrument for text-based sentiment analysis when compared to other traditional assessments like surveys and stock market performance records. Though the existing research on sentiment analysis achieved good results of performance, the techniques had drawbacks such as long-term sentence prediction, less robustness, high computational resources, lack of complementary feature extraction, and so on. In this research, the Gaussian conditional rule-based deep convolutional neural network (DCNN) (Gaussian conditional rule-based DCNN) is proposed to tackle the limitation of the existing techniques, where the Gaussian distribution is applied for the selection of the kernel filters in the formation of the feature maps, and the classifier parameters are adaptively trained using the proposed adaptive nature optimizer (ANO). Through the integration of the conditionality of the random forest algorithm into the developed architecture, the model attains the potential to adapt the processing concerning the supplementary contextual information or features. Utilizing the prominent word embedding approach maximizes the input quality, converts words into continuous vector representations in a high-dimensional space, and captures both syntactic and semantic associations between words. In addition, the Graph embedding preserves some of the graph’s structural characteristics and effectively captures the syntactic dependencies, co-occurrences, semantic similarities, as well as pertinent linguistic correlations among the texts. Specifically, the proposed ANO algorithm and the conditional rule exploited in the model provide stable as well as robust performance in the classification of sentiments. The experimental results demonstrate that the Gaussian conditional rule-based DCNN model achieves 98.36 %, 98.80%, and 97.44% for accuracy, specificity, and sensitivity, respectively.

The power communication network is the key to ensuring the safe operation of the distribution network, and how to quickly and accurately predict faults is a challenging task, especially considering the variable topology of the distribution network. To address this issue, common faults will be modeled and simulated to predict faults in power communication systems. In this study, considering the generalized Laplacian smoothing filters and the long sequence representation capability of the Transformer, an adaptive graph encoder based on historical performance graph embedding is proposed and used for fault prediction in power communication networks. The proposed method consists of two modules: (1) To better alleviate high-frequency noise in node features, a carefully designed Laplacian smoothing filter is first applied. (2) Adopting a transformer-based adaptive encoder to iteratively enhance filtering characteristics for better node embedding. The performance of the proposed method in fault prediction tasks is tested using a dataset collected from a real power communication network. The experimental results show that the proposed method consistently outperforms other fault prediction methods in terms of performance.

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

Index-shuffle graphs are introduced as candidate interconnection networks for parallel computers. The comparative advantages of index-shuffle graphs over the standard bounded-degree "approximations" of the hypercube, namely butterfly-like and shuffle-like graphs, are demonstrated in the theoretical framework of graph embedding and network emulations.

An N-node index-shuffle graph emulates:

• an N-node shuffle-exchange graph with no slowdown, which the currently best emulations of shuffle-like graphs by hypercubes and butterflies incur a slowdown of Ω(log N).

• its like-sized butterfly graph with a slowdown O(log log log N), while the currently best emulations of butterfly-like graphs by shuffle-like graphs incur a slowdown of Ω(log log N).

• an N-node hypercube that executes an on-line leveled algorithm with a slowdown O(log log N), while the slowdown of currently best such emulations of the hypercube by its bounded-degree shuffle-like and butterfly-like derivatives remains Ω(log N). Our emulation is based on an embedding of an N-node hypercube into an N-node index-shuffle graph with dilation O(log log N), while the currently best embeddings of the hypercube into its bounded-degree shuffle-like and butterfly-like derivatives incur a dilation of Ω(log N).

Reconfigurable communication networks for massively parallel multiprocessor systems offer the possibility to realize a number of application demands like special communication patterns or real-time requirements. This paper presents the design principle of a reconfigurable network which is able to realize any graph of maximal degree four. The architecture is based on a special multistage Clos network, constructed out of a number of static routing switches of equal size. Upper bounds on the cut size of 4-regular graphs, if split into a number of clusters, allow minimizing the number of switches and connections while still offering the desired reconfiguration capabilities as well as large scalability and flexible multi-user access. Efficient algorithms configuring the architecture are based on an old result by Petersen²⁷ about the decomposition of regular graphs.

The concept presented here is the basis for the Parsytec SC series of reconfigurable MPP-systems. The currently largest realization with 320 processors is presented in greater detail.

It is well known that the nearest-neighbor connections of the mesh (especially the two-dimensional meshes) are very useful in parallel computations. Consequently, it is desirable to show that the graph representing the interconnection network of a parallel computer embeds the mesh. Most existing results of mesh-embedding are only applicable to a single kind of network. Here we demonstrate that a large family of interconnection networks called the generalized Fibonacci cubes all embed the mesh.

Hypercube is an attractive structure for parellel processing due to its symmetry and regularity. To increase the reliability of hypercube based systems and to allow their use in the presence of faulty nodes, efficient fault-tolerant schemes in hypercubes are necessary. In this paper, we present an algorithm for embedding rings in hypercubes based multiprocessor network in the event of node failures. The algorithm can tolerate up to θ(2^n/2) faults, and guarantee that given any f < (n - 2k)2^k faulty nodes, it can find a ring of size at least 2ⁿ - 2f for k = 0 and 2ⁿ - 2^k f - 2^2k for k ≥ 1 in an n-dimensional hypercube. It improves over existing algorithms in the size of ring.

Hypermeshes have been given much attention as a versatile interconnection network of parallel computers. A hypermesh is obtained from a mesh by replacing each linear connection with a hyperedge. In this paper, we show how to embed a butterfly or multiple copies of a butterfly into a hypermesh. First, a butterfly B(s) of (s + 1)2^s nodes is embedded into a 2^s × X hypermesh where X = 2^{⌊log₂ s ⌋+ 1}. Second, the butterfly B(s) is embedded into a square hypermesh. Third, multiple copies of the butterfly B(s) are embedded into a hypermesh of variable aspect ratio. The efficiency of these embeddings is measured by alignment cost, congestion, and expansion. The alignment cost of all of these embeddings is optimal. The congestion of the first and third embedding is optimal. The expansion of the first and third embedding is one if s = 2^k - 1 for some integer k, otherwise, less than two. The expansion of the second embedding is 2 + ∊ (s) where ∊(s) = (2log(s + 1) + 2)/(s + 1).

Honeycomb torus networks have been recognised as an attractive alternative to existing torus interconnection networks in parallel and distributed applications. In this paper we establish that there exists a hamiltonian cycle in a honeycomb torus with two adjacent faulty nodes and that with a single fault a ring embedding with one less node than the fault free torus can be found.

Recently, Graph Embedding Framework has been proposed for feature extraction. However, it is still an open issue on how to compute robust discriminant transformation for this purpose. In this paper, we show that supervised graph embedding algorithms share a general criterion. Based on the analysis of this criterion, we propose a general solution, called General Solution for Supervised Graph Embedding (GSSGE), for extracting the robust discriminant transformation of Supervised Graph Embedding. Then, we analyze the superiority of our algorithm over traditional algorithms. Extensive experiments on both artificial and real-world data are performed to demonstrate the effectiveness and robustness of our proposed GSSGE.

Graphs provide us with a powerful and flexible representation formalism for pattern classification. Many classification algorithms have been proposed in the literature. However, the vast majority of these algorithms rely on vectorial data descriptions and cannot directly be applied to graphs. Recently, a growing interest in graph kernel methods can be observed. Graph kernels aim at bridging the gap between the high representational power and flexibility of graphs and the large amount of algorithms available for object representations in terms of feature vectors. In the present paper, we propose an approach transforming graphs into n-dimensional real vectors by means of prototype selection and graph edit distance computation. This approach allows one to build graph kernels in a straightforward way. It is not only applicable to graphs, but also to other kind of symbolic data in conjunction with any kind of dissimilarity measure. Thus it is characterized by a high degree of flexibility. With several experimental results, we prove the robustness and flexibility of our new method and show that our approach outperforms other graph classification methods on several graph data sets of diverse nature.

Graph-based representations of patterns are very flexible and powerful, but they are not easily processed due to the lack of learning algorithms in the domain of graphs. Embedding a graph into a vector space solves this problem since graphs are turned into feature vectors and thus all the statistical learning machinery becomes available for graph input patterns. In this work we present a new way of embedding discrete attributed graphs into vector spaces using node and edge label frequencies. The methodology is experimentally tested on graph classification problems, using patterns of different nature, and it is shown to be competitive to state-of-the-art classification algorithms for graphs, while being computationally much more efficient.

The direct binary hypercube interconnection network has been very popular for the design of parallel computers, because it provides a low diameter and can emulate efficiently the majority of the topologies frequently employed in the development of algorithms. The last fifteen years have seen major efforts to develop image analysis algorithms for hypercube-based parallel computers. The results of these efforts have culminated in a large number of publications included in prestigious scholarly journals and conference proceedings. Nevertheless, the aforementioned powerful properties of the hypercube come at the cost of high VLSI complexity due to the increase in the number of communication ports and channels per PE (processing element) with an increase in the total number of PE’s. The high VLSI complexity of hypercube systems is undoubtedly their dominant drawback; it results in the construction of systems that contain either a large number of primitive PE’s or a small number of powerful PE’s. Therefore, low-dimensional k-ary n-cubes with lower VSLI complexity have recently drawn the attention of many designers of parallel computers. Alternative solutions reduce the hypercube’s VLSI complexity without jeopardizing its performance. Such an effort by Ziavras has resulted in the introduction of reduced hypercubes (RH’s). Taking advantage of existing high-performance routing techniques, such as wormhole routing, an RH is obtained by a uniform reduction in the number of edges for each hypercube node. An RH can also be viewed as several connected copies of the well-known cube-connected-cycles network. The objective here is to prove that parallel computers comprising RH interconnection networks are definitely good choices for all levels of image analysis. Since the exact requirements of high-level image analysis are difficult to identify, but it is believed that versatile interconnection networks, such as the hypercube, are suitable for relevant tasks, we investigate the problem of emulating hypercubes on RH’s. The ring (or linear array), the torus (or mesh), and the binary tree are the most frequently used topologies for the development of algorithms in low-level and intermediate-level image analysis. Thus, to prove the viability of the RH for the two lower levels of image analysis, we introduce techniques for embedding the aforementioned three topologies into RH’s. The results prove the suitability of RH’s for all levels of image analysis.

With the increasing number of patent applications over the years, instances of patent infringement cases have become more frequent. However, traditional manual patent infringement detection models are no longer suitable for large-scale infringement detection. Existing automated models mainly focus on detecting one-to-one patent infringements, but neglect the many-to-one scenarios. The many-to-one patent infringement detection model faces some major challenges. First, the diversity of patent domains, complexity of content and ambiguity of features make it difficult to extract and represent patent features. Second, patent infringement detection relies on the correlation between patents and the comparison of contextual information as the key factors, but modeling the process and drawing conclusions present challenges. To address these challenges, we propose a many-to-one patent graph (MPG) embedding base infringement detection model. Our model extracts the relationship between keywords and patents, as well as association relation between keywords from many-to-one patent texts (MPTs), to construct a MPG. We obtain patent infringement features through graph embedding of MPG. By using these embedding features as input, the many-to-one infringement detection (MOID) model outputs the conclusion on whether a patent is infringed or not. The comparative experimental results indicate that our model improves accuracy, precision and F-measure by 3.81%, 11.82% and 5.37%, respectively, when compared to the state-of-the-art method.

A graph is called intrinsically knotted if every embedding of the graph contains a knotted cycle. Johnson, Kidwell and Michael, and, independently, Mattman, showed that intrinsically knotted graphs have at least 21 edges. Recently, Lee, Kim, Lee and Oh, and, independently, Barsotti and Mattman, showed that $K_7$ and the 13 graphs obtained from $K_7$ by $\nabla Y$ moves are the only intrinsically knotted graphs with 21 edges. Also Kim, Lee, Lee, Mattman and Oh showed that there are exactly three triangle-free intrinsically knotted graphs with 22 edges having at least two vertices of degree 5. Furthermore, there is no triangle-free intrinsically knotted graph with 22 edges that has a vertex with degree larger than 5. In this paper, we show that there are exactly five triangle-free intrinsically knotted graphs with 22 edges having exactly one degree 5 vertex. These are Cousin 29 of the $K_{3,3,1,1}$ family, Cousins 97 and 99 of the $E_9+e$ family and two others that were previously unknown.

Index-shuffle graphs are a family of bounded-degree hypercube-like interconnection networks for parallel computers, introduced by [Baumslag and Obrenić (1997): Index-Shuffle Graphs, …], as an efficient substitute for two standard families of hypercube derivatives: butterflies and shuffle-exchange graphs. In the theoretical framework of graph embedding and network emulations, this paper shows that the index-shuffle graph efficiently approximates the direct-product structure of the hypercube, and thereby has a unique potential to approximate efficiently all of its derivatives.

One of the consequences of our results is that any member of the following group of standard bounded-degree hypercube derivatives: butterflies, shuffles, tori, meshes of trees, is emulated by the index-shuffle graph with a slowdown in the order of the logarithm of the slowdown of the most efficient emulation achieved by any other member of this group.

Emulation algorithms are presented where the emulation host is the n-dimensional index-shuffle graph Ψ_n, having N=2ⁿ nodes. The emulated graph G is a direct product of the form: G=F₀×F₁×⋯×F_k-1 where k is a power of 2, and each factor F_i is an instance of any of the following three graph families: cycle, complete binary tree, X-tree. Let the size of each factor be |F_i|≤2^n_f, where k·n_f≤n. The index-shuffle graph Ψ_n, emulates any factor F_i in the product G with slowdown: O(log k) + O(log n_f), which is O(log n) = O(loglog N). Any collection of 2^ℓ copies of the product G, such that: ℓ+k·n_f≤n is emulated by the index-shuffle graph Ψ_n simultaneously, without any additional slowdown. Relaxing the assumption that k is a power of 2 introduces an additional factor of O(lg*N) into the slowdown.

This paper introduces a type of graph embedding called a mutual embedding. A mutual embedding between two n-node graphs $G_1=(V_1,E_1)$ and $G_2=(V_2,E_2)$ is an identification of the vertices of V₁ and V₂, i.e., a bijection $\pi :V_1\to V_2$, together with an embedding of G₁ into G₂ and an embedding of G₂ into G₁ where in the embedding of G₁ into G₂, each node u of G₁ is mapped to π(u) in G₂ and in the embedding of G₂ into G₁ each node v of G₂ is mapped to ${\pi }^{-1}\left(v\right)$ in G₁. The identification of vertices in G₁ and G₂ constrains the two embeddings so that it is not always possible for both to exhibit small congestion and dilation, even if there are traditional one-way embeddings in both directions with small congestion and dilation. Mutual embeddings arise in the context of finding preconditioners for accelerating the convergence of iterative methods for solving systems of linear equations. We present mutual embeddings between several types of graphs such as linear arrays, cycles, trees, and meshes, prove lower bounds on mutual embeddings between several classes of graphs, and present some open problems related to optimal mutual embeddings.

Automatic diagnosis of brain diseases based on brain connectivity network (BCN) classification is one of the hot research fields in medical image analysis. The functional brain network reflects the brain functional activities and structural brain network reflects the neural connections of the main brain regions. It is of great significance to explore and explain the inner mechanism of the brain and to understand and treat brain diseases. In this paper, based on the graph structure characteristics of brain network, the fusion model of functional brain network and structural brain network is designed to classify the diagnosis of brain mental diseases. Specifically, the main work of this paper is to use the Laplacian graph embed the information of diffusion tensor imaging, which contains the characteristics of structural brain networks, into the functional brain network with hyper-order functional connectivity information built based on functional magnetic resonance data using the sparse representation method, to obtain brain network with both functional and structural characteristics. Projection of the brain network and the two original modes data to the kernel space respectively and then classified by the multi-task learning method. Experiments on the epilepsy dataset show that our method has better performance than several state-of-the-art methods. In addition, brain regions and connections that are highly correlated with disease revealed by our method are discussed.