neo4j - data science - part 3

Recommendations

• 본 챕터에서는 기본적인 데이터에 대한 이해를 바탕으로 추천 author 추천 엔진을 만들어봅니다.
• 추천이라는 것은 ‘무엇을 기반으로 하느냐?’가 중요한데, 여기서는 author와 citatin 측면에서 관련있다고 생각되는 저자들을 추천하거나, 특정 키워드에 대해서 밀접하게 관련되어 있다고 판단되는 논문을 추천하거나, 로 구분됩니다. 물론, 이 둘을 합쳐서 진행하기도 합니다.

Collaborative Filtering

• Collaborative Filtering은 두 개체간의 유사성을 찾아주는 기본적인 탐색 방법입니다. 흔히들 예로 드는 것이, 쇼핑 목록이죠. 만약 A라는 사람이 상품 가, 나, 다, 라를 샀고, B라는 사람이 상품 가, 나, 다, 라 를 샀다면, 이 둘은 서로 어떤 취향이 유사하다, 라고 말해질 수 있습니다. 물론, 여기서, 그 유사도를 어떻게 측정할 것이냐?, 상품 구매유무만 볼 것인가, 상품에 대한 피드백도 볼 것인가(즉, 값이 binary냐, numerical이냐) 등에 따라서 그 유사도를 측정하는 방식이 많이 달라지기는 합니다.
• 어쨌거나, 기본적으로는 각 사람에 대해서 profile을 설정하고 이 profile 간의 유사도를 측정하는 것이 가장 기본적인 계산법이 되는 셈이죠.

Exercise 1: Coauthor Collaborative Filtering with Cypher

• 일단 환경설정을 합시다.

!pip install py2neo==4.1.3 pandas matplotlib sklearn
from py2neo import Graph
import pandas as pd

import matplotlib 
import matplotlib.pyplot as plt

plt.style.use('fivethirtyeight')
pd.set_option('display.float_format', lambda x: '%.3f' % x)
pd.set_option('display.max_colwidth', 100)

graph = Graph("bolt://18.207.236.58:35753", auth=("neo4j", "<password>"))

• 우선 authoring을 많이 한 저자를 찾아봅니다.
• 사실, 이 러한 구문은 SQL에서는 group by 를 통해 더 간단하고 직관적으로 돌아가는데, 여기서는 group by 가 없으니까 약간 헷갈리는 느낌이 있는 것 같아요

popular_authors_query = """
MATCH (author:Author)<-[rel:AUTHOR]-()
RETURN author.name AS authorName, count(rel) AS articlesPublished
ORDER BY articlesPublished DESC
LIMIT 10
"""

for k_v in graph.run(popular_authors_query).data():
    print(k_v)

• 이제는 저자별로, 저자의 저작물과 각 저작물의 citation 횟수에 대해서 가져와 봅시다. 특이한 점은, 여기에서는 parame을 변수로 넘겨주어다는 점이죠.

# query안에 `$param` 을 선언하여, 이후에 쿼리를 실행할 때 값을 넘겨서 진행할 수 있도록 처리해줌
author_articles_query = """
MATCH (author:Author {name: $authorName})<-[:AUTHOR]-(article:Article)<-[cited:CITED]-()
RETURN article.title AS article, article.year AS year, count(cited) as citations
ORDER BY citations DESC, year DESC
LIMIT 20
"""

target_author_name = "Peter G. Neumann"
# query안에 정의된 $param을 아래와 같이 딕셔너리오 형태로 넘겨줌
query_result = graph.run(author_articles_query,  {"authorName": author_name})
for k_v in query_result.data():
    print(k_v)

{'article': 'The foresight saga, redux', 'year': 2012, 'citations': 2}
{'article': 'Security by obscurity', 'year': 2003, 'citations': 2}
{'article': 'Risks of automation: a cautionary total-system perspective of our cyberfuture', 'year': 2016, 'citations': 1}
{'article': 'The foresight saga', 'year': 2006, 'citations': 1}
{'article': 'Information system security redux', 'year': 2003, 'citations': 1}
{'article': 'Risks of National Identity Cards', 'year': 2001, 'citations': 1}
{'article': 'Robust open-source software', 'year': 1999, 'citations': 1}
{'article': 'Crypto policy perspectives', 'year': 1994, 'citations': 1}
{'article': 'Are dependable systems feasible', 'year': 1993, 'citations': 1}
{'article': 'Computers, ethics, and values', 'year': 1991, 'citations': 1}

