24년 7월 3주차 그래프 오마카세

링크드인에서 Graph 를 활용하는 방식 (1) - Scaling Contextual Conversation Suggestions Over 500 Million Members

정이태

Scaling Contextual Conversation Suggestions Over LinkedIn’s Graph

안녕하세요 정이태입니다. 오늘은 그래프를 활용하는 대표 기업들 중 하나죠. 링크드인에서 그래프를 활용해 추천시스템 개선하는 방식에 대해 이야기해보려고합니다. 링크드인을 통해 직업에 대한 정보를 교류하고 계시는 분들이 많을거라 생각해요.

링크드인 그래프 설계

이때, 여러분이 원하는 직업 , 회사와 관련있는 사람과 연결되면 좋겠으나 그 인지하는 범위가 제한되어 있기에 검색을 통해 직접 정보를 탐색하시는 분들도 계시겠지만, 반대로 채팅 혹은 피드에서 노출되는 정보들을 통해 탐색하는 분들도 심심치않게 보일거라 생각합니다.

messaging3

어떻게 내가 원하는 기업에서 근무하는 사람이 내 채팅창에서 노출되지? 내 피드에 노출되지 하시는 분들이 계실겁니다. 여러분들이 기입하신 링크드인 프로필, 조직 기여도 등을 활용하여 scoring(affinity score)를 측정해주고 이 scoring 에 따라 노출이 되는거죠. 결국 이 일련의 과정이 잠재적인 '관계'를 만들기 위함이며, 이 관계로부터 형성된 네트워크 'Economic graph'를 통해 linkedin 만의 지식그래프가 구축되는겁니다.

해결하고 싶은 문제.

위처럼 회사와 직접 / 간접적인 관계를 활용해 추천을하지만 여전히, 엔지니어링 측면의 문제는 존재합니다. 데이터 엔지니어링 개선을 위해 다음 3개의 metric 을 설정하고, 3번의 시도를 합니다.

metric

1.Liquidity

기존에는 해당 기업의 페이지 view 데이터가 담긴 historical 데이터에 기반하여 company page를 추천했었습니다. 다시 말해서 Direct scoring을 통해 추천을 했었다면, Indirect scoring(기업 페이지에 직접적으로 접속하지않으나, 해당 기업에서 근무하는 직원과 관계가 있거나 관계 발생 가능성이 높음)을 활용하는 방식의 효용성을 측정하고자 Liquidity라는 지표를 설정했습니다.

2.Cost to Serve (C2S)

게시물이 작성된 17년도 당시 500M , 9M 각각의 member와 company 계정들이 존재했는데요. 이를, 모두 분석해 scoring 을 도출하고 이를 기반으로 추천해주기 위해 발생하는 연산량을 가늠해본다면 Billion 규모임을 유추해 볼 수 있습니다. 이를 효율적으로 서빙하기위해 이 지표를 설정했습니다.

3.Latency

추천을 했다면, 이를 기반으로 유저가 회사 페이지에 접속하게 됩니다. 이때, 발생하는 지연시간을 지표로 설정했습니다.

첫번째 시도

messaging5

1.Eliminate massive joins
이전에는 회사와 연결고리를 찾기 위해 '직접' ,'간접' 연결 관계를 유추해 1st , 2nd degree 에 기반하여 회사와 join을 해주었다면, 이를 직접적으로 join하기 위해 company employee table을 만들어주고 table끼리 직접 조인을 해주는 방식을 통해 연산량을 절감합니다.


2.Reduce number of keys
간단합니다. 이전에는 <viewer, company> 1:1 key mapping이 된 데이터 기반으로 추천을 했다면, 여기에서는 viewer 와 company 간 % 를 활용해 batch 로 클러스터링 해주는거죠. <viewer, (companyId, %batch_size)>

두번째 시도

messaging6

방금전의 시도를 통해 Table간 join을 직접적으로 할 수 있게되고, 이를 통해 viewer 와 company간 관계가 형성되었습니다. 이를 다르게 말하면, Graph가 형성되었다고도 볼 수 있는데요. 이를 적극적으로 활용하기 위해, Graph Service라는 컨셉을 모듈로 구성해서, 이 Graph Service 내에 있는 데이터를 Graph Search하게 됩니다.

Graph 라는 것을 자꾸 강조하게 되는데요. 여기에선 이 Graph 를 Search 로도 활용하고, Search 한 결과물을 기반으로 pre-generated feature를 만들고 이를 추가 적용하여 추천을 하게 됩니다. 이 시도를 통해 liquidty 지표가 30% -> 70% 까지 개선되었다고 합니다.

