management and curation of data, where data may be incomplete,properties may have multiple values, and the data schema may besubject to frequent change. This need for flexibility has given riseto the adoption of graph-based models for various applications,including Facebooks’s Open Graph Protocol, Google’s KnowledgeGraph, schema.org, and so forth. In other applications, users mayfurther have control over the schema, allowing not only to editnodes and edges in the graph, but also to define new types of nodesand edges; an example of such a scenario is the Wikidata knowledgegraph [39] – hosted by the Wikimedia Foundation and seen as asource of data to compliment Wikipedia – where users can add newproperties and types that can be used to define further data.While graphs enable increased levels of flexibility in terms ofhow a given data collection is managed and curated, on the flip-side,this flexibility comes with the inevitable cost of higher levels of het-erogeneity, where involved entities may be defined in diverse ways,data may have various levels of (in)completeness, etc. Conceptuallyunderstanding the current state of a knowledge graph – in terms ofwhat data it contains, what it is missing, how it can be effectivelyqueried, what has changed recently, etc. – is thus a major challenge:it is unclear how to distil an adequate, high-level description thatcaptures an actionable overview of knowledge graphs.We thus need well-founded methodologies to make sense ofknowledge graphs, where an obvious approach is to define somenotion(s) of schema for such graphs. The traditional approach inthe Semantic Web has been what Pham and Boncz [31] call theschema first approach: define the schema that the data should follow.The most established language for specifying semantic schemata isRDF Schema (RDFS) [9], which allows for defining the semanticsof terms used in the RDF [37] graph-based model; however, suchan approach does not help to understand the data that an RDFgraph contains since defined terms need not be used and furtherundefined terms may be used in such data. More recently, validatingschemata – such as the Shapes Constraint Language (SHACL) [27] –have been proposed that allow for defining various constraints thatcompliant RDF graphs must follow; however, the purpose of suchschemata is to constrain and validate graphs rather than to gain anunderstanding of the legacy data contained in a given graph.An alternative to the schema first approach is the schema lastapproach [31], which foregoes an upfront schema and rather letsthe data evolve naturally; thereafter, the goal is to understand whatthe legacy graph data contain by extracting high-level summariesthat characterise the graph, resulting in a data-driven schema. Dueto a growing realisation that traditional notions of schema arenot enough, various works have emerged on this topic, trying toextract implicit structure from – and ultimately make sense of –diverse RDF graphs [1, 2, 10–14, 19, 20, 25, 31, 32, 36]. Such works11750用形式概念分析对语义Web知识图进行动态建模0Larry González 德累斯顿电子推进中心（cfaed）德累斯顿工业大学，德国larry.gonzalez@tu-dresden.de0Aidan Hogan 语义Web研究中心DCC，智利大学ahogan@dcc.uchile.cl0摘要0在本文中，我们提出了一种受形式概念分析（FCA）启发的大规模异构知识图的新型数据驱动模式。我们首先提取与各个实体相关联的属性集合；这些属性集合（也称为特征集）用基于集合包含关系的基于格的方式进行注释，并形成描述知识图的自然分层结构。然后，我们提出了一种在这种模式格上的代数，它允许计算格之间的差异（例如，总结从一个知识图版本到另一个版本的变化），将差异添加到格中（例如，预测未来的变化），等等。虽然我们认为这种格结构（及相关的代数）可能有各种应用，但我们目前专注于对知识图的动态行为进行建模和预测的用例。在这方面，我们实例化并评估了我们的方法，分析了Wikidata知识图的版本在11周内的变化情况。我们提出了从Wikidata构建基于格的模式的算法，并评估了它们的效率和可扩展性。然后，我们评估了所得到的模式对于预测知识图在未来版本中的演变的使用。0CCS概念0• 信息系统 → 语义Web语言；基于图的数据库模型；0关键词0语义Web，模式，知识图，动态，FCA0ACM参考格式：Larry González和AidanHogan。2018年。用形式概念分析对语义Web知识图进行动态建模。在WWW2018：2018年Web会议上，2018年4月23日至27日，法国里昂。ACM，纽约，美国，10页。https://doi.org/10.1145/3178876.318601601 引言0本论文发表在知识共享署名4.0国际许可证（CC BY4.0）下。作者保留在个人和公司网站上传播作品的权利，并附上适当的归属。WWW2018，2018年4月23日至27日，法国里昂，© 2018IW3C2（国际万维网会议委员会），根据知识共享CC BY 4.0许可证发布。ACM ISBN978-1-4503-5639-8/18/04。https://doi.org/10.1145/3178876.31860160跟踪：Web内容分析，语义和知识WWW 2018年4月23日至27日，法国里昂11760考虑到各种应用，无论是帮助用户编写查询，构建浏览界面，优化查询处理，识别所涵盖的抽象主题，建模拓扑变化等等。在本文中，我们提出了一种从这些图中计算数据驱动模式的另一种方法；更具体地说，我们的方法受到形式概念分析（FCA）的启发，并基于图中所有实体的属性（出边标签）产生一个“概念”的格子（也称为特征集）。我们的方法的一个关键创新是提出了一个可以应用于非常大型、多样化的图结构知识库的FCA风格框架。为了验证由该框架提取的基于FCA的模式的实用性，作为我们的用例，我们研究了总结数据集动态和预测未来高级变化的问题。为了解决这个用例，我们提出了一个新颖的FCA风格格子代数，允许计算两个这样的模式之间的差异（通过减法运算符）并将这些差异添加到给定的模式中以投影未来的模式级变化（通过附加运算符）。我们应用这个框架来计算11个版本的Wikidata知识图的格子，评估它们对于预测未来的高级变化的适用性。我们选择Wikidata是因为：（1）它提供了我们可以用来评估预测的每周版本的历史记录，（2）它由成千上万的用户编辑，意味着每周都会观察到重大变化，（3）数据集的规模和多样性提供了（据我们所知）对FCA风格技术的前所未有的挑战，需要新的方法。我们的结果表明，所提出的框架可以适用于像Wikidata这样的数据集，并且可以提供比使用线性模型的基准方法更好的预测。0贡献：我们的主要贡献如下：（1）我们提出了应用FCA风格技术到RDF图中的形式上下文和概念的概念。（2）为了提高可扩展性，我们提出使用一个中间格子，不会实现完整的格子，而是允许概念被惰性计算（按需计算）。（3）我们提出了一个代数，用于（a）基于我们的格子结构计算两个版本的RDF图之间的高级差异，以及（b）添加格子以预测未来的变化。（4）我们通过提取11个每周版本的Wikidata知识图的格子来评估我们的方法，展示性能和可扩展性结果，并评估预测的质量。0论文概述：第2节介绍了数据驱动模式、FCA技术和语义Web动态的相关工作。第3节介绍了与RDF和FCA相关的初步知识。第4节介绍了我们从RDF图中提取格子的框架，第5节讨论了具体的算法。第6节描述了计算格子之间差异和预测未来变化的代数。第7节介绍了我们的评估，第8节总结。02 相关工作0我们现在提供了与RDF的数据驱动模式、语义Web上的FCA和知识图动态建模相关的最相关工作的概述。0数据驱动的RDF模式：许多工作提出了从RDF图中总结、概述和/或计算模式的方法（与为RDF图定义一个预先的模式相反）0根据RDFS [9]和SHACL[27]标准）。一种常见的方法是基于各种概念的商图[12]计算图摘要，该概念首先在输入图中的节点上定义一个等价关系，然后由该关系引起的每个节点分区被认为是商图中的一个节点；这样的等价关系可以根据等价关系的定义来定义，例如，双模拟[10, 14, 32,36]，节点类型[11, 19, 20,25]，同构[12]等等。这种商图的一个有趣的特性是它们可以（通常）保留原始图的某种连通性的概念。其他方法则考虑从图中提取元数据摘要，例如VoID描述[4] [8, 23, 29,34]；然而，这些方法往往提取统计描述而不是数据中固有的结构（虽然VoID的数据集分区[4]确实捕捉到了一些结构的概念）。从RDF数据集中计算固有结构的其他方法基于聚类[1]，潜在主题分析[7]，关联规则挖掘[2]，n元关系[31]，原型[13]，形式概念分析[6, 16,22]等等。我们提出的方法属于后一种类别，将形式概念分析应用于RDF图；我们现在更详细地讨论这些工作。0语义Web上的FCA：我们的提案受到形式概念分析（FCA）社区提出的方法的启发[33，40]。事实上，我们远非第一批考虑将FCA技术应用于语义Web环境的作者，其中我们可以提到Rouane-Hacene等人的关于关系概念分析（RCA）的提案[35]，其中FCA被单独应用于不同类型的实体以创建每种类型的概念格；Alam等人关于应用FCA来帮助探索和评估链接数据集的完整性的工作[3]；Kirchberg等人对应用于链接数据集的FCA算法性能的评估[26]；以及Formica [21]和d'Aquin和Motta[15]的工作，用于在语义Web数据集上实现搜索和问答应用程序。然而，虽然这些论文中的一些确实处理了与我们自己类似的数据集（例如DBpedia），但我们观察到的所有论文都将FCA应用于数据集的封闭子集，通常包括特定类型的实体子集。例如，在Kirchberg等人的性能论文中[26]，考虑的最大数据集包含大约35,000个实体，而我们考虑的是对完整（真实）的Wikidata进行FCA风格的分析，该数据集描述了数千万个实体。将搜索扩展到更一般的大规模FCA方法，我们可以找到Xu等人的工作[41]和Krajca和Vychodil[28]，他们（像我们一样）建议使用分布式MapReduce框架来提高FCA过程的可扩展性；然而，Xu等人考虑的最大数据集包含大约100,000个实体，而Krajca和Vychodil[28]考虑的最大数据集包含大约33,000个实体，仍然远远低于我们的目标规模。因此，至少就我们所知，没有任何工作考虑将FCA应用于像Wikidata这样多样且庞大的数据集；事实上，正如我们将在后面讨论的那样，典型的FCA方法需要适应以适应这样的规模。0在语义Web上建模动态行为：我们在Wikidata上应用FCA的主要用例是对数据集的动态行为进行建模并预测未来的变化。因此，在我们的相关工作中，我们可以考虑与语义Web知识图谱中变化建模相关的工作0跟踪：Web内容分析，语义和知识WWW 2018年4月23日至27日，法国里昂4FCA FOR RDF GRAPHS4.1RDF FC-LatticeExample 4.1. Consider the following example RDF graph G (inTurtle syntax) containing five subjects and four properties.ex:UT ex:name "U Thurman"; ex:star ex:Gattaca .ex:GO ex:name "G Orwell"; ex:writer ex:1984 .ex:AK ex:name "A Kurosawa"; ex:director ex:Ikiru, ex:Ran .ex:PD ex:name "PK Dick"; ex:writer ex:Ubik, ex:Valis .ex:CE ex:name "C Eastwood"; ex:director ex:Sully;ex:star ex:Unforgiven, ex:Tightrope ;Track: Web Content Analysis, Semantics and KnowledgeWWW 2018, April 23-27, 2018, Lyon, France11770在这个领域中，我们可以考虑Umbrich等人的工作[38]，他们定义了链接数据中各种类型的实体级和文档级变化，并查看这些变化是否遵循泊松分布。Käfer等人后来提出了动态链接数据观察站，以收集从Web中爬取的LinkedData的每周快照；他们通过分析数据集的各个方面，将网站按照观察到的变化类型进行分类，无论是批量变化、连续变化还是静态数据集。Käfer等人的观察站收集的数据后来被Dividino等人用于改进缓存维护等后续工作[18]。就我们所知，然而，没有任何工作尝试预测这些数据集中的高级变化；相反，这类工作的重点是对历史动态进行建模和分析。03初步0为了给论文提供一个正式的框架，我们专注于RDF数据模型。然而，这里开发的技术和结果可以推广到其他图形结构化数据模型[5]。0RDF术语和图形：RDF是一种基于三个不相交术语集的图形结构模型：IRIs（I），文字（L）和空白节点（B）。涉及这些术语的声明可以组织成RDF三元组（s，p，o）∈IB×I×IBL，其中s称为主题，p称为谓词，o称为对象。然后，RDF图G是一组有限的RDF三元组，其中三元组（s，p，o）∈G可以被视为边缘的0在有向边标记图中，将s p −→o表示为一种形式。谓词位置中使用的术语称为属性。我们使用实体一词来指代由图的主语引用的现实世界对象。给定一个RDF图G，对于•∈{s, p,o}，我们用π•(G)表示出现在G中特定三元组位置的术语的投影；例如，πs(G) := {s | �p, o : (s, p, o)∈G}。0正式上下文和概念：正式概念分析（FCA）是一种从实体集合和它们的属性中提取概念层次结构的方法[40]。更具体地说，该方法是基于从正式上下文中提取正式概念。正式上下文是一个三元组X = (E, A,I)，其中E是一组实体，2A是一组属性，I�E×A是关联关系：一组成对的集合，当且仅当属性a对实体e定义时，(e,a)∈I。为了定义正式概念，我们给出一些初始定义。给定一个正式上下文X = (E, A, I)，对于实体子集F�E，令�F�X := {a∈A | �f∈F : (f,a)∈I}；相反，对于属性子集B�A，令�B�X := {e∈E | �b∈B : (e,b)∈I}。因此，对于一组实体，�∙�取它们共享的所有属性的集合，而对于一组属性，�∙�取它们共享的所有实体的集合。然后，正式概念是一个二元组(F, B)，其中：(1) F�E，(2) B�A，(3) �F�X = B，且(4) F =�B�X。在正式概念(F,B)中，集合F称为概念的范围，而集合B称为概念的意图。在诱导概念层次结构方面，设(F1, B1)和(F2, B2)是正式上下文X = (E, A,I)的两个正式概念。我们定义基于意图的包含关系的偏序≤，使得(F1, B1)≤(F2, B2)当且仅当B1�B2。令C表示所有01 我们使用IB作为I∪B的简写。2在FCA文献中，更常见的是引用一组对象；我们避免使用这个术语，因为它与RDF三元组中的对象的概念冲突。0在X中的正式概念中，(E,�E�X)用作底部上下文，表示所有实体共享的属性，而(�A�X,A)用作顶部概念(�)，表示使用所有属性的实体；由于对于任意的c∈C，都有⊥≤c≤�，我们可以说(C,≤)形成一个完全格，称为概念格。我们注意到，在实践中�E�X和�A�X可能是空集，并且特别是�A�X往往是空的。此外，我们注意到，通过考虑基于实体在范围内的集合包含关系的双重偏序，也可以实现相同的特性；然而，在这里我们将关注基于属性的顺序。此外，考虑到与C相关的≤顺序的非传递版本将是有用的，我们用�表示，使得c�c′′当且仅当c
下载后可阅读完整内容，剩余1页未读，立即下载