• 이제 저자의 collaborator를 알아봅시다.

collaborations_query = """
MATCH (:Author {name: $authorName})<-[:AUTHOR]-(article:Article)-[:AUTHOR]->(coauthor:Author)
RETURN coauthor.name AS coauthor, count(*) AS collaborations
ORDER BY collaborations DESC
LIMIT 10
"""

target_author_name = "Peter G. Neumann"
target_author_name = "Brian Fitzgerald"

query_result_df = graph.run(collaborations_query,  {"authorName": target_author_name}).to_data_frame()
print(query_result_df)

           coauthor  collaborations
0    Klaas-Jan Stol               6
1     Joseph Feller               5
2   Scott A. Hissam               4
3  Karim R. Lakhani               3
4      Walt Scacchi               2
5     Donal O'Brien               1
6     Björn Lundell               1
7     Martin Krafft               1
8       Brian Lings               1
9  Andrea Capiluppi               1

• 그 다음으로는 co-author의 co-author를 찾습니다. 사실, 원래의 쿼리는 다음과 같아요.

MATCH (author:Author {name: $authorName})<-[:AUTHOR]-(article)-[:AUTHOR]->(coauthor),
      (coauthor)<-[:AUTHOR]-()-[:AUTHOR]->(coc)
WHERE not((coc)<-[:AUTHOR]-()-[:AUTHOR]->(author)) AND coc <> author      
RETURN coc.name AS coauthor, count(*) AS collaborations
ORDER BY collaborations DESC
LIMIT 10

• 다만, 저는 약간 full-join과 비슷하게 진행했습니다. 이렇게 하면, 사실 graphDB의 이점을 살리지 못하고, 한 단계 한단계씩 뻗어나가는 형태가 되기는 하는데, 그래도 저는 약간은, 이게 더 편한 것 같기도 해요.
• 즉, node-edge의 관계를 기반으로 하나씩 하나씩 연결하는 식으로 처리했습니다.

MATCH (target_author:Author {name: $authorName})<-[:AUTHOR]-(article1:Article), 
      (article2:Article)-[:AUTHOR]->(coauthor1:Author), //first author to author
      (coauthor2:Author)<-[:AUTHOR]-(article3:Article), 
      (article4:Article)-[:AUTHOR]->(cocoauthor:Author) //second author to author
WHERE (article1=article2) 
      AND (coauthor1=coauthor2)
      AND (article3=article4)
      AND NOT (target_author=coauthor1)
      AND NOT (target_author=cocoauthor)
      AND NOT ((target_author)<-[:AUTHOR]-()-[:AUTHOR]->(cocoauthor))
RETURN cocoauthor.name, count(*) AS COLLABORATIONS
ORDER BY COLLABORATIONS DESC
LIMIT 20

Exercise 2: Recommendations

• 여기서는 PageRank라는, 구글의 서치엔진 알고리즘을 기반으로 네트워크의 연결성, 영향력(transitive influence, connectivity)을 측정하는 알고리즘을 사용해봅니다.
• GraphDB는 기본적으로는 데이터를 Graph의 형식으로 저장하는 것을 목적으로 하지만, 기본적인 Graph Algorithm은 저장하고 있습니다. 그 중 하나가, PageRank이며, 이는 랜덤으로 그래프의 방향에 따라 돌아다니면서, 그래프에 영향력을 크게 줄 수 있는 노드를 계산하는 방법이죠.
• 특히, Citation Network에서는 방향성이 있기 때문에, 그 영향력, 다시 말하면, “많이 인용되는 논문을 중요하게 고려”하는 것과 같은 방법들이 가능해지죠. 간단하게 아래와 같이 실행하면 됩니다. 해당되는 node label과, relationship type 그리고 config을 딕셔너리로 넘겨주면 되죠.

CALL algo.pageRank(<node label>, <relationship type>, <config>)
CALL algo.pageRank('Article', 'CITED', {iterations:20, dampingFactor:0.85, concurrency:4})

