グラフ理論::Coupled node-edge scoring

注意：この記事は私の解釈です。間違っていたらつっこんでください。

GED(Graph Edit Distance)はとりあえず置いといて、Coupled Node Edge Scoringにジャンル分けされている手法を勉強します。
(SimRankはどうやらInteractive Methodというらしい cf. Laura's paper)。

参考にした論文と資料は下記の三つです。

Coupled Node Edge ScoringはKleinberg氏のノードをAuthorityとHubに分ける考えを元にしているようです。このAuthority,Hubからスコアリングして、グラフAのノードとグラフBのノードの類似度をグラフの関係性のみより導き出します。精度と計算コストは気になりますね。

論文のイントロあたりに考え方が書いてありますが、簡単な解釈としては、同じ方向性を持つ同じ名前のノードはAuthorityとHubスコアで高まるという感じでしょうか。肝の数式は下記です。

丸にバツが書いてある記号はKronecker Productというものらしい（なんだそりゃ、Help Wiki Pedia san! -> http://en.wikipedia.org/wiki/Kronecker_product )。変形に関してはvec(AXB)の公式で行ってます。
分母はノルムです。計算は二乗和をルートすればよさそうです。

知識がないので調べまくってやっと理解しましたよ。とほほ。

論文の中では初期値や収束性を議論していますが、私は数学者ではなく情報屋なのでとりあえず、計算機に落としてから考察することにします。

Algorithm:
1. Set Z0 = 1.
2. Iterate an even number of times,
and stop upon convergence
3. Output S in the last value of Zk

収束はとりあえず、気にせずループさせることにします。ちなみに収束させる方法は幾つかあるようです。

では、２つのグラフを用意します。

グラフ１

グラフ２

それでやっつけで書いたコード。(将来的に整理してcpanに上げたいと思っています)

sub CoupledNodeEdgeScoring {
    my ($self, $ref) = @_;

    my $loop = $$ref{loop};
    my $node1 = $$ref{node1};
    my $node2 = $$ref{node2};

    my $g1 = $self->graph;
    my $g2 = $self->graph2;

    die "two grpahs are needed\n" unless (defined $g2);

    unless ($g1->is_directed && $g2->is_directed) {
        die "Graphs should be directed graph";
    }

    # Create Matrix
    # for graph1 
    my $adj1 = Graph::BitMatrix->new($g1);
    my @v1 = $adj1->vertices; # the sequence order is importanct. Keep this.
    my %v1;
    my @a1;
    my $c1=0;
    for my $v (@v1){
        $v1{$v}= $c1++;
        my @tmp = $adj1->get_row($v, @v1);
        push @a1, \@tmp;
    }
    my $m1 = new Math::Matrix(@a1);

    # for graph2
    my $adj2 = Graph::BitMatrix->new($g2);
    my @v2 = $adj2->vertices; 
    my %v2;
    my @a2;
    my $c2=0;
    for my $v (@v2){
        $v2{$v}= $c2++;
        my @tmp = $adj2->get_row($v, @v2);
        push @a2, \@tmp;
    }
    my $m2 = new Math::Matrix(@a2);

    # for initial z = 1
    my @z;
    for my $v2 (@v2){
        my @tmp;
        for my $v1 (@v1){
            push @tmp, 1;
        }
        push @z, \@tmp;
    }
    my $z = new Math::Matrix(@z);

    # loop should be even count
    $loop++ unless ($loop%2 == 0);

    for (my $i=0; $i<$loop;$i++){

        # B * Z * A^T
        my $tmp1 = $m2->multiply($z)->multiply($m1->transpose);
        # B^T * Z * A
        my $tmp2 = $m2->transpose->multiply($z)->multiply($m1);
        
        my $numerator = $tmp1->add($tmp2);

        my ($m, $n) = $numerator->size;

        my $sum=0;
        for my $row(0..($m-1)){
            for my $col (0..($n-1)){
                $sum += $numerator->[$row][$col] * $numerator->[$row][$col];
            }
        }
        my $denominator = sqrt($sum);

        $z = $numerator->multiply_scalar(1/$denominator);

        #$z->print;
        #print "---\n";

    }

    print @v1, "\n";
    print @v2, "\n";
    $z->print;

    return $z->[$v2{$node2}][$v1{$node1}];

}

ループ１０回で類似度の行列は

     c                a              b
e   0.30690    0.00000    0.00189 
c   0.30690    0.00000    0.00189 
a   0.00000    0.61380    0.06062 
b   0.06062    0.00189    0.46035 
d   0.06062    0.00189    0.46035

となりました。

graph1のaとgraph2のaの類似度が最大の0.61です。
次がb-b,b-d,その次がc-c, c-e。（ちょい微妙？）
コードが間違っていなければ、存在するものに引きずられるという感じでしょうか。

まとめ：

感覚的には大きくははずれてないけど、変な数字もでてくる。他手法と組み合わせでおもしろくなりそう。

Debuginfo

思考とアウトプット

グラフ理論::Coupled node-edge scoring