**Are you an EPFL student looking for a semester project?**

Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.

Concept# Graph embedding

Summary

In topological graph theory, an embedding (also spelled imbedding) of a graph G on a surface \Sigma is a representation of G on \Sigma in which points of \Sigma are associated with vertices and simple arcs (homeomorphic images of [0,1]) are associated with edges in such a way that:

- the endpoints of the arc associated with an edge e are the points associated with the end vertices of e,
- no arcs include points associated with other vertices,
- two arcs never intersect at a point which is interior to either of the arcs. Here a surface is a compact, connected 2-manifold.

Official source

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related publications

Loading

Related people

Loading

Related units

Loading

Related concepts

Loading

Related courses

Loading

Related lectures

Loading

Related publications (6)

Loading

Loading

Loading

Related people (2)

Related concepts (11)

Planar graph

In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it c

Graph theory

In mathematics, graph theory is the study of graphs, which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of vertices (also called no

Glossary of graph theory

This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges.
Symbols
A

Related units (1)

Information retrieval (IR) systems such as search engines are important for people to find what they need among the tremendous amount of data available in their organization or on the Internet. These IR systems enable users to search in a large data collection by specifying queries that describe their information needs. Traditionally, the data elements in these collections are text documents that have no explicit relationships between them. As conventional IR systems are designed to handle text documents, the queries are limited to multisets of textual keywords. However, with the advance of social media, the data collection has become heterogenous in terms of modality as it has become easier for users to share not only texts but also images, audios and videos. In addition, data collections have evolved to contain also the relationships between data elements. For instance, in social networks, the relationships between users are as important as the users themselves. Given these changes in the data collection, conventional bags of keywords queries become underwhelming as they are unimodal which cannot handle the heterogeneity the data elements. Moreover, they ignore the relationships between the query terms as they consider them to be independent. In this thesis, we show how to support context-rich queries both in terms of heterogeneity and interconnectivity by exploiting a common underlying graph model for the data collection. Our approach follows the vector space retrieval model where we design graph embedding techniques to represent each data element and each query as a vector i.e. an embedding. Our embedding model is designed to capture both the heterogeneity and the interconnectivity available in a data collection or a query in an elegant manner. As the data collection is usually large, this leads to a very large graph model which cannot be handled by traditional graph embedding techniques. In this thesis, we also propose an approach to make graph embedding scalable to large graphs.

Karl Aberer, Chi Thang Duong, Trung-Dung Hoang, Quoc Viet Hung Nguyen

Queries to detect isomorphic subgraphs are important in graph-based data management. While the problem of subgraph isomorphism search has received considerable attention for the static setting of a single query, or a batch thereof, existing approaches do not scale to a dynamic setting of a continuous stream of queries. In this paper, we address the scalability challenges induced by a stream of subgraph isomorphism queries by caching and re-use of previous results. We first present a novel subgraph index based on graph embeddings that serves as the foundation for efficient stream processing. It enables not only effective caching and re-use of results, but also speeds-up traditional algorithms for subgraph isomorphism in case of cache misses. Moreover, we propose cache management policies that incorporate notions of reusability of query results. Experiments using real-world datasets demonstrate the effectiveness of our approach in handling isomorphic subgraph search for streams of queries.

2020Related courses (1)

This course is a modern exposition of "Duke's Theorems" which describe the distribution of representations of large integers by a fixed ternary quadratic form. It will be the occasion to introduce the students to the adelic language, the theory of automorphic forms and their associated L-functions

, ,

Effective information retrieval (IR) relies on the ability to comprehensively capture a user's information needs. Traditional IR systems are limited to homogeneous queries that define the information to retrieve by a single modality. Support for heterogeneous queries that combine different modalities has been proposed recently. Yet, existing approaches for heterogeneous querying are computationally expensive, as they require several passes over the data to construct a query answer. In this paper, we propose an IR system that overcomes the computational challenges imposed by heterogeneous queries by adopting graph embeddings. Specifically, we propose graph-based models in which both, data and queries, incorporate information of different modalities. Then, we show how either representation is transformed into a graph embedding in the same space, capturing relations between information of different modalities. By grounding query processing in graph embeddings, we enable processing of heterogeneous queries with a single pass over the data representation. Our experiments on several real-world and synthetic datasets illustrate that our technique is able to return twice the amount of relevant information in comparison with several baselines, while being scalable to large-scale data.

Related lectures (2)