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]

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]

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]

Several real-world phenomena, including social, communication, transportation, and biological networks, can be efficiently expressed as graphs. This enables the deployment of graph algorithms to infer information from such complex network interactions to enhance graph applications' accuracy, including link prediction, node classification, and clustering. However, the large size and complexity of the network data limit the efficiency of the learning algorithms in making decisions from such graph datasets. To overcome these limitations, graph embedding techniques are usually adopted. However, many studies not only assume static networks but also pay less attention to preserving the network topological and centrality information, which information is key in analyzing networks. In order to fill these gaps, we propose a novel end-to-end unified Topological Similarity and Centrality driven Hybrid Deep Learning model for Temporal Link Prediction (TSC-TLP). First, we extract topological similarity and centrality-based features from the raw networks. Next, we systematically aggregate these topological and centrality features to act as inputs for the encoder. In addition, we leverage the long short-term memory (LSTM) layer to learn the underlying temporal information in the graph snapshots. Lastly, we impose topological similarity and centrality constraints on the model learning to enforce preserving of topological structure and node centrality role of the input graphs in the learned embeddings. The proposed TSC-TLP is tested on 3 real-world temporal social networks. On average, it exhibits a 4% improvement in link prediction accuracy and a 37% reduction in MSE on centrality prediction over the best benchmark. [ABSTRACT FROM AUTHOR]

Quantum computing is a game-changing technology for global academia, research centers and industries including computational science, mathematics, finance, pharmaceutical, materials science, chemistry and cryptography. Although it has seen a major boost in the last decade, we are still a long way from reaching the maturity of a full-fledged quantum computer. That said, we will be in the noisy-intermediate scale quantum (NISQ) era for a long time, working on dozens or even thousands of qubits quantum computing systems. An outstanding challenge, then, is to come up with an application that can reliably carry out a nontrivial task of interest on the near-term quantum devices with non-negligible quantum noise. To address this challenge, several near-term quantum computing techniques, including variational quantum algorithms, error mitigation, quantum circuit compilation and benchmarking protocols, have been proposed to characterize and mitigate errors, and to implement algorithms with a certain resistance to noise, so as to enhance the capabilities of near-term quantum devices and explore the boundaries of their ability to realize useful applications. Besides, the development of near-term quantum devices is inseparable from the efficient classical simulation, which plays a vital role in quantum algorithm design and verification, error-tolerant verification and other applications. This review will provide a thorough introduction of these near-term quantum computing techniques, report on their progress, and finally discuss the future prospect of these techniques, which we hope will motivate researchers to undertake additional studies in this field. [ABSTRACT FROM AUTHOR]

Virtualized datacenters offer great flexibilities in terms of resource allocation. In particular, by decoupling applications from the constraints of the underlying infrastructure, virtualization supports an optimized mapping of virtual machines as well as their interconnecting network (the so-called virtual cluster ) to their physical counterparts: a graph embedding problem. However, existing virtual cluster embedding algorithms often ignore a crucial dimension of the problem, namely data locality : the input to a cloud application such as MapReduce is typically stored in a distributed, and sometimes redundant, file system. Since moving data is costly, an embedding algorithm should be data locality aware, and allocate computational resources close to the data; in case of redundant storage, the algorithm should also optimize the replica selection . This paper initiates the algorithmic study of data locality aware virtual cluster embeddings on datacenter topologies. We show that despite the multiple degrees of freedom in terms of embedding, replica selection and assignment, many problems can be solved efficiently. We also highlight the limitations of such optimizations, by presenting several NP-hardness proofs; interestingly, our hardness results also hold in uncapacitated networks of small diameter. [ABSTRACT FROM AUTHOR]

