[Paper Review] Knowledge Graphs

1. KG의 정의

• A graph of data intended to accumulate and convey knowledge of the real world, whose nodes represent entities of interest and whose edges represent relations between these entities

2. KG를 위한 base model

2.1. data graphs ↔ DB

• 기존에는 우리가 DB로 데이터를 정리했는데 데이터는 친절하지 않고 DB로 구축하게 되면 스키마를 수정하고 추가하는데 시간과 비용이 많이 듦
• 관계가 부족하고 자주 바뀌는 데이터를 다룰 때에는 data graph가 더 유연함
• 현실의 데이터는 불완전하고 변형되는 데이터가 많기 때문에 data graph로 구축하는 편이 더 효율적

1. data graph 1 : Directed edge-labelled graphs
   • 노드 집합과 해당 노드 간의 방향성 레이블 엣지 집합으로 정의
     • 노드집합

       1. KG의 정의

2. KG를 위한 base model

2.1. data graphs ↔ DB

• 기존에는 우리가 DB로 데이터를 정리했는데 데이터는 친절하지 않고 DB로 구축하게 되면 스키마를 수정하고 추가하는데 시간과 비용이 많이 듦
• 관계가 부족하고 자주 바뀌는 데이터를 다룰 때에는 data graph가 더 유연함
• 현실의 데이터는 불완전하고 변형되는 데이터가 많기 때문에 data graph로 구축하는 편이 더 효율적

1. data graph 1 : Directed edge-labelled graphs

   • 노드 집합과 해당 노드 간의 방향성 레이블 엣지 집합으로 정의

     • 노드집합
       
     • 노드 간의 방향성 레이블 엣지 집합

   • 그래프에 새로운 정보를 추가하는 것은 새 노드와 엣지를 추가하는 것

   • 불완전한 정보는 특정 엣지를 생략

   

2. data graph 2 : Heterogeneous graphs

   • 각 노드와 엣지에 하나의 타입이 할당된 그래프
   • 일대일 관계만 지원하지 않음

3. data graph 3 : Property graphs

   • 더 복잡한 관계를 모델링할 때 추가적인 유연성을 제공하기 위해 도입
   • 노드와 엣지에 추가 정보(속성)을 붙일 수 있는 그래프
   • 노드와 엣지에 label뿐 아니라 property-value pairs까지 붙일 수 있는 더 유연한 그래프
   • 관계가 복잡해질 때, 그 관계를 설명하기 위해 별도 노드를 많이 만들지 않고도 정보를 붙일 수 있게 함
   • 모델(그래프 구조)을 덜 복잡하게 만듦

4. data graph 4 : Graph dataset

   • 그래프 여러 개를 한꺼번에 관리하는 방식
   • named graphs 여러 개 + default graph 한 개
   • RDF(Resource Description Framework) dataset

2.2. Querying

• 그래프에서 원하는 정보를 어떻게 찾을까?

1. Querying 1 : Graph patterns

   • 그래프 안에서 어떠한 모양의 연결을 찾아라 하는 질의

   1. Querying 2 : Complex graph patterns

      • 기본 graph pattern 하나만 찾는 데서 끝나지 않고, 그 결과들을 표처럼 조합해서 더 복잡한 질의를 만드는 방식
      • graph pattern이 만든 결과표에 relational algebra(관계대수, 집합론과 1차 논리에 기반하여 관계로 표현된 데이터를 취급하는 대수적인 연산 체계)를 적용해서 더 복잡한 query를 만듦
      • relational algebra

        • unary operators

          • 입력 table 1개를 받는 연산
            • projection (π): 컬럼 일부만 남김
            • selection (σ): 조건에 맞는 행만 남김
            • renaming (ρ): 컬럼 이름 바꿈

        • binary operators
          - 입력 table 2개를 받는 연산
          - union (∪): 두 결과를 합침
          - difference (-): 첫 번째에서 두 번째를 뺌
          - join (⋈ / Z): 공통 조건으로 두 결과를 이어 붙임

          

   2. Querying 3 : Navigational graph patterns

      • 그래프에서 한 단계 관계만 보는 게 아니라, 여러 단계를 따라가며 연결 경로(path)까지 질의하는 방식
      1. path experssion
      • 경로를 표현하는 식
        • bus
          → bus edge 한 번
        • bus*
          → bus edge를 0번 이상 반복
        • bus | flight
          → bus 또는 flight
        • r1 · r2
          → r1 다음에 r2
        • r^-
          → relation을 역방향으로 따라가기
      1. regular path query
      • (x, r, y) 꼴
        • x = 시작 노드(또는 변수)
        • r = path expression
        • y = 도착 노드(또는 변수)
      • (Arica, bus*, ?city)
        → Africa에서 bus를 타고 0번 이상 갈 수 있는 city들을 찾아라

      

      

