Search

A result of Friedman and Pippenger gives a sufficient condition on the expansion properties of a graph to contain all small trees with bounded maximum degree. In this paper, we extend the tree embedding problem of expanding graphs to the degenerate graph embedding problem, and give a sufficient condition for a graph to contain strong 2 -degenerate subgraphs with bounded maximum codegree. [ABSTRACT FROM AUTHOR]

One of the important features of an interconnection network is its ability to efficiently simulate programs or parallel algorithms written for other architectures. Such a simulation problem can be mathematically formulated as a graph embedding problem. In this paper we compute the lower bound for dilation and congestion of embedding onto wheel-like networks. Further, we compute the exact dilation of embedding wheellike networks into hypertrees, proving that the lower bound obtained is sharp. Again, we compute the exact congestion of embedding windmill graphs into circulant graphs, proving that the lower bound obtained is sharp. Further, we compute the exact wirelength of embedding wheels and fans into 1,2-fault hamiltonian graphs. Using this we estimate the exact wirelength of embedding wheels and fans into circulant graphs, generalized Petersen graphs, augmented cubes, crossed cubes, Mobius cubes, twisted cubes, twisted n-cubes, locally twisted cubes, generalized twisted cubes, odd-dimensional cube connected cycle, hierarchical cubic networks, alternating group graphs, arrangement graphs, 3-regular planer hamiltonian graphs, star graphs, generalised matching networks, fully connected cubic networks, tori and 1-fault traceable graphs. [ABSTRACT FROM AUTHOR]

The efficiency of a graph embedding problem when simulating one interconnection network in another interconnection network is characterized by the influential parameter of wirelength. Obtaining the minimum wirelength in an embedding problem determines the quality of that embedding. In this paper, we obtained the convex edge partition of 3-Ary n-Cubes and the minimized wirelength of the embeddings of both 3-Ary n-Cubes and circulant networks. [ABSTRACT FROM AUTHOR]

Research on graph representation learning (a.k.a. embedding) has received great attention in recent years and shows effective results for various types of networks. Nevertheless, few initiatives have been focused on the particular case of embeddings for bipartite graphs. In this paper, we first define the graph embedding problem in the case of bipartite graphs. Next, we propose a taxonomy of approaches used to tackle this problem and draw a description of state-of-the-art methods. Then, we establish their pros and cons with respect to conventional network embeddings. Finally, we provide a description of available resources to lead experiments on the subject. [ABSTRACT FROM AUTHOR]

The one‐class classification (OCC) problem has always been a popular topic because it is difficult or expensive to obtain abnormal data in many practical applications. Most of OCC methods focused on monomodal data, such as support vector data description (SVDD) and its variants, while we often face multimodal data in reality. The data come from the same task in multimodal learning, and thus, the inherent structures among all modalities should be hold, which is called the consistency principle. However, each modality contains unique information that can be used to repair the incompleteness of other modalities. It is called the complementarity principle. To follow the above two principles, we designed a multimodal graph–regularized term and a sparse projection matrix–regularized term. The former aims to preserve the within‐modal structural and between‐modal relationships, while the latter aims to richly use the complementarity information hidden in multimodal data. Further, we follow the multimodal subspace (MS) SVDD architecture and use two regularized terms to regularize SVDD. Consequently, a novel OCC method for multimodal data is proposed, called the consistency and complementarity jointly regularized subspace SVDD (CCS‐SVDD). Extensive experimental results demonstrate that our approach is more effective and competitive than other algorithms. The source codes are available at https://github.com/wongchuang/CCS_SVDD. [ABSTRACT FROM AUTHOR]

Graph is an important data representation which appears in a wide diversity of real-world scenarios. Effective graph analytics provides users a deeper understanding of what is behind the data, and thus can benefit a lot of useful applications such as node classification, node recommendation, link prediction, etc. However, most graph analytics methods suffer the high computation and space cost. Graph embedding is an effective yet efficient way to solve the graph analytics problem. It converts the graph data into a low dimensional space in which the graph structural information and graph properties are maximumly preserved. In this survey, we conduct a comprehensive review of the literature in graph embedding. We first introduce the formal definition of graph embedding as well as the related concepts. After that, we propose two taxonomies of graph embedding which correspond to what challenges exist in different graph embedding problem settings and how the existing work addresses these challenges in their solutions. Finally, we summarize the applications that graph embedding enables and suggest four promising future research directions in terms of computation efficiency, problem settings, techniques, and application scenarios. [ABSTRACT FROM AUTHOR]

