static and dynamic robustness

Dynamic 편

• Robustness 기억나시나요? 저번주 오마카세에서는 ‘static’ 맥락을 다루었다면, 이번주차는 ‘dynamic’ 맥락입니다! ‘static 와 dynamic 의 가장 큰 차이점은 바로 ‘역학’ 입니다. 코로나를 역학조사 할 때도 쓰인 개념이죠. SIR 모델. 누군 치료되고 누군 감염되는 등 실시간으로 변화되는 네트워크 상태 예의주시하는게 핵심입니다. 그렇다면 어떻게 우리가 예측을 할 것이냐? 음..! 예측이라는 표현보다 노드와 노드간의 load(부하)가 어떻게 전달 되는지 시뮬레이션 해본다는 맥락이 더 적절하겠네요.
• dynamic robustness 에서 핵심은 바로 ‘time’ 과 ‘load’ 입니다. 특정 시간대에 부하가 어디에서 어디로 흐르고 있는지 flow 를 파악하며 cascade 현상을 유추하는거죠. 이를 통해, 현상을 정량화 및 tolerance 라는 파라미터로 측정하며하며 어느 부분이 취약점일지 파악하고 빠르게 대처하는거죠. 비단 질병 뿐만아니라, 인터넷 네트워크 시스템 등 연결로 이루어진 모든 데이터에서도 통용되는 개념입니다.
• 비즈니스 측면으로 바라본다면, 바이럴 마케팅에서도 활용됩니다! sns 상에서 information spread 뿐만 아니라 순간 확장성 그리고 타 커뮤니티로 전달되는 파급력 까지 복잡계 네트워크 지식이 연계되어 있는분야는 너무나도 다양합니다 :) 참 재밌지 않나요?!
• 제가 지금 전달드리는 내용은 ‘Complex networks: Structure and dynamics’ 의 극히 일부분에 불과합니다. rumor spreading , Fluctuating 등 여러 현상에 대한 분석이 담겨있으니 한 번 보시는 걸 추천드려요!

NodeAug: Semi-Supervised Node Classification with Data Augmentation

