糞糞糞ネット弁慶

読んだ論文についてメモを書きます．趣味の話は http://repose.hatenablog.com

Classification in Graphs using Discriminative Random Walks 読んだ & Rubyで実装した

論文 Ruby

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.139.6489
id:smlyさんに教わった論文．

概要

グラフにおけるクラス判別に関する半教師あり学習をランダムウォークの変形であるD-walksで解く．

notation

入力：なるグラフ．はノード集合であり，エッジ集合である．
ラベルつきノード集合，ラベルなしノード集合，ラベル集合とする．
ノードのラベルをとし，，とする．
出力：におけるラベル．
ランダムウォーク（値を伝播させるやつじゃなくてマルコフ連鎖のような，本来の意味でのランダムウォーク）の遷移確率として，tステップ目にq，t+1ステップ目にq'にいる確率を

とする．はからへのエッジの重み．

D-walks，D-betweenness

次に，D-walksを定義する．これは，長さステップのランダムウォークにおいて，開始ノードのラベルと終了ノードのラベルが等しく，かつ，終了時まで開始ノードのラベルを持つノードに到達しないものである．
数式にすると，に対して，であり，となるようなと表現できる．
をラベルから始まる長さのD-walksとし，をラベルから始まる長さ以下のD-walksの集合とする．
ついでに，をにおいてノードを通過する回数の期待値とし，これをD-betweennessと呼ぶ．
このbetweennessの定義は元論文では[cond-mat/0309045] A measure of betweenness centrality based on random walksに言及している．単語と著者に見覚えがあったので先週の自主ゼミで発表したスライドは晒しませんが読んだ論文だけは貼る - 糞ネット弁慶で読んだ[cond-mat/0308217] Finding and evaluating community structure in networksと比較したら後者はエッジを通過する回数をもってしてbetweennessとしていたので近いと言えば近い．

forward-backward

あとはこれをforward-backwardで解く．
前向き変数をラベルyからスタートしてtステップ目にqにやってくる確率とすると

となる．
同時に，後ろ向き変数をラベルyからスタートしてtステップ目にqから出て行く確率とすると

と書ける．
で，ここまでは何を言ってるか判るが，そもそもforward-backwardを全く知らないので次の式が判らない．
前向き変数と後ろ向き変数を使うとは次のように書ける．

であとは，最も高いbetweennessを持つラベルに割り当てる，つまりはとすると未知ノードのラベルが求められる．

Rubyで実装

簡単そうなのでRubyで実装．

添字間違ってたので書き直した．前のままだとB_Lが全てNaNになる．

# -*- coding: utf-8 -*-
class DWalks
  def initialize
    @edges = Hash.new{|h, k|h[k] = Hash.new{ }}
    @labels = { }
    @nodes = [ ]
    @labels_index = Hash.new{|h, k|h[k] = Array.new}
    @prob = Hash.new{0.0}
    @alpha = { }
    @beta = { }
  end

  # フォーマット
  # node1, node2, weight
  # ex. 1,2,100
  def read_graph(file_name)
    open(file_name){|f|
      f.each{|l|
        from, to, weight = l.chomp.split(",").map{|e|e.to_i}
        @edges[from][to] = weight
        @nodes.push from
        @nodes.push to
      }
    }
    calc_prob
    @nodes.uniq!
  end

  # フォーマット
  # node, label
  # ex. 1,3
  def read_label(file_name)
    open(file_name){|f|
      f.each{|l|
        node, label = l.chomp.split(",").map{|e|e.to_i}
        @labels[node] = label
        @labels_index[label].push node
      }
    }
  end

  # 遷移確率のテーブルを一括計算
  def calc_prob
    @edges.each_pair do |from, adj|
      sum = adj.values.inject(0.0){|s, e|s += e}
      adj.each_pair do |to, weight|
        @prob[from => to] = weight / sum
      end
    end
  end

  # アルファとベータは再帰しつつ保存しておく
  def alpha(y, q, t)
    if @alpha[[y ,q, t]].nil?
      if t == 1
        @alpha[[y, q, 1]] = @labels_index[y].inject(0.0){|s, e| s += @prob[e => q]} / @labels_index[y].size
      else
        @alpha[[y, q, t]] = (@nodes - @labels_index[y]).inject(0.0){|s, e| s+= alpha(y, e, t - 1) * @prob[e => q]}
      end
    end
    return @alpha[[y ,q, t]]
  end

  def beta(y, q, t)
    if @beta[[y, q, t]].nil?
      if t == 1
        @beta[[y, q, 1]] = @labels_index[y].inject(0.0){|s, e| s += @prob[q=> e]}
      else
        @beta[[y, q, t]] = (@nodes - @labels_index[y]).inject(0.0){|s, e| s+= beta(y, e, t - 1) * @prob[q => e]}
      end
    end
    return @beta[[y, q, t]]
  end

  # ラベル推定
  def estimation(q, length)
    b = Hash.new

    # ラベルが既にあったら終了
    if !@labels[q].nil?
      puts "query: #{q} is #{@labels[q]}!"
      exit(1)
    end

    # ノードがそもそもグラフになかったら終了
    if !@nodes.include?(q)
      puts "query: #{q} not found in graph!"
      exit(1)
    end

    @labels_index.each_pair do |label, nodes|
      demo = 0.0; nume = 0.0
      1.upto(length) do |l|
        demo += nodes.inject(0.0){|s, e| s += alpha(label, e, l)}
        1.upto(l - 1) do |t|
          nume += alpha(label, q, t) * beta(label, q, l - t)
        end
      end
      b[label] = nume / demo
    end
    return b.to_a.sort{|x, y| y[1] <=> x[1]}[0]
  end
end

if __FILE__ == $0
  d = DWalks.new
  d.read_graph("./sample_graph.txt")
  d.read_label("./sample_label.txt")
  p d.estimation(5, 3)
end

とする．ついでに次のようなテキストを読み込ませる．長いので続きを読むで．
sample_graph.txt

2,1,1
1,2,1
1,3,1
3,1,1
1,4,1
4,1,1
2,3,1
3,2,1
4,2,1
2,4,1
3,4,1
4,3,1
6,7,1
7,6,1
5,6,1
6,5,1
1,5,1
5,1,1
2,5,1
5,2,1
3,5,1
5,3,1

sample_label.txt

1,1
2,1
3,1
4,1
6,2
7,2

実行．

y_benjo@BENZA:~/memo% ruby sample_D_walks.rb
[1, 0.147540983606557]

見事ノード5はクラス1と推定されました．