# basic pagerank
# 아래와 같이 algorithm을 실행하게 되면, 각 노드에 그 결과 값이 property로 들어가있게 된다.
query = """
CALL algo.pageRank('Article', 'CITED')
"""
query_result = graph.run(query).data()
print(query_result)
print("--"*30)
query = """
MATCH (ar:Article)
RETURN ar.title AS TITLE, ar.pagerank AS NODE_PG
LIMIT 5
"""

query_result_df = graph.run(query).to_data_frame()
print(query_result_df)

• 다만, 위와 같이 실행하게 되면, 해당 pagerank 값이 바로 각 node의 property로 들어가게 됩니다. 따라서, 값을 저장하지 않고, 바로 전달받고 싶다면 다음처럼 실행하는 것이 좋아요.
  • algo.pageRank.stream을 통해서 값들을 저장하지 않고, 바로 읽어들이고,
  • 이를 YIELD를 사용하여, 필요한 값을 남깁니다.
  • 그리고, RETURN을 통해 출력하는 식으로 진행되죠.

CALL algo.pageRank.stream('Page', 'LINKS', {iterations:20, dampingFactor:0.85})
YIELD nodeId, score
RETURN nodeId, score
LIMIT 10 

Personalized PageRank

• 전체 노드에 대해서 pagerank 알고리즘을 계산하지 않고, 필요한 중요한 노드만 선별한 다음 계산하는 것 또한 가능합니다. 가령, 특정 연도, 특정 저자 등에 대해서 처리할 수 있겠죠. 이처럼, 특정한 node들에 대해서만 처리해주기 위해서는, algo.pageRank.stream('Page', 'LINKS', {sourceNodes: sourceNodes})처럼, sourceNodes에 대한 정보를 config에 넘겨주면 됩니다.
• 우선 그렇다면 sourceNode를 가져와 봅시다. 다음의 형식으로 가져오며, 의도는 우리가 이미 정의한 author가 쓴 논문과 이 논문을 1차적으로 인용한 논문들만을 가져옵니다.

MATCH (a:Author {name: $author})<-[:AUTHOR]-(article)-[:CITED]->(other)
WITH collect(article) + collect(other) AS sourceNodes
RETURN sourceNodes

• 그리고, 가져온 sourceNode를 config으로 넘겨주고, 다음처럼 실행합니다. 아래의 쿼리는 순서가 다음과 같습니다.
  • MATCH: 적합한 노드를 검색합니다
  • WITH + collect: 필요한 노드를 집합으로 합쳐서, sourceNodes라는 변수에 저장해줍니다.
  • CALL algo.pageRank.stream에 config으로 sourceNodes을 넘겨주고, 대상으로 하는 label(Article)과, relationship(CITED)을 함께 넘겨줍니다.
  • 그렇게 생긴 nodeId, score를 남기고,
  • 다만, 지금은 nodeId만 있습니다. 이 아이는 primary_key인데, id로 노드를 반환해주는 algo.getNodeById를 통해서, node를 반환받죠.
  • 이제 그다음 필요한 요소들을 RETURN을 통해서 전달합니다.

query = """
MATCH (a:Author {name: $author})<-[:AUTHOR]-(article)-[:CITED]->(other)
WITH collect(article) + collect(other) AS sourceNodes
CALL algo.pageRank.stream('Article', 'CITED', {sourceNodes: sourceNodes})
YIELD nodeId, score
WITH algo.getNodeById(nodeId) as node, score
RETURN node.title AS article_title, score
ORDER BY score DESC
LIMIT 10
"""

## personalized pagerank
author_name = "Peter G. Neumann"
query_result = graph.run(query, {"author": author_name}).data()
for n in query_result:
    print(n)
print(query_result)

• 코드 실행 결과는 대략 다음과 같습니다.

{'article': 'A technique for software module specification with examples', 'score': 0.3585283908905801}
{'article': 'A messy state of the union: taming the composite state machines of TLS', 'score': 0.33168750405311587}
{'article': 'Crypto policy perspectives', 'score': 0.27750000506639483}
{'article': 'Risks of automation: a cautionary total-system perspective of our cyberfuture', 'score': 0.27750000506639483}
{'article': 'The foresight saga', 'score': 0.27750000506639483}
{'article': 'Risks of e-voting', 'score': 0.27750000506639483}

