282 results on '"graph embedding problem"'
Search Results
2. Embedding Wheel-like Networks.
- Author
-
Rajan, R. Sundara, Rajalaxmi, T. M., Stephen, Sudeep, Shantrinal, A. Arul, and Kumar, K. Jagadeesh
- Subjects
PETERSEN graphs ,VIRTUAL networks ,HAMILTONIAN graph theory ,CUBES ,PARALLEL algorithms - Abstract
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]
- Published
- 2023
- Full Text
- View/download PDF
3. On Optimal Embeddings in 3-Ary n -Cubes.
- Author
-
Rajeshwari, S. and Rajesh, M.
- Subjects
ISOPERIMETRICAL problems ,CUBES - Abstract
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]
- Published
- 2023
- Full Text
- View/download PDF
4. A survey on bipartite graphs embedding.
- Author
-
Giamphy, Edward, Guillaume, Jean-Loup, Doucet, Antoine, and Sanchis, Kevin
- Abstract
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]
- Published
- 2023
- Full Text
- View/download PDF
5. A combinatorial approach to phase transitions in random graph isomorphism problems
- Author
-
Diamantidis, Dimitris, Konstantopoulos, Takis, and Yuan, Linglong
- Subjects
Mathematics - Combinatorics ,Mathematics - Probability ,60C05, 05C60, 60F99, 05A19 - Abstract
We consider two independent Erd\H{o}s-R\'enyi random graphs, with possibly different parameters, and study two isomorphism problems, a graph embedding problem and a common subgraph problem. Under certain conditions on the graph parameters we show a sharp asymptotic phase transition as the graph sizes tend to infinity. This extends known results for the case of uniform Erd\H{o}s-R\'enyi random graphs. Our approach is primarily combinatorial, naturally leading to several related problems for further exploration., Comment: 38 pages
- Published
- 2024
6. Block Coordinate Descent Methods for Optimization under J-Orthogonality Constraints with Applications
- Author
-
He, Di, Yuan, Ganzhao, Wang, Xiao, and Xu, Pengxiang
- Subjects
Computer Science - Data Structures and Algorithms - Abstract
The J-orthogonal matrix, also referred to as the hyperbolic orthogonal matrix, is a class of special orthogonal matrix in hyperbolic space, notable for its advantageous properties. These matrices are integral to optimization under J-orthogonal constraints, which have widespread applications in statistical learning and data science. However, addressing these problems is generally challenging due to their non-convex nature and the computational intensity of the constraints. Currently, algorithms for tackling these challenges are limited. This paper introduces JOBCD, a novel Block Coordinate Descent method designed to address optimizations with J-orthogonality constraints. We explore two specific variants of JOBCD: one based on a Gauss-Seidel strategy (GS-JOBCD), the other on a variance-reduced and Jacobi strategy (VR-J-JOBCD). Notably, leveraging the parallel framework of a Jacobi strategy, VR-J-JOBCD integrates variance reduction techniques to decrease oracle complexity in the minimization of finite-sum functions. For both GS-JOBCD and VR-J-JOBCD, we establish the oracle complexity under mild conditions and strong limit-point convergence results under the Kurdyka-Lojasiewicz inequality. To demonstrate the effectiveness of our method, we conduct experiments on hyperbolic eigenvalue problems, hyperbolic structural probe problems, and the ultrahyperbolic knowledge graph embedding problem. Extensive experiments using both real-world and synthetic data demonstrate that JOBCD consistently outperforms state-of-the-art solutions, by large margins.
- Published
- 2024
7. HUGE: Huge Unsupervised Graph Embeddings with TPUs
- Author
-
Mayer, Brandon, Tsitsulin, Anton, Fichtenberger, Hendrik, Halcrow, Jonathan, Perozzi, Bryan, Mayer, Brandon, Tsitsulin, Anton, Fichtenberger, Hendrik, Halcrow, Jonathan, and Perozzi, Bryan
- Abstract
Graphs are a representation of structured data that captures the relationships between sets of objects. With the ubiquity of available network data, there is increasing industrial and academic need to quickly analyze graphs with billions of nodes and trillions of edges. A common first step for network understanding is Graph Embedding, the process of creating a continuous representation of nodes in a graph. A continuous representation is often more amenable, especially at scale, for solving downstream machine learning tasks such as classification, link prediction, and clustering. A high-performance graph embedding architecture leveraging Tensor Processing Units (TPUs) with configurable amounts of high-bandwidth memory is presented that simplifies the graph embedding problem and can scale to graphs with billions of nodes and trillions of edges. We verify the embedding space quality on real and synthetic large-scale datasets., Comment: As appeared at KDD 2023
- Published
- 2023
- Full Text
- View/download PDF
8. Consistency and Complementarity Jointly Regularized Subspace Support Vector Data Description for Multimodal Data.
- Author
-
Wang, Chuang, Hu, Wenjun, Wang, Juan, Qian, Pengjiang, Wang, Shitong, and Ortale, Riccardo
- Abstract
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]
- Published
- 2024
- Full Text
- View/download PDF
9. Decomposing User-APP Graph into Subgraphs for Effective APP and User Embedding Learning
- Author
-
Yu, Tan, Zhi, Jun, Zhang, Yufei, Li, Jian, Fei, Hongliang, Li, Ping, Yu, Tan, Zhi, Jun, Zhang, Yufei, Li, Jian, Fei, Hongliang, and Li, Ping
- Abstract
APP-installation information is helpful to describe the user's characteristics. The users with similar APPs installed might share several common interests and behave similarly in some scenarios. In this work, we learn a user embedding vector based on each user's APP-installation information. Since the user APP-installation embedding is learnable without dependency on the historical intra-APP behavioral data of the user, it complements the intra-APP embedding learned within each specific APP. Thus, they considerably help improve the effectiveness of the personalized advertising in each APP, and they are particularly beneficial for the cold start of the new users in the APP. In this paper, we formulate the APP-installation user embedding learning into a bipartite graph embedding problem. The main challenge in learning an effective APP-installation user embedding is the imbalanced data distribution. In this case, graph learning tends to be dominated by the popular APPs, which billions of users have installed. In other words, some niche/specialized APPs might have a marginal influence on graph learning. To effectively exploit the valuable information from the niche APPs, we decompose the APP-installation graph into a set of subgraphs. Each subgraph contains only one APP node and the users who install the APP. For each mini-batch, we only sample the users from the same subgraph in the training process. Thus, each APP can be involved in the training process in a more balanced manner. After integrating the learned APP-installation user embedding into our online personal advertising platform, we obtained a considerable boost in CTR, CVR, and revenue.
- Published
- 2022
10. Learning Adaptive Node Embeddings Across Graphs
- Author
-
Guo, Gaoyang, Wang, Chaokun, Yan, Bencheng, Lou, Yunkai, Feng, Hao, Zhu, Junchao, Chen, Jun, He, Fei, and Yu, Philip S.
- Abstract
Recently, learning embeddings of nodes in graphs has attracted increasing research attention. There are two main kinds of graph embedding methods, i.e., transductive embedding methods and inductive embedding methods. The former focuses on directly optimizing the embedding vectors, and the latter tries to learn a mapping function for the given nodes and features. However, little work has focused on applying the learned model from one graph to another, which is a pervasive idea in Computer Vision or Natural Language Processing. Although some of the graph neural networks (GNNs) present a similar motivation, none of them considers both the structure bias and the feature bias between graphs. In this paper, we present a novel graph embedding problem called Adaptive Task (AT), and propose a unified framework for the adaptive task, which introduces two types of alignment to learn adaptive node embeddings across graphs. Then, based on the proposed framework, a novel Graph Adaptive Embedding network (GraphAE) is designed to address the adaptive task. Furthermore, we extend GraphAE to a multi-graph version to consider a more complex adaptive situation. The extensive experimental results demonstrate that our model significantly outperforms the state-of-the-art methods, and also show that our framework can make a great improvement over a number of existing GNNs.
- Published
- 2023
- Full Text
- View/download PDF
11. A Comprehensive Survey of Graph Embedding: Problems, Techniques, and Applications.
- Author
-
Cai, Hongyun, Zheng, Vincent W., and Chang, Kevin Chen-Chuan
- Subjects
EMBEDDING theorems ,REPRESENTATIONS of graphs ,NODAL analysis ,TAXONOMY ,COMPUTATIONAL mechanics - Abstract
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]
- Published
- 2018
- Full Text
- View/download PDF
12. SLIGHTLY SUPEREXPONENTIAL PARAMETERIZED PROBLEMS.
- Author
-
LOKSHTANOV, DANIEL, MARX, DÁNIEL, and SAURABH, SAKET
- Subjects
PARAMETERIZATION ,ALGORITHMS ,PROBLEM solving ,COMPUTATIONAL complexity ,MATHEMATICAL bounds - Abstract
A central problem in parameterized algorithms is to obtain algorithms with running time f(k) · n
O (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]- Published
- 2018
- Full Text
- View/download PDF
13. General Knowledge Embedded Image Representation Learning.
- Author
-
Cui, Peng, Liu, Shaowei, and Zhu, Wenwu
- Abstract
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]
- Published
- 2018
- Full Text
- View/download PDF
14. Continual Learning of Knowledge Graph Embeddings
- Author
-
Daruna, Angel, Gupta, Mehul, Sridharan, Mohan, Chernova, Sonia, Daruna, Angel, Gupta, Mehul, Sridharan, Mohan, and Chernova, Sonia
- Abstract
In recent years, there has been a resurgence in methods that use distributed (neural) representations to represent and reason about semantic knowledge for robotics applications. However, while robots often observe previously unknown concepts, these representations typically assume that all concepts are known a priori, and incorporating new information requires all concepts to be learned afresh. Our work relaxes this limiting assumption of existing representations and tackles the incremental knowledge graph embedding problem by leveraging the principles of a range of continual learning methods. Through an experimental evaluation with several knowledge graphs and embedding representations, we provide insights about trade-offs for practitioners to match a semantics-driven robotics applications to a suitable continual knowledge graph embedding method., Comment: 8 pages, 4 figures. Accepted for publication in IEEE Robotics and Automation Letters (RA-L)
- Published
- 2021
15. Dynamic community detection algorithm based on hyperbolic graph convolution.
- Author
-
Wu, Weijiang, Tan, Heping, and Zheng, Yifeng
- Abstract
Purpose: Community detection is a key factor in analyzing the structural features of complex networks. However, traditional dynamic community detection methods often fail to effectively solve the problems of deep network information loss and computational complexity in hyperbolic space. To address this challenge, a hyperbolic space-based dynamic graph neural network community detection model (HSDCDM) is proposed. Design/methodology/approach: HSDCDM first projects the node features into the hyperbolic space and then utilizes the hyperbolic graph convolution module on the Poincaré and Lorentz models to realize feature fusion and information transfer. In addition, the parallel optimized temporal memory module ensures fast and accurate capture of time domain information over extended periods. Finally, the community clustering module divides the community structure by combining the node characteristics of the space domain and the time domain. To evaluate the performance of HSDCDM, experiments are conducted on both artificial and real datasets. Findings: Experimental results on complex networks demonstrate that HSDCDM significantly enhances the quality of community detection in hierarchical networks. It shows an average improvement of 7.29% in NMI and a 9.07% increase in ARI across datasets compared to traditional methods. For complex networks with non-Euclidean geometric structures, the HSDCDM model incorporating hyperbolic geometry can better handle the discontinuity of the metric space, provides a more compact embedding that preserves the data structure, and offers advantages over methods based on Euclidean geometry methods. Originality/value: This model aggregates the potential information of nodes in space through manifold-preserving distribution mapping and hyperbolic graph topology modules. Moreover, it optimizes the Simple Recurrent Unit (SRU) on the hyperbolic space Lorentz model to effectively extract time series data in hyperbolic space, thereby enhancing computing efficiency by eliminating the reliance on tangent space. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
16. Maximizing the algebraic connectivity in multilayer networks with arbitrary interconnections
- Author
-
Tavasoli, Ali, Ardjmand, Ehsan, Shakeri, Heman, Tavasoli, Ali, Ardjmand, Ehsan, and Shakeri, Heman
- Abstract
The second smallest eigenvalue of the Laplacian matrix is determinative in characterizing many network properties and is known as algebraic connectivity. In this paper, we investigate the problem of maximizing algebraic connectivity in multilayer networks by allocating interlink weights subject to a budget while allowing arbitrary interconnections. For budgets below a threshold, we identify an upper-bound for maximum algebraic connectivity which is independent of interconnections pattern and is reachable with satisfying a certain regularity condition. For efficient numerical approaches in regions of no analytical solution, we cast the problem into a convex framework that explores the problem from several perspectives and, particularly, transforms into a graph embedding problem that is easier to interpret and related to the optimum diffusion phase. Allowing arbitrary interconnections entails regions of multiple transitions, giving more diverse diffusion phases with respect to one-to-one interconnection case. When there is no limitation on the interconnections pattern, we derive several analytical results characterizing the optimal weights by individual Fiedler vectors. We use the ratio of algebraic connectivity and the layer sizes to explain the results. Finally, we study the placement of a limited number of interlinks by greedy heuristics, using the Fiedler vector components of each layer., Comment: 46 pages, 25 figures
- Published
- 2020
17. RiQ-KGC: Relation Instantiation Enhanced Quaternionic Attention for Complex-Relation Knowledge Graph Completion.
- Author
-
Wang, Yunpeng, Ning, Bo, Jiang, Shuo, Zhou, Xin, Li, Guanyu, and Ma, Qian
- Subjects
KNOWLEDGE graphs ,RECOMMENDER systems ,COMPLETE graphs ,QUATERNIONS ,QUATERNION functions - Abstract
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]
- Published
- 2024
- Full Text
- View/download PDF
18. Digital Three-dimensional Smocking Design.
- Author
-
JING REN, SEGALL, AVIV, and SORKINE-HORNUNG, OLGA
- Published
- 2024
- Full Text
- View/download PDF
19. Embeddability and Universal Theory of Partially Commutative Groups.
- Author
-
Casals-Ruiz, Montserrat
- Subjects
EMBEDDINGS (Mathematics) ,ABELIAN groups ,SUBGRAPHS ,GEOMETRIC rigidity ,ARBITRARY constants - Abstract
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]- Published
- 2015
- Full Text
- View/download PDF
20. Heuristics for the data arrangement problem on regular trees.
- Author
-
Çela, Eranda and Staněk, Rostislav
- Abstract
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]
- Published
- 2015
- Full Text
- View/download PDF
21. Embedding of Complete graphs and Cycles into Grids with holes.
- Author
-
Mary, R. Stalin and Rajasingh, Indra
- Subjects
COMPLETE graphs ,DEFINITIONS - Abstract
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]
- Published
- 2020
- Full Text
- View/download PDF
22. All Graphs Lead to Rome: Learning Geometric and Cycle-Consistent Representations with Graph Convolutional Networks
- Author
-
Phillips, Stephen, Daniilidis, Kostas, Phillips, Stephen, and Daniilidis, Kostas
- Abstract
Image feature matching is a fundamental part of many geometric computer vision applications, and using multiple images can improve performance. In this work, we formulate multi-image matching as a graph embedding problem then use a Graph Convolutional Network to learn an appropriate embedding function for aligning image features. We use cycle consistency to train our network in an unsupervised fashion, since ground truth correspondence is difficult or expensive to aquire. In addition, geometric consistency losses can be added at training time, even if the information is not available in the test set, unlike previous approaches that optimize cycle consistency directly. To the best of our knowledge, no other works have used learning for multi-image feature matching. Our experiments show that our method is competitive with other optimization based approaches., Comment: 9 pages, 7 figures, 2 tables, 2 supplemental figures
- Published
- 2019
23. Finetuning Discrete Architectural Surfaces by use of Circle Packing.
- Author
-
Kaji, Shizuo and Zhang, Jingyao
- Published
- 2024
- Full Text
- View/download PDF
24. BITS Darshini.
- Author
-
Talasila, Prasad, Kakrambe, Mihir, Rai, Anurag, Santy, Sebastin, Goveas, Neena, and Deshpande, Bharat M.
- Published
- 2018
- Full Text
- View/download PDF
25. Symmetrization for Embedding Directed Graphs
- Author
-
Sun, Jiankai, Parthasarathy, Srinivasan, Sun, Jiankai, and Parthasarathy, Srinivasan
- Abstract
Recently, one has seen a surge of interest in developing such methods including ones for learning such representations for (undirected) graphs (while preserving important properties). However, most of the work to date on embedding graphs has targeted undirected networks and very little has focused on the thorny issue of embedding directed networks. In this paper, we instead propose to solve the directed graph embedding problem via a two-stage approach: in the first stage, the graph is symmetrized in one of several possible ways, and in the second stage, the so-obtained symmetrized graph is embedded using any state-of-the-art (undirected) graph embedding algorithm. Note that it is not the objective of this paper to propose a new (undirected) graph embedding algorithm or discuss the strengths and weaknesses of existing ones; all we are saying is that whichever be the suitable graph embedding algorithm, it will fit in the above proposed symmetrization framework., Comment: has been accepted to The Thirty-Third AAAI Conference on Artificial Intelligence (AAAI 2019) Student Abstract and Poster Program
- Published
- 2018
26. Intelligent and Resource-Conserving Service Function Chain (SFC) Embedding.
- Author
-
Rodis, Panteleimon and Papadimitriou, Panagiotis
- Abstract
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]
- Published
- 2023
- Full Text
- View/download PDF
27. A Comprehensive Survey of Graph Embedding: Problems, Techniques and Applications
- Author
-
Cai, Hongyun, Zheng, Vincent W., Chang, Kevin Chen-Chuan, Cai, Hongyun, Zheng, Vincent W., and Chang, Kevin Chen-Chuan
- Abstract
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 maximally 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 address 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., Comment: A 20-page comprehensive survey of graph/network embedding for over 150+ papers till year 2018. It provides systematic categorization of problems, techniques and applications. Accepted by IEEE Transactions on Knowledge and Data Engineering (TKDE). Comments and suggestions are welcomed for continuously improving this survey
- Published
- 2017
28. Embedding Complete Multipartite Graphs into Certain Trees
- Author
-
Shantrinal, A. Arul, Rajan, R. Sundara, Babu, A. Ramesh, Anil, S., and Ahmed, Mohammed Ali
- Subjects
Mathematics - Combinatorics - Abstract
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 embed complete multipartite graphs into certain trees, such as $k$-rooted complete binary trees and $k$-rooted sibling trees., Comment: Page=14, Figures=4, Journal=Accepted in the special issue of JCMCC. arXiv admin note: text overlap with arXiv:1901.07717
- Published
- 2019
29. Embedding onto Wheel-like Networks
- Author
-
Rajan, R. Sundara, Rajalaxmi, T. M., Stephen, Sudeep, Shantrinal, A. Arul, and Kumar, K. Jagadeesh
- Subjects
Mathematics - Combinatorics - Abstract
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 wheel-like 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, M\"{o}bius 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., Comment: 12 Pages, 5 Figures
- Published
- 2019
30. MinLA of (K9-C9)n and its optimal layout into certain trees.
- Author
-
Afiya, Syeda and Rajesh, M
- Subjects
COMPLETE graphs ,TREES ,ISOPERIMETRICAL problems ,BANANAS - Abstract
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]
- Published
- 2023
- Full Text
- View/download PDF
31. Ontological Approach to a Knowledge Graph Construction in a Semantic Library.
- Author
-
Ataeva, O. M., Serebryakov, V. A., and Tuchkova, N. P.
- Abstract
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]
- Published
- 2023
- Full Text
- View/download PDF
32. Topological Similarity and Centrality Driven Hybrid Deep Learning for Temporal Link Prediction.
- Author
-
Sserwadda, Abubakhari, Ozcan, Alper, and Yaslan, Yusuf
- Abstract
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]
- Published
- 2023
- Full Text
- View/download PDF
33. Near-term quantum computing techniques: Variational quantum algorithms, error mitigation, circuit compilation, benchmarking and classical simulation.
- Author
-
Huang, He-Liang, Xu, Xiao-Yue, Guo, Chu, Tian, Guojing, Wei, Shi-Jie, Sun, Xiaoming, Bao, Wan-Su, and Long, Gui-Lu
- Abstract
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]
- Published
- 2023
- Full Text
- View/download PDF
34. Data locality and replica aware virtual cluster embeddings.
- Author
-
Fuerst, Carlo, Pacut, Maciej, and Schmid, Stefan
- Subjects
- *
DATA libraries , *EMBEDDINGS (Mathematics) , *PROBLEM solving , *DEGREES of freedom , *NP-hard problems - Abstract
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]
- Published
- 2017
- Full Text
- View/download PDF
35. Supervised Local High-Order Differential Channel Feature Learning for Pedestrian Detection.
- Author
-
Shen, Jifeng, Zuo, Xin, Liu, Hui, Wang, Haoran, Yang, Wankou, and Qian, Chengshan
- Subjects
SUPERVISED learning ,FILTER banks ,DIMENSION reduction (Statistics) ,EMBEDDINGS (Mathematics) ,GRAPH theory - Abstract
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]
- Published
- 2017
- Full Text
- View/download PDF
36. Graph Representation Learning and Its Applications: A Survey.
- Author
-
Hoang, Van Thuy, Jeon, Hyeon-Ju, You, Eun-Soon, Yoon, Yoewon, Jung, Sungyeop, and Lee, O-Joun
- Subjects
REPRESENTATIONS of graphs ,MATRIX decomposition ,DATA structures ,SHALLOW-water equations - Abstract
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]
- Published
- 2023
- Full Text
- View/download PDF
37. ExpRec: Deep knowledge-awared question routing in software question answering community.
- Author
-
Liu, Jiahui, Deng, Ansheng, Xie, Xinqiang, and Xie, Qiuju
- Subjects
COMMUNITIES ,COMPUTER software ,KNOWLEDGE graphs ,INFORMATION sharing ,PROBLEM solving ,ROUTING algorithms ,EMBEDDING theorems - Abstract
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]
- Published
- 2023
- Full Text
- View/download PDF
38. Improved NMR‐data‐compliant protein structure modeling captures context‐dependent variations and expands the scope of functional inference.
- Author
-
Das, Niladri R., Chaudhury, Kunal N., and Pal, Debnath
- Abstract
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]
- Published
- 2023
- Full Text
- View/download PDF
39. A Cluster-Based 3D Reconstruction System for Large-Scale Scenes.
- Author
-
Li, Yao, Qi, Yue, Wang, Chen, and Bao, Yongtang
- Subjects
SMART cities ,SUBGRAPHS ,CAMERAS - Abstract
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]
- Published
- 2023
- Full Text
- View/download PDF
40. The Genus of a Graph: A Survey.
- Author
-
Wan, Liangxia
- Subjects
NP-hard problems ,TREE graphs ,COMPUTATIONAL complexity ,MATHEMATICIANS ,LOGICAL prediction - Abstract
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]
- Published
- 2023
- Full Text
- View/download PDF
41. Multivariate temporal process monitoring with graph‐based predictable feature analysis.
- Author
-
Fan, Wei, Zhu, Qinqin, Ren, Shaojun, Xu, Bo, and Si, Fengqi
- Subjects
TIME series analysis ,LATENT variables ,INFORMATION theory ,DATA mining ,DIMENSION reduction (Statistics) ,HEATING ,QUALITY control charts - Abstract
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]
- Published
- 2023
- Full Text
- View/download PDF
42. Network embedding on Planar Octahedron networks.
- Author
-
Simon Raj, F. and George, A.
- Published
- 2015
- Full Text
- View/download PDF
43. A Combinatorial Algorithm for Minimizing the Maximum Laplacian Eigenvalue of Weighted Bipartite Graphs
- Author
-
Universidade Federal do Rio Grande do Sul, Helmberg, Christoph, Rocha, Israel, Schwerdtfeger, Uwe, Universidade Federal do Rio Grande do Sul, Helmberg, Christoph, Rocha, Israel, and Schwerdtfeger, Uwe
- Abstract
We give a strongly polynomial time combinatorial algorithm to minimise the largest eigenvalue of the weighted Laplacian of a bipartite graph. This is accomplished by solving the dual graph embedding problem which arises from a semidefinite programming formulation. In particular, the problem for trees can be solved in time cubic in the number of vertices.
- Published
- 2015
44. Embedding of Hypercube into Cylinder
- Author
-
Ji, Weixing, Liu, Qinghui, Wang, Guizhen, Shen, ZhuoJia, Ji, Weixing, Liu, Qinghui, Wang, Guizhen, and Shen, ZhuoJia
- Abstract
Task mapping in modern high performance parallel computers can be modeled as a graph embedding problem, which simulates the mapping as embedding one graph into another and try to find the minimum wirelength for the mapping. Though embedding problems have been considered for several regular graphs, such as hypercubes into grids, binary trees into grids, et al, it is still an open problem for hypercubes into cylinders. In this paper, we consider the problem of embedding hypercubes into cylinders to minimize the wirelength. We obtain the exact wirelength formula of embedding hypercube $Q^r$ into cylinder $C_{2^3}\times P_{2^{r-3}}$ with $r\ge3$., Comment: 11 pages, 2 figures
- Published
- 2015
45. Multiple Object Tracking through Background Learning.
- Author
-
Sharma, Deependra and Jaffery, Zainul Abdin
- Subjects
OBJECT tracking (Computer vision) ,IMAGE processing ,GRAPH theory ,DATA integrity ,BLOCK diagrams - Abstract
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]
- Published
- 2023
- Full Text
- View/download PDF
46. A Survey on Embedding Dynamic Graphs.
- Author
-
BARROS, CLAUDIO D. T., MENDONÇA, MATHEUS R. F., VIEIRA, ALEX B., and ZIVIANI, ARTUR
- Subjects
VECTOR spaces ,RANDOM walks ,POINT processes ,MATRIX decomposition ,FACTORIZATION - Abstract
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]
- Published
- 2023
- Full Text
- View/download PDF
47. ContE: contextualized knowledge graph embedding for circular relations.
- Author
-
Ma, Ting, Li, Mingming, Lv, Shangwen, Zhu, Fuqing, Huang, Longtao, and Hu, Songlin
- Subjects
KNOWLEDGE graphs ,QUESTION answering systems ,VECTOR spaces ,CIRCLE - Abstract
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]
- Published
- 2023
- Full Text
- View/download PDF
48. Embedding and the rotational dimension of a graph containing a clique.
- Author
-
Gomyou, Takumi
- Subjects
EIGENVALUES - Abstract
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]
- Published
- 2023
- Full Text
- View/download PDF
49. Attributed Graph Embedding Based on Attention with Cluster.
- Author
-
Wang, Bin, Chen, Yu, Sheng, Jinfang, and He, Zhengkun
- Subjects
MESSAGE passing (Computer science) ,MACHINE learning - Abstract
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]
- Published
- 2022
- Full Text
- View/download PDF
50. Discovery of urban functional regions based on Node2vec.
- Author
-
Cai, Li, Zhang, Lanqiuyue, Liang, Yu, and Li, Jin
- Subjects
LOCATION data ,URBAN land use ,URBAN growth ,SPACE ,SEMANTICS - Abstract
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]
- Published
- 2022
- Full Text
- View/download PDF
Catalog
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.