여러 요소들을 추가했으니, 그만큼 풍부한 정보에 기반해 추천을 해주기때문에 당연하게도 성능이 개선됩니다. 추가된 정보들인 1) direct path , 2) 1st, 2nd degree connection , 3) feature 3가지를 single call 마다 가져오면 기존 방식 대비 시간이 더 소요되겠죠? 이를 세번째 시도에서 개선합니다.

세번째 시도

messaging7

두번째 시도를 통해 정확도가 개선되었습니다. 세번째 시도에서는 이제 그 개선된 결과물을 유저에게 신속하게 전달하기 위해 어떤 부분을 개선했는지 이야기합니다. 간단합니다. 이전에는 단순하게 Affinity scores 만을 기록하고 있었다면, 이젠 direct , indirect affinity score 를 모두 사전에 연산하고 이를 저장해서 recommendation request 가 발생했을때, response 를 전달해주는겁니다.

Wrap-up

총 세 번의 과정 및 시도를 통해 시스템 개선에 성공했습니다. 이를 통해, Linkedin team 은 다음과 같은 교훈을 얻었다고 하는데요.

  1. Data Jiujitsu : data product 를 만들때, 작게 시작해서 여러 아이디어들을 반복 시도하며 개선하라.
  2. Hadoop joins: 만약 offline flow에서 latency 가 높다면 , 시스템이 massive join을 한다라고 유추하고 이를 개선할 수 있는 시스템 디자인을 고려하라.
  3. Use hybrid: online recommendation service를 만들기 위해 online에 치중한 시스템 엔지니어링도 물론 중요하지만, 시스템 관점과 더불어 feature 관점도 고려 요소로 편입하여 디자인하라.

이번주 오마카세에서는 추천 시스템 정교화 및 신속한 추천 결과물 전달을 위해 링크드인에서 그래프 관점을 접목하여 엔지니어링한 게시물에 대해 리뷰해보았습니다. 총 3가지 시도를 통해 연산량 및 Latency 감소를 이뤄냈으며, 이 시도동안 어떤 lessons learned 가 있는지까지를 공부했습니다.

이 귀한 경험을 포스팅을 통해 볼 수 있다는 것에 너무 감사하네요. Graph 본질적인 접근보다 엔지니어링 접근이라 Graph technique 에 대한 언급은 거의 없었지만,KPI 를 무엇으로 설정하고 어떻게 이를 개선해나가는지에 대한 과정 및 결과를 참고하기 좋은 리소스라는 측면에서 재밌었던 포스팅이였습니다. 여러분에게 도움이 되길 바랍니다.

linkedin ; https://www.linkedin.com/in/iitaejeong


Signal Processing on Simplicial Complexes (1)

paper link : https://arxiv.org/abs/2106.07471

배지훈

Summary of previous post

  • 토폴로지 관점에서 그래프 개념을 확장시킨 TDL 혹은 TDA에 대해 Real world complex data로의 연구 관심 및 적용 사례가 증가하고 있는 것 같습니다.
  • 단순히 Pairwise relationship을 고려하는 것 보다 다른 차원으로 정의되는 노드(0차원 simplex), 엣지(1차원 simplex), 그 이상의 토폴로지 요소들을 higher-order complexes으로 묶어 서로 간의 dynamic communication을 포괄적으로 고려하는 것이 훨씬 더 효율적일 수 있습니다. 실제로 이러한 특성이 Real world data (gene, protein, brain, social network etc..)에도 적합하기에 더욱 활용도가 높아지고 있는 것 같습니다.
  • 이러한 higher-order relationship 관계를 잘 나타내는 그래프 (토폴로지) 네트워크에는 simplicial complexes (SCs), cell complexes (CCs) 등이 있음을 말씀드렸습니다. 또한 이러한 네트워크를 분석하고 활용하기 위한 대표적인 TDA 기법으로 Persistence Homology, Topology signal process (TSP) 등이 있었습니다. 그리고 이러한 방법들을 뉴럴 네트워크로 발전시켜 higher-order relationship을 학습하는 TDL 모델들도 많이 제안되고 있습니다. (e.g. Simplicial convolutional & attention networks etc..)