Topic Sensitive Search

• 여기서는, 같은 검색어를 사용하는 두 저자의 경우도, 그들의 연구 분야에 따라서, 검색 결과가 달라질 수 있다는 것을 말하고 있습니다. 즉, 저자의 배경을 고려하여, 검색이 변경되어야 한다는 것이죠.
• 그래서, text를 활용해서 ‘해당 텍스트가 포함된 아티클만을 검색’하는 등의 일들이 필요해지는데, 여기서 중요한 것은 그 작업들이 모두 텍스트로 구성되어 있기 때문에, 매우 긴 시간이 소요될 수 있다는 것이죠. 따라서, 보통 이러한 text들의 경우, 그리고 그 데이터가 바뀌지 않는 일이 많으므로 텍스트에 대해서는 index화 해두면, 이후에 훨씬 빠르게 관련 데이터들을 검색할 수 있습니다.
• 여기서도, Article 노드를 대상으로 title, abstract의 프로퍼티에 대해서 text search index를 생성합니아. 이렇게 할 경우, 이후 검색에서 보다 빠르게 해당 텍스트를 검색하고 노드를 가져올 수 있겠죠.
• Article 라벨을 가진 노드를 대상으로 title, abstract의 프로퍼티에 대해 text search index를 만드는 쿼리는 다음과 같습니다. 순서대로, indexName, nodeProperties를 parameter로 넣게 되죠.

Create Index and Check it.

CALL db.index.fulltext.createNodeIndex('articles', ['Article'], ['title', 'abstract'])

• index가 만들어졌는지를 확인해보려면 다음처럼 하면 됩니다.

query = """
CALL db.indexes()
YIELD description, indexName, tokenNames, properties, state, type, progress
WHERE type = "node_fulltext"
RETURN *
"""
query_result_df = graph.run(query).to_data_frame()
print(query_result_df)
print("== check index ")

• 위를 실행하면, 다음의 결과가 나옵니다. 만들어진 index에 대한 간단한 설명들이죠.

{
    'description': 'INDEX ON NODE:Article(title, abstract)', 
    'indexName': 'articles', 
    'progress': 100.0, 
    'properties': ['title', 'abstract'], 
    'state': 'ONLINE', 
    'tokenNames': ['Article'], 
    'type': 'node_fulltext'
}

fulltext search by index.

• 자, 이제 만들어준 index를 사용해서 text를 검색해보겠습니다.
• db.index.fulltext.queryNodes: 만들어진 index인 articles에 대해서 open source에 대한 full text search를 합니다. 어떤 방식으로 full-text search를 하는지는 여기서는 언급되어 있지 않고, apache-lucene를 사용해서 한다고 하네요.
• YIELD: 생성된 결과에서 node, score를 가져옵니다.
• RETURN : 그리고, 그 값을 가져오는데, 여기서, pattern comprehension이 들어갑니다. -[(author)<-[:AUTHOR]-(node) | author.name]: 이는 [<GraphQuery> | <target_value>]의 형식으로 정리되는데, 그냥 list comprehension이죠. 직관적이므로 굳이 설명하지는 않겠습니다.

query = """
CALL db.index.fulltext.queryNodes("articles", "open source")
YIELD node, score
RETURN node.title AS NodeTitle, score as Score, [(author)<-[:AUTHOR]-(node) | author.name] AS authors
LIMIT 10
"""
query_result_df = graph.run(query).to_data_frame()
#print(query_result_df.columns)
print(query_result_df[['Score']])

• 결과는 다음과 같죠.

   Score
0  4.252
1  4.081
2  4.071
3  3.815
4  3.784
5  3.693
6  3.690
7  3.543
8  3.515
9  3.492

• score가 나오니까, 존재하는 모든 문서에 대해서, score를 매긴 다음 순차적으로 보여주는 것처럼 생각하기 쉽습니다만, 알고리즘에 따라서 적합하다고 판단되는 문서들만을 리턴합니다. 즉, 실제로 존재하는 Article은 약 51,995개가 있는 반면, 위의 ‘open source’에 대해서 full-text search를 한 경우에는 약 3,080개의 문서가 도출됩니다. 따라서, ful-text search를 한 것 자체로, 그나마 관련 있는 문서들만을 추릴 수 있는 것이죠.

