知識グラフを対象とした初歩的な検索技術

この記事は[情報検索・検索技術 Advent Calendar 2022](https://adventar.org/calendars/7389)の21日目の記事です。また、[ナレッジグラフ Advent Calendar 2022](https://qiita.com/advent-calendar/2022/knowledgegraph)の21日目の記事です。

検索に関わることなら何でもOKということで、知識グラフ（ナレッジグラフ: KG）を対象とした検索について初歩的な記事を書かせていただきます。すでにこういった記事はたくさんあるとは思いますが、情報が埋もれやすい昨今ですので、一部最新情報を含めて改めてまとめてみました。急いで書きなぐったので誤字脱字等ご容赦ください。。。

対象読者
・KG初心者
・情報検索でKGを扱ってみたい人

# 目次
- [ナレッジグラフとは](#ナレッジグラフとは)
- [代表的なナレッジグラフ](#代表的なナレッジグラフ)
- [SPARQLを使った検索](#sparqlを使った検索)
    - [DBpedia検索](#dbpedia検索)
    - [Wikidata検索](#wikidata検索)
    - [ナレッジグラフ推論チャレンジ【実社会版】](#ナレッジグラフ推論チャレンジ実社会版)

# ナレッジグラフとは

ここ数年ずっと米ガートナー社の[ハイプ・サイクル for AI](https://www.gartner.com/en/articles/what-s-new-in-artificial-intelligence-from-the-2022-gartner-hype-cycle)で過度な期待のピーク期に居座っており、バズワード的に浸透していますが、古くからある、意味ネットワーク、オントロジーなどの知識表現と本質的にはかわりません（もちろん個々に細かな特徴はあります）。W3C標準のRDFを指していたり、もっと緩いCSV程度のものを指していることもあり混沌としています。
2012年の[Google Knowledge Graph](https://blog.google/products/search/introducing-knowledge-graph-things-not/)をきっかけに単語が広まり、明確な定義がされないまま広まっていきましたが、いくつかの論文([Ehrlinger et al. 2016](https://ceur-ws.org/Vol-1695/paper4.pdf), [Hogan et al. 2022](https://doi.org/10.1145/3447772))で定義をしています。国内では、3年前にセマンティックウェブとオントロジー研究会で議論しています（*[知識グラフの定義についての議論](https://github.com/KnowledgeGraphJapan/Tutorial/blob/master/What_Is_KG.md)*）。Qiitaでも3年前に@MeguruMokkeさんがよく調べてくださっていたのを見つけました（*[Knowledge Graph とはなにか](https://qiita.com/MeguruMokke/items/e707d231d75db8057f96)*）。

最近では今年出版されたHoganらの定義が最も無難かなと思います。簡単に訳したものがこちらです。

*実世界の知識を蓄積し、伝達することを目的とした「データのグラフ」であり、そのノードは関心のあるエンティティを表し、エッジはこれらのエンティティの間の様々な関係を表す。*
*その「データのグラフ」はグラフベースのデータモデルに準拠し、エッジラベル付き有向グラフ、異種グラフ、プロパティグラフなどがある。*

この記事では、このナレッジグラフのデータモデルとして特に&lt;subject, predicate, object&gt;の三つ組でエンティティの関係性を表現するResource Description Framework (RDF)を扱います。

RDFに関する初歩的な説明は下記の私のスライドをご覧いただけますと幸いです。
下記は[ナレッジグラフ推論チャレンジ【実社会版】技術勉強会](https://github.com/KnowledgeGraphJapan/KGRC-ws-2022)で紹介したスライドです。ちなみにその他のスライドも[こちらのGitHubリポジトリ](https://github.com/KnowledgeGraphJapan/KGRC-ws-2022)で公開しています。
<br>
<script async class="speakerdeck-embed" data-id="161040000e6140a0acdead6f14101564" data-ratio="1.77777777777778" src="//speakerdeck.com/assets/embed.js"></script>
<br>

（追記）[動画がYouTubeで公開されました](https://www.youtube.com/watch?v=Ww6gwOsm-Dg&list=PLHaRK-B0LUwhany_uYrCONI5vyGI0fboj)

この記事でも少し解説すると、RDFではすべての情報を主語、述語、目的語の三つ組（トリプルと呼ぶ）で表現します。RDFはもともとWeb上でのデータの共有を意図しているので、全てのリソースに一意なUniform Resource Identifier ([URI](https://ja.wikipedia.org/wiki/Uniform_Resource_Identifier))を付与します。

- リソース
    - 主語や目的語として使われるもの。一意なURIでグラフのノードに相当。
- プロパティ
    - 述語として使われるもの。グラフのエッジに相当。
- リテラル
    - 数値や文字列等。目的語としてしか使用できず、URIを持たない。

## 代表的なナレッジグラフ
すでに様々なナレッジグラフが誰でも利用できるように公開されており、特に[ある条件](https://www.slideshare.net/KoujiKozaki/linked-datalod)を満たしているものはLinked Open Data (LOD)と呼ばれ、高い利便性と再利用性を有しています。

- [DBpedia](https://www.dbpedia.org/)
    - 主にWikipediaのInfoboxを基に構築されたLOD。
- [DBpedia Japanese](https://ja.dbpedia.org/)
    - Wikipedia日本語版から構築されたDBpedia。
- [Wikidata](https://www.wikidata.org/wiki/Wikidata:Main_Page)
    - データ版Wikipedia。データそのものをWikipediaのように編集することができる。
- [YAGO](https://yago-knowledge.org/)
    - Yet Another Great Ontology。Wikipediaなどから構築された大規模オントロジー。
- [GeoNames](https://www.geonames.org/)
    - 地名のLOD
- [LinkedGeoData](http://linkedgeodata.org/)
    - OpenStreetMapを基に構築された地理空間情報のLOD。
- [Bio2RDF](https://bio2rdf.org/)
    - ライフサイエンス分野の老舗LOD
- [ConceptNet](https://conceptnet.io/)
    - 一般的な単語のLOD
- [ジャパンサーチ](https://jpsearch.go.jp/)
    - 日本のデジタルアーカイブ

その他名前を挙げだしたらきりがないので、興味のある方は[LOD Cloud](https://lod-cloud.net/)をご覧ください。こちらにあるものも登録に一定の基準が設定されているので、世の中に存在するLODの一部になります。
国内のLODは[Linked Data API Navi](https://uedayou.net/ldapinavi/)によくまとめられています。

# SPARQLを使った検索
だいぶ前置きが長くなってしまいましたが、ここからが本題の検索に関する説明です。
SPARQLはRDFデータを検索する際に使用するにクエリ言語で、関係データベースにおけるSQLに相当します。
SPARQLの基礎的な説明も下記の私のスライドをご覧いただけますと幸いです。
下記は[ナレッジグラフ推論チャレンジ【実社会版】技術勉強会](https://github.com/KnowledgeGraphJapan/KGRC-ws-2022)で紹介したスライドなので、最後4スライドは[こちらのデータセット](https://github.com/KnowledgeGraphJapan/KGRC-RDF/tree/kgrc4si)を対象としたクエリです。
<br>
<script async class="speakerdeck-embed" data-id="1f916c382afc43f784336c99bf92a618" data-ratio="1.77777777777778" src="//speakerdeck.com/assets/embed.js"></script>
<br>

（追記）[動画がYouTubeで公開されました](https://www.youtube.com/watch?v=vJKgjkN068s&list=PLHaRK-B0LUwhany_uYrCONI5vyGI0fboj)

実例を見てもらったほうが早いと思うので、いくつか紹介します。

```sparql
# トリプルを100件取得する
SELECT ?s ?p ?o 
WHERE {
  ?s ?p ?o .
} LIMIT 100
```
こちらは、対象とするRDFデータから、主語?s（変数）、述語?p（変数）、目的語?o（変数）に当てはまるトリプルを検索し、各変数の値を100件まで取得するSPARQLクエリです。すなわち、全トリプルが該当し、そのうち100件を取得します。

それではもう少し複雑な例を見てみましょう。

## DBpedia検索

```sparql
# DBpedia内に含まれているアスリートの名前（日本語）と出生地（英語）を取得する
PREFIX dbo: <http://dbpedia.org/ontology/>
PREFIX rdf: <http://www.w3.org/1999/02/22-rdf-syntax-ns#>
PREFIX rdfs: <http://www.w3.org/2000/01/rdf-schema#>
SELECT DISTINCT ?label ?dp_label WHERE {
  ?s rdf:type dbo:Athlete ; rdfs:label ?label .
  OPTIONAL {?s dbo:birthPlace ?dp . ?dp rdfs:label ?dp_label . }
  FILTER(LANG(?label)="ja")
  FILTER(LANG(?dp_label)="en")
} limit 100
```

こちらは「DBpediaにあるアスリートの名前（日本語）と出生地（英語）を取得する」SPARQLクエリです。
ではDBpediaに対してSPARQLクエリを実行するにはどうしたらよいでしょうか？答えはSPARQLエンドポイントという検索窓口を使用します。
- https://dbpedia.org/sparql

こちらにブラウザでアクセスすると、クエリを入力するテキストエリアが確認できます。
ここに上記のSPARQLを貼り付けて「Execute Query」ボタンを押下すると、結果を確認できるはずです。
[実行結果を確認](https://dbpedia.org/sparql?default-graph-uri=http%3A%2F%2Fdbpedia.org&query=PREFIX+dbo%3A+%3Chttp%3A%2F%2Fdbpedia.org%2Fontology%2F%3E%0D%0APREFIX+rdf%3A+%3Chttp%3A%2F%2Fwww.w3.org%2F1999%2F02%2F22-rdf-syntax-ns%23%3E%0D%0APREFIX+rdfs%3A+%3Chttp%3A%2F%2Fwww.w3.org%2F2000%2F01%2Frdf-schema%23%3E%0D%0ASELECT+DISTINCT+%3Flabel+%3Fdp_label+WHERE+%7B%0D%0A++%3Fs+rdf%3Atype+dbo%3AAthlete+%3B+rdfs%3Alabel+%3Flabel+.%0D%0A++OPTIONAL+%7B%3Fs+dbo%3AbirthPlace+%3Fdp+.+%3Fdp+rdfs%3Alabel+%3Fdp_label+.+%7D%0D%0A++FILTER%28LANG%28%3Flabel%29%3D%22ja%22%29%0D%0A++FILTER%28LANG%28%3Fdp_label%29%3D%22en%22%29%0D%0A%7D+limit+100%0D%0A&format=text%2Fhtml&timeout=30000&signal_void=on&signal_unconnected=on)

プログラムからAPIとして使用するには、下記のパラメータを穴埋めしたURIをGETします。

```bash
https://dbpedia.org/sparql?query={SPARQLクエリのURIエンコード}&format={フォーマット}
```

フォーマットは
- text/html
- text/csv
- application/xml
- application/json
- ...

## Wikidata検索

WikidataのSPARQLエンドポイントではサンプルクエリが用意されているため、SPARQLを書く上で参考になるでしょう。
- https://query.wikidata.org/

左メニューのフォルダのアイコンから様々なSPARQLを試すことができます。
例えば猫の画像を取得するクエリはこちら。
```sparql
#猫（画像付き）
#defaultView:ImageGrid
SELECT ?item ?itemLabel ?pic
WHERE
{
?item wdt:P31 wd:Q146 .
?item wdt:P18 ?pic
SERVICE wikibase:label { bd:serviceParam wikibase:language "[AUTO_LANGUAGE],en" }
}
```

[実行結果を確認](https://query.wikidata.org/#%23%E7%8C%AB%EF%BC%88%E7%94%BB%E5%83%8F%E4%BB%98%E3%81%8D%EF%BC%89%0A%23defaultView%3AImageGrid%0ASELECT%20%3Fitem%20%3FitemLabel%20%3Fpic%0AWHERE%0A%7B%0A%3Fitem%20wdt%3AP31%20wd%3AQ146%20.%0A%3Fitem%20wdt%3AP18%20%3Fpic%0ASERVICE%20wikibase%3Alabel%20%7B%20bd%3AserviceParam%20wikibase%3Alanguage%20%22%5BAUTO_LANGUAGE%5D%2Cen%22%20%7D%0A%7D)

レベルアップして初心者の域を超えてしまいますが、複数のLODを横断的に検索して結果取得するSPARQLクエリを実行することもできます。ただし、検索先のSPARQLエンドポイントが[Federated Query](https://www.w3.org/TR/sparql11-federated-query/)に対応している必要があります。
*[Wikidata:SPARQL query service/Federated queries](https://www.wikidata.org/wiki/Wikidata:SPARQL_query_service/Federated_queries)*

```sparql
# イギリスの彫刻家をWikidataから検索し、その彫刻家の作品をジャパンサーチから検索する
PREFIX jps: <https://jpsearch.go.jp/term/property#>
SELECT DISTINCT ?name ?work_link ?work ?creatorLabel ?date
WITH {
  SELECT ?creator WHERE {
     VALUES ?citizenship {wd:Q145 wd:Q174193} . # UK, Britain & Ireland
    ?creator wdt:P6698 [];   # Only get things with a Japan Search ID
   wdt:P27 ?citizenship; wdt:P106 wd:Q1281618}    # sculptors
     } AS %creators
WHERE {
include %creators
  SERVICE <https://jpsearch.go.jp/rdf/sparql/> {
   ?jps_creator owl:sameAs ?creator . # convert Wikidata ID to Japan Search ID
    ?work schema:creator ?jps_creator .  # Works by this artist
    OPTIONAL {?work schema:name ?name }   # This will return separate names in English and Japanese names
    OPTIONAL {?work schema:dateCreated ?date}
    }
FILTER (lang(?name)="en")  # Show only the English name
BIND(URI( REPLACE(STR(?work), "/data/", "/item/") ) AS ?work_link)
SERVICE wikibase:label { bd:serviceParam wikibase:language "[AUTO_LANGUAGE],en". }
} ORDER BY ?date
```
[実行結果](https://query.wikidata.org/#PREFIX%20jps%3A%20%3Chttps%3A%2F%2Fjpsearch.go.jp%2Fterm%2Fproperty%23%3E%0ASELECT%20DISTINCT%20%3Fname%20%3Fwork_link%20%3Fwork%20%3FcreatorLabel%20%3Fdate%0AWITH%20%7B%0A%20%20SELECT%20%3Fcreator%20WHERE%20%7B%0A%20%20%20%20%20VALUES%20%3Fcitizenship%20%7Bwd%3AQ145%20wd%3AQ174193%7D%20.%20%23%20UK%2C%20Britain%20%26%20Ireland%0A%20%20%20%20%3Fcreator%20wdt%3AP6698%20%5B%5D%3B%20%20%20%23%20Only%20get%20things%20with%20a%20Japan%20Search%20ID%0A%20%20%20wdt%3AP27%20%3Fcitizenship%3B%20wdt%3AP106%20wd%3AQ1281618%7D%20%20%20%20%23%20sculptors%0A%20%20%20%20%20%7D%20AS%20%25creators%0AWHERE%20%7B%0Ainclude%20%25creators%0A%20%20SERVICE%20%3Chttps%3A%2F%2Fjpsearch.go.jp%2Frdf%2Fsparql%2F%3E%20%7B%0A%20%20%20%3Fjps_creator%20owl%3AsameAs%20%3Fcreator%20.%20%23%20convert%20Wikidata%20ID%20to%20Japan%20Search%20ID%0A%20%20%20%20%3Fwork%20schema%3Acreator%20%3Fjps_creator%20.%20%20%23%20Works%20by%20this%20artist%0A%20%20%20%20OPTIONAL%20%7B%3Fwork%20schema%3Aname%20%3Fname%20%7D%20%20%20%23%20This%20will%20return%20separate%20names%20in%20English%20and%20Japanese%20names%0A%20%20%20%20OPTIONAL%20%7B%3Fwork%20schema%3AdateCreated%20%3Fdate%7D%0A%20%20%20%20%7D%0AFILTER%20%28lang%28%3Fname%29%3D%22en%22%29%20%20%23%20Show%20only%20the%20English%20name%0ABIND%28URI%28%20REPLACE%28STR%28%3Fwork%29%2C%20%22%2Fdata%2F%22%2C%20%22%2Fitem%2F%22%29%20%29%20AS%20%3Fwork_link%29%0ASERVICE%20wikibase%3Alabel%20%7B%20bd%3AserviceParam%20wikibase%3Alanguage%20%22%5BAUTO_LANGUAGE%5D%2Cen%22.%20%7D%0A%7D%20ORDER%20BY%20%3Fdate)

## ナレッジグラフ推論チャレンジ【実社会版】

せっかくなので、紹介したスライドの主題だった[ナレッジグラフ推論チャレンジ【実社会版】](https://challenge.knowledge-graph.jp/2022/)のSPARQLエンドポイントにもクエリを投げてみます。
「ナレッジグラフ推論チャレンジ【実社会版】」自体の説明資料は[こちら](https://github.com/KnowledgeGraphJapan/KGRC-ws-2022/blob/main/20221115Seminer.pdf)。

- http://kgrc4si.home.kg:7200/
    - リポジトリはKGRC4SIv3を選択してください

このナレッジグラフは、仮想空間内での日常生活行動シミュレーションの動画データの内容を記しています。より詳細な説明は[こちら](https://github.com/KnowledgeGraphJapan/KGRC-RDF/tree/kgrc4si)。

このナレッジグラフから、キャラクターによく掴まれているオブジェクトを検索します。

```sparql
# よく掴まれているオブジェクト
PREFIX ho: <http://www.owl-ontologies.com/VirtualHome.owl#>
PREFIX rdfs: <http://www.w3.org/2000/01/rdf-schema#>
PREFIX : <http://example.org/virtualhome2kg/ontology/>
PREFIX dcterms: <http://purl.org/dc/terms/>
PREFIX ac: <http://example.org/virtualhome2kg/ontology/action/>
select ?name (count(?object) AS ?count) where { 
	?objectClass rdfs:subClassOf :Object .
    ?object a ?objectClass ;
            rdfs:label ?label ; 
            dcterms:identifier ?id .
    ?event ho:object ?object .
    ?event :action ac:grab .
    BIND(concat(?label, ?id) AS ?name)
} group by ?object ?name order by desc(count(?object))
```
[実行結果を確認](http://kgrc4si.home.kg:7200/sparql?name=&infer=true&sameAs=false&query=PREFIX%20ho%3A%20%3Chttp%3A%2F%2Fwww.owl-ontologies.com%2FVirtualHome.owl%23%3E%0APREFIX%20rdfs%3A%20%3Chttp%3A%2F%2Fwww.w3.org%2F2000%2F01%2Frdf-schema%23%3E%0APREFIX%20%3A%20%3Chttp%3A%2F%2Fexample.org%2Fvirtualhome2kg%2Fontology%2F%3E%0APREFIX%20dcterms%3A%20%3Chttp%3A%2F%2Fpurl.org%2Fdc%2Fterms%2F%3E%0APREFIX%20ac%3A%20%3Chttp%3A%2F%2Fexample.org%2Fvirtualhome2kg%2Fontology%2Faction%2F%3E%0Aselect%20%3Fname%20(count(%3Fobject)%20AS%20%3Fcount)%20where%20%7B%20%0A%09%3FobjectClass%20rdfs%3AsubClassOf%20%3AObject%20.%0A%20%20%20%20%3Fobject%20a%20%3FobjectClass%20%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20rdfs%3Alabel%20%3Flabel%20%3B%20%0A%20%20%20%20%20%20%20%20%20%20%20%20dcterms%3Aidentifier%20%3Fid%20.%0A%20%20%20%20%3Fevent%20ho%3Aobject%20%3Fobject%20.%0A%20%20%20%20%3Fevent%20%3Aaction%20ac%3Agrab%20.%0A%20%20%20%20BIND(concat(%3Flabel%2C%20%3Fid)%20AS%20%3Fname)%0A%7D%20group%20by%20%3Fobject%20%3Fname%20order%20by%20desc(count(%3Fobject)))

このように、LOD化されたナレッジグラフは基本的にSPARQLエンドポイントを設置しているため、SPARQLクエリを使用して欲しいデータを検索して取得できます。あとは自由自在にSPARQLをいじくり回して複雑な検索をかけてみるとよいでしょう。

本当は推論のところまで書きたかったですが、力尽きたのでここまでとさせていただきます。時間ができたら続編を書きたいと思います。

情報検索あるいはナレッジグラフに興味のある読者の皆様の何かの参考になりましたら幸いです。