In terms of Topological Signal Processing (TSP)

  • 저는 특히 TSP 관점에서 접근하여 토폴로지 네트워크의 다른 차수 간의 신호 변동 및 상호작용에 집중하고, 이로부터 수많은 대수적 이해 및 해석 (e.g. Understanding signal flowing, Smoothness, Denoising, Sampling & Filtering etc..)이 가능합니다.
  • 예전 글에서 소개해드렸던 그래프 신호 처리 (Graph signal processing, GSP)의 pairwise 방법을 확장하여 더욱 복잡한 multiyway description을 요구하는 시스템적 상호작용을 나타내는 정보를 잘 포착하기 위해 등장한 개념입니다. 상대적으로 누릴 수 있는 이점이 더 많을 것으로 생각합니다.
    • 본 논문에서는 Preliminary로 GSP에 대한 간략한 배경 및 개념들을 잘 정리해주고 있습니다. 이 부분을 꼭 참고해 읽어주시면 뒤의 TSP 개념 이해에 큰 도움이 될 것으로 생각합니다 !
    • 해당 글에서는 GSP에 대한 자세한 설명은 생략하도록 하겠습니다.
  • 논문 제목에서도 알 수 있듯이 저자들은 Simplicial complex 상에서 정의되는 신호를 분석하는 방법론을 설명하고, 그로부터 얻을 수 있는 이점들을 제공합니다. 그리고 원본 데이터로부터 잘 표현된 simplicial complex의 토폴로지를 해석하고 추론하는 방법을 제안합니다.
  • 이번 글에서는 TSP의 기본이 되는 Simplicial complex 개념과, 그 요소들의 관계정보, 그리고 Boundary operator 까지만 알아보도록 하겠습니다.

What is Simplicial complex ?

  • 먼저 Simplicial complex란 무엇인지 알고 가야 할 것 같습니다. 저자들은 Briefly하게 다음 개념을 설명해주고 있습니다. (Chap 4.1 Brief recap of simplicial complexes를 참고해주시기 바랍니다.)
    • k-simplex (or simplex of order k) : k+1개의 구성 요소를 갖는 유한 노드 집합 (V)의 하위 집합을 의미합니다. 예를 들어, 0-simplex는 1개의 요소 (점 혹은 노드)를 포함하는 하위 집합 전체를 나타내며 (e.g. {1}, {2}, ...) , 1-simplex는 2개의 요소 (점 2개로 구성된 엣지)를 포함하는 하위 집합 전체를 나타냅니다. (e.g. {1,2} , {2,3} ...)
      • 0-simplex : 노드 (점 1개), 1-simplex : 엣지 (점 2개), 2-simplex : 삼각형 (점 3개), so forth.. 로 생각해볼 수 있습니다.
    • Simplicial complex : 다음 조건 (Incidence property - 포함 조건)을 만족하는 simplices의 집합을 나타냅니다.
      • Incidence property : Simplicial complex에 포함되는 임의의 k-simplex에 대하여 그 k-simplex의 임의 하위집합 역시 Simplicial complex에 속해야 합니다.
      • 예를 들어, Simplicial complex (X) = ({1}, {2},{3}, {1,2}, {2,3}, {1,2,3})으로 정의되는 경우를 생각해보면, 2-simpliex (3개의 점으로 구성된 삼각형) : {1,2,3}에 대하여 그 하위 집합 : ({1,2} {2,3})역시 Simplcial complex의 요소에 포함됩니다. 그로부터 위의 Incidence property를 만족한다고 볼 수 있습니다.
    • Face / Co-face : 위의 Incidence property로부터 얻어지는 중요한 higher-order relationship으로, 아래와 같은 조건을 만족할 때 정의될 수 있습니다.
      • Face : (k+1)-simplex의 하위집합으로 임의의 k-simplex가 포함되어 있을 때, 해당 k-simplex를 (k+1)-simplex에 대한 Face라고 정의합니다. 예를 들어 위의 예시 X에서, 2-simplex (e.g. {1,2,3}) 속에 1-simplex (e.g. {1,2})가 포함되어 있기 때문에 해당 1-simplex는 2-simplex의 Face라고 볼 수 있습니다.
      • Co-face : k-simplex를 Face로 가지는 (k+1)-simplex를 해당 k-simplex의 Co-face라고 정의합니다. 간단하게 k-simplex보다 1개 요소가 더 추가된 (k+1)-simplex는 co-face가 됩니다.
    • Orientation (방향성) : k / (k+1)-simplex 사이의 관계성을 대수적으로 연산하기 위한 필수 요소로써, 각 simplex에 대한 방향성이 고려되어야만 합니다. 여기에서 기존 그래프의 방향 그래프 (direct-graph)와는 별개의 개념이라는 것을 꼭 기억해주셔야 합니다.
      • 일반적으로, 노드 레이블의 오름차순을 따라 무작위하게 방향성이 결정됩니다. 그 외에도 해당 데이터의 특성에 맞게 방향성을 새롭게 정의할 수 있습니다.
      • Fig 2 (a)의 화살표가 해당 simplices의 방향성을 나타냅니다. 예를 들어, 1-simplex (엣지) 방향성은 노드 레이블 1 -> 3, 1 -> 4, 3->4 로 오름차순을 따라 지정되어 있으며, 2-simplex (삼각형) 역시 노드 레이블 1 -> 3 -> 4 순서로 rotational하게 정해져 있습니다.
      • '왜 이런 방향성이 중요하냐 ?' 라는 질문을 주실 수 있는데, 상당히 좋은 질문이라 생각합니다. 간략하게 해당 방향성 정보를 기준으로 (아래에서 설명드릴) Boundary operator를 정의할 수 있고, 해당 operator를 decomposition 함으로써 spectral properties를 얻어낼 수 있기 때문입니다.
    • Boundary operator (바운더리 연산자) : TSP에서 정말정말 기본적이면서도 중요한 역할을 담당하는 친구입니다. 다음 연산자는 위의 방향성이 정의되면 얻을 수 있는 행렬적 표현으로, 다른 차수의 simplices 사이의 관계성 (incidence property)을 요소로써 인코딩하는 일종의 맵핑 함수로 정의됩니다.
      • Boundary matrix (B_k) : 행 요소에는 (k-1)-simplices를, 열 요소에는 k-simplices를 나타냅니다. 0이 아닌 요소 (+1, -1) 는 두 simplices 사이의 Face 및 Co-face 관계를 나타내는 정보를 담고 있으며, 0 요소는 어떠한 관계를 갖지 않음을 의미합니다.
      • (+,-) 의 부호는 두 simplices 사이의 in-flow 혹은 out-flow (for B_1), 또는 방향성 일치 여부 (for B_2)를 나타냅니다.
    • 좀더 쉬운 이해를 위해, 논문에서 Fig 2의 예시를 따라 정의되는 Boundary operator를 보여주고 있습니다.