3. SCHEMA, IDENTITY, CONTEXT

• 지식 축적을 위한 추가 구조를 제공하는 스키마, 동일성 및 컨텍스트와 관련된 데이터 그래프의 다양한 개선 및 확장

3.1. Schema

• 데이터를 어떤 틀로 정리하고 이해할 지 정한 구조도
• 그래프의 의미 규칙집

1. Semantic Schema

   • 그래프 안에서 쓰는 단어들(class, relation)가 무슨 뜻인지 정해주는 의미 규칙
   • 그래프에서 쓰는 high-level terms의 meaning을 정의 → reasoning을 가능하게 함
   1. Subclass
      • 어떤 클래스가 더 큰 클래스의 하위 개념
   2. Subproperty
      • 어떤 relation이 더 일반적인 relation의 하위 관계
   3. domain
      • 어떤 relation이 어디서 시작해야 하는지
   4. range
      • 어떤 relation이 어디로 가야 하는지

   

   

   1. Validating Schema

      • 그래프가 형식적으로 잘 들어왔는지 검사하는 규칙집
      • 제약을 정의해서 그래프를 검사
      • 기존 데이터를 검증하는데 목적이 있음

      

   2. Emergent Schema

      • 데이터 그래프 자체에서 숨어 있는 구조를 자동으로 뽑아낸 스키마
      • 사람이 미리 안정해도 자동으로 데이터에서 구조를 발견하는 방식
      1. quotient graph
         • 비슷한 역할을 하는 노드들을 묶어서 만든 하나의 대표 그래프

   3.2. Identity

   • 그래프 안의 어떤 노드가 현실 세계의 정확히 누구/무엇을 가리키는 정하는 문제
   • 예를 들어서 지원이 사람의 이름 지원인지, 돕다의 지원인지, 원서를 넣는 지원인지 모름!
   • 같은 이름 충돌 방지 / 같은 대상을 서로 연결
   1. Persistent identifiers
      • 시간이 지나도 바뀌지 않도록 만든, 오래 유지되는 고유 식별자
      • 이름만 같다고 같은 대상이 되면 안됨
      • 처음부터 헷갈리지 않게 이름 짓기
   2. External identity links
      • 내 그래프의 어떤 노드와, 외부 그래프의 어떤 노드가 같은 대상이라고 연결해주는 링크
      • 서울 = 서울특별시
      • 이미 다른 이름을 쓰는 것들을 사후에 연결
   3. Datatypes
      • 그래프 안의 값이 무슨 종류의 값인지 정해줌
   4. Lexicalisation
      • 그래프의 노드에 사람이 읽을 수 있는 이름, 별칭, 설명 같은 언어 정보를 붙임
   5. Existential nodes
      • 어떤 대상이 분명히 존재하긴 하는데, 아직 그게 정확히 무엇인지 모를 때 쓰는 익명 노드

   3.3. Context

   • 어떤 사실이 어떤 조건/관점/범위에서 참
   • scope of truth
   • 문맥을 명시적으로 만들면 데이터를 다양한 관점에서 해석할 수 있게 함
   • 예를 들어서 2016년에 내가 고등학생이었다는건 참, 하지만 지금은 아님

   1. Direct representation

      • context도 그냥 데이터처럼 그래프 안에 직접 작성
      • 같은 edge들이 어느 시간 범위에서 참인지를 나타냄 → temporal context

   2. Reification

      • 문장 자체를 다시 하나의 대상으로 만들어서, 그 문장에 대해 말함
      • 관계 자체를 하나의 노드처럼 끄집어내서 그 관계에 설명을 붙이는 방법
      1. Higher-arity representation
         • 이진 관계만으로는 context를 붙이기 어려움 → 더 많은 항을 가진 구조로 표현
         • 관계 + context를 한 묶음으로 더 풍부하게 표현
      2. Annotations
         • context에 자동 reasoning/query를 하는 방법
         • context를 숫자/구간/가중치처럼 붙여서, 기계가 자동 계산할 수 있게 만드는 방식

4. Deductive Knowledge(연역적 지식)

• 이미 알고 있는 사실과 의미 규칙으로부터, 논리적으로 따라오는 새 사실을 도출하는 방법

  1. data graph → 사실 저장
  2. semantic schema/ontology → 의미 해석
  3. deductive knowledge → 새 사실 추론 ⇒ 여기서 바로 reasoning이 가능해져 진정한 KG가 됨

• 사람은 죽는다 + 소크라테스는 사람이다 ⇒ 소크라테스는 죽는다

4.1 Ontologies

• 추론을 하려면 쓰는 단어의 의미를 정확히 파악
• 어떤 용어가 그 도메인 안에서 무엇을 의미하는지 형식적으로 표현한 것
• 모델링을 guide
  • 데이터를 어떻게 모델링할 지 guide