A central problem in parameterized algorithms is to obtain algorithms with running time f(k) · nO(1) such that f is as slow growing a function of the parameter k as possible. In particular, a large number of basic parameterized problems admit parameterized algorithms where f(k) is single-exponential, that is, ck for some constant c, which makes aiming for such a running time a natural goal for other problems as well. However, there are still plenty of problems where the f(k) appearing in the best-known running time is worse than single-exponential and it remained "slightly superexponential" even after serious attempts to bring it down. A natural question to ask is whether the f(k) appearing in the running time of the best-known algorithms is optimal for any of these problems. In this paper, we examine parameterized problems where f(k) is kO(k) = 2O(k log k) in the best-known running time, and for a number of such problems we show that the dependence on k in the running time cannot be improved to single-exponential. More precisely we prove the following tight lower bounds, for four natural problems, arising from three different domains: (1) In the Closest String problem, given strings s1, ..., st over an alphabet Σ of length L each, and an integer d, the question is whether there exists a string s over Σ of length L, such that its hamming distance from each of the strings si, 1 ≤ i ≤ t, is at most d. The pattern matching problem Closest String is known to be solvable in times 2O(d log d) · nO(1) and 2O(d log |Σ|) · nO(1). We show that there are no 2o(d log d) · nO(1) or 2o(d log |Σ|) · nO(1) time algorithms, unless the Exponential Time Hypothesis (ETH) fails. (2) The graph embedding problem Distortion, that is, deciding whether a graph G has a metric embedding into the integers with distortion at most d can be solved in time 2O(d log d) · nO(1). We show that there is no 2o(d log d) · nO(1) time algorithm, unless the ETH fails. (3) The Disjoint Paths problem can be solved in time 2O(w log w) · nO(1) on graphs of treewidth at most w. We show that there is no 2o(w log w) · nO(1) time algorithm, unless the ETH fails. (4) The Chromatic Number problem can be solved in time 2O(w log w) ·nO(1) on graphs of treewidth at most w. We show that there is no 2o(w log w) · nO(1) time algorithm, unless the ETH fails. To obtain our results, we first prove the lower bound for variants of basic problems: finding cliques, independent sets, and hitting sets. These artificially constrained variants form a good starting point for proving lower bounds on natural problems without any technical restrictions and could be of independent interest. Several follow-up works have already obtained tight lower bounds by using our framework, and we believe it will prove useful in obtaining even more lower bounds in the future. [ABSTRACT FROM AUTHOR]

Image representation learning is a fundamental problem in understanding semantics of images. However, traditional classification-based representation learning methods face the noisy and incomplete problem of the supervisory labels. In this paper, we propose a general knowledge base embedded image representation learning approach, which uses general knowledge graph, which is a multitype relational knowledge graph consisting of human commonsense beyond image space, as external semantic resource to capture the relations of concepts in image representation learning. A relational regularized regression CNN (R$^3$CNN) model is designed to jointly optimize the image representation learning problem and knowledge graph embedding problem. In this manner, the learnt representation can capture not only labeled tags but also related concepts of images, which involves more precise and complete semantics. Comprehensive experiments are conducted to investigate the effectiveness and transferability of our approach in tag prediction task, zero-shot tag inference task, and content-based image retrieval task. The experimental results demonstrate that the proposed approach performs significantly better than the existing representation learning methods. Finally, observation of the learnt relations show that our approach can somehow refine the knowledge base to describe images and label the images with structured tags. [ABSTRACT FROM PUBLISHER]

A knowledge graph is a structured semantic network designed to describe physical entities and relations in the world. A comprehensive and accurate knowledge graph is essential for tasks such as knowledge inference and recommendation systems, making link prediction a popular problem for knowledge graph completion. However, existing approaches struggle to model complex relations among entities, which severely hampers their ability to complete knowledge graphs effectively. To address this challenge, we propose a novel hierarchical multi-head attention network embedding framework, called RiQ-KGC, which integrates different-grained contextual information of knowledge graph triples and models quaternion rotation relations between entities. Furthermore, we propose a relation instantiation method for alleviating the difficulty of expressing complex relations between entities. To enhance the expressiveness of relation representation, the relation is integrated by Transformer to obtain multi-hop neighbor information, so that one relation can be embedded into different embeddings according to different entities. Experimental results on four datasets demonstrate that RiQ-KGC exhibits strong competitiveness compared to state-of-the-art models in link prediction, while the ablation experiments reveal that the proposed relation instantiation method achieves great performance. [ABSTRACT FROM AUTHOR]

