グラフ理論::Similarity Flooding

今回はSimilarity Floodingというアルゴリズムの論文を読んでみました。

論文を読んでいると、この方法には有向でラベル付きEdgeが必要のようです。イメージとしてはInitialMapからグラフの関係を利用して重み付けを繰り返すという感じな気がします。

アルゴリズムは下記のようになっています。

SQLからグラフは論文中ので説明です。"Versatile"をうたっているので有向ラベル付きグラフを用意すればよさそうです。
InitialMapはノード間の類似度です。特に論文中では述べられてませんが、編集距離で類似度を求めれば問題ないでしょう。
Similarity Floodを使って重み付けしていくステップです。
最後にマッチング処理で取り出す

それではこのSimilarity Floodを見てみましょう。やることはFigure3をみればわかります。
(4のステップは私の今回の興味ではないので省略)

Pairwise connectivity Graph,Induce propagation graphを作ってFixpoint Valueを作る。

さてさて、どうすればプログラムに落とせるのか。
ぐぐっても、疑似コードのようにわかりやすいものはでてこない。
かといって、オリジナルのjavaソース達を読む気にはならない。

しょうがないから自分で書いてみます。

必要なものは

類似度の行列
ラベル付きEdgeのPairwise Connectivy Graph(PCG)

の二つがあれば力づくて類似度が計算できそうです。
とは思ったものの、意外と大変でした。Figure3をじっくり読んでふるまいをコードに落としました。

sub SimilarityFlooding {
    my ($self) = @_;

    # Store similarity matrix $sim{vertex1}{vertex2} 
    my %sim;
    my $g1 = $self->graph;
    my $g2 = $self->graph2;

    # Create InitialMap
    # Similarity is calculated by 1 - (edit distnace(stringA, stringB) / length of the stringA + stringB)
    # This calcualtion can be changed
    for my $v1 ($g1->vertices){
        for my $v2 ($g2->vertices){
            $sim{$v1}{$v2} = 1 - (distance($v1, $v2) / length("$v1$v2"));
            #$sim{$v1}{$v2} = 1;
        }
    }

    # Create Pairwise Connectivity Graph
    my $pcg = Graph->new(multiedged => 1);

    # Frist, collect source, destination node and label
    # The is for Graph1
    my %m1;
    my %labels;
    for my $v1 ($g1->vertices){
        for my $p1 ($g1->predecessors($v1)){
            for my $label ($g1->get_multiedge_ids($p1, $v1)){
                # {"LABEL"}{"SOURCE NODE"}{"DESTINATION NODE"}
                $m1{$label}{$p1}{$v1} = 1; # There is no meaing to put 1. Just want to pickup unique key later
                $labels{$label} = 1;
            }
        }
    }
    # For Graph2
    my %m2;
    my @labels;
    for my $v2 ($g2->vertices){
        for my $p2 ($g2->predecessors($v2)){
            for my $label ($g2->get_multiedge_ids($p2, $v2)){
                # {"LABEL"}{"SOURCE NODE"}{"DESTINATION NODE"}
                $m2{$label}{$p2}{$v2} = 1;
                $labels{$label} = 1;
            }
        }
    }
    # Secondary, add pairwise node. 
    # Node name is src1(from graph1)/src2(from graph2) or dest1(from graph1)/dest2(from graph2)
    # %edges used for couting the label of neighbors
    my %edges;
    for my $label (keys %labels) {
        #print $label, "------\n";
        for my $src1 (keys %{$m1{$label}}){   
            for my $src2 (keys %{$m2{$label}}){
                for my $dest1 (keys %{$m1{$label}{$src1}}){   
                    for my $dest2 (keys %{$m2{$label}{$src2}}){
                        #print "src - $src1,$src2\n";
                        #print "dest - $dest1,$dest2\n";
                        $pcg->add_edge_by_id("$src1/$src2", "$dest1/$dest2", $label );
                        $pcg->add_edge_by_id("$dest1/$dest2", "$src1/$src2", $label );
                        $edges{"$src1/$src2"}{$label}++;
                        $edges{"$dest1/$dest2"}{$label}++;
                    }
                }
            }
        }
    }


    # Start iteration 
    for (my $i=0; $i<5; $i++){

        # Based on label info, create the logic to behave as the same as "Induced Propagation Graph" in the paper
        my $max=0;
        my %next_sim;
        for my $v1 ($g1->vertices){   
            for my $v2 ($g2->vertices){

                my $sum=0;
                for my $n ($pcg->neighbours("$v1/$v2")){
                    for my $label ($pcg->get_multiedge_ids($n, "$v1/$v2")){
                        #print 1/$edges{$n}{$label};
                        #print " * $n : neighbor of $v1/$v2\n";
                        my ($n1, $n2) = split /\//, $n;
                        $sum += $sim{$n1}{$n2} / $edges{$n}{$label};

                    }
                }

                $next_sim{$v1}{$v2} = $sim{$v1}{$v2} + $sum;
                if ($max < $next_sim{$v1}{$v2}){
                    $max = $next_sim{$v1}{$v2};
                }
            }
        }

        # Normalizing
        # Deviding the maximum value
        for my $v1 ($g1->vertices){
            for my $v2 ($g2->vertices){

                if (defined $next_sim{$v1}{$v2}){
                    $sim{$v1}{$v2} = $next_sim{$v1}{$v2} / $max;
                }
                else {  
                    $sim{$v1}{$v2} = $sim{$v1}{$v2} / $max;
                }
            }
        }

    }

    print Dumper %sim;

}

やれやれだぜ。時間をかけてやっとFigure3と似た数字がでるようになりました。

では、例で見ていきます。

グラフ１

グラフ２

５回Iterateさせると類似度が下記になります。

$VAR1 = 'swim';
$VAR2 = {
          'apple juice' => '0.00833163161119053',
          'she' => '0.0142827970477552',
          'swim' => '0.0249948948335716',
          'cake' => '0.0124974474167858'
        };
$VAR3 = 'apple';
$VAR4 = {
          'apple juice' => '0.0156218092709822',
          'she' => '0.0124974474167858',
          'swim' => '0.011108842148254',
          'cake' => '0.708066162956912'
        };
$VAR5 = 'I';
$VAR6 = {
          'apple juice' => '0.00208290790279763',
          'she' => '1',
          'swim' => '0.00499897896671431',
          'cake' => '0.00499897896671431'
        };
$VAR7 = 'coffee';
$VAR8 = {
          'apple juice' => '0.705942413722687',
          'she' => '0.011108842148254',
          'swim' => '0.00999795793342863',
          'cake' => '0.0149969369001429'
        };

ラベルに引っ張られてなかなか良い類似度がでてるのではないかと思います。

まとめ

この方法はEdgeラベルが超重要。Edgeラベルに信頼性のあるデータなら試してみる価値あり。

Debuginfo

思考とアウトプット

グラフ理論::Similarity Flooding