• 추론을 자동화
• ontology language
  • OWL(Web Ontology Language) → RDF와 호환되는 대표 ontology 언어
  • OBOF(Open Biomedical Ontologies Format)

1. Interpretations
   • 그래프를 무슨 뜻으로 읽을 것인가
   • domain graph : 현실 세계를 나타내는 그래프
   • mapping : 데이터 그래프와 실제 엔티티와 관계의 대응 관계
   • 기본 가정
     • CWA(Closed World Assumption) : 그래프에 없으면 거짓
     • OWA(Open World Assumption) : 그래프에 없다고 해서 거짓이라 단정 X
     • UNA(Unique Name Assumption) : 이름이 다르면 다른 대상
     • NUNA(No Unique Name Assumption)
   • OWL은 OWA + NUNA
2. Individual
   • 개별 대상에 대하 ontology가 무엇을 말하는지
   • individual들 사이 관계를 직접 주장
   • 두 이름이 사실 같은 대상을 가리킨다고 말함
   • 두 이름이 다른 대상을 가리킨다고 말함
   • 어떤 관계가 성립하지 않는다고 말함
   • 개별 대상들 사이의 사실, 동일성, 구별, 그리고 일부 부정 정보를 ontology 안에서 표현하는 기능
3. Properties
   • relation/property에 대해 ontology가 무엇을 말할 수 있는지
   • relation이 단순 연결 이름이 아니라, 어떤 논리적 성질을 갖는지까지 정의
4. Classes
   • class를 더 풍부하게 만듦
   • 집합 연산으로 class 만들기
   • property restriction으로 class 만들기
   • 어떤 대상이 어떤 조건을 만족하면 이 class에 속함
   • class를 단순한 이름이 아니라, 집합 연산과 property restriction을 이용해 논리적으로 정의하는 기능

4.2. Semantic and Entailment

• ontology로 의미 규칙을 썼을 때, 어떤 사실이 새로 따라와야 하는가

1. Semantic conditions
   • ontology axiom이 현실 세계에서 어떤 조건(domain graph)을 강제하는지
   • ontology 문장이 domain에서 어떤 의미를 갖는지 풀어쓴 조건
2. Entailment
   • 어떤 그래프가 다른 그래프를 논리적으로 포함하는가
   • 포함관계
3. If-then vs if-and-only-if semantics
   1. if-then semantics
      • 일방향
      • 역변역 X
   2. if-and-only-if semantics
      • 양방향 동치
      • OWL이 적용

4.3 Reasoning

1. Rules
   • if-then style consequence를 코드화
   • if : 그래프 안에 이런 패턴이 있으면 → then : 이런 새 triple도 성립
   • materialisation
     • rule을 적용해서 새로 나온 결론을 다시 그래프에 넣고 더이상 새로운 결론이 나오지 않을 때까지 반복하는 것
2. Description Logics
   • ontology를 더 엄밀하게 쓰기 위한 논리 언어

5. Inductive Knowledge(귀납적 지식)

• 데이터에서 패턴을 일반화해서 예측
• 데이터 패턴을 학습해서 새로운 지식을 예측

5.1 Graph Analytics

• 노드들이 어떻게 연결돼 있는지를 보고 유용한 정보를 뽑아냄
• 비지도학습에 가까움
• 정답 라벨 없이도 그래프 구조만 보고 통찰을 얻는 방식

5.2 Knowledge Graph Embeddings

• knowledge graph를 숫자 벡터로 바꿈
• 그리고 scoring function을 통해 plausibility가 높아지도록 학습
• entity와 relation을 저차원 벡터로 표현해, triple의 plausibility를 계산하고 예측에 활용하는 self-supervised numeric model

5.3 Graph Neural Networks

• 그래프 구조에 맞춘 신경망을 만듦
• 노드 분류, 그래프 분류, 특정 task용 예측을 직접 학습

1. Recursive GNNs
   • 어떤 노드의 상태를 이웃 노드들의 상태를 보고 계속 갱신하면서, 원하는 출력에 맞게 학습
   • 이웃 정보를 반복해서 섞어가며 노드 표현을 만듦
2. Convolutional GNNs
   • CNN 아이디어 → 그래프
   • 그래프에서는 노드와 그 이웃을 하나의 local region처럼 보고 convolution 비슷한 연산을 적용
   • 그래프 위의 지역 구조를 CNN처럼 스캔하는 방식

5.4 Symbolic Learning

• 숫자 벡터를 배우는 대신, 사람이 읽을 수 있는 논리식 자체를 배움

1. Rule Mining
   • 그래프에서 의미 있는 패턴을 rules 형태로 발견
2. Axiom Mining
   • ontology에 가까움
   • 같은 axiom도 데이터에서 배울 수 있음
   • 이 relation은 이런 성질을 가짐, 이 class는 저 class의 하위 개념인 것 같음~