what does score mean?

• 다만, 약간 의아할 수 있는 것은 그 결과에 score라는 값이 포함되어 있는 것이죠.
• full text search에서는 exact match(해당 단어가 텍스트에 반드시 포함되어 있는 경우)뿐만 아니라, approximate match에 대해서도 결과를 포함시킵니다. 따라서, 함께 넘겨준 ‘open source’와 가장 유사한 것이 무엇인지를 계산해서 score를 매기고 그것을 내림차순으로 보여주는 것이죠.
• 그리고, 이 단계에서 어떤 방식으로 full-text search에 대한 인덱스를 만드는지에 대해서는 apache-lucene에 기반하고 있다고 하네요. 간단히, open source search software라고 하는데, 이는 이후에 시간이 나면 다시 정리해보겠습니다.
• 간단하게는 tf-idf와 같은 방식으로 문서를 벡터화해서 처리하는 것 같네요.

### why it is over 1.0?

그리고, score 값이 1.0을 넘는다는 것이죠. 표준화가 되어 있지 않으므로, 이 값이 어느 정도의 신뢰도를 가지고 있는지 가늠하기가 어렵습니다. 하나의 쿼리에 대해서 이처럼 1.0을 넘는 값들이 보이는데, 이러한 값의 편차는 query에 따라서 달라집니다. 즉, 어떤 쿼리에서는 최대의 값이 4.2일 수 있고, 다른 값에서는 그 값을 넘을 수 있다는 것이죠.

• 이에 대한 비슷한 질문이 이미 stackoverflow에 있습니다. stackoverflow: how to normalize lucene scores. 그리고, 그 방법 자체가 유효하지 않다고 되어 있죠.
• 뿐만 아니라 Confluence Wiki에는 ScoreAsPercentage라는 글이 작성되어 있고, 다음의 내용들이 작성되어 있습니다.
  • 사람들은 빈번하게, lucene score를 100% 단위로 생각하려고 하며, 이는 보통 normalized socre라고 불린다.
  • 그러나, 이런 방식으로 생각하지 마라. 사실, 그냥 가장 큰 값으로 해당 값을 0.0과 1.0 사이의 값으로 위치시키는 것은 가능하지만, 그것은 결국 표본에 따라서 달라지는 것일 뿐이다. 가령, 최대값이 10인 표본들(A 집합)과, 최대값이 5인 표본들(B 집합)이 있을 때, 각각을 표준화시킨다면, 최대값이 10인 표본과 최대값이 5인 표본의 표준화된 값이 같아지게 된다. 즉, 이런 식으로 변경해서는 유사도를 정확하게 대표할 수 없다.
• 즉, 유사도라는 것은 결국 당신이 대상으로 한 데이터들에 기반해서 결정된다. 그 데이터 집합이 어떻게 구성되어 있느냐에 따라서 값이 달라지는 것인데, 데이터는 늘 새롭게 추가되거나, 없어질 수 있다. 그러므로, 그 값 또한 변경가능한 것이 당얀한 것이며, 서로 다른 데이터 집단끼리 비교하기 위해서 무리해서 1.0 이하의 값으로 표준화하는 것은 권장되지 않는다, 라는 것이죠. 타당한 지적으로 보이기도 합니다만, 그렇다면, 계산상 산출 가능한 최대의 score는 무엇인가? 하는 궁금증이 남기는 합니다. 비교 집단이 없을 경우, 이 값이 도대체 어느 정도 비슷한지에 대해서 각이 서지 않는 거니까요.

Full-text search and pagerank