The first part of the paper centers in the study of embeddability between partially commutative groups. In [10], for a finite simplicial graph Γ, the authors introduce an infinite, locally infinite graph Γ e, called the extension graph of Γ . They show that each finite-induced subgraph Δ of Γ e gives rise to an embedding between the partially commutative groups G(Δ) and G(Γ ). Furthermore, it is proved that, in many instances, the converse also holds. Our first result is the decidability of the Extension Graph Embedding Problem: there is an algorithm that given two finite simplicial graphs Δ and Γ decides whether or not Δ is an induced subgraph of Γ e. As a corollary, we obtain the decidability of the Embedding Problem for 2D partially commutative groups. In the second part of the paper, we relate the Embedding Problem between partially commutative groups to the model-theoretic question of classification up to universal equivalence. We use our characterization to transfer algebraic and algorithmic results on embeddability to model-theoretic ones and obtain some rigidity results on the elementary theory of atomic pc groups as well as to deduce the existence of an algorithm to decide if an arbitrary pc group is universally equivalent to a 2D one. [ABSTRACT FROM AUTHOR]

The data arrangement problem on regular trees (DAPT) consists in assigning the vertices of a given graph G to the leaves of a d-regular tree T such that the sum of the pairwise distances of all pairs of leaves in T which correspond to edges of G is minimised. This problem is a special case of the generic graph embedding problem and is NP-hard for every fixed $$d\ge 2$$ . In this paper we propose construction and local search heuristics for the DAPT and introduce a lower bound for this problem. The analysis of the performance of the heuristics is based on two considerations: (a) the quality of the solutions produced by the heuristics as compared to the respective lower bound (b) for a special class of instances with known optimal solution we evaluate the gap between the optimal value of the objective function and the objective function value attained by the heuristic solution, respectively. [ABSTRACT FROM AUTHOR]

An important feature of an interconnection network is its ability to efficiently simulate one architecture by another. Such a simulation problem can be mathematically formulated as a graph embedding problem. Although the definition of an embedding is an into mapping from Guest Graph to Host Graph, so far in the literature, the embedding has been considered as a mapping from G onto H. In other words, the number of processors in G and H are considered to be the same. In this paper, we increase the number of processors in H by 1. The question is to find the processor in H which does not have the pre-image under the embedding mapping, so that the wirelength of the embedding is minimum. We relate this problem to finding transmission of vertices in the host graph. [ABSTRACT FROM AUTHOR]

Research in VLSI placement, an NP-hard problem, has branched in two different directions. The first one employs iterative heuristics with many tunable parameters to produce a near-optimal solution but without theoretical guarantee on its quality. The other one considers placement as a graph-embedding problem and designs approximation algorithms with provable bounds on the quality of the solution. In this article, we aim at unifying the above two directions. First, we extend the existing approximation algorithms for graph embedding in 1D and 2D grid to those for hypergraphs, which typically model circuits to be placed on a FPGA. We prove an approximation bound of O(d√log nlog log n) for 1D, that is, linear arrangement and O(d log nlog log n) for the 2D grid, where d is the maximum degree of hyperedges and n, the number of vertices in the hypergraph. Next, we propose an efficient method based on linear arrangement of the CLBs and the notion of space-filling curves for placing the configurable logic blocks (CLBs) of a netlist on island-style FPGAs with an approximation guarantee of O( ∜log n√kd log log n), where k is the number of nets. For the set of FPGA placement benchmarks, the running time is near linear in the number of CLBs thus allowing for scalability towards large circuits. We obtained a 33x speed-up, on average, with only 1.31x degradation in the quality of the solution compared to that produced by the popular FPGA tool VPR, thereby demonstrating the suitability of this very fast method for FPGA placement, with a provable performance guarantee. [ABSTRACT FROM AUTHOR]