Boundary operator between 0-simplices (node, row) and 1-simplices (edge, col)
      • 예를 들어, 위의 B_1 (k=1) 연산자 예시는 0-simplices와 1-simplices 사이의 관계성 (=incidence property)를 나타내고 있습니다. (0, 1)의 요소 값은 포함 여부를 나타내고 있으며 (Face / Co-face 정보), (+, -) 기호는 각각 in-flow (들어가는 신호의 노드, "신호가 추가된다") 및 out-flow(나가는 신호의 노드, "신호가 줄어든다")에 대한 정보를 나타냅니다.
Boundary operator between 1-simplices (edge) and 2-simplices (triangle)
      • 또한 B_2(k=2) 연산자 예시는 1-simplices와 2-simplices 사이의 관계성을 나타내고 있습니다. 마찬가지로 (0, 1)의 요소 값은 포함 여부를 나타내고 있으며, (+, -) 기호는 방향성 일치 여부를 나타냅니다.
      • 전자공학을 전공하신 분들은 회로이론의 '키르히호프 전류 법칙 (KCL, Kirchhoff's Current Law)'를 생각하면 바로 이해되실 것 같습니다.
  • 이렇게 정의되는 Boudary operator를 기반으로 Simplicial complexes에 대한 shift-operator로써 'Hodge Laplacian' 행렬을 정의할 수 있게 됩니다. 다음 행렬은 GSP의 shift-operator로 동작하는 graph Laplacian (L)의 노드 간 pairwise relations를 인코딩하는 역할 뿐 아니라, higher-order relation까지도 인코딩하는 연산자로 확장시킨 개념입니다. 다음 개념은 TSP에서 정말 정말 정말 정말 중요한 개념이기 때문에 꼭 숙지하셔야 하며, 다음 행렬로부터 해당 Simplicial complex의 spectral properties를 이해하고 분석 및 활용까지 해볼 수 있게 됩니다.
  • Hodge Laplacian 관련한 내용은 다음 오마카세 작성 글에서 자세하게 설명드릴 수 있도록 하겠습니다 !

[Contact Info]

Gmail : jhbae1184@akane.waseda.jp

Twitter (X): @jhbae1184

LinkedIn

Subscribe for daily recipes. No spam, just food.