• 이제, 이 단계에서는 full-text search를 사용하며 동시에 pagerank 알고리즘을 사용해서 저자가 관심있어할만한 article을 찾습니다. 처음에는 pagerank만을 사용했습니다만, 그 경우에는 특정 주제에 대해서는 고려하지 못한다는 한게를 가집니다. 그리고 두번째인 full-text search에서는 저자에게 필요한, 저자의 potential collaborator를 고려하지 못한다는 한게를 가지죠.
• 따라서, 여기서는 그 둘을 혼합해서 사용합니다.
• full-text search를 사용해서는 apache lucene에서 정의한 방법에 따라서 scoring이 되죠(그리고 이 값은 표준화되어 있지 않습니다). 그리고 pagerank는 해당 네트워크에 랜덤으로 흐름을 만들어서, 그 흐름이 결국 어디에서 수렴하는지를 통해 해당 node의 영향력을 측정하는 방법론입니다. 즉, 이 두 방법이 각각 새로운 값을 측정하죠.
• 쿼리가 좀 복잡하여 주석을 나름대로 상세하게 작성했습니다. 조금 더 정리를 해보자면,
  1. target_author의 저작물(article)과 이를 인용한 저작물들(others)을 대상으로 하고,
  2. searchTerm에 속한다고 판단되는 article을 db.index.fulltext.queryNodes을 통해 찾습니다.
  3. 그 다음, searchTerm에 속하며, 첫번째에서 만든 집합과 교집합에 대해서 page_rank를 계산하고,
  4. 그 결과중에서 필요없는 것을 제외하고 출력합니다.

query = """
// author의 저작물들(article)과 이를 인용한 저작물들(others)를 sourceNode에 저장한다.
MATCH (target_author:Author {name: $author})<-[:AUTHOR]-(article)-[:CITED]->(other)
WITH target_author, collect(article) + collect(other) AS sourceNodes
// pageRank를 계산하는데, 이 때 여기서는 cypher-projection을 사용해서 그래프를 넘겨줍니다. 
CALL algo.pageRank.stream(
    // node-query
    'CALL db.index.fulltext.queryNodes("articles", $searchTerm)
    YIELD node, score AS text_sim_score
    RETURN id(node) as id',
    // relationship-query
    'MATCH (a1:Article)-[:CITED]->(a2:Article) 
    RETURN id(a1) as source,id(a2) as target', 
    // 그리고 cypher-graph-projection을 통해서 넘겨주므로, 
    // graph:'cypher' 를 함께 넘겨주어야 합니다.
    {sourceNodes: sourceNodes,graph:'cypher', params: {searchTerm: $searchTerm}}
)
// 이제 pagerank에서 발생한 결과인 nodeId, score를 넘겨주고,
YIELD nodeId, score AS pagerank_score
// 여기서 nodeId를 사용해서 원래 node에 접근합니다. 여기서 node의 label은 article이죠.
WITH algo.getNodeById(nodeId) AS nodeArticle, pagerank_score
// 그리고, target_author에 의해 작성된 nodeArticle은 제외하고, pagerank_score가 0인 경우도 제외합니다.
WHERE not(exists((target_author)<-[:AUTHOR]-(nodeArticle))) AND pagerank_score > 0
// 그리고 결과를 리턴하며, 참여한 저자들을 list-comprehension의 형태로 넘겨줍니다.
RETURN nodeArticle.title as article, pagerank_score, [(node)-[:AUTHOR]->(author) | author.name][..5] AS authors
order by pagerank_score desc limit 10
"""

• 결과 값은 다음과 같다.

      article  score
0  Static det  0.386
1  Concern gr  0.278
2  Characteri  0.278
3  Automated,  0.278
4  Who should  0.278
5  Conceptual  0.236
6  Semantics-  0.150
7  Bandera: e  0.150
8  AsDroid: d  0.150
9  EXSYST: se  0.128

wrap-up

• 길고 복잡해보이지만, 사실 2가지 측면에서 정리됩니다.
• author-network: 저자들의 인용 네트워크를 기반으로 pagerank 알고리즘을 사용하여, 영향력 있는 저자를 분석할 수 있습니다.
• topic-sensitive search: searchterm을 넘겨주면, apache lucene 엔진을 이용하여, 해당 검색어와 유사하다고 판단되는 노드들의 ID와 score(유사도)를 넘겨줍니다(유사도가 0이하인 노드는 제외하는 것으로 보입니다).
• 그리고, 위에서 나온 둘을 섞어서, ‘특정한 저자들만이 쓴 논문들(A)과 특정 검색어에 속하는 논문들(B)의 교집합에 대해서 pagerank를 사용해서 결과를 보여주는 것’ 또한 가능합니다.