In this paper, a novel supervised local high-order differential channel feature is proposed for fast pedestrian detection. This method is motivated by the recent successful use of filtering on the multiple channel maps, which can improve the performance. This method firstly compute the multiple channel maps for the input RGB image, and average pooling is acted on the channel maps in order to reduce the effect of noise and sample misalignment. Then, each of the pooled channel maps is convolved with our proposed local high-order filter bank, which can enhance the discriminative information in the feature space. Finally, due to the increasing memory consumption incurred by the higher dimension of resulting feature, we have proposed a local structure preserved supervised dimension reduction method which aims to keep the manifold structure of samples in the feature space. This method is formulated as a classical spectral graph embedding problem which can be solved by the LPP algorithms. Thorough experiments and comparative studies show that our method can achieve very competitive result compared with many state-of-art methods on the INRIA and Caltech datasets. Besides, our detector can run about 20 fps in 480 $$\times $$ 640 resolution images. [ABSTRACT FROM AUTHOR]

Graphs are data structures that effectively represent relational data in the real world. Graph representation learning is a significant task since it could facilitate various downstream tasks, such as node classification, link prediction, etc. Graph representation learning aims to map graph entities to low-dimensional vectors while preserving graph structure and entity relationships. Over the decades, many models have been proposed for graph representation learning. This paper aims to show a comprehensive picture of graph representation learning models, including traditional and state-of-the-art models on various graphs in different geometric spaces. First, we begin with five types of graph embedding models: graph kernels, matrix factorization models, shallow models, deep-learning models, and non-Euclidean models. In addition, we also discuss graph transformer models and Gaussian embedding models. Second, we present practical applications of graph embedding models, from constructing graphs for specific domains to applying models to solve tasks. Finally, we discuss challenges for existing models and future research directions in detail. As a result, this paper provides a structured overview of the diversity of graph embedding models. [ABSTRACT FROM AUTHOR]

Software question answering community (SQAC) as an effective platform of knowledge sharing has achieved rapid development. In SQAC, one critical and challenging problem is question routing (or expert recommendation). To solve this problem, previous approaches focus on learning the relevance between the question and answerers. However, such approaches usually suffer from the data sparsity and noise issues which may reduce the accuracy of the question routing. Moreover, previous approaches also ignored the response quality and timeliness of the question routing. To tackle those issues, we study the question routing problem from two aspects: 1) the answerer's relevance to the given question, and 2) the answerer's capability. We first propose a deep knowledge-awared question routing framework (termed ExpRec) which leverages the attentive embedding propagates and their high-order connectivities to learn the answerer's relevance to the given question. Then we explicitly model the answerer's capability and incorporate it with the answerer's relevance to the given question. Finally, to evaluate the performance of ExpRec, we conduct extensive experiments on two real-world datasets. The experimental results show that ExpRec outperforms other five state-of-the-art approaches significantly. [ABSTRACT FROM AUTHOR]

Nuclear magnetic resonance (NMR) spectroscopy can reveal conformational states of a protein in physiological conditions. However, sparsely available NMR data for a protein with large degrees of freedom can introduce structural artifacts in the built models. Currently used state‐of‐the‐art methods deriving protein structure and conformation from NMR deploy molecular dynamics (MD) coupled with simulated annealing for building models. We provide an alternate graph‐based modeling approach, where we first build substructures from NMR‐derived distance‐geometry constraints combined in one shot to form the core structure. The remaining molecule with inadequate data is modeled using a hybrid approach respecting the observed distance‐geometry constraints. One‐shot structure building is rarely undertaken for large and sparse data systems, but our data‐driven bottom‐up approach makes this uniquely feasible by suitable partitioning of the problem. A detailed comparison of select models with state‐of‐art methods reveals differences in the secondary structure regions wherein the correctness of our models is confirmed by NMR data. Benchmarking of 106 protein‐folds covering 38–282 length structures shows minimal experimental‐constraint violations while conforming to other structure quality parameters such as the proper folding, steric clash, and torsion angle violation based on Ramachandran plot criteria. Comparative MD studies using select protein models from a state‐of‐art method and ours under identical experimental parameters reveal distinct conformational dynamics that could be attributed to protein structure–function. Our work is thus useful in building enhanced NMR‐evidence‐based models that encapsulate the contextual secondary and tertiary structure variations present during the experimentation and expand the scope of functional inference. [ABSTRACT FROM AUTHOR]