A well-known problem in protein modeling is the determination of the structure of a protein with a given set of inter-atomic or inter-residue distances obtained from either physical experiments or theoretical estimates. A general form of the problem is known as the distance geometry problem in mathematics, the graph embedding problem in computer science, and the multidimensional scaling problem in statistics. The problem has applications in many other scientific and engineering fields as well such as sensor network localization, image recognition, and protein classification. We describe the formulations and complexities of the problem in its various forms, and introduce a geometric buildup approach to the problem. Central to this approach is the idea that the coordinates of the atoms in a protein can be determined one atom at a time, with the distances from the determined atoms to the undetermined ones. It can determine a structure more efficiently than other conventional approaches, yet without requiring more distance constraints than necessary. [ABSTRACT FROM AUTHOR]

Network Function Virtualization (NFV) opens us great opportunities for network processing with higher resource efficiency and flexibility. In this respect, there is an increasing need for intelligent orchestration mechanisms, such that NFV can exploit its potential and live up to its promise. Genetic algorithms have emerged as a promising alternative to the proliferation of heuristic and exact methods for the Service Function Chain (SFC) embedding problem. To this end, we design and evaluate a genetic algorithm (GA), which computes efficient embeddings with runtimes on par with approximate methods. We present a GA model as state-space search in order to clarify the design choices of a GA. Our proposed GA utilizes a heuristic for the generation of the initial population, with the aim of directing the search towards the solution. Given the sensitivity of GAs on their various parameters, we introduce a parameter adjustment framework for GA fine-tuning. A comparative evaluation among a range of GA variants with diverse features sheds light on the impact of these features on SFC embedding efficiency. The GA variant that stands out is further benchmarked against a baseline greedy algorithm and a state-of-the-art heuristic. Our evaluation results indicate that the GA yields notable gains in terms of request acceptance and resource efficiency. [ABSTRACT FROM AUTHOR]

We derive here a lower bound on the number of edges f(c, d) that one must remove from a depth- d complete binary tree in order to partition the tree into c equal size pieces (to within rounding). We show that for the sequence of integers c=3× 2. We then apply this bound to a graph-embedding problem related to the design of fault-tolerant VLSI processor arrays. An earlier study has exhibited a fault-tolerant implementation of arbitrary binary trees, using a particular design strategy. We show here that that implementation is optimal in area consumption (to within constant factors) among designs using that strategy, even when the array to be simulated must have the structure of a complete binary tree. [ABSTRACT FROM AUTHOR]

Embedding deals with simulating one architecture called guest into another called host, as it helps in modifying algorithms designed for the guest graph to be implemented in the host graph. In this paper, we have obtained the optimal wirelength of embedding (K 9 - C 9) n into P 9 n and certain trees, where (K 9 - C 9) n is the Cartesian product of complete graph on 9 vertices with a deletion of a cycle on 9 vertices and P 9 n is a path on 9 n vertices. Furthermore, we have also obtained the wirelength of embedding the Cartesian product graph (K 9 - C 9) n into Banana trees and Firecracker trees. [ABSTRACT FROM AUTHOR]

The paper considers an approach to a knowledge graph construction based on the ontological representation of scientific subject areas. The presentation is based on concepts related to information and data mining, such as knowledge, knowledge extraction, domain ontology, scientific domain, thesaurus, semantic digital library, user information need, ontological design method and, in fact, the knowledge graph. The digital semantic library LibMeta is presented as a repository of various structured data with the possibility of their integration with other data sources. Assumes the possibility of specifying personal content by describing a local subject area within LibMeta. The ontology of the content of the semantic library acts as a means of formalization. This paper addresses the experience of building semantic libraries based on thesauri and ontological design. Building ontologies based on the thesaurus of the subject area LibMeta allows us to say that the presence of internal semantic links ensures the consistency and reliability of search results, which is a necessary condition for extracting scientific knowledge. The digital library ontology defines the data structure of the library content. Each data element loaded into the library can be associated with an ontology vertex (top) that determines the position of the data element in the ontology. Based on the ontology links and the links defined at the design stage, you can build a data graph. On the example of the ontology of the LibMeta semantic library, the technology of forming the knowledge graph of modern applications in mathematics is discussed. The problems of filling a graph, embedding in a graph, extracting links and nodes of a graph are discussed. [ABSTRACT FROM AUTHOR]