[https://dl.acm.org/doi/abs/10.1145/3394486.3403063]

• Imbalanced data task 를 맡게 되면 곧바로 떠오르는 생각이죠. Data augmentation. 그래프에서도 데이터 증강이 가능합니다. 본 논문에서는 node attribute 와 graph structure 를 변형해주며 graph augmentation 을 진행합니다. 또한, subgraph mini-batch training 을 통해 large graph 에서 어떤식으로 training 하면 좋을지에 대한 이야기도 나눕니다.
• Data augmentation → 데이터 증강은 단순하게 데이터 분포 혹은 조작 단계 뿐만아니라,  증강된 데이터가 적합한 데이터인지 검증하는 단계도 필요합니다. 먼저, 증강된 데이터라 함은 그래프와 연결된 노드 엣지를 random remove / replace 하고, reconnect 를 의미합니다.
• 이 후 , 검증하는 단계는 remove / replace 전 / 후 그래프의 분포를 KL 로 측정하며 minimize 로 이루어집니다. 되게 간단하게 말했지만 remove 과정에서 굉장히 흥미로운 아이디어들이 있어요. 논문을 보실 분들이시라면 이 측면 꼭 유념하시면서 보시는걸 추천드려요 !
• Subgraph mini-batch 는 심플하게 whole graph training 이 아닌 , label 에 연결되어있는 subgraph 만을 batch training 해주는 기법을 의미합니다.
• 실험결과들 모두 자신들의 아이디어가 젱리 좋다 라는 식의 평이한 논리전개를 띄곤하는데요. 본 논문도 마찬가지입니다. 그런데 여기 여러분들에게 유용한 인사이트가 실험 해석에 존재합니다. 데이터 증강이 어떤 그래프 임베딩에서 효과적인지에 대해 실험 결과와 왜 그런 결과가 나왔는지에 대한 해석인데요.
• GCN GAT LGCN 과 같은 대표적인 모델에 모두 적용했으나, GCN 이 그 중 돋보일만큼 퍼포먼스 향상되었다고 하네요. 왜 그런지에 대한 이유는 논문에서 살펴보시면 좋을거 같아요! 모든 data agumentation 이 만능이 아니라는 관점을 견지하시고 보시면 재밌는 아이디어까지 이어질 것 같습니다 🙂

Industry

ByteGraph: A Graph Database for TikTok

[https://www.mydistributed.systems/2023/01/bytegraph-graph-database-for-tiktok.html?m=1]

• Short video 플랫폼으로 유명한 틱톡에서는 어떻게 데이터를 관리할까요? 직관적으로 보기에도 real-time 이 굉장히 중요한 요소일거라 생각되는데요. 많은 실시간 데이터를 관리하기 위해 직접 데이터베이스를 만들었습니다. ByteGraph!
• Low latency , high scalability 두 조건들을 만족하기위해 1. Edge-tree 2. Adaptive optimization 3. geographic replication 요소들을 중점으로 데이터베이스를 설계했습니다.
• 세 요소들을 하나씩 간단히 말씀드리자면, edge-tree 는 그래프 형태 (adjancecy list)를 b-tree 구조만들어주고 관리해줍니다. Tree 라면 node 들 또한 존재하겠죠? Root , meta, edge 3가지 노드를 통해 데이터 를 읽고 쓰는데 필요한 사이즈들을 upper-bound 와 lower-bound 로 관리해줍니다. Upper bound 나 lower bound 는 데이터들이 bound에 근접할 때 disk I/O 를 줄인다거나 늘린다거나 하는 일종의 데이터 가용 경계라고 보시면 될 것 같아요.
• Adaptive optimization 은 데이터에 대한 요청에 발생할 때, 어느 thread pool 에서 처리하면 효율적인지 판단해주는 dynamic thread pool 과 데이터에 매칭되는 key가 존재하지 않을 때 전체 edge-tree 를 scanning 하면 비효율적이니, 이를 edge property 로 sorting 그리고 매칭해주는 secondary edge-tree 로 이루어져 있습니다.
• Geographic replication 는 with a data center , cross data centers in the same region , cross data centers in different region 3가지를 통해 fault tolerance 와 high availability 에서 효율적이였다 라고 합니다. 각 geographic 특성에 따라 어떻게 db 를 deployment 할지에 대한 전략이 나와있다고 생각하시면 될 거 같아요.
• Production 레벨에서 중요한 high scalablilty , low latency 요소를 어떻게 설계하는지 궁금하셨던 분들에게 유용한 레퍼런스라 생각되네요. 여러 유명한 GDB 특히 neptune 과 비교한 실험이 기억에 남네요. OLTP , OLSP , OLAP 를 모두 아우르며 고성능을 보여준 bytegraph 대단하다고 느껴집니다..!

NFT Wash Trading in the Ethereum Blockchain

[https://arxiv.org/pdf/2212.01225.pdf]

• 한 때 광풍이였던 가상화폐, 그중에서 NFT 기억나실까요? NFT 에 대한 가치 산정은 주로 rariety 라는 지표로 이루어지고 있었습니다. 근데 여기에서 rariety 지표는 낮음에도 불구하고 가격이 높은 NFT 들이 발생하곤 하는데요. 물론 그 상황에 대한 여러 원인들이 존재하겠으나 대다수는 유저간 담합을 통해 가격을 상승시키는 악의적 행동으로 그렇다고하네요.
• 그 행동들이 주로 어떤식으로 나타나는지에 대해 다룬 논문입니다. 뿐만아니라, 저희 일전에 공부했던 strongly connected component 기억나실까요? 복잡계 네트워크 지식이 여기에서도 쓰입니다. 많고 많은 데이터들 중 의심 행위를 분별할 때 쓰이는데요. 왜 connected component 인가에 대해 기술하는 부분도 역시 재밌습니다.
• 지금 비록 NFT에 대한 관심이 많이 시들긴 했으나, 미래는 또 모르니깐요! 그래프 와 블록체인이 결합하여 abnormal tx detection이 어떻게 이루어지는지 overview 를 잘 기술한 논문이기에 추천드립니다 🙂 쉽고 재밌어요 !

ZeRO: Memory Optimizations Toward Training Trillion Parameter Models

[https://arxiv.org/pdf/1910.02054.pdf]

• parallelism 에 대해 논의하며 과연 data parallelism 이 model training 이 긍정적인 영향을 줄것인가에 대해 논의하는 논문입니다. 말은 쉽게 드리지만, 엔지니어링 스킬들의 집약체 논문이라 생각되네요.
• Pipeline parallelism , Model parallelism , Cpu offloading 등 전문가들의 다양한 실험과 해석들이 총 집합되어 있다 생각됩니다. Traillion parameter 급의 모델을 다루는 엔지니어링 분들에게 많은 도움이 되리라 생각됩니다.

big graph with 모델

big graph 2번째 시리즈입니다. 모델을 통해 big graph 를 다루는 방식입니다. 이 부분은 OGB LSC에서 지금 이 시간에도 많은 연구자들이 경쟁하고 있는 중입니다.

Recent Advances in Efficient and Scalable Graph Neural Networks

[https://www.chaitjo.com/post/efficient-gnns/#scalable-and-resource-efficient-gnn-architectures]

• Scalable and resource efficient GNN architectures 항목을 보시면 오늘 제가 논의드릴 내용들이 모두 담겨있습니다. 주 콘셉은 feature aggregation 에서 과도한 memory overhead 가 발생하므로 그것들을 pre-computation 해서 MLP (linear-layer) 에 태우면 light 하다 라는 맥락입니다. lightGCN 의 모티브인 SGC 부터 시작해서 설명이 잘 되어있습니다.
• GNN ML 엔지니어가 목표라면 필독 해야할 블로그라 생각되네요. 다양한 엔지니어링 스킬 그리고 practical 그래프 임베딩 논문들이 수록되어 있기 때문이죠. 좀처럼 보기 힘든 양질의 포스팅이라 생각됩니다.