The reconstruction of realistic large-scale 3D scene models using aerial images or videos has significant applications in smart cities, surveying and mapping, the military and other fields. In the current state-of-the-art 3D-reconstruction pipeline, the massive scale of the scene and the enormous amount of input data are still considerable obstacles to the rapid reconstruction of large-scale 3D scene models. In this paper, we develop a professional system for large-scale 3D reconstruction. First, in the sparse point-cloud reconstruction stage, the computed matching relationships are used as the initial camera graph and divided into multiple subgraphs by a clustering algorithm. Multiple computational nodes execute the local structure-from-motion (SFM) technique, and local cameras are registered. Global camera alignment is achieved by integrating and optimizing all local camera poses. Second, in the dense point-cloud reconstruction stage, the adjacency information is decoupled from the pixel level by red-and-black checkerboard grid sampling. The optimal depth value is obtained using normalized cross-correlation (NCC). Additionally, during the mesh-reconstruction stage, feature-preserving mesh simplification, Laplace mesh-smoothing and mesh-detail-recovery methods are used to improve the quality of the mesh model. Finally, the above algorithms are integrated into our large-scale 3D-reconstruction system. Experiments show that the system can effectively improve the reconstruction speed of large-scale 3D scenes. [ABSTRACT FROM AUTHOR]

The problem of determining the genus for a graph can be dated to the Map Color Conjecture proposed by Heawood in 1890. This was implied to be a Thread Problem by Hilbert and Cohn-Vossen. The conjecture was finally established by Ringel, Youngs, and many other mathematicians. Subsequently, the genera of some special graphs with symmetry were determined. The study of genus embeddings of graphs is closely related to other invariants of a graph. Specifically, the computational complexity is dependent on the genus of the underlying graph for certain well-known NP-hard problems. In this survey, main construction techniques and certain criteria are stated in the topic of the genus of a graph. Most graphs with a known genus are listed. A new theorem is shown that the method of joint trees of a graph is reasonable. Moreover, a formal set is introduced, and related results are obtained. Although a cubic graph of Hamilton cycle is asymmetric, it is interesting that a set of associate surfaces of all its joint trees is a formal set with symmetry. [ABSTRACT FROM AUTHOR]

Dynamic latent variable (DLV) methods have been widely studied for high dimensional time series monitoring by exploiting dynamic relations among process variables. However, explicit extraction of predictable information is rarely emphasized in these DLV methods. In this paper, the graph‐based predictable feature analysis (GPFA) algorithm is introduced for statistical process monitoring due to its explicit predictability, and a novel index, prediction information, is designed to determine the number of its principal components for dimensionality reduction and parameter optimization. A GPFA‐based dynamic process monitoring framework is proposed to differentiate among dynamic faults, normal operating condition changes, and break in relation in the normal data. Case studies on the Tennessee Eastman process and a high‐pressure feedwater heater are conducted to demonstrate the superiority of GPFA over other approaches in terms of fault detection performance. [ABSTRACT FROM AUTHOR]

This paper discusses about the new approach of multiple object tracking relative to background information. The concept of multiple object tracking through background learning is based upon the theory of relativity, that involves a frame of reference in spatial domain to localize and/or track any object. The field of multiple object tracking has seen a lot of research, but researchers have considered the background as redundant. However, in object tracking, the background plays a vital role and leads to definite improvement in the overall process of tracking. In the present work an algorithm is proposed for the multiple object tracking through background learning. The learning framework is based on graph embedding approach for localizing multiple objects. The graph utilizes the inherent capabilities of depth modelling that assist in prior to track occlusion avoidance among multiple objects. The proposed algorithm has been compared with the recent work available in literature on numerous performance evaluation measures. It is observed that our proposed algorithm gives better performance. [ABSTRACT FROM AUTHOR]

