# Bluesky Path Finder を実装した
Bluesky はオンラインソーシャルネットワーキングサービスです．これまで招待コードが必要だったのですが，2024年2月6日に招待コード不要で誰でも登録できるようになったため現在急速に盛り上がっています．個人的には Twitter (X) に何かあったときのためにそれなりに盛り上がっていてくれるといいなと思っています．
ところで，ソーシャルネットワークはユーザを頂点・フォロー関係を枝とする巨大なグラフです．巨大なグラフを見たら最短路を計算したくなりますよね．一般にソーシャルネットワークはユーザ同士を少ないホップ数で繋ぐ（[スモールワールド性](https://ja.wikipedia.org/wiki/%E8%A4%87%E9%9B%91%E3%83%8D%E3%83%83%E3%83%88%E3%83%AF%E3%83%BC%E3%82%AF#%E3%82%B9%E3%83%A2%E3%83%BC%E3%83%AB%E3%83%AF%E3%83%BC%E3%83%AB%E3%83%89%E6%80%A7)）といわれているので，実際どんなものか見てみたいのは自然な気持ちです．
というわけで計算するプログラムを書きました．[こちら](https://bluesky-apps.raven-sun.ts.net/path-finder)から遊ぶことができます．ここでは実装の概要を紹介します．
## 問題設定・アルゴリズム
クエリとしてユーザが 2 人指定されるので，その間の最短路を計算して出力します．
一般に，このタスクは**最短路クエリ**と呼ばれています．カーナビにも用いられる基本的なグラフタスクですが，実は効率的に計算するのが結構難しい問題として知られています．以下 $n$ でグラフの頂点数，$m$ でグラフの枝数を表すことにします．最も素朴なアルゴリズムはクエリが与えられるたびに最短路を計算するものですが，これはクエリのたびに $\Theta(m)$ 時間かかってしまうため，オンラインサービスにするには遅すぎて実用的ではありません．別の素朴なアルゴリズムは事前に全頂点間の距離を計算しておくものです．これはクエリに対する応答は $O(1)$ 時間でできますが，そのかわりに $\Theta(nm)$ 時間の前処理と $\Theta(n^2)$ 空間がかかります．これらはいくら前計算といっても大規模グラフでは許容できません．これらの間をうまく取れるかはかつて盛んに研究されていたトピックであり，一般には近似ですら難しいことがわかっています．詳しくは http://www.shortestpaths.com/spq-survey.pdf などを参照してください.
さて，いくら最短路クエリが理論的に難しいタスクとはいえ，実用上重要な問題なので解かなければいけません．そこで研究者たちはグラフの性質を利用した様々なヒューリスティクスを提案してきました．ソーシャルネットワークの最短路クエリでは，ソーシャルネットワークが**少数の "ハブ" を通じて多くの頂点が結びついている**ことに着目した手法が多く提案されてきました．そのような手法の１つに [Hub Labelling](https://en.wikipedia.org/wiki/Hub_labels) があります．これはハブ $h_1, h_2, \dots$ までの距離 $d(s, h_i)$ とハブからの距離 $d(h_i, t)$ を事前計算しておくことで頂点 $s$, $t$ 間の距離を $\min_i d(s,h_i) + d(h_i,t)$ で推定するものです．これは適当なハブを経由するパスに制限したことになります．作り方からハブを経由しない最短路を見逃すので個別の頂点対に対する精度は保証されません．ハブを見出すのはそれ自身が非自明なタスクですが，実用的には次数の高い頂点を選んでおくとそれなりにうまくいきます．
ここでは Hub Labelling アルゴリズムとして [Akiba-Iwata-Yoshida 2013](https://arxiv.org/abs/1304.4661) を実装します．このアルゴリズムではラベルにハブを逐次的に追加していきます．新しいハブ $h$ を追加する際には $h$ から各頂点 $u$ までの距離を BFS によって計算するのですが，もしハブ $h$ から $u$ までの距離がこれまでのラベルを使って計算できているなら，すなわち $d(h, u) = \min_i d(h, h_i) + d(h_i, u)$ であるなら，$u$ 以降を BFS で展開する必要はありません（$\because$ $h_i$ からの経路で代替できるため）．これを使ってラベルの構築時間とサイズを削減するのがこの手法の骨子です．ソーシャルネットワークではこの削減が非常に強力に働くことが知られています．アルゴリズムの詳細は論文を参照してください．
## データセット
Bluesky のソーシャルネットワークをクロールしてグラフを作りました．負荷をかけないためにクロール速度を落としているのとユーザが急速に増えているのとで網羅率は全然ですが，それでも一応 2M 頂点 20M 枝くらいはあります．公式アナウンスとあわせると概ね 50% くらいの頂点をカバーしていることになります．
とはいえ Twitter や Facebook といったすでに確立しているソーシャルネットワークたちが 2B 程度の頂点をもつことを考えると 2M 頂点は全然小さく，巨大グラフとは言いづらい規模感です．一方でこれくらいの規模であればグラフを全てメモリに入れて素朴なアルゴリズムを実行することができるので，我々が手元の計算機で遊ぶにはちょうどよいサイズとも言えます．
## 実装のポイント
クエリされる頂点 $s$, $t$ は手元のデータセットにあるとは限りません．これは Bluesky が急速に成長していることとクロール速度がそれに追いついていないことに起因します．特に新規ユーザのまわりの枝状況はデータセット構築時点とクエリ時点で大きく異なる可能性があるため前計算したラベルが信頼できません．
論文の実験であれば手元のグラフでだけうまく動けばいいのですが，今回のようにサービスとして公開して遊んでもらうのであれば，どんなユーザに対してもそれなりの出力を返すのが望ましいです．
今回はこの問題を解決するために次の手順で計算を行っています．
1. $s$ と $t$ が同一頂点なら距離 $0$．
2. Bluesky API を呼び出して $s$ の近傍の一部 $N_s$ と $t$ の近傍の一部 $N_t$ を取得する．
3. $s \in N_t$ もしくは $t \in N_s$ であれば距離 $1$．
4. $N_s \cap N_t \neq \emptyset$ であれば距離 $2$．
5. $u \in N_s \cup \{s\}$ と $v \in N_t \cup \{ t \}$ を適当にサンプルして前計算しておいたラベルを用いて最短路を参照する．距離 3 のものを見つけたらただちに終了する．
このアルゴリズムであれば，クエリされた頂点の近傍に１つでもラベルを信頼できる頂点があれば精度が担保されます．近傍サイズはデプロイ当初は Bluesky API の都合で 100 頂点としていたのですが，直接フォローしている相手を見つけられないことが多かったので 300 頂点に増やしました．仕様上 300 人以上フォローしているユーザ同士の直接のつながりは見落とすことがあります．
## その他
最短路計算は CPU ヘビーな処理なので Rust でバックエンドサービスとして実装しました．格納されているデータを読み込むために [sqlx](https://github.com/launchbadge/sqlx) を使い，API サーバとしてサーブするために [Axum](https://github.com/tokio-rs/axum/) を使っています．Bluesky API の呼び出しには [Atrium](https://github.com/sugyan/atrium) を使いました．
グラフ構造とグラフアルゴリズムは自前で実装しています．せっかくなのでこの部分のコードだけ添付しておきます．
```rust=
use std::collections::HashMap;
#[derive(Clone)]
pub struct Graph {
pub index: HashMap<String, usize>,
pub name: Vec<String>,
pub source: Vec<usize>,
pub target: Vec<usize>,
pub first_out: Vec<Option<usize>>,
pub first_in: Vec<Option<usize>>,
pub next_out: Vec<Option<usize>>,
pub next_in: Vec<Option<usize>>,
}
impl Graph {
pub fn num_nodes(&self) -> usize {
self.first_out.len()
}
pub fn num_edges(&self) -> usize {
self.next_out.len()
}
pub fn new() -> Self {
Self {
index: HashMap::new(),
name: Vec::new(),
source: Vec::new(),
target: Vec::new(),
first_out: Vec::new(),
first_in: Vec::new(),
next_out: Vec::new(),
next_in: Vec::new(),
}
}
pub fn get_or_create_index(&mut self, node: &str) -> usize {
if let Some(&id) = self.index.get(node) {
id
} else {
let id = self.name.len();
self.index.insert(node.to_owned(), id);
self.name.push(node.to_owned());
self.first_out.push(None);
self.first_in.push(None);
id
}
}
pub fn add_edge(&mut self, source: &str, target: &str) -> usize {
let id = self.source.len();
let source_id = self.get_or_create_index(source);
let target_id = self.get_or_create_index(target);
self.source.push(source_id);
self.target.push(target_id);
self.next_out.push(self.first_out[source_id]);
self.first_out[source_id] = Some(id);
self.next_in.push(self.first_in[target_id]);
self.first_in[target_id] = Some(id);
id
}
pub fn out_degree(&self, u: usize) -> usize {
let mut d = 0;
let mut iter = self.first_out[u];
while let Some(e) = iter {
d += 1;
iter = self.next_out[e];
}
d
}
pub fn in_degree(&self, u: usize) -> usize {
let mut d = 0;
let mut iter = self.first_in[u];
while let Some(e) = iter {
d += 1;
iter = self.next_in[e];
}
d
}
}
```
```rust=
use std::cmp::Reverse;
use std::collections::{HashMap, VecDeque};
use crate::graph::Graph;
#[derive(Clone)]
pub struct HubLabelling {
index: HashMap<String, usize>,
name: Vec<String>,
source_tree: Vec<HashMap<usize, (usize, usize)>>, // (s', d) = source_tree[s].get(h)
target_tree: Vec<HashMap<usize, (usize, usize)>>, // (t', d) = target_tree[t].get(h)
}
impl HubLabelling {
fn _hub(&self, s: usize, t: usize) -> Option<(usize, usize)> {
// find the hub
let mut best = None;
for (h, (ds, _)) in self.source_tree[s].iter() {
if let Some((dt, _)) = self.target_tree[t].get(h) {
let x = Some((*ds + *dt, *h));
if best.is_none() || x < best {
best = x;
}
}
}
best
}
fn _distance(&self, s: usize, t: usize) -> usize {
if let Some((d, _)) = self._hub(s, t) {
d
} else {
usize::MAX
}
}
pub fn query(&self, source: &str, target: &str) -> Option<Vec<String>> {
let s = self.index.get(source)?.to_owned();
let t = self.index.get(target)?.to_owned();
if let Some((_, h)) = self._hub(s, t) {
let source_path = {
let mut path = Vec::new();
let mut curr = s;
while curr != h {
path.push(self.name[curr].to_owned());
if let Some((_, next)) = self.source_tree[curr].get(&h) {
curr = *next;
}
}
path
};
let target_path = {
let mut path = Vec::new();
let mut curr = t;
while curr != h {
path.push(self.name[curr].to_owned());
if let Some((_, next)) = self.target_tree[curr].get(&h) {
curr = *next;
}
}
path
};
let path: Vec<_> = source_path
.into_iter()
.chain(std::iter::once(self.name[h].to_owned()))
.chain(target_path.into_iter().rev())
.collect();
Some(path)
} else {
None
}
}
pub fn new(graph: &Graph, limit: usize) -> Self {
let mut this = Self {
index: graph.index.clone(),
name: graph.name.clone(),
source_tree: vec![HashMap::new(); graph.num_nodes()],
target_tree: vec![HashMap::new(); graph.num_nodes()],
};
// generate a degree-sorted nodes
let mut order = Vec::new();
let num_nodes = graph.num_nodes();
for u in 0..num_nodes {
let degree = graph.out_degree(u) + graph.in_degree(u);
order.push((Reverse(degree), u));
}
order.sort();
for (_, h) in order.into_iter().take(limit) {
println!("Indexing hub {}", h);
// run outgoing bfs from h
let mut queue = VecDeque::new();
let mut distance = vec![usize::MAX; graph.num_nodes()];
distance[h] = 0;
this.target_tree[h].insert(h, (0, h));
queue.push_front(h);
while let Some(u) = queue.pop_back() {
let mut iter = graph.first_out[u];
while let Some(e) = iter {
let v = graph.target[e];
let d = distance[u] + 1;
if d < distance[v] && d < this._distance(h, v) {
this.target_tree[v].insert(h, (d, u));
queue.push_front(v);
distance[v] = d;
}
iter = graph.next_out[e];
}
}
// run incoming bfs from h
let mut queue = VecDeque::new();
let mut distance = vec![usize::MAX; graph.num_nodes()];
distance[h] = 0;
this.source_tree[h].insert(h, (0, h));
queue.push_front(h);
while let Some(u) = queue.pop_back() {
let mut iter = graph.first_in[u];
while let Some(e) = iter {
let v = graph.source[e];
let d = distance[u] + 1;
if d < distance[v] && d < this._distance(v, h) {
this.source_tree[v].insert(h, (d, u));
queue.push_front(v);
distance[v] = d;
}
iter = graph.next_in[e];
}
}
}
println!("Finished indexing");
this
}
}
```
Sign in with Wallet
Connect another wallet