Generating Preview Tables for Entity Graphs

Ning Yan, Abolfazl Asudeh, Chengkai Li

Department of Computer Science and Engineering

The University of Texas at Arlington

<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
Users and developers are tapping into big, complex entity graphs for numerous applications. It is challenging to select entity graphs for a particular need, given abundant datasets from many sources and the oftentimes scarce information available for them.  We propose methods to automatically produce preview tables for entity graphs, for compact presentation of important entity types and relationships. The preview tables assist users in attaining a quick and rough preview of the data.  They can be shown in a limited display space for a user to browse and explore, before she decides to spend time and resources to fetch and investigate the complete dataset.
We formulate several optimization problems that look for previews with the highest scores according to intuitive goodness measures, under various constraints on preview size and distance between preview tables.  The optimization problem under distance constraint is -hard.  We design a dynamic-programming algorithm and an Apriori-style algorithm for finding optimal previews.  The experiments and user studies on Freebase demonstrated both the scoring measures' accuracy and the discovery algorithms' efficiency.

§ INTRODUCTION

We witness an unprecedented proliferation of big, complex entity graphs that capture entities and their relationships in many domains. For instance, in Fig. <ref>—a tiny excerpt of an entity graph, the edge labeled Actor between nodes Will Smith and Men in Black captures the fact that the person is an actor in the film.  Real-world entity graphs include knowledge bases (e.g., DBpedia [2], YAGO [11], Probase [13] and Freebase [3], which powers Google's knowledge graph), [<http://www.google.com/insidesearch/features/search/knowledge.html>] social graphs, biomedical databases, and program analysis graphs, to name just a few.  Users and developers are tapping into entity graphs for numerous applications such as search, recommendation systems, business intelligence and health informatics.

Entity graphs are often represented as RDF triples, due to heterogeneity of entities and the often lacking schema.  The Linking Open Data community has interlinked billions of RDF triples spanning over several hundred datasets. [<http://www.w3.org/wiki/LinkedData>]  Many other entity graph datasets are also available from data repositories such as Amazon's Public Data Sets, [<http://aws.amazon.com/publicdatasets/>] Data.gov [<http://www.data.gov/>] and NCBI's databases. [<http://www.ncbi.nlm.nih.gov/>]

An Excerpt of an Entity Graph.

It is challenging to select entity graphs for a particular need, given abundant datasets from many sources and the oftentimes scarce information available for them.  While sources such as the aforementioned data repositories often provide dataset descriptions, users cannot get a direct look at an entity graph before fetching it.  In this paper, we propose methods to automatically produce preview tables for entity graphs.  Given an entity graph with many types of entities and relationships, we generate a set of tables, each for an important entity type.  A table comprises a set of attributes, each of which corresponds to a relationship associated with the entity type.  A tuple in the table consists of an entity belonging to the entity type and its related entities for the table attributes.

Fig. <ref> is a possible preview of the entity graph in Fig. <ref>.  It consists of two preview tables—the upper table has attributes Film, Director and Genres, and the lower table has attributes Film Actor and Award Winners.  In this preview, entities of types Film and Film Actor are deemed of central importance in the entity graph.  Hence, Film and Film Actor are the key attributes of the two tables, respectively, marked by the underlines beneath them.  Attributes Director and Genres in the upper table are considered highly related to Film entities. Similarly, Award Winners in the lower table is highly related to Film Actor entities.  The two tables contain 4 and 2 tuples, respectively.  For instance, the first tuple of the upper table is $t_1=$ Men in BlackBarry Sonnenfeld{Action Film, Science Fiction}.  The tuple indicates that entity Men in Black belongs to type Film and has a relationship Director from Barry Sonnenfeld and has relationship Genres to both Action Film and Science Fiction. CL: (1) someone may wonder why Film Actor is not an attribute of Film and vice versa; (2) not a good idea to show complete table without missing values. want to emphasize the entities are heterogeneous.
Ning: thinking using mock up GUI as shown in Fig. <ref> to motivate efficient dynamic preview generation, we can say the users could selected a particular entity graph (domain), and during use of the GUI he can adjust the number of tables/attribute/distance

Film     Director     Genres

$t_1$     Men in Black     Barry Sonnenfeld     {Action Film, Science Fiction}

$t_2$     Men in Black II     Barry Sonnenfeld     {Action Film, Science Fiction}

$t_3$     Hancock     Peter Berg     -

$t_4$     I, Robot     Alex Proyas     {Action Film}

Film Actor     Award Winners

$t_5$     Will Smith     Saturn Award

$t_6$     Tommy Lee Jones     Academy Award

A 2-Table Preview of the Entity Graph in Fig. <ref>. (Upper and lower tables for subgraphs #1 and #2 in Fig. <ref>, respectively.)

The proposed preview tables are for compact presentation of important types of entities and their relationships in an entity graph.  They assist users in attaining a quick and rough preview of the schema of the data.  The tuples in the tables further give the users an intuitive understanding of the data. (Note that it is only necessary to show a few sample tuples instead of all.)  The preview tables can be shown in a limited display space for a user to browse and explore, before the user decides to spend more time and (monetary) resources to fetch and investigate the complete entity graph.

The Schema Graph for the Entity Graph in Fig. <ref>.

To this end, two other approaches are arguably less adequate for gaining a quick overview of a data graph.

(1) One solution is to show a schema graph corresponding to the data graph.  Fig. <ref> is the schema graph for the entity graph in Fig. <ref>.  While its definition is given in Sec. <ref>, we note that it is generated by merging same-type entity graph vertices (i.e., entities) and edges (i.e., relationships).  Although a schema graph is much smaller than the corresponding entity graph, it is not small enough for easy presentation and quick preview.  For instance, in a September 2012 snapshot of the “film” domain of Freebase, there are 190K vertices and 1.6M edges.  The corresponding schema graph consists of 50 entity types and 136 relationship types.

(2) Another approach is to present a summary of the schema graph, by schema summarization techniques [14, 15, 16, 12, 17]. Some of these methods [14, 15, 16] work on relational and semi-structured data, instead of graph data.
Some [16, 12, 17] produce trees or graphs as output instead of flat tables.

It is unclear how to apply these methods on an entity graph or its schema graph, due to differences in data models.

Although it is plausible that some of these approaches can be adapted for entity graphs, several reasons can render them ineffective. First, schema summary can still be quite large.  The most closely related work, [14, 15], clusters the tables in a database but does not reduce the number of tables or the complexity of database schema.  If we treat each entity type as a table and its neighboring entity types in the schema graph as the table attributes, the number of tables would equal the number of entity types.  For the aforementioned “film” domain in Freebase, it means the users would have to understand the result of clustering 50 tables.  Second, schema summarization is for helping database administrators and programmers in gaining a detailed understanding of a database in order to form queries.  Our goal is to assist users in attaining a quick and rough understanding of an entity graph, before they decide to grasp such a detailed understanding.  Therefore, our work can be viewed as an approach of finding a succinct representation of the schema graph (instead of clustering it). We are not aware of such an approach in previous studies.

In our definition (details in Sec. <ref>), a preview is a set of preview tables, each of which has a key attribute (corresponding to an entity type) and a set of non-key attributes (each corresponding to a relationship type).  Given an entity graph and its schema graph, there is thus a large space of possible previews.  Our goal is to find an “optimal” preview in the space.  To this end, we tackle several challenges:  (1) We discern what factors contribute to the goodness of a preview and propose several scoring functions for key and non-key attributes as well as preview tables. The scoring functions are based on several intuitions related to how much information a preview conveys and how helpful it is to users. (2) Based on the scoring measures, a preview's score is maximized when it includes as many tables and attributes as possible.  However, the purpose of having a preview is to help users attain a quick understanding of data and thus a preview must fit into a limited display space.  Considering the tradeoff, we enforce a constraint on preview size.  Furthermore, we consider enforcing an additional constraint on the pairwise distance between preview tables.  Given the spaces of all possible previews, we formulate the optimization problem of finding an preview with the highest score among those satisfying the constraints.  The optimization is non-trivial, as we prove that it is -hard under distance constraint.  (3) The search space of previews grows exponentially by data size and the constraints.  A brute-force approach is thus too costly.  For efficiently finding optimal previews, we designed a dynamic programming algorithm and an Apriori [1]-style algorithm.

In summary, this paper makes the following contributions:

* We motivated a novel concept of preview for entity graphs.

* We proposed ideas for measuring the goodness of previews based on several intuitions. (Sec. <ref>)

* We formulated optimal preview discovery problem, and proved its -hardness under distance constraint. (Sec. <ref>)

* We developed a dynamic-programming algorithm and an Apriori-style algorithm for finding optimal previews. (Sec. <ref>)

* Extensive experiments and user study verified the accuracy of the scoring measures, the efficiency of the algorithms, and the overall effectiveness of discovered previews. (Sec. <ref>)

§ PREVIEW DISCOVERY PROBLEM

An entity graph is a directed multigraph $G_d(V_d,E_d)$ with vertex set $V_d$ and edge set $E_d$.
Each vertex $v \in V_d$ represents an entity and each edge $e(v, v') \in E_d$ represents a directed relationship from entity $v$ to $v'$.
$G_d$ is a multigraph since there can be multiple edges between two vertices.
(E.g., in Fig. <ref>, there are two edges Actor and Executive Producer from entity Will Smith to entity I, Robot.)

$G_d(V_d,E_d)$     an entity graph

$v \in V_d$      an entity

$e(v, v') \in E_d$      a directed relationship from entity $v$ to entity $v'$

$G_s(V_s,E_s)$     a schema graph

$\tau \in V_s$     an entity type

$\gamma(\tau, \tau') \in E_s$     a relationship type from entity type $\tau$ to entity type $\tau'$

$T$     a preview table

$T.key$     the key attribute of $T$

$T.nonkey$     the non-key attributes of $T$

$T.\tau$     the set of entities of type $\tau$, which is the key attribute of $T$

$t \in T$     a tuple $t$ in preview table $T$

$t.\tau$     $t$'s value on $\tau$ which is the key attribute of $T$

$t.\gamma$     $t$'s value on non-key attribute $\gamma$

$\mathcal{P} = \{\mathcal{P}[1], ..., \mathcal{P}[k]\}$     a preview, which consists of $k$ preview tables

$\mathcal{P}_{opt}$     an optimal preview

$S(\mathcal{P})$     the score of preview $\mathcal{P}$

$S(T)$     the score of preview table $T$

$S_{cov}(\tau)$, $S_{walk}(\tau)$     score of key attribute $\tau$ based on coverage and random walk

$S^{\tau}_{cov}(\gamma)$, $S^{\tau}_{ent}(\gamma)$      score of non-key attribute $\gamma$ based on coverage and entropy

$\mathbb{T}$     the space of all possible preview tables

$\mathbb{P}$     the space of all possible previews

$dist(\tau, \tau')$     distance between $\tau$ and $\tau'$ in schema graph $G_s$

Each entity is labeled by a name.  For simplicity and intuitiveness of presentation, we shall mention entities by their names, assuming all entities have distinct names, although in reality they are distinguished by unique identifiers.  Each entity belongs to one or more entity types, underlined in Fig. <ref>.  (E.g., Will Smith belongs to types Film Actor and File Producer and I, Robot belongs to type Film.)  Each relationship belongs to a relationship type. (E.g., the edge from Will Smith to Men in Black has type Actor.)  The type of a relationship determines the types of its two end entities.  For instance, an edge of type Actor is always from an entity belonging to File Actor to an entity belonging to Film.  We will mention edges by the surface names of their relationship types.  Two different relationship types may have the same surface name for intuitively expressing their meanings, although underlyingly they have different identifiers.  For instance, the Award Winners edge from Will Smith to Saturn Award and the Award Winners edge from Barry Sonnenfeld to Razzie Award belong to two different relationship types.  The former is for relationships from Film Actor to Award, while the latter is for relationships from Film Director to Award.

Given an entity graph $G_d(V_d,E_d)$, its schema graph is a directed graph $G_s(V_s,E_s)$,
where each vertex $\tau \in V_s$ represents an entity type and each directed edge
$\gamma(\tau, \tau') \in E_s$ represents a relationship type from entity type $\tau$ to $\tau'$.
An edge $\gamma(\tau, \tau') \in E_s$ if and only if there exists an edge $e(v, v') \in E_d$
where $e$ has type $\gamma$, $v$ has type $\tau$ and $v'$ has type $\tau'$.
Fig. <ref> shows the schema graph corresponding to the entity graph in Fig. <ref>.
A schema graph is a multigraph as there can be multiple relationship types between two entity types.
(E.g., two relationship types—Producer and Executive Producer—are from entity type Film Producer to Film.)
It is clear from the above definitions that, given a data graph, the corresponding schema graph is uniquely determined.

Given an entity graph $G_d(V_d,E_d)$ and its schema graph $G_s(V_s,E_s)$,
a preview table $T$ has a mandatory key attribute (denoted $T.key$)
and at least one non-key attributes (denoted $T.nonkey$).
$T$ corresponds to a star-shape subgraph of the schema graph $G_s(V_s,E_s)$.
The key attribute corresponds to an entity type $\tau \in V_s$, and each non-key attribute
corresponds to a relationship type $\gamma(\tau, \tau') \in E_s$ or $\gamma(\tau', \tau) \in E_s$.
Note that the edges from and to an entity are both important.
Hence, a non-key attribute corresponds to either $\gamma(\tau, \tau')$ or $\gamma(\tau', \tau)$.

The preview table $T$ consists of a set of tuples.
The number of tuples equals the number of entities of type $\tau$ (the key attribute of $T$),
i.e., $|T| = |T.\tau|$ and $T.\tau = \{v|v \in V_d \wedge v \text{ has type } \tau\}$.
Given an arbitrary tuple $t \in T$, we denote $t$'s key attribute value by $t.\tau$.
Each tuple $t$ attains a distinct value of $t.\tau$.
Its value on a non-key attribute $\gamma(\tau, \tau')$, denoted $t.\gamma(\tau, \tau')$ or simply $t.\gamma$,
is a set—the set of entities in entity graph $G_d$ incident from $t.\tau$ through an
edge of type $\gamma(\tau, \tau')$.
More formally, $t.\gamma(\tau, \tau') = \{u| u \in V_d \wedge e(t.\tau,u) \in E_d \wedge u \text{ belongs to type } \tau'\}$.
Symmetrically, its value on a non-key attribute $\gamma(\tau', \tau)$ is the set of entities in $G_d$ incident to $t.\tau$ through an edge of type $\gamma(\tau', \tau)$,
i.e., $t.\gamma(\tau', \tau) = \{u| u \in V_d \wedge e(u,t.\tau) \in E_d \wedge u \text{ belongs to type } \tau'\}$.

A preview $\mathcal{P}$ is a set of preview tables, i.e., $\mathcal{P}=\{\mathcal{P}[1], ..., \mathcal{P}[k]\}$,
where $\forall i\neq j, \mathcal{P}[i].key \neq \mathcal{P}[j].key$,
$k \leqslant |V_s|$ is the total number of preview tables.
Note that $|V_s|$ is the number of vertices in $G_s$, i.e., the number of entity types in $G_d$.

According to Definition <ref>, the upper and lower tables in Fig. <ref> correspond to the star-shape subgraphs #1 and #2 in Fig. <ref>, respectively.
The key attribute in the upper table is Film and the non-key attributes are Director and Genres.
The key attribute in the lower table is Film Actor and its non-key attribute is Award Winners. Due to the aforementioned symmetric relation, if there exists a preview table with key attribute Director, it may have Film as one of its non-key attributes.
It is worth noting that, although each tuple's value on the key attribute is non-empty, unique and single-valued, its value on a non-key attribute can be empty (e.g., $t_3.\edge{Genres}$ in Fig. <ref>), duplicate
(e.g., $t_1.\edge{Director}$ and $t_2.\edge{Director}$ in Fig. <ref>) and multi-valued (e.g., $t_1.\edge{Genres}$ and $t_2.\edge{Genres}$ in Fig. <ref>).  It also follows that a preview table is not a relational table.

CL: need more examples for the above concepts in Definition.

By Definition <ref>, every vertex $\tau$ in a schema graph can serve as the key attribute of a candidate preview table, which also includes at least one non-key attribute—an edge incident on $\tau$.  We use $\mathbb{T}$ to denote the space of all possible preview tables.  A preview is a set of preview tables.  We use $\mathbb{P}$ to denote the space of all possible previews.  Note that $\mathbb{P} \subset 2^\mathbb{T}$, i.e., not every member of the power set $2^\mathbb{T}$ is a valid preview, because by Definition <ref> preview tables in a preview cannot have the same key attribute.

Problem Statement: Given an entity graph $G_d(V_d,E_d)$ and its corresponding schema graph $G_s(V_s,E_s)$, the preview discovery problem is to find $\mathcal{P}_{opt}$—the optimal preview among all possible previews.
We shall develop the notion of goodness for a preview and define its measures in Sec. <ref>.

Note that the preview discovery problem focuses on selecting key and non-key
attributes for preview tables.  It does not select tuples.
As our goal is to help users attain a good initial understanding of the
schema of an entity graph, it is only necessary to show a small number of tuples
instead of all.  Our current approach is to randomly select a few.
How to define representativeness of tuples and choose the most
representative tuples is left for future work.

§ SCORING MEASURES FOR PREVIEWS

In this section, we discuss the scoring functions for measuring the
goodness of previews for entity graphs.  The measures are based on
the intuition that a good preview should 1) relate to as many entities
and relationships as possible and 2) help users understand an entity
graph and its schema graph.  The first intuition is obvious, as a
preview relating to only a small number of entities or relationships will
inevitably lose lots of information and thus lead to poor comprehensibility
of the original graph.  The second intuition models the goodness of previews
according to users' behavior in browsing entity and schema graphs.

CL: the intuitions are unclear.

§.§ Preview Scoring

The score of a preview $\mathcal{P}=\{\mathcal{P}[1], ..., \mathcal{P}[k]\}$
is simply aggregated from individual preview tables' scores, by summation:

\begin{equation}\label{eq:preview-score}
S(\mathcal{P}) = \sum_{i=1}^{k} S(\mathcal{P}[i]),
\end{equation}

where $S(\mathcal{P}[i])$ is the score of a preview table $\mathcal{P}[i]$, defined as:

\begin{equation}\label{eq:table-score}
S(\mathcal{P}[i]) = S(\tau) \times \!\!\!\!\! \sum_{\gamma \in \mathcal{P}[i].nonkey} \!\!\!\!\!\!\!\!\!\! S^{\tau}(\gamma),
\end{equation}

where $S(\tau)$ is the score of the key attribute of $\mathcal{P}[i]$ (i.e., $\mathcal{P}[i].key$=$\tau$)
and $S^{\tau}(\gamma)$ is the score of a non-key attribute $\gamma$ in $\mathcal{P}[i]$.
$S(\tau)$ and $S^{\tau}(\gamma)$ are defined and elaborated in
Sec. <ref> and Sec. <ref>.

In the above definition, the score of a preview table equals the product of its key attribute's score and the summation of its non-key attributes' scores.  The definition gives the key attribute $\tau$ much higher importance than any individual non-key attribute, because the preview table centers around the entities of type $\tau$ and describes their non-key attributes, i.e., their relationships with other entities.

It is possible to propose many viable scoring measures for key and non-key attributes.
Furthermore, techniques such as learning-to-rank [8]
can be applied in ranking previews by features related to key
and non-key attributes, although the feasibility of collecting many labelled
data is less clear in this case.  We leave it to the future work to explore this direction.

§.§ Key Attribute Scoring

Coverage-based scoring measure:

Given an entity graph $G_d(V_d,E_d)$ and its corresponding schema graph $G_s(V_s,E_s)$, the key attribute $\tau$ of a candidate preview table $T$ corresponds to an entity type, i.e., $\tau \in V_s$.  If the entity graph consists of many entities of type $\tau$, including $T$ in the preview makes the preview relevant to all those entities.  The coverage-based scoring measure thus defines the score of $\tau$ as the number of entities bearing that type:

S_{cov}(\tau) = |\{v| v \in V_d \wedge v \text{ has type } \tau\}|

For example, given the entity graph in Fig. <ref> and the corresponding schema graph in Fig. <ref>, the coverage-based score of the key attribute Film is $S_{cov}(\etype{Film})=4$.

Random-walk based scoring measure:

We consider a random-walk process over a graph $G$ converted from the schema graph $G_s(V_s,E_s)$, inspired by the PageRank algorithm [4] for Web page ranking. In $G$, the vertices are entity types and the edges are undirected.  The edge between $\tau_i$ and $\tau_j$ in $G$ is weighted by the number of relationships (i.e., the number of edges) in the entity graph between entities of types $\tau_i$ and $\tau_j$.  We denote the weight by $w_{ij}$, defined as follows.

\begin{align*}
w_{ij} = w_{ji} &= \!\! \sum_{\gamma(\tau_i,\tau_j)\in E_s} \!\!\!\!\! |\{e| e \in E_d \wedge e \text{ has type } \gamma(\tau_i,\tau_j)\}| \\
&+ \!\! \sum_{\gamma(\tau_j,\tau_i)\in E_s} \!\!\!\!\! |\{e| e \in E_d \wedge e \text{ has type } \gamma(\tau_j,\tau_i)\}|
\end{align*}

The transition matrix $M$ is a $|V_s| \times |V_s|$ matrix where an element $M_{ij}$ corresponds to the transition probability from $\tau_i$ to $\tau_j$ in $G$.  $M_{ij}$ equals the ratio of $w_{ij}$ to the total weight of all edges incident on $\tau_i$ in $G$:

M_{ij} = w_{ij} / \sum_{k} w_{ik}

For example, the transition probability from Film to Film Genre is $M_{\etypesmall{Film}, \etypesmall{Film Genre}}$ = $w_{\etypesmall{Film},\etypesmall{Film Genre}} / (w_{\etypesmall{Film},\etypesmall{Film Genre}}$ + $w_{\etypesmall{Film},\etypesmall{Film Actor}}$ + $w_{\etypesmall{Film},\etypesmall{Film Director}}$ + $w_{\etypesmall{Film},\etypesmall{Film Producer}})$ = $5/(5+6+4+3)$ = $0.28$.  The transition probability from Film to Film Producer is $M_{\etypesmall{Film}, \etypesmall{Film Producer}}$ = $w_{\etypesmall{Film},\etypesmall{Film Producer}} / (w_{\etypesmall{Film},\etypesmall{Film Genre}}$ + $w_{\etypesmall{Film},\etypesmall{Film Actor}}$ + $w_{\etypesmall{Film},\etypesmall{Film Director}}$ + $w_{\etypesmall{Film},\etypesmall{Film Producer}})$ = $3/(5+6+4+3)$ = $0.17$.

Suppose a user traverses in $G$, either by going from an entity type $\tau_i$ to another entity type $\tau_j$ through the edge between them with probability $M_{ij}$ or by jumping to a random entity type.  Entity types that are more likely to be visited by the user are of higher importance.  The random walk process will converge to a stationary distribution which represents the chances of entity types being visited.  The stationary distribution $\pi$ of the random walk process is given as follows.  Note that a similar idea was applied in [14] for ranking relational tables by importance.

\pi = \pi M

The random-walk based score of a candidate key attribute $\tau_i$ is:

S_{walk}(\tau_i) = \pi_i, \text{where } \pi_i \text{ is the stationary probability of } \tau_i.

CL: The equations do not discuss damping factor (jumping to random node).

§.§ Non-Key Attribute Scoring

Coverage-based scoring measure:

The coverage-based scoring measure for non-key attribute is similar to that for key attribute.  Given an entity graph $G_d(V_d,E_d)$ and its schema graph $G_s(V_s,E_s)$, consider a candidate preview table $T$ with key attribute $\tau$.  A non-key attribute $\gamma$ of $T$ corresponds to a relationship type, i.e., $\gamma \in E_s$.  If the entity graph contains many edges (i.e., relationships) belonging to the type $\gamma$, incorporating such a relationship type into the table $T$ makes it relevant to all those relationships and their corresponding entities.  The coverage-based scoring measure thus defines the score of $\gamma$ as the number of relationships bearing that type:

S^{\tau}_{cov}(\gamma) = |\{e| e \in E_d \wedge e \text{ has type } \gamma\}|

For example, given the entity graph in Fig. <ref> and the schema graph in Fig. <ref>, the coverage-based scores of non-key attributes Director and Genres are $S^{\etype{Film}}_{cov}(\edge{Director})=4$ and $S^{\etype{Film}}_{cov}(\edge{Genres})=5$.

The coverage-based scoring measure for non-key attribute is symmetric, i.e., given $\gamma(\tau, \tau')$ (or $\gamma(\tau', \tau)$) $\in$ $T.nonkey$, $S^{\tau}_{cov}(\gamma) \equiv S^{\tau'}_{cov}(\gamma)$.  Both $\tau$ and $\tau'$ can be the key attribute of a different preview table, in which $\gamma$ is a non-key attribute.  The scores of $\gamma$ in the two tables are equal.

Entropy-based scoring measure:

For a preview table $T$ with key attribute $\tau$, we measure the goodness of a non-key attribute $\gamma(\tau, \tau')$ (or $\gamma(\tau', \tau)$) by how much information it provides to $T$, for which the entropy of $\gamma$ ($H(\gamma)$) is a natural choice of measure:

S^{\tau}_{ent}(\gamma) = H(\gamma) = \sum_{j=1} \frac{n_j}{|t.\gamma|} \log(\frac{|t.\gamma|}{n_j}),

where $n_j$ is the number of tuples in $T$ that attain the same $j$th attribute value $u$ on
non-key attribute $\gamma(\tau, \tau')$ (or $\gamma(\tau', \tau)$), i.e.,
$u \in V_d \wedge u \text{ has type } \tau'$ and $n_j = |\{ v | v \in T.\tau \wedge e(v,u) \in E_d \text{ (or } e(u,v) \in E_d \text{)} \wedge e \text{ has type } \gamma \}|$.
$|t.\gamma|$ is the number of tuples in $T$ with non-empty values on $\gamma(\tau, \tau')$ (or $\gamma(\tau', \tau)$).
Continue with the example above, the entropy-based scores of non-key attributes Director and Genres are $S^{\etype{Film}}_{ent}(\edge{Director})=(2/4)\log(4/2)+(1/4)\log(4/1)+(1/4)\log(4/1)=0.45$, and $S^{\etype{Film}}_{ent}(\edge{Genres})=(2/3)\log(3/2)+(1/3)\log(3/1)=0.28$.
Note that for two values on a multi-valued attribute (e.g., {Action Film, Science Fiction} and {Action Film} for Film.Genres in Fig. <ref>), we consider them equivalent if and only if they have the same set of component values.CL: (1) The equation is different from your implementation. Please make them consistent by changing either the equation or implementation.  (2) should $|T|$ be replaced by the number of tuples with not-null value on $\gamma$?
By definition, the entropy-based scoring measure for non-key attribute is asymmetric, i.e., given $\gamma(\tau, \tau')$ (or $\gamma(\tau', \tau)$) $\in$ $T.nonkey$, $S^{\tau}_{ent}(\gamma) \not\equiv S^{\tau'}_{ent}(\gamma)$.

Navigation-cost based scoring measure:

Our third scoring measure for non-key attribute is based on a user effort model <cit.>, in which we assume a user browses through non-key attribute values to find a tuple in table $T$ whose value on the key attribute is $v$. For example, in Table <ref> a user may use Director attribute value Barry Sonnenfeld to find $t_1$ whose value on key attribute Film is Men in Black.  During this navigation process the user efforts are two folds—selecting a value from all distinct values of a non-key attribute, and selecting a target entity from all distinct entities on the key attribute such that the entity bears the chosen non-key attribute value.  The scoring measure combines the costs of these two efforts by summation.  Consider a preview table $T$ with key attribute $\tau$.  To define the score of non-key attribute $\gamma(\tau, \tau')$,[The score of $\gamma(\tau', \tau)$ is similarly defined.] we use $C_{\gamma}$ to denote the number of distinct values on $\gamma$ and $C_{\tau=v \wedge \tau'=u}$ to denote the number of distinct target entities $v$ (of type $\tau$) that have value $u$ on $\gamma$.  In other words, $C_\gamma = |\{ u | e(v,u) \in E_d \wedge e \text{ has type } \gamma(\tau, \tau') \}|$ and $C_{\tau=v \wedge \tau'=u} = |\{ v | v \in T.\tau \wedge e(v,u) \in E_d \wedge e \text{ has type } \gamma(\tau, \tau') \}|$.

The score of $\gamma$, with regard to $\tau$, is the total number of distinct entities a user needs to look at in average.  The scoring measure is thus given by the following equation:CL:several problems with the equation: (1) penalty undefined; (3) should also aggregate over different $v$ values.

S^{\tau}_{nav}(\gamma(\tau, \tau')) =-\frac
{\sum_{v \text{ has type } \tau}(C_{\gamma}+C_{\tau=v \wedge \tau'=u})}
{S(\tau)} + \rho_{penalty}

The navigation-cost based scoring measure for non-key attribute is asymmetric, i.e., given $\gamma(\tau, \tau')$ (or $\gamma(\tau', \tau)$) $\in$ $T.nonkey$, $S^{\tau}_{nav}(\gamma)$ $\not\equiv$ $S^{\tau'}_{nav}(\gamma)$.

CL: We need examples for the last two measures for non-key attributes.

§ OPTIMAL PREVIEWS UNDER SIZE AND DISTANCE CONSTRAINTS

CL: We need examples for the optimal preview problem.

In this section, based on the scoring measures defined in Sec. <ref>, we formulate several optimization problems that look for the optimal previews with best scores under various constraints on preview size and distance between preview tables.  We prove that some of these optimization problems are -hard.

By Eq. <ref> (or any other monotonic aggregate function), the score of a preview monotonically increases by its member preview tables—the more preview tables in a preview, the higher its score.  Similarly by Eq. <ref>, the score of a preview table monotonically increases by its non-key attributes.  The properties are formally stated in the following two propositions.  Recall that $\mathbb{P}$ and $\mathbb{T}$ denote the space of all possible previews and all possible preview tables.

Given previews $\mathcal{P}_1, \mathcal{P}_2 \in \mathbb{P}$, if $\mathcal{P}_1 \supseteq \mathcal{P}_2$, then $S(\mathcal{P}_1)\geq S(\mathcal{P}_2)$.

Given preview tables $T_1, T_2 \in \mathbb{T}$, if $T_1.key = T_2.key$ and $T_1.nonkey \supseteq T_2.nonkey$, then $S(T_1)\geq S(T_2)$.

By the above propositions, a preview's score is maximized when it includes as many tables and attributes as possible.
However, the purpose of having a preview is to help users attain a quick understanding of data and thus a preview must fit into a limited display space.
Therefore the size and the goodness score of a preview present a tradeoff.
Considering the tradeoff, we enforce a constraint on preview size, given by a pair of integers $(k,n)$,
where $k$ is the number of allowed preview tables and $n$ is the number of allowed
non-key attributes in the tables.
The previews satisfying the size constraint are called concise previews.

Furthermore, we consider enforcing an additional constraint on the
pairwise distance between preview tables.  The distance between two
preview tables $T_1$ and $T_2$ (denoted $dist(T_1, T_2)$) is the length
of the shortest undirected path[An undirected path in a
directed graph is a path in which the edges are not all oriented in the
same direction.] between their key attributes $T_1.key$ and $T_2.key$ in
schema graph $G_s$.  (Recall that the key attributes are vertices
(i.e., entity types) in $G_s$.)  For example, the distance between the
two tables in Fig. <ref> is $1$, which is the shortest path
length between Film and Film Actor in the schema graph in
Fig. <ref>.  Similarly, for two tables whose key attributes
are Film and Award, their distance would be $2$.

Based on the above notion of distance, the constraint on table distance is given by an integer $d$, which is the maximum (minimum) distance between preview tables.  The previews satisfying the distance constraint are called tight (diverse) previews.  Intuitively speaking, the preview tables in a tight preview are highly related to each other due to their short pairwise distance, while the preview tables in a diverse preview are not tightly related to each other and cover different types of concepts.  Arguably, both types of previews are useful for understanding an entity graph.  We shall compare them empirically in Sec. <ref>.

Given the spaces of all possible concise, tight and diverse previews, we
formulate three optimization problems—finding an
optimal preview with the highest score in the
corresponding space of previews.  Below we formally define the three types
of previews and the corresponding optimization problems.
Note that we assume the constraints $k,n,d$ are given.
While it is intuitive for a user to specify desired values for these
constraints, it is helpful if a system can automatically suggest
values.  We leave it to the future work.

Given the size constraint $(k,n)$, a concise preview has $k$ preview tables (i.e., key attributes) and no more than $n$ non-key attributes in the tables. [A preview with less than $n$ non-key attributes may outscore another preview with exactly $n$ non-key attributes. Further, a set of $k$ entity types may have only less than $n$ edges in the schema graph. Hence, the condition $|\mathcal{P}[i].nonkey| \leq n$ instead of $|\mathcal{P}[i].nonkey| = n$.  On the other hand, it is safe to assume that an entity graph with practical significance always has more than $k$ entity types under any reasonably small $k$.  Therefore an optimal preview always should have exactly $k$ preview tables, given the monotonic scoring function (cf. Eq. <ref>).] The space of all concise previews is

\begin{equation}
\mathbb{P}_{k,n} = \{ \mathcal{P}\ \big|\ \mathcal{P}\in \mathbb{P}, |\mathcal{P}| = k, \sum_{i=1}^{k} |\mathcal{P}[i].nonkey| \leq n\}.\nonumber
\end{equation}

Given the size constraint $(k,n)$ and the distance constraint $d$, a tight preview (diverse preview) is a concise preview in which the distance between any pair of preview tables is smaller (greater) than or equal to $d$.   The space of all tight previews is

\begin{equation}
\mathbb{P}_{k,n,\leq d} = \{ \mathcal{P}\ \big|\ \mathcal{P}\in \mathbb{P}_{k,n}, \forall T_1, T_2 \in \mathcal{P}, dist(T_1,T_2) \leq d\}.\nonumber
\end{equation}

The space of all diverse previews is

\begin{equation}
\mathbb{P}_{k,n,\geq d} = \{ \mathcal{P}\ \big|\ \mathcal{P}\in \mathbb{P}_{k,n}, \forall T_1, T_2 \in \mathcal{P}, dist(T_1,T_2) \geq d\}.\nonumber \qed
\end{equation}

The optimization problem of finding an optimal preview is defined
as follows, where $\mathbb{P}$ can be any of the aforementioned three
spaces—$\mathbb{P}_{k,n}$, $\mathbb{P}_{k,n,\leq d}$ and $\mathbb{P}_{k,n,\geq d}$.

\begin{equation}\label{eq:opt}
\mathcal{P}_{opt} \in \argmax_{\mathcal{P}\in \mathbb{P}} S(\mathcal{P})
\end{equation}

Note that the $\argmax$ function may return a set of optimal previews
due to ties in scores.

For example, given the entity graph in Fig. <ref>, using
coverage-based scoring measures for both key and non-key attributes, an
optimal concise preview consisting of 2 tables and 6 non-key
attributes (i.e., $k$=$2$, $n$=$6$) is $\mathcal{P}=\{T_1:\etype{Film}, \edge{Actor}, \edge{Genres}, \edge{Director}, $ $ \edge{Producer}$; $T_2:\etype{Film Actor}, \edge{Actor}, \edge{Award Winners}\}$.
The edge Actor is a non-key attribute in both $T_1$ and $T_2$, in different directions.
An optimal diverse preview under the same size constraint ($k$=$2$, $n$=$6$) and distance constraint $d$=$2$
is $\mathcal{P}=\{T_1:\etype{Film}, \edge{Actor}, \edge{Genres}, \edge{Director},$ $\edge{Producer}, \edge{Executive Producer}; T_2:\etype{Award}, \edge{Award Winners}\}$.

The optimal preview discovery problem is non-trivial.
Particularly, the problem in the spaces of both tight previews ($\mathbb{P}_{k,n,\leq d}$) and diverse previews ($\mathbb{P}_{k,n,\geq d}$) is -hard.

The optimal tight preview discovery problem is -hard.

The decision version of the optimal tight preview discovery problem is $\mathit{TightPreview}(G_s,k,n,d,s)$—Given a schema graph $G_s$, decide whether there exists such a preview $\mathcal{P}$ that (1) $\mathcal{P}$ has $k$ tables and no more than $n$ non-key attributes; (2) the distance between every pair of preview tables is not greater than $d$; and (3) the preview's score is at least $s$, i.e., $S(\mathcal{P}) \geq s$.

We construct a reduction, in polynomial-time, from the -hard Clique problem to $\mathit{TightPreview}(G_s,k,n,d,s)$.  Recall that the decision version of $\mathit{Clique}(G,k)$ is to, given a graph $G(V, E)$, decide whether there exists a clique in $G$ with $k$ vertices.  The reduction is by constructing a schema graph $G_s$ from $G$.  For simplicity of exposition, in both this proof and the proof of Theorem <ref>, we assume the schema graph $G_s$ is undirected and every edge $\gamma$ in $G_s$ corresponds to the same relationship type.  This assumption is made without loss of generality.  Note that our following proof casts no requirement on the score of a preview (i.e., $s=0$) and thus no requirement on the scores of key and non-key attributes in $G_s$.  Hence, edge orientation and its corresponding relationship type bears no significance in the proof. CL:  the paper may become more clear if the assumption on undirected graph is made early on, even in Section 2

Formally, we construct a schema graph $G_s(V_s$, $E_s)$ from $G$ through a vertex bijection $f : V \rightarrow V_s$:

* $\forall e(v,v') \in E$, there exists an edge (i.e., relationship type) $\gamma(\tau,\tau')$ $\in$ $E_s$, where $\tau=f(v)$ and $\tau'=f(v')$.

* $\forall \gamma(\tau,\tau') \in E_s$, there exists an edge $e(v,v') \in E$, where $v=f^{-1}(\tau)$ and $v'=f^{-1}(\tau')$.

$Clique(G, k)$ is thus reduced to $\mathit{TightPreview}(G_s,k,k,1,0)$ by the above bijections.

The -hardness of the optimal diverse preview discovery problem is also based on a reduction from the Clique problem, although the proof is more complex.

The optimal diverse preview discovery problem is -hard.

The decision version of the optimal diverse preview discovery problem is $\mathit{DiversePreview}(G_s,k,n,d,s)$—Given a schema graph $G_s$, decide whether there exists such a preview $\mathcal{P}$ that (1) $\mathcal{P}$ has $k$ tables and no more than $n$ non-key attributes; (2) the distance between every pair of preview tables is not smaller than $d$; and (3) the preview's score is at least $s$, i.e., $S(\mathcal{P}) \geq s$.

We construct a reduction, in polynomial-time, from the -hard $\mathit{Clique}(G,k)$ to $\mathit{DiversePreview}(G_s,k,n,d,s)$.  The reduction is also by constructing a schema graph $G_s($$V_s$, $E_s)$ from $G$.  It is similar to the reduction for $\mathit{TightPreview}(G_s,k,n,d,s)$ in Theorem <ref>, but also bears two important differences.  (1) $G_s$ contains a special vertex, denoted $\tau_0$, that is directly connected to every other vertex in $G_s$.  (2) Barring $\tau_0$ and all its incident edges, $G_s$ is the complement graph of $G$—There is still a vertex bijection $f : V \rightarrow V_s$, but an edge exists between two vertices in $G_s$ if and only if there is no edge between the corresponding vertices in $G$.
Formally, the construction of $G_s$ from $G$ is as follows:

* $\forall \tau, \tau' \in V_s \backslash \{\tau_0\}$, $\gamma(\tau,\tau') \in E_s$  if and only if $\nexists e(v,v') \in E$, where $v=f^{-1}(\tau)$ and $v'=f^{-1}(\tau')$.

* $\forall \tau \in V_s \backslash \{\tau_0\}$, $\gamma(\tau_0,\tau) \in E_s$.

$Clique(G, k)$ is thus reduced to $\mathit{DiversePreview}(G_s,k,k,2,0)$ by the above construction of $G_s$.

Construction of $G_s$ from $G$, for Reduction from the Clique Problem to the Optimal Diverse Preview Discovery Problem.

Fig. <ref> can help understand the reduction from $Clique(G, k)$ to $\mathit{DiversePreview}$ $(G_s,k,k,2,0)$ in the above proof.
The figure shows an example with $G$ (left) and the constructed schema graph $G_s$ (right), where the gray vertex in $G_s$ is $\tau_0$.  Consider an arbitrary pair of vertices ($v, v'$) in $G$ and their corresponding vertices ($\tau, \tau'$) in $G_s$.  On the one hand, if $v$ and $v'$ are not directly connected in $G$ (e.g., $v_1$ and $v_6$), an edge between $\tau$ and $\tau'$ (i.e., $\tau_1$ and $\tau_6$) is included into $G_s$.  When finding a diverse preview where pairwise table distance must be at least $2$, $\tau$ and $\tau'$ will never be chosen together as the key attributes of two tables in the preview.  Correspondingly, this means a clique must not include both $v$ and $v'$.  On the other hand, if $v$ and $v'$ are directly connected in $G$ (e.g., $v_1$ and $v_2$), there must not be a direct edge between $\tau$ and $\tau'$ (i.e., $\tau_1$ and $\tau_2$) in $G_s$.  The distance between $\tau$ and $\tau'$ is exactly $2$, since they are only indirectly connected through $\tau_0$.  They will thus be considered in choosing the key attributes of two tables in a diverse preview where pairwise table distance must be at least $2$.  Correspondingly, the directly connected $v$ and $v'$ are considered together in forming a clique.

§ ALGORITHMS

CL: In general,  we lack examples in this paper, including examples for explaining algorithms.

In this section we discuss algorithms for solving the optimal preview discovery problem.  As given in Eq. <ref>, the problem is to find a preview with the highest score among candidate previews, where the space of candidates can be concise previews ($\mathbb{P}_{k,n}$), tight previews ($\mathbb{P}_{k,n,\leq d}$) or diverse previews ($\mathbb{P}_{k,n,\geq d}$).   Recall that we use $S(\tau)$ to denote the score of a candidate key attribute $\tau$ for a preview table $T$ and $S^{\tau}(\gamma)$ to denote the score of a candidate non-key attribute $\gamma(\tau, \tau')$ (or $\gamma(\tau', \tau)$) for $T$ whose key attribute is $\tau$.

Our effort focuses on reducing the cost in finding optimal previews.
Both the schema graph and the scoring measures defined in Sec. <ref>
are computed before optimal preview discovery.
This is a realistic assumption, since
the schema graph and scoring measures do not change by the size and distance
constraints $k,n,d$.  Furthermore, they can be incrementally updated
when the underlying entity graph is updated (details omitted).
On the other hand, the optimal previews cannot be incrementally updated.

Before we present the algorithms, consider the space of all possible previews.
Every entity type $\tau$ can be the key attribute of a preview table $T$.
Let $\Gamma^{\tau}$ denote the set of all edges (i.e., relationship types) incident on $\tau$ in schema graph $G_s$.  Any $\gamma \in \Gamma^{\tau}$ can be a candidate for the non-key attributes of $T$.  By the scoring function in Eq. <ref> and the problem formulation in Eq. <ref>, the non-key attributes of $T$ must have the highest scores among the candidates in $\Gamma^{\tau}$.
This property, stated in Theorem <ref>, is important to our algorithms.

Suppose an optimal (concise, tight or diverse) preview $\mathcal{P}_{opt}$ contains a preview table $T \in \mathbb{T}$ with key attribute $\tau$.  If $T$ has $m$ non-key attributes, they must be the top-$m$ non-key attributes by scores, i.e., $\forall \gamma, \gamma' \in \Gamma^{\tau}$, if $\gamma \in T.nonkey$ and $\gamma' \notin T.nonkey$, then $S^{\tau}(\gamma) \geq S^{\tau}(\gamma)$.

§.§ A Brute-Force Algorithm

Alg. <ref> is a brute-force algorithm for the optimal preview discovery problem.  It enumerates all possible $k$-subsets of entity types, as the $k$ entity types in each subset form the key attributes of $k$ preview tables in a preview $\mathcal{P}$ (Line <ref>).  For a candidate key attribute $\tau$, the elements in the set of its candidate non-key attributes $\Gamma^{\tau}$ are ordered by their scores.  We denote these candidates in descending order of scores by
$\gamma^{\tau}_1$, $\gamma^{\tau}_2$, and so on (Line <ref>).  Suppose preview table $T$ uses $\tau$ as its key attribute. Each table must contain at least one non-key attribute, according to Definition <ref>.  Hence, $\gamma^{\tau}_1$ (i.e., the candidate non-key attribute with the highest score) must be included into $T.nonkey$ (Line <ref>), by Theorem <ref>.  Further, among the remaining candidate non-key attributes for the $k$ entity types, the top-($n$$-$$k$) candidates by scores must be included into $\mathcal{P}$ (Lines <ref>–<ref>), by Theorem <ref>.  Note that, since the sorted list of candidate non-key attributes for each $\tau$ is already created (Line <ref>), it is unnecessary to do a full sorting in order to determine the top-($n$$-$$k$) candidates $\Gamma$.  Instead, a simple merge operation on the $k$ sorted lists will get $\Gamma$.

The algorithm has an exponential complexity $O(KN\log N+{K\choose k}(k+n))$, where $K=|V_s|$ is the number of candidate key attributes, $N=2|E_s|$ is the number of candidate non-key attributes for all candidate key attributes, $K\choose k$ is the number of $k$-subsets, and $KN\log N$ is for sorting individual lists of candidates (Line <ref>), in which each list contains at most $N$ elements.  CL: If we clearly explain the assumption on dynamic data, then we can ignore the sorting cost.

Alg. <ref> is for finding one of the optimal previews.  To find all optimal previews, it needs simple extension to deal with ties in scores, which we will not further discuss.

The same brute-force algorithm is applicable for optimal preview discovery in all three types of spaces—concise, tight and diverse previews.  The pseudo code in Alg. <ref> is for concise previews and does not enforce distance constraint, for simplicity of presentation.  Enforcing distance constraint for tight/diverse previews is straightforward, by performing distance check on every pair of preview tables in each $k$-subset of entity types.

§.§ A Dynamic-Programming Algorithm for Concise Preview Discovery Problem

As the combinatorial number of $k$-subsets grows exponentially, the performance of the above brute-force algorithm becomes unacceptable for finding an optimal preview under modest size constraints. We thus developed a dynamic-programming algorithm to discover optimal concise previews more efficiently.

Consider an arbitrary order on all $K$ entity types—$\tau_1$, …, $\tau_K$.  We use $\mathcal{P}_{opt}(k,n,x)$ to denote an optimal concise preview among the first $x$ entity types $\tau_1$, …, $\tau_x$.  Thus the optimal concise preview discovery problem is to find $\mathcal{P}_{opt}(k,n,K)$.  $\mathcal{P}_{opt}(k,n,x)$ can be constructed from the solutions to smaller problems, in two ways:  (1) It can be equal to $\mathcal{P}_{opt}(k,n,x-1)$, i.e., its $k$ tables and $n$ non-key attributes are from the first $x-1$ entity types and the $x$-th entity type $\tau_x$ does not contribute anything; (2) It can also be the union of $\mathcal{P}_{opt}(k-1,n-m,x-1)$ and a table $T_x^m$, where   $\mathcal{P}_{opt}(k-1,n-m,x-1)$ is an optimal preview with $k-1$ tables and $n-m$ non-key attributes among the first $x-1$ entity types, and  $T_x^m$ is the table whose key attribute is $\tau_x$ and whose non-key attributes are the top-$m$ elements in $\Gamma^{\tau_x}$—the sorted list of candidate non-key attributes for $\tau_x$.  The number $m$ is between $1$ and $n-(k-1)$ (or less if there are less than  $n-(k-1)$ elements in $\Gamma^{\tau_x}$), since each of the $k-1$ tables in $\mathcal{P}_{opt}(k-1,n-m,x-1)$ must contribute at least one non-key attribute.
The optimal substructure of the problem is as follows.  (We do not discuss boundary cases ($k=1$ or $x=1$ or $n=k$) due to space limitations.)

\mathcal{P}_{opt}(k,n,x) = \operatorname*{arg\,max}_{\mathcal{P}\in \mathbb{P}(k,n,x)}S(\mathcal{P})

\mathbb{P}(k,n,x) =
\left\{
\begin{array}{l l}
\mathcal{P}_{opt}(k,n,x\!-\!1),\\
\mathcal{P}_{opt}(k\!-\!1,n\!-\!1,x\!-\!1)\, \bigcup\, \{T_x^1\},\\
\mathcal{P}_{opt}(k\!-\!1,n\!-\!2,x\!-\!1)\, \bigcup\, \{T_x^2\},\\
\mathcal{P}_{opt}(k\!-\!1,k\!-\!1,x\!-\!1)\, \bigcup\, \{T_x^{n-(k-1)}\}
\end{array}
\right\},

where $T_x^m.key$ = $\tau_x$ and $T_x^m.nonkey$ = top-$m$ candidate non-key attributes in $\Gamma^{\tau_x}$.
Note that the optimal substructure is inapplicable when previews must satisfy distance constraint in addition to size constraint (details omitted).  Therefore the dynamic-programming algorithm is for concise previews but not tight/diverse previews.

The pseudo code of the dynamic-programming algorithm is shown in Alg. <ref>.  Its complexity is $O(KN\log N+Kkn^2)$.  Similar to Alg. <ref>, Alg. <ref> is for finding one optimal preview.  Finding all optimal previews requires simple extension to deal with ties in scores, which we will not further discuss. CL: Explain briefly why DP is better than brute-force in practice, by analyzing the complexity.

Both Alg. <ref> and <ref> assume that, given any $k$ entity types (key attributes), they always together have at least $n$ non-key attributes.  That may not be true in reality.  In fact, for two previews with the same number of tables, the preview with less non-key attributes may have the higher score than the other preview.  Note that, in Eq. <ref>, the optimal preview is not required to have exactly $n$ non-key attributes.  It is simple to extend Alg. <ref> and <ref> to fully comply with the definition.  Given any entity type $\tau$, if it has less than $n$ candidate non-key attributes, we can simply pad the sorted list $\Gamma^{\tau}$ by pseudo non-key attributes with zero scores.

§.§ An Apriori-style Algorithm for Tight / Diverse Preview Discovery Problem

Since the dynamic-programming algorithm is inapplicable when previews must satisfy distance constraint, we propose an efficient algorithm for optimal tight/diverse preview discovery, shown in Alg. <ref>. It consists of two steps: (1) finding $k$-subsets of entity types (i.e., vertices in $G_s$) satisfying the distance constraint (Lines <ref>– <ref>); (2) for each qualifying $k$-subset of entity types, forming a preview under the size constraint, computing its score and choosing a preview with the highest score (Lines <ref>– <ref>).

The first step is essentially finding $k$-cliques in a graph converted from the schema graph $G_s$, in which vertices are considered adjacent if they are within distance $d$ (for tight previews) or apart by at least distance $d$ (for diverse previews).  The $k$-clique problem is well-studied and many efficient algorithms have been designed in the past.  Our method is inspired by the well-known Apriori algorithm [1] for frequent itemset mining.  In [7], an algorithm was proposed for finding $k$-cliques (where edges correspond to metabolite correlations) by similar ideas, although the connection to Apriori was not made.  Their experimental results demonstrated superior efficiency in comparison with the more well-known Bron-Kerbosch algorithm [5].  Nevertheless, the two broad steps of our optimal tight/diverse preview discovery algorithm are independent from each other, and thus any more efficient or even approximate algorithm for finding $k$-cliques can be plugged into it to further improve its execution efficiency.

Domain       # of vertices     # of edges
books        6M / 91         15M / 201

film         2M / 63        18M / 136

music        27M / 69       187M / 176

people       3M / 45       17M / 78

tv           2M / 59       17M / 177

basketball     19K / 6      557K / 21

architecture     133K / 23     432K / 48

Sizes of Entity/Schema Graphs.

Domain       Coverage     Entropy
books        0.8          0.786

film         0.2          0.25

music        0.528        0.589

people       0.708        0.606

tv           0.622        0.379

MRR of Non-Key Attribute Scoring.

2 c| Key Attribute Scoring     2 c| Non-Key Attribute Scoring
Domain       Coverage     Random Walk     Coverage     Entropy
books        0.55               0.43          0.43               0.43

film         0.48               0.25          0.35               0.35

music      0.33               0.46            0.42               0.41

people     0.31               0.29             0.43               0.43

tv        0.69               0.65            0.47               0.47

PCC of Key and Non-Key Attribute Scoring.

In more details, the first step of Alg. <ref> iteratively generates a $k$-subset of entity types by merging two $(k$$-$$1)$-subsets.  Entity types are arbitrarily ordered as $\tau_1, \ldots, \tau_K$. In the $i$-th iteration of the algorithm, if two $(i$$-$$1)$-subsets $A$ and $B$ only differ by their last entity types $\tau_{A[i-1]}$ and $\tau_{B[i-1]}$, and the distance between their last entity types satisfies the distance constraint, a candidate $i$-subset is generated by appending $\tau_{B[i-1]}$ to the end of $A$.

In the second step, for each candidate $k$-subset of entity types, a preview is computed ($\mathit{ComputePreview}(A)$ in Line <ref> of Alg. <ref>). The details of function $\mathit{ComputePreview}$ are omitted.  It follows Theorem <ref> and is essentially the same as Lines <ref>– <ref> in Alg. <ref>.
The score of each preview is computed (the same as in Lines <ref>– <ref> of Alg. <ref>) and a preview with the highest score is returned.

The worst-case complexity of Alg. <ref> is the same as that of Alg. <ref>.  However, as Sec. <ref> shows, in practice it significantly outperforms the brute-force algorithm, since Line <ref> could filter out many combinations that do not satisfy the distance constraint.

§ EVALUATION

We conducted experiments to evaluate the preview scoring
measures' accuracy (Sec. <ref>), the preview discovery
algorithms' efficiency (Sec. <ref>), and the overall
quality of discovered previews (Sec. <ref>).
All experiments were conducted on a Dell T100 server running Ubuntu 8.10.
The server has a Dual Core Xeon E3120 processor, 6MB cache, 4GB RAM,
and two 250GB RAID1 SATA hard drivers.  All algorithms are implemented in
C++ and compiled with `-O2' optimization in GCC-4.3.2.

The entity graph used in our experiment is a dump of Freebase at
September 28, 2012.[<https://developers.google.com/freebase/data>]
The dataset is imported into a MySQL database.
In Freebase, the entire entity graph is partitioned into many domains.
Our experiments were conducted on eight domains.  The sizes of
the entity and schema graphs in these domains are shown in Table <ref>.
Our work currently is limited to named entities, thus all numeric attribute values from the data dump have been removed.  Note that a schema graph may be disconnected.  To ensure the convergence of random walk in such a graph, we added a small transition probability $10^{-5}$ to every pair of entity types. CL: (1) Make sure we discuss incremental update somewhere, and remove “details omitted” if possible; (2) My understanding is that this small probability is highly related but not identical to damping factor, for two reasons: a) they can be computed from each other but are not the same; b) Damping factor can be used to introduce randomness to the process, even if the graph is connected.

§.§ Accuracy of Preview Scoring Measures

We conducted two experiments to evaluate the accuracy of the scoring measures for both key and non-key attributes presented in Sec. <ref>.  One experiment compares the ranking orders of candidate key (non-key) attributes by the scoring measures with gold standard ranking orders.  The other experiment calculates the correlation between two pairwise ordering results on candidate key (non-key) attributes—one by the scoring measures and the other collected from user study through crowdsourcing.

§.§.§ Comparison with Gold Standard

Precision-at-$K$ of Key Attribute Scoring.

We collected gold standard data for 5 largest entity domains in Freebase—“books”, “film”, “music”, “people” and “tv”.  For each domain, Freebase offers an entrance page showing 6 major entity types in that domain.  A user can choose to browse entities in any of the 6 types. [The entrance pages were all under “Featured Data” on <Freebase.com>.  For instance, <http://www.freebase.com/view/film> was the entrance page for domain “film”.  We collected these pages shortly after September 28, 2012, which is the timestamp of the Freebase entity graph dump used in our experiments.
These pages have become unavailable lately.]  As such entrance pages were manually created by Freebase, our conjecture is that they are of high quality and reflect the most popular entity types.  We thus treated the 6 entity types listed in the entrance page of a domain as the gold standard for top-6 key attributes in that domain.

For both the coverage-based and the random-walk based scoring measures in Sec. <ref>, we ranked all candidate key attributes by their scores.  We calculated the accuracy of a scoring measure by several widely-used IR evaluation measures, including Precision-at-$K$ (P@$K$), Mean Average Precision (MAP) and Normalized Discounted Cumulative Gain (nDCG) [9].
Since they demonstrate similar results, we only report P@$K$ due to space limitations.
For a scoring measure for key attributes, P@$K$ is the percentage of its top-$K$ results that belong to the aforementioned gold standard top-6 key attributes.
The results are in Fig. <ref>.
The topmost curves (“Optimal P@$K$”) represent the best possible P@$K$ that can be archived by any method.
For instance, P@10 can be at most 0.6, since there are only 6 gold standard key attributes in each domain, as mentioned above.
The figure shows that both the coverage-based and the random-walk based scoring measures had
P@10 close to 0.6 in 4 out of the 5 domains.

For each entity type, Freebase offers a table for users to browse and query the entities belonging to that type. [<http://www.freebase.com/music/artist?instances=>, for instance, would display a table for type Artist in “music” domain.]  The table always has 3 common columns for recording names, types and article contents of entities.  It also has 3 or less type-dependent non-key attributes manually selected by Freebase editors.  Although Freebase allows users to add more attributes into this table, we believe the original $3$ type-dependent attributes in general bear higher quality.  We thus treated these attributes as the gold standard for top non-key attributes for that entity type.

For both the coverage-based and the entropy-based scoring measures in Sec. <ref>, we ranked all candidate non-key attributes by their scores.  We calculated the accuracy of a scoring measure by Mean Reciprocal Rank (MRR) [9] instead of P@$K$ as there are only 3 or less gold standard answers for top non-key attributes in each entity type.  For a scoring measure for non-key attributes, the reciprocal rank is the multiplicative inverse of the rank of the first gold standard non-key attribute among its ranking results.  MRR is the average reciprocal rank across all entity types with at least 5 candidate non-key attributes.  (If an entity type has only less than 5 candidates, the gold standard answers are ranked deceptively high.  Thus we exclude such entity types, to obtain more accurate evaluation.)
The results are shown in Table <ref>.  In every domain except “film” and for both the coverage-based and the entropy-based measures, MRR is above 0.5.
This means in average a gold standard non-key attribute appeared in the top-2 ranked results.
The lower MRR for “film” domain is from only one entity type and thus is not truly indicative, since only that entity type has at least
5 candidate non-key attributes.

§.§.§ User Study

We conducted an extensive user study in Amazon Mechanical Turk (AMT)[<https://www.mturk.com/mturk/>]—a popular crowdsourcing service—and measured the correlation between our scoring measures and users' opinions with regard to key and non-key attributes ranking.  We explain the user study procedure for evaluating key attribute ranking in one domain, since the procedure is repeated for all 5 gold standard domains and is the same for both key and non-key attribute ranking.

Given a domain, we randomly generated $50$ pairs of entity types, i.e., candidate key attributes.  Each pair was presented to $20$ AMT workers.  The workers were asked which of the 2 entity types in the pair is more important.  Hence, we collected $1,000$ opinions in total.  We then constructed two lists—$X$ and $Y$, each of which contains $50$ values corresponding to the $50$ pairs.  A value in $X$ represents the difference in the ranking positions (by our scoring measures) of the two entity types in the corresponding pair.  A value in $Y$ represents the difference in the numbers of AMT workers favoring the two entity types.  The correlation between $X$ and $Y$ is measured by Pearson Correlation Coefficient (PCC) [6] as follows.

\begin{align}
PCC =  \frac{\text{E}(XY)-\text{E}(X)\text{E}(Y)}{\sqrt{\text{E}(X^2)-(\text{E}(X))^2}\sqrt{\text{E}(Y^2)-(\text{E}(Y))^2}}
\end{align}

The PCC value ranging from $-1$ to $1$ indicates the degree of correlation between the pairwise ranking orders produced by our scoring methods and the pairwise preferences given by AMT workers.
A PCC value in the ranges of [$0.5$,$1.0$], [$0.3$,$0.5$) and [$0.1$,$0.3$) indicates a strong, medium and small positive correlation, respectively.

PCC values for the 5 gold standard domains are in Table <ref>.
For all 5 domains, the results show at least a medium positive correlation between our scoring measures and AMT workers.

§.§ Efficiency of Algorithms

This section presents results on the efficiency of the optimal preview discovery algorithms in Sec. <ref>.
On optimal concise preview discovery, we compared the Brute-Force Alg. <ref> and the Dynamic-Programming Alg. <ref>.  Specifically, we compared their execution times by varying: (1) size of schema graph (i.e., number of candidate key attributes ($K$) and number of candidate non-key attributes ($N$)); (2) number of preview tables (i.e., key attributes) in a preview ($k$); and (3) maximum number of non-key attributes in a preview ($n$).  For (1), we fixed $k$=$5$, $n$=$10$ and experimented with $3$ domains—“basketball” (B), “architecture” (A), and “music” (M). They differ greatly in the sizes of their schema graphs (B: $K$=$6$, $N$=$21$; A: $K$=$23$, $N$=$48$; M: $K$=$46$, $N$=$133$).
For (2), we varied $k$ from $3$ to $9$, fixed $n$=$20$ and used “music” domain.
For (3), we varied $n$ from $8$ to $20$, fixed $k$=$6$ and used “music” domain.

On optimal tight/diverse preview discovery, we compared the Brute-Force Alg. <ref> and the Apriori-style Alg. <ref>, by varying not only the aforementioned 3 parameters but also the distance constraint on $d$.  When we varied other parameters, $d$ is fixed at $2$ and $4$ for tight and diverse previews, respectively.  When we fixed other parameters, $d$ was varied from $2$ to $6$.

The results are in Figs. <ref> and <ref>. In all results, the execution time is averaged across 3 runs, and execution time less than 1 millisecond is rounded to 1 millisecond.
The results show that both the Dynamic-Programming and the Apriori-style algorithms outperformed the Brute-Force algorithm by orders of magnitude in most cases.  The exceptions are the smallest domain “basketball” and when the number of requested preview tables is small ($k$=$3$).
In these cases, the overheads of complex data structures and calculations in the advanced algorithms outweighed their benefits.

Fig. <ref> shows that the Apriori-style algorithm did not perform well for $d$=$6$ in tight preview discovery and $d$=$2$ in diverse preview discovery.  It is due to the excessive number of candidate $k$-subsets that satisfy the distance constraint in such cases.  For instance, the diameter of a schema graph typically is not large.  In the schema graph of “film” domain, the longest path length is 7 and the average path length is around 3–4.  Setting distance constraint $d$=$6$ in finding tight previews will make most previews “tight”.  It is unnecessary to enforce such a distance constraint.

§.§ Sample Optimal Previews

Key attributes      Non-key attributes (Target entity types)

2 |c|  Domain=“film”, KS=Coverage, NKS=Coverage, $k$=$5$, $n$=$10$
Film Character      Portrayed in films (Film, Film Actor)

Film Actor          Film performances (Film, Film Character)

Film                Performances (Film actor, Film Character),

Genres (Film Genre),  Runtime (Film Cut),

Country of origin (Country),

Directed by (Film Director),

Languages (Human Language)

Film Director       Films directed (Film)

Film Crewmember     Films crewed (Film, Film crew role)

2 |c|  Domain=“music”, KS=Random Walk, NKS=Coverage, $k$=$5$, $n$=$10$
Musical Recording     Releases (Musical Release),

Tracks (Release Track),

Recorded by (Musical Artist)

Musical Release       Tracks (Musical Recording),

Track list (Release Track)

Release Track         Release (Musical Release),

Recording (Musical Recording)

Musical Artist        Tracks recorded (Musical Recording)

Musical Album         Releases (Musical Release),

Release type (Musical Album Type)

2 |c|  Domain=“tv”, KS=Random Walk, NKS=Entropy, $k$=$5$, $n$=$10$

TV Episode     Previous episode (TV Episode),

Next episode (TV Episode),

Performances (TV Actor, TV Character),

Season (TV Season),   Series (TV Program) ,

Personal appearances

(Person, Personal Appearance Role)

TV Program     Regular acting performances

(TV Actor, TV Character, TV Season)

TV Season     Episodes (TV Episode)

TV Actor     TV episode performances

(TV Episode, TV Character)

TV Director     TV episodes directed (TV Episode)

Sample Optimal Concise Previews.

Key attributes      Non-key attributes (Target entity types)

2 |c|  Domain=“film”, KS=Coverage, NKS=Coverage, $k$=$5$, $n$=$10$, $d$=$2$
Film              Performances (Film Character, Film Actor),

Genres (Film Genre),   Runtime (Film Cut),

Country of origin (Country),

Directed by (Film Director),

Languages (Human Language)

Film Director     Films directed (Film)

Film Producer     Films produced (Film)

Film Writer       Film writing credits (Film)

Film Editor       Films edited (Film)

2 |c|  Domain=“film”, KS=Coverage, NKS=Coverage, $k$=$5$, $n$=$10$, $d$=$4$
Film Character                        Portrayed in films (Film, Film Actor),

Portrayed in films (dubbed) (Film, Film Actor)

Film Crewmember                        Films crewed (Film, Film Crew Role)

Person or Entity      Films appeared in (Film, Type of Appearance)

appearing in Film

Film Festival                          Individual festivals (Film Festival Event),

Location (Location),

Focus (Film Festival Focus),

Sponsoring organization (Sponser)

Film Company                           Films (Film)

Sample Optimal Tight (Upper) and Diverse Previews (Lower).

To demonstrate the combined effectiveness of both scoring measures and preview discovery algorithms, Table <ref> presents the optimal concise previews in 3 selected domains by 3 different combinations of key attribute scoring (KS) and non-key attribute scoring (NKS) measures.  The size constraint is set as $k$=$5$ and $n$=$10$.  All result previews show that the selected key and non-key attributes have covered important entity types and their important relationship types.
Further, Table <ref> shows the optimal tight ($d$=$2$) and diverse ($d$=$4$) previews in “film” domain by one particular choice of key and non-key attribute scoring measures.
We see that, in the tight preview result, the chosen key attributes are all highly related to one entity type Film.  In the diverse preview result, the chosen key attributes are far less related to each other.  Both verify the effectiveness of the concepts of tight/diverse previews.

Note that in the generated previews, certain non-key attributes represent relationship types involving more than two entity types.  An example in Table <ref> is Portrayed in films, which is a non-key attribute of entity type Film Character.  Different from other non-key attribute such as Films directed, it represents a 3-way relationship among Film Character, Film and Film Actor. For instance, Agent J is a Film Character played by Film Actor Will Smith in Film Men in Black.
To present the values of such a multi-way non-key attribute in a preview table, we employ a simple approach of presenting values for all participating entity types in this relationship.  It is arguable that this approach widens the preview table, which to some extent violates a given size constraint.  An alternative solution is to use separate preview tables for all multi-way relationships. These pose interesting directions for our future work.

§ RELATED WORK

There have been several studies on schema summarization for relational databases [14, 15, 16], XML [16] and general graph data [12, 17].
[16] produces schema summarization for relational databases and XML data.  Its summary is in the form of a condensed schema tree where a node may correspond to multiple nodes or a trunk in the original schema tree.
The notion of summary in [14, 15] refers to clustering the tables in a database by their semantic roles and similarities as well as identifying direct join relationships and indirect join paths between the tables.

The graph summarization in [12, 17] groups graph nodes based on their attribute similarity and allows users to browse the summary from different grouping granularities.

As explained in Sec. <ref>, these methods are inapplicable or ineffective for producing preview tables from entity graphs, due to differences in input/output data models and goals.

There are many works on graph clustering [10].  They are not effective for generating preview tables, since clustering focuses on partitioning but does not present a concise structure.  On the contrary, a preview only selects a small number of key attributes (vertices) and non-key attributes (edges) from a schema graph.

§ CONCLUSION

This paper studies how to generate preview tables for entity graphs.  The problem is challenging due to the scale and complexity of such graphs.  We proposed effective scoring measures for preview tables.  We proved that the optimal preview discovery problem under distance constraint is -hard.  We designed efficient algorithms for discovering optimal previews. Our experiments on Freebase data verified the accuracy and efficiency of our methods.

For future work, one direction is to study how to select representative entity tuples for preview tables.  Using random tuples may not be adequate since a user may not be familiar with them.
Another direction is to investigate how to incorporate numeric attributes into preview tables. It is not straightforward to compare the importance of numeric values and entities.

[1]
R. Agarwal and R. Srikant.
Fast algorithms for mining association rules.
In VLDB, pages 487–499, 1994.

[2]
S. Auer, C. Bizer, G. Kobilarov, J. Lehmann, R. Cyganiak, , and Z. Ives.
DBpedia: A nucleus for a Web of open data.
In ISWC, 2007.

[3]
K. Bollacker, C. Evans, P. Paritosh, T. Sturge, and J. Taylor.
Freebase: a collaboratively created graph database for structuring
human knowledge.
In SIGMOD, 2008.

[4]
S. Brin and L. Page.
The anatomy of a large-scale hypertextual web search engine.
In WWW, 1998.

[5]
C. Bron and J. Kerbosch.
Algorithm 457: finding all cliques of an undirected graph.
CACM, 16(9):575–577, Sept. 1973.

[6]
J. Cohen.
Statistical Power Analysis for the Behavioral Sciences.

[7]
F. Kose, W. Weckwerth, T. Linke, and O. Fiehn.
Visualizing plant metabolomic correlation networks using
clique-metabolite matrices.
Bioinformatics, 17(12):1198–1208, Dec. 2001.

[8]
T.-Y. Liu.
Learning to rank for information retrieval.
Found. Trends Inf. Retr., 3(3):225–331, Mar. 2009.

[9]
C. D. Manning, P. Raghavan, and H. Schtze.
Introduction to Information Retrieval.
Cambridge University Press, 2008.

[10]
S. E. Schaeffer.
Survey: Graph clustering.
Comput. Sci. Rev., 1(1):27–64, Aug. 2007.

[11]
F. M. Suchanek, G. Kasneci, and G. Weikum.
YAGO: a core of semantic knowledge unifying WordNet and
In WWW, pages 697–706, 2007.

[12]
Y. Tian, R. A. Hankins, and J. M. Patel.
Efficient aggregation for graph summarization.
In SIGMOD, pages 567–580, 2008.

[13]
W. Wu, H. Li, H. Wang, and K. Q. Zhu.
Probase: a probabilistic taxonomy for text understanding.
In SIGMOD, pages 481–492, 2012.

[14]
X. Yang, C. M. Procopiuc, and D. Srivastava.
Summarizing relational databases.
PVLDB, 2(1):634–645, 2009.

[15]
X. Yang, C. M. Procopiuc, and D. Srivastava.
Summary graphs for relational database schemas.
PVLDB, 2011.

[16]
C. Yu and H. V. Jagadish.
Schema summarization.
In VLDB, 2006.

[17]
N. Zhang, Y. Tian, and J. M. Patel.
Discovery-driven graph summarization.
In ICDE, pages 880–891, 2010.


* Levin and Wen [2005] M. A. Levin and X.-G. Wen, String-net condensation: A physical mechanism for topological phases, Phys. Rev. B 71, 045110 (2005).
  * Lin and Levin [2014] C.-H. Lin and M. Levin, Generalizations and limitations of string-net models, Phys. Rev. B 89, 195130 (2014).
  * Lan and Wen [2014] T. Lan and X.-G. Wen, Topological quasiparticles and the holographic bulk-edge relation in $(2+1)$-dimensional string-net models, Phys. Rev. B 90, 115119 (2014).
  * Hahn and Wolf [2020] A. Hahn and R. Wolf, Generalized string-net model for unitary fusion categories without tetrahedral symmetry, Phys. Rev. B 102, 115154 (2020).
  * Lin  _et al._ [2021] C.-H. Lin, M. Levin, and F. J. Burnell, Generalized string-net models: A thorough exposition, Phys. Rev. B 103, 195155 (2021).
  * [15] A. Kirillov, String-net model of Turaev-Viro invariants, arXiv:1106.6033.
  * [16] Z. Wang, Topological Quantum Computation, CBMS Regional Conference Series in Mathematics, No. 112 (American Mathematical Society, Providence, RI, 2010).
  * Hu  _et al._ [2018] Y. Hu, N. Geer, and Y.-S. Wu, Full dyon excitation spectrum in extended Levin-Wen models, Phys. Rev. B 97, 195154 (2018).
  * [18] Actually, the notion of Morita equivalence is defined for algebras and not for UFCs. Two algebras that have the same modules (i.e. irreducible representations) are said to be Morita equivalent. Here if two input categories $\mathcal{C}$ and $\mathcal{C}^{\prime}$ have tube algebras $\mathcal{TA}$ and $\mathcal{TA}^{\prime}$ that are Morita equivalent, it means that they have the same modules. But these are in one to one correspondence with the simple objects in the Drinfeld center, so that $\mathcal{Z}(\mathcal{C})$ and $\mathcal{Z}(\mathcal{C})^{\prime}$ are equivalent. By abuse of language, we say that two UFCs that have the same Drinfeld center are Morita equivalent.
  * Moore and Seiberg [1989] G. Moore and N. Seiberg, Classical and quantum conformal field theory, Commun. Math. Phys. 123, 177 (1989).
  * Verlinde [1988] E. Verlinde, Fusion rules and modular transformations in 2D conformal field theory, Nucl. Phys. B 300, 360 (1988).
  * Buerschaper and Aguado [2009] O. Buerschaper and M. Aguado, Mapping Kitaev’s quantum double lattice models to Levin and Wen’s string-net models, Phys. Rev. B 80, 155136 (2009).
  * [22] S. H. Simon, Topological Quantum, Oxford University Press (2023), to appear.
  * Asaeda and Haagerup [1999] M. Asaeda and U. Haagerup, Exotic Subfactors of Finite Depth with Jones Indices $(5+\sqrt{13})/2$ and $(5+\sqrt{17})/2$, Commun. Math. Phys. 202, 1 (1999).
  * Hong  _et al._ [2008] S.-M. Hong, E. Rowell, and Z. Wang, On exotic modular categories, Commun. Contemp. Math. 10, 1049 (2008).
  * Vidal [2022] J. Vidal, Partition function of the Levin-Wen model, Phys. Rev. B 105, L041110 (2022).
  * Schulz  _et al._ [2013] M. D. Schulz, S. Dusuel, K. P. Schmidt, and J. Vidal, Topological Phase Transitions in the Golden String-Net Model, Phys. Rev. Lett. 110, 147203 (2013).
  * Schulz  _et al._ [2014] M. D. Schulz, S. Dusuel, G. Misguich, K. P. Schmidt, and J. Vidal, Ising anyons with a string tension, Phys. Rev. B 89, 201103(R) (2014).
  * Schulz  _et al._ [2015] M. D. Schulz, S. Dusuel, and J. Vidal, Russian doll spectrum in a non-Abelian string-net ladder, Phys. Rev. B 91, 155110 (2015).
  * Hu  _et al._ [2012] Y. Hu, S. D. Stirling, and Y.-S. Wu, Ground-state degeneracy in the Levin-Wen model for topological phases, Phys. Rev. B 85, 075107 (2012).
  * Hu  _et al._ [2014] Y. Hu, S. D. Stirling, and Y.-S. Wu, Emergent exclusion statistics of quasiparticles in two-dimensional topological phases, Phys. Rev. B 89, 115133 (2014).
  * [31] A. Ocneanu, Chirality for operator algebras, Subfactors (World Scientific, Singapore, 1994), p. 39.
  * Ocneanu [2001] A. Ocneanu, Operator Algebras, Topology and Subgroups of Quantum Symmetry —Construction of Subgroups of Quantum Groups—, Adv. Stud. Pure Math. 31, 235 (2001).
  * [33] J. Slingerland, List of small multiplicity-free fusion rings.
  * Kitaev [2006] A. Kitaev, Anyons in an exactly solved model and beyond, Ann. Phys. (NY) 321, 2 (2006).
  * [35] P. H. Bonderson, Ph. D. thesis, Caltech, 2007.
  * Tambara and Yamagami [1998] D. Tambara and S. Yamagami, Tensor categories with fusion rules of self-duality for finite abelian groups, J. Algebra 209, 692 (1998).
  * Pasquier [1987] V. Pasquier, Operator content of the ADE lattice models, J. Phys. A 20, 5707 (1987).
  * Kane and Fisher [1997] C. L. Kane and M. P. A. Fisher, Quantized thermal transport in the fractional quantum Hall effect, Phys. Rev. B 55, 15832 (1997).
  * Kitaev and Kong [2012] A. Kitaev and L. Kong, Models for gapped boundaries and domain walls, Commun. Math. Phys. 313, 351 (2012).
  * Kong [2014] L. Kong, Anyon condensation and tensor categories, Nucl. Phys. B 886, 436 (2014).
  * Neupert  _et al._ [2016] T. Neupert, H. He, C. von Keyserlingk, G. Sierra, and B. A. Bernevig, Boson condensation in topologically ordered quantum liquids, Phys. Rev. B 93, 035103 (2016).
  * Levin [2013] M. A. Levin, Protected Edge Modes without Symmetry, Phys. Rev. X 3, 021009 (2013).
  * Lan  _et al._ [2015] T. Lan, J. C. Wang, and X.-G. Wen, Gapped Domain Walls, Gapped Boundaries, and Topological Degeneracy, Phys. Rev. Lett. 114, 076402 (2015).
  * Simon and Fendley [2013] S. H. Simon and P. Fendley, Exactly solvable lattice models with crossing symmetry, J. Phys. A 46, 105002 (2013).
  * M. Müger [2003] M. Müger, From subfactors to categories and topology II: The quantum double of tensor categories and subfactors, J. Pure Appl. Algebra 180, 159 (2003).
  * [46] J. Slingerland, private communication.
  * Beigi  _et al._ [2011] S. Beigi, P. W. Shor, and D. Whalen, The Quantum Double Model with Boundary: Condensations and Symmetries, Commun. Math. Phys. 306, 663 (2011).
  * Vanhove  _et al._ [2022] R. Vanhove, L. Lootens, M. V. Damme, R. Wolf, T. J. Osborne, J. Haegeman, and F. Verstraete, Critical Lattice Model for a Haagerup Conformal Field Theory, Phys. Rev. Lett. 128, 231602 (2022).
  * [49] A. Ritz-Zwilling, J.-N. Fuchs, S. H. Simon, and J. Vidal, (unpublished).
  * L. Lootens, B. Vancraeynest-De Cuiper, N. Schuch and F. Verstraete [2022] L. Lootens, B. Vancraeynest-De Cuiper, N. Schuch and F. Verstraete, Mapping between Morita-equivalent string-net states with a constant depth quantum circuit, Phys. Rev. B 105, 085130 (2022).
  * Bultinck  _et al._ [2017] N. Bultinck, M. Mariën, D. J. Williamson, M. B. Şahinoğlu, J. Haegeman, and F. Verstraete, Anyons and matrix product operator algebras, Ann. Phys. (NY) 378, 183 (2017).
  * [52] L. Lootens, C. Delcamp, and F. Verstraete, Dualities in one-dimensional quantum lattice models: topological sectors, arXiv:2211.03777.
  * [53] This equation is reminiscent of the relation between the central idempotents $P_{A}$ and the string operators $W_{B}$ involving the $S$-matrix [see Eq. (79)]. It relates the projectors $p_{A}^{11}$ onto the fluxons in the $11$ sector to the input string operators (or horizontal tubes) $Q^{i}_{11i}$ via the mock $S$-matrix $\tilde{s}$. It is also a particular case of  $p_{A}^{11}=\sum_{i\in\mathcal{C}}(\mathbf{M}^{-1})_{A,i}\,Q^{i}_{11i},$ which is the inverse of  $Q^{i}_{11i}=\sum_{A\in\mathcal{F}}\mathbf{M}_{i,A}\,p_{A}^{11},$ where we introduced the square matrix $\mathbf{M}$ defined by its elements $\mathbf{M}_{i,A}=M^{i}_{A,11i}=\Omega^{i}_{A,11i}\,d_{i}$.
  * Bais and Slingerland [2009] F. A. Bais and J. K. Slingerland, Condensate-induced transitions between topologically ordered phases, Phys. Rev. B 79, 045316 (2009).
  * Lan  _et al._ [2020] T. Lan, X. Wen, L. Kong, and X.-G. Wen, Gapped domain walls between 2+1D topologically ordered states, Phys. Rev. Research 2, 023331 (2020).
  * Kawahigashi [2015] Y. Kawahigashi, A remark on gapped domain walls between topological phases, Lett. Math. Phys. 105, 893 (2015).
  * [57] I. Cong, M. Cheng, and Z. Wang, Topological Quantum Computation with Gapped Boundaries,arXiv:1609.02037.
  * Grossman and Snyder [2012] P. Grossman and N. Snyder, Quantum Subgroups of the Haagerup Fusion Categories, Commun. Math. Phys. 311, 617 (2012).


# COMPARISON OF GROUND-BASED AND GAIA PHOTOMETRY OF ASTROMETRIC RADIO SOURCES

###### Abstract

A comparison was made between $Gaia$ magnitudes and magnitudes obtained from
ground-based observations for astrometric radio sources . The comparison
showed that these magnitudes often not agree well. There may be several
reasons for this disagreement. Nevertheless, such an analysis can serve as an
additional filter for verification of the object cross-identification. On the
other hand, it can help to detect possible errors in optical magnitudes of
astrometric radio sources coming from unreliable or inconsistent data sources.

Z. MALKIN1,2

1Pulkovo Observatory, Pulkovskoe shosse 65, St. Petersburg 196140, Russia

E--mail<EMAIL_ADDRESS>
2Kazan Federal University, Kremlyovskaya street 18, Kazan 420008, Russia

##  1 INTRODUCTION

Comparison of the VLBI and $Gaia$ positions of astrometric radio sources gives
us an opportunity to investigate both systematic errors of both catalogs and
the physical structure and evolution of objects observed by optical and radio
techniques. However, the reliability of the results of such studies depends on
the reliability of cross-identification between objects in VLBI and $Gaia$
catalogs. Although for most sources the cross-identification looks
straightforward, this is is not always the case. Errors in cross-
identification introduce additional noise and outliers in the position
difference statistics, which may impact the result and conclusions of these
studies.

Different authors use different strategies for cross-identification between
the objects in radio and optical catalogs (Mignard et al. 2016, Petrov and
Kovalev 2017, Lindegren et al. 2018, Malkin 2018, Makarov et al. 2019, Liu et
al. 2020). They all are based on analysis of the differences between VLBI and
$Gaia$ source position, sometimes along with other criteria, such as quality
of the $Gaia$ astrometric solution (Mignard et al. 2016, Lindegren et al.
2018) or object density in the vicinity of the source (Petrov and Kovalev
2017). Some of these supplement criteria may be disputable, but a comparison
and discussion of cross-identification methods described in the literature is
beyond the scope of this paper.

The present study is aimed at an investigation of a possibility of using
$Gaia$ and ground-based photometry as a supplement criterium to verify the
cross-identification based on an analysis of the difference between radio and
optics positions.

##  2 COMPARISON OF GROUND-BASED AND GAIA PHOTOMETRY

In this study, the $G$ magnitudes given in the $Gaia$ DR2 release were
compared to ground-based magnitudes provided in the OCARS
catalog111http://www.gaoran.ru/english/as/ac_vlbi/ocars_m.txt (Malkin 2018).
There are 8197 sources in common between the $Gaia$ DR2 and OCARS. 7179 of
them have photometry data in OCARS in at least one of four bands: $V$, $r$,
$R$, and $i$, close to $Gaia$ $G$ band. The latter sources were used in this
work.

OCARS magnitudes are taken from different data sources: Sloan Digital Sky
Survey222http://www.sdss.org (SDSS), NASA/IPAC Extragalactic
Database333http://ned.ipac.caltech.edu (NED),
SIMBAD444http://simbad.u-strasbg.fr/simbad/ database managed by the Centre de
Donnees astronomiques de Strasbourg (CDS), the Million Quasars (Milliquas)
catalog555https://heasarc.gsfc.nasa.gov/W3Browse/all/milliquas.html, and Large
Quasar Astrometric Catalogue666https://cdsarc.unistra.fr/viz-
bin/cat/J/A%2bA/624/A145 (LQAC), in the order of preference. The contribution
of two latter catalogs is small. The data in these catalogs and data bases are
not always consistent and reliable. To mitigate this impact, the average
magnitude of $V,r$, $R$, and $i$ was used in this work. The magnitude
differences $Gaia$ $G$ minus OCARS for all 7179 common sources are shown in
Fig. 1. One can see that they can be both positive and negative in the
interval from about $-3^{m}$ to about $9^{m}$.

Figure 1: Differences between $Gaia$ $G$ and ground-based magnitudes for 7179
common sources between the $Gaia$ DR2 and OCARS catalogs.

The positive magnitude differences can generally be explained by the fact that
corresponding objects are extended galaxies hosting AGN observed by VLBI.
Their ground-based (OCARS) magnitudes are related to the integrated flux from
the entire galaxy or its wide central region, whereas $Gaia$ most probably
observes the brightest point-like center of the galaxy. Three typical objects
of this type are shown in Fig. 2. Therefore, positive magnitude difference is
mostly a trivial case.

Figure 2: Top row: three objects with large negative $Gaia$ minus OCARS
optical magnitude difference. They all are large galaxies. Bottom row: three
faint objects with large positive $G$–$R$ difference. The images are provided
by the Aladin Sky Atlas (https://aladin.u-strasbg.fr/).

To check this conclusion, the same data were re-organized and depicted in Fig
3, where the magnitude difference $G$–$R$ is shown as a function of $R$. One
can see that optically faint objects show relatively small magnitude
difference $Gaia$ minus OCARS, while bright objects show much large
differences. Most probably, this is a consequence of the $Gaia$ observing mode
for which the faint galaxies are observed as a single object, unlike large
(extended) galaxies. Detailed discussion of observation of galaxies with
$Gaia$ is given by de Souza et al. 2014.

Figure 3: Differences between $Gaia$ $G$ and ground-based $R$ magnitudes as
function of $R$.

More interesting is a case of negative magnitude difference, which is the
subject of a special investigation for each source that shows such a feature.
There may be various reasons for this:

  * •

The observed magnitude difference may be a result of wrong cross-
identification of the astrometric radio source with $Gaia$ object.

  * •

The observed magnitude difference may be a result of a source optical
variability. The photometry data in $Gaia$ and OCARS were generally made at
different epochs as discussed by Damljanović et al. 2017. Results of optical
monitoring of ICRF sources made by, e.g., Taris et al. 2016, showed the spread
of the brightness variations may exceeds two magnitudes.

  * •

The observed magnitude difference may be a result of wrong cross-
identification of the radio source with an optical object in one of the
catalogs contributed to OCARS. In the course of the present work about a half
of dozen of such cases was found.

Of course, the same considerations can be applied to positive $Gaia$ minus
OCARS magnitude differences.

##  3 CONCLUSION

The goal of this work was to investigate whether a comparison of the optical
magnitudes of astrometric radio sources with the magnitudes obtained from
ground-based (or other wide-field) observations can be useful to improve the
reliability of cross-identification of $Gaia$ objects with radio sources
included in VLBI astrometric catalogs. It was found that the direct comparison
of $Gaia$ and ground-based magnitudes can hardly be practical for this
purpose. A typical case is a bright galaxy for which VLBI and $Gaia$ positions
are measured for the optically and radio strong central point-like area (AGN),
whereas the ground-based magnitudes are related to the integral galaxy flux.

Therefore, comparison of the $Gaia$ and OCARS magnitudes cannot be used
straightforward for check of object cross-identification in $Gaia$ and VLBI
catalogs. However, in some cases, this may be useful to detect a wrong cross-
identification, especially in case of negative $Gaia$ minus OCARS magnitude
differences. Besides, this comparison allows us to identify possible
inconsistencies or even errors in a ground-based photometry data taken from
different, not always reliable, catalogs and data bases. In particular, in the
course of this work, several OCARS sources with erroneous magnitudes were
detected and corrected or flagged in OCARS.

In any case, a further deeper investigations in this direction may be useful
to improve the reliability of the object cross-identification in VLBI and
$Gaia$ catalogs.

Acknowledgments

This work has made use of data from the European Space Agency (ESA) mission
$Gaia$777https://www.cosmos.esa.int/gaia, processed by the $Gaia$ Data
Processing and Analysis
Consortium888https://www.cosmos.esa.int/web/gaia/dpac/consortium (DPAC).
Funding for the DPAC has been provided by national institutions, in particular
the institutions participating in the $Gaia$ Multilateral Agreement.

This research has made use of the SIMBAD database and Aladin Sky Atlas
operated at at the Centre de Données Astronomiques999https://cds.u-strasbg.fr/
(CDS), Strasbourg, France, and the SAO/NASA Astrophysics Data
System101010https://ui.adsabs.harvard.edu/ (ADS).

This research has made use of the SAO/NASA Astrophysics Data
System111111https://ui.adsabs.harvard.edu/ (ADS).

This work was partly supported by the Russian Government program of
Competitive Growth of Kazan Federal University.

The author is grateful to Sergey Klioner for useful discussion and to the
anonymous referee for suggestions on improving the manuscript.

References

de Souza, R. E., Krone-Martins, A., dos Anjos, S., Ducourant, C., Teixeira, R.
: 2014, Astron. Astrophys., 568, A124.

Damljanović, G, Taris, F., Andrei, A. : 2017, Astrometry and Astrophysics in
the Gaia sky, Proc. IAU, 330, 88.

Lindegren, L., Hernández, J., Bombrun, A., et al. : 2018, Astron. Astrophys.,
616, A2.

Liu, N., Lambert, S. B., Zhu, Z., Liu, J. C. : 2020, Astron. Astrophys., 634,
A28.

Makarov, V. V., Berghea, C. T., Frouard, J., Fey, A., Schmitt, H. R. : 2019,
Astrophys. J., 873, 132.

Malkin, Z. : 2018, Astrophys. J. Suppl. Series, 239, 20.

Mignard, F., Klioner, S., Lindegren, L., et al. : 2016, Astron. Astrophys.,
595, A5.

Petrov, L., Kovalev, Y. Y. : 2017, Mon. Not. R. Astron. Soc., 467, L71.

Taris, F., Andrei, A., Roland, J., Klotz, A., Vachier, F., Souchay, J. : 2016,
Astron. Astrophys., 587, A112.