Embedding static graphs in low-dimensional vector spaces plays a key role in network analytics and inference, supporting applications like node classification, link prediction, and graph visualization. However, many real-world networks present dynamic behavior, including topological evolution, feature evolution, and diffusion. Therefore, several methods for embedding dynamic graphs have been proposed to learn network representations over time, facing novel challenges, such as time-domain modeling, temporal features to be captured, and the temporal granularity to be embedded. In this survey, we overview dynamic graph embedding, discussing its fundamentals and the recent advances developed so far. We introduce the formal definition of dynamic graph embedding, focusing on the problem setting and introducing a novel taxonomy for dynamic graph embedding input and output. We further explore different dynamic behaviors that may be encompassed by embeddings, classifying by topological evolution, feature evolution, and processes on networks. Afterward, we describe existing techniques and propose a taxonomy for dynamic graph embedding techniques based on algorithmic approaches, from matrix and tensor factorization to deep learning, random walks, and temporal point processes. We also elucidate main applications, including dynamic link prediction, anomaly detection, and diffusion prediction, and we further state some promising research directions in the area. [ABSTRACT FROM AUTHOR]

Knowledge graph embedding has been proposed to embed entities and relations into continuous vector spaces, which can benefit various downstream tasks, such as question answering and recommender systems, etc. A common assumption of existing knowledge graph embedding models is that the relation is a translation vector connecting the embedded head entity and tail entity. However, based on this assumption, the same relation connecting multiple entities may form a circle and lead to mistakes during computing process. To solve this so-called circular relation problem that has been ignored previously, we propose a novel method called ContE (Contextualized Embedding) for knowledge graphs by exploring collaborative relations. Specifically, each collaborative relation combines an explicit relation and a latent relation, where the explicit one is the original relation between two entities, and the latent one is introduced to capture the implicit interactions obtained via the context information of the two entities. With the collaborative relations, the same relations will be embedded varying across different contexts, and the sharing of similar semantics will be guaranteed as well. We conduct extensive experiments in link prediction and triple classification tasks on five benchmark datasets. The experimental results demonstrate that the proposed ContE achieves improvements over several baselines. [ABSTRACT FROM AUTHOR]

The rotational dimension is a minor-monotone graph invariant related to the dimension of a Euclidean space containing a spectral embedding corresponding to the first nonzero eigenvalue of the graph Laplacian, which is introduced by Göring, Helmberg and Wappler. In this paper, we study rotational dimensions of graphs which contain large complete graphs. The complete graph is characterized by its rotational dimension. It will be obtained that a chordal graph may be made large while keeping the rotational dimension constant. [ABSTRACT FROM AUTHOR]

Graph embedding is of great significance for the research and analysis of graphs. Graph embedding aims to map nodes in the network to low-dimensional vectors while preserving information in the original graph of nodes. In recent years, the appearance of graph neural networks has significantly improved the accuracy of graph embedding. However, the influence of clusters was not considered in existing graph neural network (GNN)-based methods, so this paper proposes a new method to incorporate the influence of clusters into the generation of graph embedding. We use the attention mechanism to pass the message of the cluster pooled result and integrate the whole process into the graph autoencoder as the third layer of the encoder. The experimental results show that our model has made great improvement over the baseline methods in the node clustering and link prediction tasks, demonstrating that the embeddings generated by our model have excellent expressiveness. [ABSTRACT FROM AUTHOR]

Identifying urban functional regions is a trending topic in urban computing. It helps understand the economic and cultural development of cities and assists decision-makers in land-use planning. However, the studies to date have not fully mined the spatio-temporal characteristics of location data, and most have used the direct clustering method to judge differences among urban land use types, resulting in low identification accuracies. Here, we propose a novel framework for urban functional region discovery based on residents' travel patterns. The framework uses GPS trajectory data and check-in data to construct a travel pattern graph with temporal and spatial attributes and learns the vector representations of urban regions using the Node2vec method to identify urban functional regions. In addition, a novel detection method that combines semantic information of check-in data and well-known points of interest (POIs) was constructed to annotate the semantics of the functional regions. Real location data sets were used for verification. The experimental results showed that the proposed graph embedding learning method could effectively discover urban functional regions. Moreover, this method solved the problem of accurately identifying the semantics of functional regions to a certain extent. [ABSTRACT FROM AUTHOR]