2009-05-28

Web Spam Taxonomy

論文

Zoltan Gyongyi, Hector Garcia-Molina
Web Spam Taxonomy
In Proceedings of 1st International Workshop on Adversarial Information Retrieval on the Web
2005. May
論文の在処

概要

タイトル通りウェブスパムの分類をしている。
Term SpammingとLink Spammingと大きく二つに分けている。
スパム行為を隠すテクニックに関しても少し書いている。
他の３つの論文の３つのスパムに関するデータを用いて、スパムページの割合などを議論している。

1. Introduction

導入。
検索エンジンはWebの入り口。
検索結果に対してスパムは悪影響を。実際"Kaiser pharamcy"で検索したときの例を用いている。
次にスパムにより検索エンジンのインデックスが膨張し、processed queryにかかるコストが増えることを問題だとしている。

2. Definition

まず、relevanceとimportanceの定義。relevanceは特定のクエリに対する関連性で、importanceはクエリーに関係なくページの重要性。

spamming refers to any deliberate human action that is meant to trigger an unustifiably favorable relevance or importance for some web page, considering the page's true value.
spamという形容詞をspammingによって生み出されるウェブのコンテンツやリンクに対して使う。spammingをする人をspammerと呼ぶ。

いくつかのSEOはweb communityに利益をもたらすが、ほとんどをspammingとみなす。

web spamに関連したテクニックは二つのカテゴリに分けられる。一つはrelevanceやimportanceを大きくするテクニック。もう一つはその行為を隠すテクニック。

3. Boosting Techniques

検索結果を向上させるテクニックを紹介。

3.1 Term Spamming

Term Spammingとはページのテキストフィールドのコンテンツをいくつかのクエリに対してrelevanceを上げるために仕立てるテクニック。

3.1.1 Target Algorithms
TFIDF。

3.1.2 Techniques
まずspammingを行うテキストフィールドによって分類できる。

・Body spam：
シンプルにbodyで行う。

・Title spam：
今日の検索エンジンはtitleに大きく重みを与えるので、titleでのspammingは理にかなっている。

・Meta tag spam：
最近の検索エンジンはheavy spammingのためメタタグの重みを小さくしている。

・Anchor text spam：
titleと同じように検索エンジンはアンカーテキストに大きな重みを与えている。
他のページをいじらないとできないことに注意

・URL spam：
いくつかの検索エンジンはURLを分析してrelevanceを決定するのに利用している。スパマーは時々spam termの連続の長いURLを使う。

spammingテクニックは良く合わせて使われる。

別の分類の方法はテキストフィールドに追加されたtermsのタイプによって行われる。

・Repetition：
少ない数のクエリに対してrelevanceを大きくする。

・Dumping：
関係ないterms、often even entire dictionariesをdumpする。
たくさんの異なるクエリに対してrelevanceを大きくする。dumpingは比較的rareでobscureなtermを含むクエリに対して有効。そのようなクエリに対してrelevantなページは少ないので、spam pageがトップに出てきやすい。

・Weaving：
他のページ（ニュース記事など）のテキストをコピーして、その間にspam termsを埋め込む。オリジナルのテキストがrareなとき有効。spam termsの繰り返をばれにくくする効果もある。

・Phrase stitching：
ほかのページからsentencesやphrasesをコピーしてきてつなげる。

3.2 Link Spamming

ページのimportanceを大きくするためにリンク構造を作る。

3.2.1 Target Algorithms
まずspammerが以下の三つのタイプのページを利用できるモデルを考える。
1. Inaccessible pages：このページの出リンクはいじれない。
2. Accessible pages：他の人に管理されているが、出リンクを書くことができる。
3. Own pages：何でもできる。own pagesの集合をスパムファームと呼ぶ。スパマーはこのようなページをn個持てるとする。

このモデルを念頭において、HITSとPageRankについて議論する。

3.2.2 Techniques
spammingテクニックを、ポピュラーなページへの出リンクを増やすか、入リンクをtargetページやページの集合にに集めるかで分類する。

Outgoing linkes
良く知られたページに手動でリンクをはったり、DMOZ Open DirectoryやYahoo! directoryなどをコピーする。

Incoming links
以下のような戦略で特定のページにリンクを集める。

・Create a honey pot：
Unix documentation pagesのコピーなどの有用なリソースを与えるページの集合（honey pot）を作り、そこから特定のスパムページへのリンクを張る。honey potは人々を引きつけ他のページからのリンクを集め、間接的にtargetページのランキングを上げる。

・Infiltrate a web directory：
いくつかのweb directoriesはウェブの管理者に彼らのサイトへのリンクをディレクトリのtopicの下に貼ることを許している。このようなdirectoriesのeditorがリンクの追加を管理しきれないこともある。そのときスパマーはtargetページへのリンクをこのようなdirectoryに追加する。directoriesは高いPageRankとhub scoreを持っている傾向があるので、このspamming techniqueはPageRankとauthority score両方を上げる効果がある。

・Post links on blogs, unmoderated message boards, guest books, or wikis：
targetページへのリンクを他のブログのコメントなどに埋め込む。

・Participate in link exchange：
しばしばスパマーのグループがリンクを交換する構造をset upしているので、それに参加する。

・Buy expired domains：
期限の切れたドメインを買って、そこにスパムページを作り、そこに向かって張られていたリンクを利用してrelevanceとimportanceを高める。

・Create own spam farm：
自分でリンクファームを構成する。

4. Hiding Techniques

ウェブユーザや検索エンジン会社のeditorからスパム行為を隠すテクニック。

4.1 Content Hiding

・背景色と同じ色でテキストを書く
・1ピクセルのアンカーイメージを埋め込む
・visible属性をfalseにする

4.2 Cloaking

crawlerと通常のウェブブラウザに対して別々のページを与えるようにする。

4.3 Redirection

検索エンジンにindexされたページからユーザを自動的に他のURLにredirectする。

5. Statisctics

他の論文の３つのスパムに関する統計データに関して議論。

6. Conclusions

この論文ではさまざまな一般に使われているウェブspammingテクニックを示し、分類した。research communityのawarenessをあげるのにこのようなstructureされた議論は重要だと主張する。このspam taxonomyは対抗策の似たようなtaxonomyも自然に導く。検索エンジンがspamとの戦いに適用できる二つのアプローチの要点を以下に記す。

1. Identify instances of spam：特定のタイプのスパムを発見し、そのようなページのクロールあるいはインデクシングをやめる。検索エンジンは自動、半自動の専売特許のスパム発見アルゴリズムと、indexesからスパムページを特定し取り除くhuman editorsの専門技術をいつも利用する。例えば[3]に示されたテクニックは機械により生成された構造、コンテンツのスパムファームを特定するのに利用されている。

2. Prevent spamming：特定のspammingテクニックを防ぐ。例えばクローキングを避けるため検索エンジンのクローラが普通のウェブブラウザのように振る舞う。

3. Counterbalance the effect of spamming：今日の検索エンジンは基本的なランキングメソッドのバリエーションを使っている。これらの特徴はspamにたいする復元力。

一方で個々のspammingテクニックに関わらず、spammingの問題にまとめて取り組むことも可能。このアプローチはスパムページのいくつかの共通するfeaturesに頼る。
例えば[5]に示されているスパム発見メソッドは立派なnon-spamページのapproximate isolationを利用している。立派なページは滅多にスパムをささない。なので、適切なリンク解析アルゴリズムは立派なページをスパムページから切り離すことができる、それぞれのspammingテクニックを個々に扱うことなしに。

2009-01-12

A Large-Scale Study of Link Spam Detection by Graph Algorithms

論文

H. Saito, M. Toyoda, M. Kitsuregawa, K. Aihara
A Large-Scale Study of Link Spam Detection by Graph Algorithms
In Proceedings of 3rd International Workshop on Adversarial Information Retrieval on the Web
2007. May
論文の在処

概要

リンク構造からグラフアルゴリズムを用いてリンクファームを見つけ、分析している。
強連結成分分解、極大クリーク発見、最小カット法を用いている。
2007年の日本のウェブサイトに対して実験。

1. INTRODUCTION

スパマーはlink farmと呼ばれる密なリンク構造を持つサイトを利用することが多く、[8]に要約されているような様々なテクニックを使う。

リンクファームのリンク構造に対する研究はほとんどなされておらず、この論文では大規模なグラフでのリンクファーム全体の構造と分布を調べる。
日本のWebで5.8mのサイト、283mリンクのデータを利用。

スパムの構造を調べるために３つのグラフアルゴリズムを利用。
まず、グラフを強連結成分に分解する。最大連結成分をcoreと呼ぶ。coreのサイズは[5]と同じように30%くらい。面白いことにcore周りのほとんどの大きな連結成分はリンクファームからなることを観察した。0.6mくらいのスパムサイトがこれらの成分の中に見つかった。
coreの内部のスパムサイトを見つけるため、spam seed setを元にスパムとノンスパムサイトの間のリンクを分けるminimum cut techniqueを利用。リンクファームのseedsとして極大クリークを列挙した。この列挙できつくつながったリンクファームを形成する8,000のスパムサイトが見つかった。minimum cut techniqueのspam seed setとして、この列挙された極大クリークと前述の大きな強連結成分を利用。これによりさらに49thouのサイトが高いprecisionでスパムとして見つかった。従って、57thouのスパムがcoreの中に見つけられたことになる。

以降の論文の構成は以下。
Section 2では関連した先行研究を簡単に眺める。Section 3ではデータセットの説明をする。Section 4ではデータセットの強連結成分への分解の結果を示す。Section 5では極大クリーク列挙のアルゴリズムを分解された成分に対して適用する。さらにSection 6ではweb graphにより得られたネットワークでの最小カットによるクラスタリングを提案する。最後にSection 7で結論を示す。

2. RELATED WORK

リンクスパムは主にPageRank[16]やHITS[10]などのリンクに基づいたランキングアルゴリズムを攻撃する。
ランキングスコアをあげるために、人気のあるサイトからのリンクを加え、多くのリンクをターゲットとなるサイトに集めようと、様々な手段を使う。例えば彼らのサイトをお互いにリンクしあう[8]。
リンクスパムのテクニックがPageRankに与える影響が[4,7]で実験されている。

リンクスパムに対抗する様々なテクニックが提案されてきた。
それらのうちのいくつかは、入次数や出自数、ランキングスコアに基づいたリンクになどのリンク構造をfeaturesとして機械学習を利用している[1,2,3]。
他のアプローチはリンクスパムに対して頑強になるようにランキングアルゴリズムを改善すること。いろいろなランキングアルゴリズムが提案され、実データにたいしてテストされている[4,9,11]。
[15,17,13]のようにlink-basedのアプローチもいくつかあり、二重連結成分やcommonality of neighborsといったいくつかのグラフ理論の考えを使っている。

知る限りではリンクスパムサイトの分布、範囲の広いweb graph構造でのそれらの繋がりは研究されていないが、多くのスパムサイトを特定するためにはこれらは重要。

Broderら[5]もまたweb graphに対して強連結成分への分解を行っており、グラフのglobal propertyを観察している。この論文では彼らの観察に加えてcoreの周りの大きな強連結成分に含まれるほとんどのサイトがスパムで、coreにより連結されることを発見した。

Flakeらはでトピックに関連したサイトの集合であるコミュニティを効果的に特定することができるmaximum flow/ minimum cut frameworkを提案している[6]。これらのアプローチはサイト間のリンクの向きを無視しているが、リンクスパム発見ではリンクの向きは非常に重要なので（[9]で観察されているようにスパムサイトは有料サイトに頻繁にリンクを張り、有料サイトはスパムサイトにほとんどリンクを張らない。）この論文ではリンクの向きを組み込んだmaximum flow frameworkを提案し、coreに適用する。

3. DATASET

2004年5月にクロールして得られた日本のウェブアーカイブのスナップショットを実験に使った。基本的にクローラーは[14]のbreadth-first crawlingに基づいている。
.jp以外のドメインでも日本語で書かれているページは集めた。
日本語で書かれていないページをフィルタリングするときはウェブサイトをユニットとして扱い、サイト内の最初の数ページに日本語のページが出てこなかったら、そのサイトから集めるのをやめた。
日本語のページは60%と見積もられ、全体のスナップショットは96mページ、4.5bnリンクからなる。

ノードがウェブサイトで、エッジがサイト内のページ間でのリンクを表すサイトレベルのグラフを使った。
このサイトグラフではページレベルのグラフでは見つからないようなスパムサイト間での密なつながりが簡単に見つかる。

サイトグラフを構築するため、まずそれぞれのサイトの代表のページを選ぶ。代表ページには３以上の他のサイトからのin-linksを持ち、URLが３開層以内のページ（http://A/B/B/のようなサイト）を選ぶ。次にそれぞれの代表ページの下のページが一つのサイトにまとめられる。最後にそれぞれのサイト内のページ間にリンクがある場合にサイト間のエッジを張る。
構築されたサイトグラフは5.8mのサイトと283mのリンクを持った。

このデータセットをweb graphとこの論文では呼ぶ。web graphのいくらかの特徴と統計量がTable 1とTable 2に示してある。
論文での計算が行われた環境はfour AMD Opteron 2.8 GHz processors、16GB RAM。

4. STRONGLY CONNECTED COMPONENTS DECOMPOSITION

強連結、強連結成分の説明。
強連結成分は一意にノードをばらばらのunionに分解し、その分解は線形時間で見つかる。
スパムサイトはお互いに密に繋がっていて、良いサイトはほとんどスパムにリンクを張らないので、スパムサイトが良いサイトのない強連結成分を構成すると期待できる。

以降ではいくつかの観察結果を示す。
web graphは3,424,385の成分に分解される。サイズの分布は[5]で観察されたようになり、指数2.32のベキ上則に従う。最大強連結成分（core）の濃度（ノードの数）は1,784,322。kono
coreは多くのそうそうたるサイトを含んでいて、データの中心と見ることができる。
単一のページからなる成分は3,398,316。

[5]に習ってbow tie structureがFigure 1に示されている。koreha
coreと他の部分との繋がりを含まれるサイトの割合とともに示してある。
このstructureの中にどのようにリンクファームが分布しているかは残りのsectionで示す。

次にcore以外で比較的大きな成分、100ノード以上を持つ成分について見て行く。
そのような成分は551あり、約571thouのサイトがその中に含まれる。
頻繁なドメインは.com（70.2%）、.info（16.4%）、.net（8.5%）で.jpドメインはなかった。

Figure 2にはそれぞれの成分の密度の分布が示してある。密度とはサブグラフ内のエッジの数を存在しうる最大のエッジの数で割った値。半分以上の成分が密度0.5以上の密度を持つ密なリンク構造を持つことがわかる。

さらに、これらからランダムに110の成分を抽出し、それぞれから５つのサイトをサンプルとしてランダムに抽出し、spam、suspicious、non-spamの三つのカテゴリーに分類した。Table 3にその数と割合が示してあり、サンプルのほとんどがスパムであることがわかる。

最後に得られた成分がbow tie structureの中でどのように分布しているのかを考える。
Table 4にはbow tie structureの４つの領域、OUT・IN・TENDRIL・OTHERS、に含まれる成分の数、サイトの数が示してあり、リンクファームのほとんどがOUTに属していることがわかる。
Figure 3にはcoreとリンクファームの繋がりが示してある。Figure 3はcore・IN・OUTからサイズが1000以上の強連結成分を抽出することで得た。
多くの大きな強連結成分がcore周りに存在し、驚くべきことにそのすべてがリンクファームだった。coreから大きな強連結成分への弧が多く存在し、これらの強連結成分がoptimal link farms[7]（inlinkを集め外にはリンクを張らないリンクファーム）を構成していることがわかる。

これらの強連結成分がスパムサイトをとても高いprecisionで含んでいるので、section 6のさらなるリンクファーム発見のためのseed setとして使える。

強連結性は分解にはとても弱い尺度で、例えばスパマーがこの方法を矢売ろうと思えば、良いサイトにリンクを張るだけで良い。
実際coreにはまだ多くのスパムサイトが含まれているので、より強固な部分グラフの高密度の基準を次のsectionで考える。

5. ENUMERATION OF MAXIMAL CLIQUES

このsectionではcoreの中のスパムサイトを見つけるために極大クリークを列挙する。大きなクリークはおそらくスパマーに作られたであろうと考える。

有向グラフG=(V,A)に対して部分集合K⊆Vを、含まれるすべてノード間にどちらむきのエッジも存在するときクリークと呼ぶ。G_c=(C, A(C))を強連結成分C⊆Vからからなる部分グラフとし、G'_c=(V_c,E_c)をG_cでお互いにエッジが張られているノードだけを残した無効グラフとする。
無向グラフG'_cにおいて通常の意味でのクリークのときかつそのときに限り、Kは有向グラフG_cでクリークとなる。

以下に計算結果を示す。以降ではcore Cに集中する。
無向グラフを作ることにより、ノード数とエッジ数は1.09mと6.59mになる。G'_cの最大次数は3,904。
[12]の極大クリーク列挙アルゴリズムはΔをグラフの最大次数としてO(Δ^4)の計算時間なので、G'_cに使うには時間がかかりすぎる。故に次数が80以下ののノードだけに切りつめる。
このアドホックな処理により、ノード数は1,064,922、エッジ数は3,222,189となり、平均次数は6.5となった。
さらにサイズが40以上の極大クリークを無視した。なぜならば、そのようなクリークの数は莫大で、より大きいクリークの方がリンクファームになりやすいので。

得られたクリークは26,931で8,346の別個のサイトを含む。これらの多くのクリークはお互いにオーバーラップしている。
これらの8,346のサイトには.comが62.8%で、.netが11.2%。
165のサイトを8,346からサンプリングし、spam、suspicious、non-spamに人手で分類した結果がTable 5にあり、これらのクリークのほとんどがスパムサイトで構成されていることがわかる。
これらのクリークもまた高いpresicionでスパムサイトを含むので、次のsectionでさらなるリンクファーム発見のためのseed setとして使うことができる。

6. SPAM DETECTION BY MINIMUM CUT

このsectionでは最小s-t cutとその双対、つまり最大s-t flowに基づいたスパム発見の手法を提案する。
前述したようなスパムサイトから良いサイトへのリンクがあっても良いサイトからスパムサイトへのリンクはほとんどないという予想から、良いサイトからスパムサイトへの"local edge connectivity"は小さいと考えられる。ゆえに良いサイトからスパムサイトへのflowを考えたとき、最小カットが良いサイトからスパムサイトへのリンクを分割すると期待できる。

W⊆Vを良いサイトのseed set、B⊆Vをスパムサイトのseed setとする。
ネットワークN_w,B = ((V∪{s,t}, A∪A_s∪A_t), c, s, t)を考える。
仮想供給点（virtual source） sと仮想需要点（virtual sink） tとし、A_sはsからWに含まれる点（良いサイトのseed set）への弧、A_tはBに含まれる点（スパムサイトのseed set）からtへの弧とする。粉の容量はA_s∪A_tで無限大、それ以外で1とする。
このネットワークに対して、以下の最小s-tカット問題を解く。
min{Σ_a∈A(U:V＼U) c(a) | U∪{s} is an s-t cut} ----- (1)
A(U:V＼U)はUのカット集合。V＼U*をリンクファームと見なす。U*はU*∪{s}が最小s-tカットとなるような部分集合。

実際の計算では(1)の双対問題である最大s-tフロー問題をGoldbergとTarjanのプッシュリラベルアルゴリズム（push-relabel algorithm）で解き、約30分かかった。最小s-tカットはniqueでないので、得られた最大フローの残余ネットワークのtから幅優先探索をして最小s-tカットを得た。

次に計算結果を示す。
ネットワークはcoreをもとに組み立てられる。人手で210の良いサイトのseed setを選ぶ。スパムサイトのseed setは前述のように8,346のsection 5のクリーク内のサイトと、448,688のsection 4の大きな強連結成分内のサイト。

最小カット手法でcore内のseed set8,346は57,350まで広がり、49,004のサイトを得られたことになる。
この中で最も多かったドメインは.com（62.9%）で、.net（19.8%）が続く。.jpドメインのページはは62のみ。
Table 6には得られたリンクファームからサンプリングした487のサイトが示してあり、手法の有用性を示している。

7. CONCLUDING REMARKS

大規模なweb graphにおけるリンクファームの全体的な構造と分布についてグラフアルゴリズムを用いて研究した。
まず、強連結成分分解をweb graphに対して行い、core周りの大きな成分のほとんどがリンクファームから成ることを発見した。
次にcore内の極大クリークをリンクファームのseedsとして列挙し、大きな極大クリークの列挙はリンクファームのseedsの発見に効果的であることを示した。
最後にこれらのseedを最小カット法により拡大した。
0.6mのスパムサイトをcore周りの強連結成分の中に見つけ、core内の8thouのサイトを極大クリークの列挙によりスパムとして抽出し、さらに49thouのサイトを得た。つまり約57thouのサイトをとても高いprecisionでcoreの中に見つけた。
これらのほとんどのリンクスパムは英語で書かれたサイトであることを観察した。

しかしながらまだ多くのリンクファームがcoreの中に残っていることを単純なサンプリングにより観察した。故にこのリンクベースのアプローチを改善するためのさらなる手法を提案することも重要な問題。

極大クリーク列挙では次数の大きいノードを計算時間のために無視したので、一部のリンクファームしか見つけられなかった。またクリークは高濃度の基準として厳しすぎるので、より見つかるリンクファームの数を減らしている。

最小カットのアプローチでは弧の容量やseed setsで他のものを選択する余地が多く残されている。

この手法を他のベンチマークに応用することも重要な問題。

8. ACKNOWLEDGMENTS

We thank Takeaki Uno for providing us with an implemention of the maximal clique enumeration algorithm.

9. REFERENCES

[1] L. Becchetti, C. Castillo, and D. Donato. Link-based characterization and detection of web spam. In Proc. of AIRWEB 2006, Seattle, 2006.
[2] L. Becchetti, C. Castillo, D. Donato, S. Leonardi, and R. Baeza-Yates. Using rank propagation and probabilistic counting for link-based spam detetection. In Proc. of KDD 2006, Philadelphia, Pennsylvania, 2006.
[3] A. Bencz´ur, K. Csalog´any, and T. Sarl´os. Link-based similarity search to fight web spam. In Proc. of AIRWEB 2006, Seattle, 2006.
[4] A. Bencz´ur, K. Csalog´any, T. Sarl´os, and M. Uher. Spamrank – fully automatic link spam detection. In Proc. of AIRWEB 2005, Chiba, 2005.
[5] A. Broder, R. Kumar, F. Maghoul, P. Raghavan, S. Rajagopalan, R. Stata, A. Tomkins, and J. Wiener. Graph structure in the web. Computer Networks, 33:309–320, 2000.
[6] G. W. Flake, S. Lawrence, and C. L. Giles. Efficient identification of web communities. In Proc. of KDD 2000, Boston, 2000.
[7] Z. Gy¨ongyi and H. Garcia-Molina. Link spam alliances. In Proc. of VLDB 2005, Trondheim, 2005.
[8] Z. Gy¨ongyi and H. Garcia-Molina. Web spam taxonomy. In Proc. of AIRWEB 2005, Chiba, 2005.
[9] Z. Gy¨ongyi, H. Garcia-Molina, and J. Pedersen. Combating web spam with trustrank. In Proc. of VLDB 2004, Toronto, 2004.
[10] J. Kleinberg. Authoritative sources in a hyperlinked environment. Journal of ACM, 46:119–130, 1997.
[11] V. Krishnan and R. Raj. Web spam detection with anti-trust rank. In Proc. of AIRWEB 2006, Seattle, 2006.
[12] K. Makino and T. Uno. New algorithms for enumerating all maximal cliques. In SWAT 2004, Humlebaek, 2004.
[13] P. T. Metaxas and J. DeStefano. Web spam, propaganda and trust. In Proc. of AIRWEB 2005, Chiba, 2005.
[14] M. Najork and J. L. Wiener. Breadth-first crawling yields high-quality pages. In Proc. of WWW 2001, Hong Kong, 2001.
[15] T. Ono, M. Toyoda, and M. Kitsuregawa. An examination of techniques for identifying web spam by link analysis. In Proc. of DEWS 2006, Tokyo, 2006.
[16] L. Page, S. Brin, R. Motwani, and T. Winograd. The pagerank citation ranking: Bringing order to the web. Technical report, Stanford University, 1998.
[17] B. Wu and B. Davidson. Identifying link farm spam pages. In Proc. of WWW 2005, Tokyo, 2005.

2008-12-18

Web spam Identification Through Content and Hyperlinks

論文

J. Abernethy, O. Chapelle, C. Castillo
Web spam Identification Through Content and Hyperlinks
In Proceedings of Fourth International Workshop on Adversarial Information Retrieval on the Web
2008. Apr.
論文の在処

概要

いろいろなページのfeaturesを全部利用して、それぞれに重みを付けてWeb spamを発見しようと言うアイディア。
重みを付ける方法をSVM-likeな方法で学習する。
SVM＋グラフのリンク構造＋スラック変数。
結果はかなり良いみたい。Web Spam ChallengeのTrack 穸のAUCでは一番だったらしい。

1. INTRODUCTION

不当やり方でいくつかのWebページの重要性や好ましい関連性を生み出すため、意図的に生み出されたコンテンツとしてWeb spamは現れる[9]。
自動分類器のためにspamページとnon-spamページの間には統計的な特徴の違いが見つけられることがわかっている[13]。

機械学習の観点からで見ると、それぞれのページやホストの特徴だけでなく、その間の有効ハイパーリンクの情報を利用できる点で、spam発見は典型的な分類の仕事とは異なっている。
ハイパーリンクはページの類似性の度合いを表している[7,16]。ハイパーリンクには複雑な構造が見られる。例えばspamホストはnon-spamホストにリンクを張るが、non-spamホストはspamホストに対して滅多にリンクを張らない。このアイディアを利用して(dis)trustの伝播に基づいた技術が研究されている[10,12,17]。

この論文ではWeb spam Identification Through Content and HyperlinksのためのWITCHという学習アルゴリズムを提案する。WITCHはページのfeaturesとともにハイパーリンクの構造を学習に利用する。
具体的にはSVM-likeな目的関数を使ってfeature空間での線形分類器を学習する。
リンクされたページの間で滑らかに変化するpredictorを生み出すgraph regulatizationの方法でハイパーリンクのデータを利用する。
結果はこのgraph regularizationとSVMの方法はWeb spam発見にとても有効であることを示し、最新のすべての他の方法を圧倒した。

知る限りではトレーニングにハイパーリンクのグラフとページの特徴を同時に利用した初めての技術。
これらのfeaturesはどんなタイプのfeatures、content-based features、link-based featuresの組み合わせでもできる。

2. ALGORITHMS

この論文ではspam、non-spamへのホストの分類に関して議論する。ホストとはURLに同じ"host"を持つようなWebページのグループ。すべての技術は個々のページにも同じように適用できる。
以下のように記号を定義する。
(i)ラベル付けされたl個の例、(x_1, y_1), ... , (x_l, y_l)。x_iはi番目のホストのfeatureのベクトルで、y_iはそのラベル。
(ii)ラベル付けされていないu個の例、x_{l+1}, ... , x_n、n = l + u。
(iii)重み付き有向グラフ。ノードはx_1, ... , x_n。Eを(i, j)の集合。x_iからx_jへのリンクの重さをa_ij。

2.1 Learning with Graph Regularization

線形分類器 f(x) = w・xをまず説明。
似たようなアプローチは線形Support Vector Machine（SVM）[15]をトレーニングすること。この場合、wは以下の目的関数のminimizerとして見つけられる。
Ω(w) = 1/l Σ^l_i=1 R(w・x_i, y_i) + λw・w ------ (1)
ラムダはアルゴリズムのパラメータ。
上記の式はfitnessとcomplexityの間のトレードオフを捉え、large marginを維持しながらトレーニングデータを正確に分類できるようwを選ぶことができる。
ここではhinge function R(u, y) = max(0, 1-uy)をトレーニングデータのロスを表すために使うが、他のconvex loss functionもおそらく使われる。
w・wはmarginのサイズを表し、しばしばregularization term（正規化項）と呼ばれる。

Webの分類ではノード間のハイパーリンクを追加情報として使える。
ハイパーリンクはランダムに配置されている訳ではなく、リンク元とリンク先での類似の度合いを示唆していることが実験的に見られている[11, 7]。この観察に基づけば以下のようにregularizerを目的関数に追加することは自然。
Ω(w) = 1/l Σ^l_i=i R(w・x_i, y_i) + λw・w + γΣ_(i, j)∈E a_ijΦ(w・x_i, w・x_j) ------ (2)
a_ijはノードiからノードjへのリンクの重さ。
最初の二つの項はもとの線形SVMと一緒。三つ目の項は上記のgraph regularizationを実現するように働く。
関数Φはdistortion measureを表し、問題に応じて選ばれる。

目的関数 (2)は[4, 16]で提案されており、ΦはΦ(u, v) := (u - v)^2と選ばれている。これはハイパーリンクされている隣接ノードは似たような値が予想されるべきであると言う期待を意味する。
[4, 16]に対して今回新しいのは、非対称のグラフの特徴をWeb spam分類の特定の仕事に対して調節して用いること。
spamに関してはハイパーリンクの向きを組み込むことは重要。なぜならspamホストは頻繁にgenuineなホストにリンクを張るが、逆は希であるから。このことは[6, 8]で実験的に確かめられている。
Φ(u, v) = max(0, v-u)^2として、ハイパーリンクの向きを利用する。より詳細な議論は3.1にて行う。

2.2 Additional Slack Variables

feature空間が十分にリッチでないとき、単純な線形分類器w・xは十分にflexibleでないかもしれない。
しかし[16]の通り、パラメータz_iをすべてのノードiに導入し、form f(x_i) = w・x_i + z_iの分類器を学習できる。
この特別な項は学習された分類器をより自由にする追加のスラック変数と見ることができる。
あらたな目的関数は以下のようになる。
Ω(w, z) = 1/l Σ^l_i=1 R(w・x_i + z_i, y_i) + λ_1 w・w + λ_2 z・z + γΣ_(i, j)∈E a_ijΦ(w・x_i + z_i, w・x_j + z_j) ------ (3)
wとzの値をコントロールするためにλ_1とλ_2を正則化パラメータとして導入する。

この最後の目的関数がWITCHのベースになっており、その要約がAlgorithm 1に示してある。

2.3 Optimization

目的関数は凸関数（convex）で微分可能（differentiable）なので、最適化にnonlinear conjugate gradient（非線形共役勾配）[14]を簡単に使える。
これは非線形最適化では一般的でとても有効な方法で、勾配を計算しさえすれば良い。
[16]のdual algorithmよりもずっと高速。
詳細は[3]にある。

(3)を最適化するもう一つの方法はwとzで交互に最適化を行うこと。
このアプローチの良いところはどちらのステップでも一般的なアルゴリズムを使って行えること。
wの最小化は回帰アルゴリズム（regression algorithm）を使い、zの最小化にはグラフのstandard iterative propagation algorithmを使える。
この方法の詳細は[3]に任せる。

3. IMPLEMENTATION AND RESULTS

このsectionでのすべての実験結果はsection 4で紹介しているデータセットに基づいている。
それぞれの方法のパフォーマンスを比べるためにArea Under the ROC curve（AUC）を使う。AUCはアルゴリズムのoutputしたテストセットの順序のみから、予想されたランキングの正確の自然な尺度を与える。
実験のより正確な条件は[3]にある。

3.1 Design Elements

WITCHのパフォーマンスの分析を続ける。
アルゴリズムの個々の設定の詳細な記述から始める。

Graph weights:
ノードのペアi,jに対してn_i,jをホストiとホストjの間のリンクの数とする。
graph regularizationを使うためにエッジの重さを定義する必要があり、様々な重みの付け方を試した。
a_i,j := n_i,jとするとハイパーリンクが豊富なホストをover-regularizeしがちなので、それを改良したのが1か0かの重みを持つa_i,j := 1[n_i,j > 0]と平方根を利用したa_i,j := √n_i,j。
最も良いパフォーマンスだったのは対数を利用した重み、a_i,j := log(1 + n_i,j)で、以降のすべての結果にはこれを利用している。

Graph Regularizer:
ホストのスパムらしさ（spamicity）は局所的に保存されると思われるため、graph regularization関数Φ(・,・)はこの局所性を予測に反映させることを実現すべきである。
ノードiがノードjにリンクを張っていたとき、Φ(f_i, f_j)はspamスコアがf_iのノードがf_jノードにリンクを張るのがどれだけunnaturalかを計るべき。
すでに定義された二つのregularization関数の候補は以下。
Φ_sqr(f_i, j_j) △= (f_i - f_j)^2
Φ^+_sqr(f_i, f_j) △= max(0, f_j - f_i)^2 = [f_j - f_i]^2_+

一つ目の式はiとjのスパムらしさの偏りを２乗したものを課す。一方二つ目の式はリンクの元のノードがその先のノードよりも低いスパムらしさのときにだけ課す。
二つ目の式はリンクを通してスパムらしさが減ることがあっても増えることがない、つまり悪いノードから良いノードへのリンクではスパムらしさが減るが、良いノードから悪いノードへのリンクでスパムらしさが増えはしないという想定を実現している。

後者の方がより適切だと思われる。一般的に、悪いノードは良いノードにリンクを張る。良いノードは悪いノードにリンクを張る動機がない。ゆえに良いノードから悪いノードへのリンクは少ないと予想される。
このことはWEBSPAM-UK2006のデータセットでも示されており、non-spamホストからspamホストへのリンクは1.8なのに対し、spamホストからnon-spamホストへのリンクは14.7%。

面白いことに最も良いregularization関数の選択は上記のどちらでもなく、そのミックスだった。
任意のα∈[0, 1]に対し、
Φ_α(a, b) △= αΦ_sqr(a, b) + (1 - α)Φ^+_sqr(a, b)
と定義し、このミックスregularization関数がとても有効で、もとの二つに比べて大きな改善が得られた。
Figure 1にαを変化させたときのAUCで計ったパフォーマンスが示されている。
αが0のときはnon-spamからspamへのリンクだけ課される。αが1のときはすべてのspamスコアの偏りが課される。
αは0.1に設定した。もっと慎重に選ぶこともできるが、パフォーマンスはこのあたりの値なら安定している。

Model Selection:
WITCHは三つのハイパーパラメータ、λ_1、λ_2、γを調節できる。
トレーニングデータの20%のランダムなサンプルを使い、7×7×7のパラメータのコンビネーションでWITCHをトレーニングし、もっともパフォーマンスの良かった三つ組み（λ_1、λ_2、γ）を選んだ。
Table 1の最終的な結果はこの評価の後に得られた結果。

3.2 Comparison with Vriant Algorithms

section 4にあるデータセットでの、WITCHのパフォーマンスについて示す。

WITCHはホストfeatures、スラック変数、ハイパーリンクグラフでのregularization、という３つの道具をトレーニングに使うことができる。
それぞれ違った役割をし、様々なレベルでパフォーマンスに貢献する。
それぞれの相対的な重要性を見るために、以下のようないくつかの異なるアプローチを行った。

Only Features:
featureだけを利用して線形分類器をトレーニング。(3)の式でλ_2=0、γ=0にした場合で、これは標準的なSVM。

Features + Graph Regularization (GR):
featureに加えてハイパーリンクのグラフ構造をもとにregularizeする。(2)を最小化することに一致する。

Slack Variables + GR:
featureを無視して、グラフregularizationのみで学習する。これは(3)をw=0にして最適化することに等しい。

Features + Slack + GR (WITCH):
すべての道具を使う。線形分類器とスラック変数を同時にトレーニングし、グラフ構造に従い値をregularizeする。

Table 1に上記の方法のそれぞれのパフォーマンスがある。
スラック変数を使うとかなりの上昇が見られる。これは恐らくunderfittingの結果。与えられtfeature空間でspamを正確に発見できる一つの線形predictor wはたぶん存在しないので、スラック変数がモデルに自由度を与えたことが原因。

パフォーマンスがトレーニングセットのサイズでどのように変わるかを見るために、Figure 2には７つのサイズでの結果が示してある。

4. COMPARISON WITH OTHER METHODS

WWWのspam発見の手法を比較するため、研究者のグループが最近Web Spam Challenge[2]というのをWEBSPAM-UK2006*1に基づいて組織した。
そのchallengeに出された236のfeatureを使い、トレーニングセットとテストセットの分割はWeb Spam Challenge Track 穵で使われた分割で固定した。

competitionのfirst trackは2007年の4月に終わり、AUCでのもっとも良いパフォーマンスはGordon Cormackらの0.956だった。（著者らは参加せず）
同じデータでWITCHはfirst trackの他の投稿を圧倒しAUCで0.963を得た。（λ_1、λ_2、γはsection 3.1で説明した値を使用）

challengeは2007年の7月に終わったTrack 穸も含んでおり、このtrackではこの論文で議論した方法でWITCHにより得えられた予測は他の10の投稿を押さえ最も高いAUCを得た[1]。
Track 穸のデータはfirst trackのデータから生成され、feature集合が修正され、トレーニングセットとテストセットの分割が新しくなり、ページのコンテンツとホストアドレスを省略している。

Table 1にはこの論文で議論した方法のパフォーマンスの要約と、２つの最新のweb spam発見の手法（stacked graphical learning[6]、transductive link spam[17]、いずれもハイパーリンクの情報のみ利用している）のパフォーマンスがある。
この方法は他の良く知られたラベルの伝播を利用したTrustRank[10]やAnti-Trust Rank[12]も圧倒する。この二つの手法のさらなる実験結果は[3]にある。

5. CONCLUSINS

本論文ではWITCHというWeb spam発見のための新しいアルゴリズムを提案した。
WITCHをいくつかのほかのアルゴリズムと比較して、それが他を圧倒することを発見した。
最後にWITCHは独立したWeb spam発見challengeで最も高いAUCを獲得した。

これらの良い結果にはいくつかのポイントとなる観察がある。
一つはcontent featuresとhayperlink構造を同時に利用したときに最も結果が良いということ。
二つ目はgraph-regularizeされた線形predictorをただトレーニングしただけではだめで、スラック変数を加えることで劇的な改善がなされるということ。
三つ目は正しいgraph regularizerを選ぶ必要があること。spamからnonspamへのリンクとnonspamからspamへのリンクどちらにもpenalizeすることが重要だが、後者のほうに重きを置くべきであること。
最後にgraphの重みがパフォーマンスに顕著な影響を与え、リンクの数のlogarithmを使うと一番良いと言うこと。

6. REFERENCES

[1] Graph Labeling Workshop. http://graphlab.lip6.fr/, 2007.
[2] Web Spam Challenge. http://webspam.lip6.fr/, 2007.
[3] J. Abernethy, O. Chapelle, and C. Castillo. WITCH: A new approach to web spam detection. Technical Report 2008-001, Yahoo! Research, 2008.
[4] M. Belkin, P. Niyogi, and V. Sindhwani. On manifold regularization. In Proceedings of the Tenth International Workshop on Articial Intelligence and Statistics (AISTATS), 2005.
[5] C. Castillo, D. Donato, L. Becchetti, P. Boldi, S. Leonardi, M. Santini, and S. Vigna. A reference collection for web spam. SIGIR Forum, 40(2):11{24, December 2006.
[6] C. Castillo, D. Donato, A. Gionis, V. Murdock, and F. Silvestri. Know your neighbors: Web spam detection using the web topology. In Proceedings of SIGIR, Amsterdam, Netherlands, July 2007. ACM.
[7] B. D. Davison. Topical locality in the web. In Proceedings of the 23rd annual international ACM SIGIR conference on research and development in information retrieval, pages 272{279, Athens, Greece, 2000. ACM Press.
[8] Q. Gan and T. Suel. Improving web spam classiers using link structure. In AIRWeb '07: Proceedings of the 3rd international workshop on Adversarial information retrieval on the web, pages 17{20, New York, NY, USA, 2007. ACM.
[9] Z. Gyongyi and H. Garcia-Molina. Web spam taxonomy. In First International Workshop on Adversarial Information Retrieval on the Web, pages 39{47, Chiba, Japan, 2005.
[10] Z. Gyongyi, H. Garcia-Molina, and J. Pedersen. Combating Web spam with TrustRank. In Proceedings of the 30th International Conference on Very Large Data Bases (VLDB), pages 576{587, Toronto, Canada, August 2004. Morgan Kaufmann.
[11] S. W. Haas and E. S. Grams. Page and link classications: connecting diverse resources. In DL '98: Proceedings of the third ACM conference on Digital libraries, pages 99{107, New York, NY, USA, 1998. ACM Press.
[12] V. Krishnan and R. Raj. Web spam detection with anti-trust rank. In ACM SIGIR workshop on Adversarial Information Retrieval on the Web, 2006.
[13] A. Ntoulas, M. Najork, M. Manasse, and D. Fetterly. Detecting spam web pages through content analysis. In Proceedings of the World Wide Web conference, pages 83{92, Edinburgh, Scotland, May 2006.
[14] J. R. Shewchuk. An introduction to the conjugate gradient method without the agonizing pain. Technical Report CMU-CS-94-125, School of Computer Science, Carnegie Mellon University, 1994.
[15] V. Vapnik. Statistical Learning Theory. John Wiley & Sons Inc, 1998.
[16] T. Zhang, A. Popescul, and B. Dom. Linear prediction models with graph regularization for web-page categorization. In KDD '06: Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 821{826, New York, NY, USA, 2006. ACM Press.
[17] D. Zhou, C. J. C. Burges, and T. Tao. Transductive link spam detection. In AIRWeb '07: Proceedings of the 3rd international workshop on Adversarial information retrieval on the web, pages 21{28, New York, NY, USA, 2007. ACM Press.

*1:ホストレベルで注釈のついた公のWeb Spamのデータセット、.ukドメインの11,402のホストを含み、7,473がラベル付けされている

2008-12-10

Exploring Linguistic Features for Web Spam Detection: A Preliminary Study

論文

J. Piskorski, M. Sydow, D. Weiss
Exploring Linguistic Features for Web Spam Detection: A Preliminary Study
In Proceedings of Fourth International Workshop on Adversarial Information Retrieval on the Web
2008. Apr.
論文の在処

概要

Webのspamに関連した論文。
ページの文書を言語学的に解析して、spamを見つけようとしている。
すごいのは、とにかくたくさんの方法で試してみていることと、そのすべてを定量的に評価していること。
そしてその結果を誰でも利用できるようにしている。
彼らによると、これまでにWebのspam発見の分野ではこのような言語学的なアプローチは無かったらしい。

1. INTRODUCTION

この論文ではSydowらにより[12]で報告された仕事を、より多くのlinguistic-based featuresとWeb spam分類への利用の可能性を研究することで、extendした。
この論文での努力はSection 1.1にある他のcontent-based featuresに関連した仕事の補完。
主なcontributionsは以下
（１）200以上のlinguistic-based attributesを計算したこと。より良い、偏りのない洞察を得るため、様々なNLP toolsと、三つのdocument length-restrictionモードの二つのWeb spam corporaをテストした。
（２）Web spam discriminatorsとしてすべてのattributesの1200以上の分布を準備し、研究したこと。
（３）最も有望なattributesを二つの客観的な基準で実験的に特定したこと。
（４）計算済みのattributesをhistogramsの形でresearch communityで利用できるようにしたこと。*1

この論文で議論されているすべてのfeaturesは計算的には扱いやすく、documentレベルで計算できる。

1.1 Related Work

様々な有用なcontent-based featuresが報告されている。
Fetterlyらは[7]で単純なfrequency-based measuresが有用であることを証明している。
Drostらは[4]でchecksumsとword weighting techniquesに基づいたfeatureを加えることにより、リストを広げている。この方向でのさらなる探求がNtoulasらに[11]で行われている。
Mshneらは[10]でWeb documentのコンテンツを解析し、blog spam発見のためにその言語モデルをその引用しているブログの言語モデルと比較している。
Fetterlyらは[8]でそのコンテンツがnon-spamページからのフレーズの張り合わせで自動的に生成されたようなspamページを特定する技術を報告している。
Urvoyらは[13]で自動生成されパターンに基づいたspamページを発見するためのHTML文書構造に基づいたfeaturesを紹介している。
Benczurらは[2]でMicrosoft OCI、Yahoo! Mindsetや、Google AdWords及びGoogle AdSenseから抽出したキーワードを利用して、ページのcommercial attractivenessを研究している。

既存の様々な結果に基づき、何人かの著者はcontent-based featuresとlink-based featuresを利用した自動spam分類を報告し、bagging、exploration of the link structure for label-smoothing、2-level stacked graphical learning、graph regularizationを含むより洗練された技術を加えてうまく利用している[3,1]。

2. LINGUISTIC FEATURES

Zhouらは[15]であるlanguage featuresがテキストベースのコミュニュケーションにおけるhuman deception detectionに対して特有なポテンシャルを持つことを証明した。
この仕事に触発され、これらのfeaturesのsubsetをWeb spam分類へ適用した。
オープンで制限されていないWebのテキストではよりエラーの多い高いレベルの言語ツールはノイズを生み出すと考え、多くの言語的な洗練された計算をしていないfeaturesだけ考えた。

linguistic featuresの計算のために２種類のNLPツールを使った。
一つはCoreleoneで[9]、extended MULTEXT resource [5]に基づいた形態論的解析器をcomes with。
もう一つはGeneral Inquirerで、辞書に与えられたカテゴリーの数と共にインプットしたテキストをマップする道具。現在のバージョンはHarvard IV-4とLaswellの辞書でカテゴリーは全部で182。

計算はHTMLのボディをテキストに変換したものだけに限定し、すべてのテキストは英語であると仮定して行った。

2.1 Corleone-based features

Corleoneにより計算されるfeaturesは主に品詞情報に基づいているが、品詞の曖昧さはWebのopen-domainという早くから言及されている特徴により解消されていない。
ここでは曖昧な単語に対して品詞タグという時にはタグは全てのを表すとする。たとえばfightという単語にはNVタグがつき、noun(N)とverb(V)を意味する。

Type:
Webページは自由なテキスト、大量のデータ、あるいはそのどちらもを含んでいる。ページの'type'（character）を見積もるための二つのattributesを紹介する。
Lexical validity = # of valid word forms / # of all token
Text-like fraction = # of potential word forms / # of all tokens
potential word formsは掲載粗解析を受けたトークンで、数字、URL、句読点を表すもの、文字じゃないものは含まれない。

Quantity:
テキストの量と言うcontextで全てのトークンの数に対する名詞の割合（Noun Fraction）、動詞の割合（Verb Fraction）、大文字で始まるトークン（Capitalized Tokens）を計算する。

Diversity:
テキストの多様性として以下の三つのタイプを調べる。
Lexical diversity = # of different tokens / # of all tokens
Content diversity = # of different nouns & verbs / # of all nouns & verbs
Syntactical diversity = # of different POS n-grams / # of all POS n-grams
morphological componentに'unknown'とタグ付けされた、頭文字の大文字の単語はContent diversityの文脈では名詞と計算される。Syntactical diversityは２、３、４-gramsで計算される。

さらに品詞n-gramsの分布のエントロピーであるSyntactical entropyを計算する。G = g_1, ... g_kをページの品詞n-gramsの全ての集合として、{p_g}をGの品詞n-gramsの分布とすると、syntactical entropyは以下で計算される。
Syntactical Entropy = -Σ_g∈G p_g・log p_g

Expressivity:
言語の表現性として、content wordの中のmodifiersの割合であるEmotivenessを選ぶ。
Emotiveness = # of adjectives & adverbs / # of all nouns & verbs

Non-immediacy:
言語的なnon-immediacyはcommunicatorが彼ら自身に言及する際のverbal inderectnessのdegreeとして見ることができる。
non-immedicacyのdegreeの測定方法として以下の二つのスコアを定義する。
Passive Voice = # of passive constructions / # of all verbs
Self Referencing = # of 1st person pronouns / # of all pronouns

Ucertainty:
uncertaintyの測定方法として、全ての動詞に対する法動詞の割合を計算する。（Modal Verbs）

Affect:
ページのaffectを計算するため、SENTIWORDNET[6] （Coreleoneに組み込まれている）を利用。SENTIWORDNETではWORDNET *2のそれぞれのsynset sはPos(s)とNeg(s)という二つのスコアを持っていて、それぞれsynset s含まれるtermsがどれくらい'positive'か'negative'かを表す。特に、t_iはテキストの中のi番目のトークンを表すとして、テキストT = t_1 ... t_2として、以下のPosSentとNegSentを計算する。
PosSent = Σ_t∈T max(Pos(t)) / Σ_t∈T max(Pos(t)) + max(Neg(t))
NegSent = Σ_t∈T max (Neg(t)) / Σ_t∈T max(Pos(t)) + max(Neg(t))
トークン（term）tは潜在的に違った意味を持っているので、それぞれのトークンtに対して、tが所属するsynsetsのスコアで最大のPosスコアと最大のNegスコアを計算する。
このようにして、positiveな意味とnegativeな意味両方で使われているtermsはなんとか中和される。

次に、重さの就いていないaffectスコアを計算する。それは約1200のopinion expressionsに基づいた全てのopinion expressionsに対する'positive' tonality expressionsの割合（Tonality）。

2.2 Features obtained with General Inquirer

General Inquirer（GI）の182のカテゴリーは社会科学者によるcontent analysisの適用により開発された。GIによって割当てられるこれらのカテゴリーの値はoccurrence statisticsに基づいている。
これらのいくつかはsection 2.1で定義されたfeaturesとかぶっているが、それぞれのGIカテゴリーを別のものとして扱う。GIによってカバーされているカテゴリーのスナップショットがTable 1に示されており、詳細はWebページ*3で見られる。

3. EXPERIMENTS

3.1 Data Sets

Web spamのデータセットとしてWebSpam-Uk2006とWebSpam-Uk2007[14]を用いた。
これらのデータは.uki Web domainの２回の一般的なクロールで得られたもので、それぞれのページのコンテンツ、リンク、人の手によって割り当てられたカテゴリー（spam、non-spam、borderline、undecided）を持っている。

実験ではホストごとに幅優先探索による400のサンプルページを用いた。
元のGZIP-compressed WARCファイルをまずbinaryのblock-compressed wequenceファイルに変換し、map-reduce programming paradigmを用いて分散実行できるようにした。
10 quad-coreマシンのクラスタで動いているHadoop project*4を計算に用いた。
データセットの統計データはTable 1にある。

3.2 Histograms

二つのデータセットに対してCorleoneとGeneral Inquirerを使ってlinguistic attributesを計算した。
計算するにあたり以下の三つのモードを考えた。
(0)50k以下のトークンを含むからでない文書
(1)150から20kのトークンを含む文書
(2)400から5kのトークンを含む文書
(1)と(2)はとても短い文書（多くのノイズを生み出す可能性がある）と、とても長い文書（文書の長さがベキ則のようになっているので、計算速度の低下を招く）の影響を調べるためのもの。

以上の６つのコンビネーションに対して、208のlinguistic attributesを計算した。（23がCoreleone、185がGeneral Inquierer）
そして、それぞれのattributeの値にたいして、文書レベルでの度数分布図を、spam、non-spam、borderlineのカテゴリーに対して作った。（文書レベルでのラベル付けはWebSpam-Uk2006でもWebSpam-Uk2007でもなされていないため、文書にはそのホストのラベルを付けた。）これにより1200以上の度数分布図が生成された。
すべての度数分布図は横軸にattributesの値の幅（bins）、縦軸にはその範囲に入るページのパーセンテージを取った。
これらの度数分布図の予備的な調査結果は以下。

長さの制限をした文書に対して得られた度数分布図は顕著に（mode-0に比べて）ノイズが少なかった。
mode-2の度数分布図はmode-1のそれと比べてわずかにnoisyだと思われたため、次のsectionではmode-2のみを使う。
borderlineの度数分布図は一般的にspamのそれと近かったが、この点はより厳密に調べる必要がある。

3.3 Objective selection of the best attributes

主観的な観察を広げるため、客観的な方法で有望なattributesを特定するために、以下に定義されるの二つのdifference measures（absDist、sqDist）を紹介する。
それぞれのattributeに対して、spamクラスとnon-spamクラスの差異をこのmeasuresを用いて測定する。

attributeの度数分布図hに対して、{s^h}_iと{n^h}_iをbins i∈Iのバーの高さのsequencesとする。
absDist(h) = Σ_i∈I |s^h_i - n^h_i| / 200
これはspamとnon-spamの度数分布のカーブに囲まれた部分の面積の割合と解釈できる。
sqDist(h) = Σ_i∈I (s^h_i/max_h - n^h_i / max_h)^2 / |I|
max_hは正規化のファクターの類いで、{s^h}_iと{n-h}_iの中で最大の値。

absDistはより自然な幾何学的な解釈なので、より直感的に思える。しかし二つの違った測定基準が結果の偏りを減らしてくれる。
いずれの測定基準でも高い値がより識別の力があることを意味する。

次に、最も良いattributesを特定するために、1200からなる度数分布図に対して両方のmeasuresを計算し、6つのセッティングごとに値の降順でソートした。
面白いことにトップ10のattributesではどちらのmeasuresでも6つのセッティングによらず長さの制限はほとんど意味をなさなかった。例えば二つの測定基準がまるで違うにもかかわらず、Corleoneのトップ9のattributesは二つのデータセット、測定基準で同じリストになった。結果はTable 2にある。
absDistの場合いくつかの度数分布図ではAUC（area under the ROC curve）が25パーセント違った。これはそれらの潜在的な識別の力を示している。
4-grams、mode-2、WebSpam-Uk2007のSyntactical Diversityの度数分布図がFigure 2にある。

同じような実験をGIにより得られたattributesに対しても行った。
absDistではトップ7のattributesが二つのデータセットで一致した。Table 3に結果あり。
いくつかのattributesではspamの度数分布図のAUCとnon-spamの度数分布図のAUCでは30パーセント違い、Coreleoneにより得られたattributesよりも有望だと言える。

sqDistではトップ9のattributesが二つのデータセットで一致した。Table 3に結果あり。
全く違った測定基準から顕著なオーバーラップをもったリストが得られた。

GIから得られたattributesでいくつかのものが一つだったり別のmeasureやセッティングでもトップ10に入った。それらは以下
EnlOth、EnlTot（enlightenment words、啓蒙語）
WltTot、WltOth（Words in wealth domain、例えばpursuit of wealth）
ECON、Wcon@dat（words reffering to objects、例えばfood、vehicles、building）
Leftover（他の'大きい'GIのカテゴリーに関連付けられなかった'lasswell dictionary'のattributesを網羅し、達成、取引、望まれるあるいは望まれない終わりやゴールの単語、意味や実用性に言及した単語、俳優、国家、感情を意味する単語を含む）
CorleoneのattributesよりGIのattributsの方が7倍も多いので、GIにより得られたattributesのトップリストはより不安定であると言える。

3.4 Discussion

一般的に、明らかな分布の違いが見られたことから、計算したattributesの中で最も良いものはspamかnon-spamの見極めにかなり有望であることを観察した。
また、attriutesのトップリストはWebコーパスの選択に関してかなり安定しており、attributesにとっては重要な良い側面である。

Corleoneにより得られたattributesよりGIにより得られたattributesの方がより潜在的な識別の力が大きいように思われる。
驚くべきことではないが、GIから得られたattributesでトップスコアだったものは商品の購入、取引、ビジネス、産業、人間でないもの、啓蒙運動の周りのvocabulary centeringに関連したものだった。

別の面白い発見として、syntactical diversityがlexical diversityよりも良い識別の力を示したことがある。
これはキーワードを大雑把に組み合わせてできたspamページは浅薄なsyntactical analysisにより決定できることを意味する。
一方で明らかにspamとnon-spamのクラスを分けられるようなattributesはなかった。これはおそらくspammersが現存するWebコンテンツを再利用し、繰り返し使ったり、自分のコンテンツと交互に重ねて使ったりしているからである。
最後に[15]の仕事とは対照的に、表現力、あいまいさ、感情はspamを見つけるの力がないように思われた。
たぶん、より良い洞察を得るために、前述のlanguage featuresを計算するためのより洗練されたattributesが研究されるべきである。

4. CONCLUSION

200以上のlinguistic-based attributesを二つのWeb spam コーパスに対して計算し、1200以上の解析結果の度数分布図の一般的な特徴に関して議論した。
知る限りではこのようなattributesはWeb spam発見の文脈ではこれまでに研究されていない。
特に、二種類の、分布の違いの測定方法はもっとも有望なattributesを特定するのに使える。あとの方のリストはいろいろなセッティングに対して安定しているように思われるが、これらの本当の有用性は今後研究される。
すべての計算されたattributesと度数分布図は研究目的で利用可能。

5. REFERENCE

[1] J. Abernethy, O. Chapelle, and C. Castillo. Witch: A new approach to web spam detection, 2007. submitted.
[2] A. Bencz´ur, I. B´ır´o, K. Csalog´any, and T. Sarl´os. Web spam detection via commercial intent analysis. In Proceedings of AIRWeb 2007, pages 89–92, New York, NY, USA, 2007. ACM.
[3] C. Castillo, D. Donato, A. Gionis, V. Murdock, and F. Silvestri. Know your neighbors: web spam detection using the web topology. In SIGIR ’07: Proceedings of the 30th ACM SIGIR conference, Amsterdam, The Netherlands, pages 423–430. ACM, 2007.
[4] I. Drost and T. Scheffer. Thwarting the nigritude ultramarine: learning to identify link spam. In Proceedings of ECML 2005, volume 3720 of LNAI, pages 233–243, Porto, Portugal, 2005.
[5] T. Erjavec. MULTEXT – East Morphosyntactic Specifications, 2004. URL: http://nl.ijs.si/ME/V3/msd/html.
[6] A. Esuli and F. Sebastiani. SentiWordNet: A publicly available lexical resource for opinion mining. In Proceedings of LREC 2006, pages 417–422, Genova, IT, 2006.
[7] D. Fetterly, M. Manasse, and M. Najork. Spam, damn spam, and statistics: using statistical analysis to locate spam web pages. In Proceedings of WebDB ’04, New York, USA, 2004.
[8] D. Fetterly, M. Manasse, and M. Najork. Detecting phrase-level duplication on the world wide web. In Proceedings of SIGIR ’05, pages 170–177, New York, NY, USA, 2005. ACM.
[9] Jakub Piskorski. Corleone - Core Linguistic Entity Extraction. Technical Report. JRC of the European Commission, 2008.
[10] G. Mishne, D. Carmel, and R. Lempel. Blocking blog spam with language model disagreement. In Proceedings of AIRWeb 2005, May 2005.
[11] A. Ntoulas, M. Najork, M. Manasse, and D. Fetterly. Detecting spam web pages through content analysis. In Proceedings of WWW 2006, Edinburgh, Scotland, pages 83–92, 2006.
[12] M. Sydow, J. Piskorski, D. Weiss, and C. Castillo. Application of machine learning in combating web spam, 2007. submitted for publication in IOS Press.
[13] T. Urvoy, T. Lavergne, and P. Filoche. Tracking web spam with hidden style similarity. In AIRWeb 2006, pages 25–31, 2006.
[14] Webspam corpora. URL: http://yr-bcn.es/webspam/datasets, accessed February 21, 2008.
[15] A. Zhou, J. Burgoon, J. Nunamaker, and D. Twitchell. Automating Linguistics-Based Cues for Detecting Deception of Text-based Asynchronous Computer-Mediated Communication. Group Decision and Negotiations, 12:81–106, 2004.

*1:http://www.pjwstk.edu.pl/~msyd/lingSpamFeatures.html

*2:http://wordnet.princeton.edu

*3:http://www.wjh.harvard.edu/~inquirer/homecat.htm

*4:http://hadoop.apache.org

2008-12-04

Query-log mining for detecting spam

論文

C. Castillo, C. Corsi, D. Donato, P. Ferragina, A. Gionis
Query-log mining for detecting spam
In Proceedings of Fourth International Workshop on Adversarial Information Retrieval on the Web
2008. Apr.
論文の在処

概要

Webのspamに関連した論文。
ユーザーのクエリーログをもとにspamを見つけようしている。
クエリーログから、クリックグラフ、ビューグラフ、アンチクリックグラフを作り、
それをもとにいくつかのfeaturesを定義している。

1. INTRODUCTION

click graph[1, 4]からはじめ、新しいグラフの定義:view graphとanticlick graphを定義する。
この二つのグラフのqueriesとdocumentsのspammicityを特徴付ける上での利便性を調査し、syntacticなfeatureとsemanticなfeatureを紹介する。
syntactic featuresはこのようなグラフのdocumentノードに定義され、隣接したqueriesとの差によりquery attractivenessをとらえる。
semantic featuresはグラフのすべてのノード（documentsとqueries）に対して定義され、ノードのtopicsのinferred categoriesの分布に対して定義されたentropyの概念に基づいている。

topical datawを得るために、[1, 9, 12, 16]に従い、Open Directory Project（DMOZ）から得られたtopically-categorizedページの集合から始め、queriesとdocumentsにラベル漬けするためにこれらのカテゴリーを広げる。
queriesとdocumentsはどちらも一つのカテゴリーのラベルを得るのではなく、すべてのラベルの確率の分布をラベルとして持つ。
このラベルはqueriesとdocumentsがmulti-topicalかどうかの指標に利用でき、故にquery attractivenessの指標に利用でき、故に潜在しているspamのqueriesやdocumentsの指標に利用できる。
グラフ構造を使ってラベルを広めるというアイディア[11, 16, 4, 13]は新しくないが、これまでの研究と違うのは、category propagationを新しいfeaturesの計算のためのステップとして用いているところ。そのfeaturesは現在のspam発見のための機械学習アルゴリズム[3, 6, 7, 15, 5]を改良できる。

Web spam detection:
直感的に、spammersは頻繁に使われるqueriesで検索のトップにくるように、そして多くのウェブユーザーをカバーするためにそれらのqueriesがお互いにsemanticallyに離れたものになることを狙っている。
なので、spammersがサイトを作るのに使っているテクニックに対応するのではなく、結果として生まれたものに対して、query logグラフの中の特定の構造とコンテンツパターンを見つけることで、対応する。

Query spam detection:
検索結果の上位N番以内に現れるspamページが多いようなqueriesに興味があり、これを見つけることで、このようなqueries（spam-attracting queries）での検索のときによりaggressiveなspam 閾値を使ったり、このようなqueriesをより洗練されたspam発見アルゴリズムの設計に使ったりすることができる。

2. PRELIMINARIES AND NOTATION

click graph C = (V_Q, V_D, E)は無効、重み付き、ラベル付き二部グラフ。
V_Qはquery logに現れた別個のqueries。V_Dは別個のdocuments。
(q,d)∈Eは一人以上のユーザーがquery qがdocument dのクリックを導いたときに張られる。重みは２種類で、一つはqueriyがユーザーのクリックを導いた回数。もう一つはqがdをクリックした別個のsearch-sessionsの数。
N_k(x)をノードxから距離kは慣れたノードの集合とし、N_≦k(x)をノードxから距離k以内のノードの集合とする。

click-graphを起点として、以下の二つのグラフを定義する。
View graph:
click graphのエッジを、クリックされた場合ではなく、ユーザーに返された結果のリストに含まれて（veiwされて）いればエッジを張る。click graphのgeneralization。click graphに現れなかったノードも現れる。veiw graphはユーザーのfeed backを含んでいないためclick graphよりもnoisyだが、spamサイトは異なるqueriesの結果のリストに現れようとするので、spamサイトの発見に使える。
Anticlick graph:
anti-click graph A_rはclick graphのエッジ(q,d)を、以下の３つの条件を満たしたときに張ったもの。一つはdocument dがquery qの検索結果のリストのトップrに現れたこと。二つ目はqを送ったユーザーがdをクリックしなかったこと。三つ目はユーザーがdよりも下位のdocumentをクリックしたこと。
このようなnegative feedbackが有用であることは[10]で示されている。
小さいrを考えることがreasonableで、r = 3とした。

上記のグラフはdocumentノードの集合をhostsに置き換えて定義できる。
良いhostにspamページが見られることは良くあることだが、section 4でhost-graphsのアプローチがrobustで知られている結果を改善していることを示す。

以降ではグラフをそれぞれ、C_d、C_h、V_d、V_h、A_d、A_hと書く。これらのグラフの区別が必要ないときはGと書く。
すべてのノードx∈V_Q∪V_D∪V_Hで、l(x)はノードを表す文字列を表し、xがqueryならqueryの文字列、そうでないならURLかhostの文字列を表す。

3. QUERY GRAPH MEASUREMENTS

機械学習モデルの構築使われ、spam query/document発見のアプリケーションで使用されるグラフのfeaturesを定義する。

3.1 Syntactic features

最も明らかなfeatureは単純にノードの次数。N_1(d)、つまりdocument dに隣接しているqueriesの集合は"good description"を与える[17, 8]。
次にこのfeatureを磨いて頻度に基づいたpopular elementsを見ていく。
・それぞれのdocument dに対して、topQ_x(d)をquery logの中で出現しているqueriesの中で出現頻度がx％以上のqueriesでdに隣接しているqueriesの数とする。例えばtopQ_1.0(d)　＝N_1(d)。|topQx(u)|を濃度とする（論文にはuと書いてあるが、uに関する説明がないので誤字じゃないかと思います）。xは0.01と1.0を考える。0.01に近い値からは同じような集合0.01のときと同じような集合が得られる。
・それぞれのdocument dに対して、topT_y(d)をquery logの中で出現しているquery termsの中で出現頻度がx％以上のqueriesに含まれる単語でdに隣接しているqueriesを構成している単語（stop wordsを除く）の数とする。 |topT_y(d)|を濃度とする。例えばtopT_1.0(u)はすべてのquery termsの辞書（またuが突然登場します）。yは0.01と1.0を考える。

topT_y(u)はtopQ_x(u)よりも正確でないが、query compositionの変化の少なさへの依存を和らげる（またu登場）。
上記の二つのfeaturesの選択の理由は、直感的にこれらの値が高いほど強く広いquery attractivenessを持っており、spam pageと考えられること。
明らかにこれは多岐にわたるトピックを扱う良いページに対するfalse positive発見を誘発する。しかし、そのようなページは古典的なリンクベース、コンテンツベース、その両方のアプローチにより簡単にnon-spamでないとわかる。これはsection 4に説明してある。

3.2 Semantic features

syntactic featuresの値はdocumentのsemantic coverageのrobustなestimatorではない。だが今度はそのようなdocumentがspam hostsをより効率的に見つけるのに利用できる。
例えばcloaked hostsはたぶん多くの違ったqueriesに対して返される。
もちろんこの確率はサイトのspam判別式としては使えないが、automatic classifierの配置を考えるのに良いfeatureを与える。

ノード（documentかquery）のsemantic coverageの尺度をこれまでのグラフとOpen Directory DMOZのようなWeb directoriesに基づいて提案する。
アプローチは二つのフェーズからなっていて、まずdocumentsのなかでDMOZに見られるものにカテゴリーを付ける。次にDMOZの適用範囲を広げるため、グラフの構造やエッジの重みにより他のqueryやdocumentのノードにもカテゴリーを付ける。最後には多くのカテゴリーがノードに付けられている。これはノードがqueryならpolysemousだということだし、ノードがdocumentかhostならmulti-topicalということ。
さらにそれぞれのノードとカテゴリーラベルとの関係の強さを表すassignment strengthもそれぞれのカテゴリーが持つ。
この伝播のプロセスは[16]に基づいており、２種類の実装をされていて、その詳細は次のsection。
最後にこのmultiでweightedなカテゴリーの割当をsemantic spreadを捉えられるであろうすべてのノードの三つの分散量度を導くために使う。

3.2.1 The Category Tree and its computation

T_LをDMOZ directoryのうち、トップLレベルより深い部分を切り落としたカテゴリー木とする。
本論文ではL=2として、カテゴリーの数は577になる。
T_Lのカテゴリー（木の節）はカテゴリー名を表すl(c)と関連づける。
目標は全てのノードに対してT_L(v)を関連づけること。
カテゴリー（木の節）に対して、score_v(c)というノードvとカテゴリーcの関連の強さを表すスコアを付ける。
この木T_L(v)を観察することで、ノードvのsemantic coverageの良いdescriptionが得られる。
"wider"は木の節の中の正のスコアの分布で、widerはノードvのsemantic spreadであるべき。（意味がよくわかりませんが。）

これらの木を計算するために、まずすべてのノードに対してすべてのスコアを0にした木を作る。
次にすべてのdocumentノードでDMOZのカテゴリーに割り当てられているかを調べ、document dが割当られていたら、T_L(d)の中のそのカテゴリーとその祖先のスコアを全て１にする。dがレベルLより深いカテゴリーに割り当てられていた場合、その祖先でレベルLのカテゴリーに対して、同じ操作を行う。
カテゴリcのすべての子供のスコアの和が１になるように正規化する。こうすることで、score_v(c)をノードvがcに含まれている時にsub-topic c'に含まれている条件券就き確率と見ることができる。

score_(c)に対して、π(c)をT_Lでのcの親として、score'_v(c) = score'_v(π(c))×score_v(c)と定義する。特にrがT_L(v)の根だった場合、score'_v(r) = 1とする。
score'_v(c)はT_Lの根からスタートしてスコアに従って下って行った時にcに到達する確率を表す。

ここまでが初期化で、いくつかの木がnullでなくなる。つぎに、category propagationプロセスを行う。Gの構造とエッジの重みに基づいて他のノードにカテゴリーを広げて行く。
二種類の戦略を用いる。

Tree-based propagation by weighted average:
最初のアルゴリズムはグラフを投票者のネットワーク（network of voters）として見なす方法。
それぞれのノードのcontributionsは複数のパスで足し合わされる。この考えを実現するため以下の式で表されるようにスコアを計算する。
score_v^{i+1}(c) += α^{i-1}Σ_(v', v)∈E score_v'^i(c)×f(v', v)
score_v^0(c) = score_v(c)で、fはincreasing functionでlog_2(1 + w(v', v))。αはdamping factorで距離tのノード間のrelatednessがtに応じて少なくなることを実現する。
エッジの重さが大きいほど影響をうけ、そのノードとの間のパスが多いほど影響を受けやすくなる。
一般的なPageRank アルゴリズムと同様にαは0.85で、t=2とする。
それぞれのpropagationステップで子どものスコアのが１となるように正規化する。

Propagationo by random walk:
２番目のpropagationアルゴリズムはトップレベルの17のカテゴリーだけを考えることでカテゴリーの構造を平らにする。
click graphをランダムウォークして、移動するエッジは重みによる確率w(v, v')/Σ_z(w, z)により選ぶ[4]。たまにrestart（あるいはteleport）し、そのときの移動先のノードは、すべてのdocumentsノードの中からscore'_v(c)に応じた確率で選ぶ。
この操作をすべてのDMOZのトップレベルの17のカテゴリーに対して行うことで、すべてのノードのカテゴリー木を確率分布p[v]として得られる。特にこれらのベクトルを正規化したバージョンをp[v]/||p[v]||_1とする。

3.2.2 Measures of dispersion

ノードのsemantic spreadを捉えるべく三つの分散測定方法を提案する。
T_L(v)でレベルiを固定して、以下の条件付きエントロピーを考える。
H_i(v) = - Σ_{level(c)=i-1} p(c) Σ_{c'∈child(c)} p(c'|c)log_2 p(c'|c)
cはDMOZのレベル(i-1)の範囲のノード。さらに
p(c'|c) = score_u(c') / Σ_{x∈child(c) score_u(x)
はxの親ノードcからxに到達する確率を表す。
故にH_i(v)はレベル(i-1)から始めたときの、レベルiのカテゴリーの選び方の不確実性を測れる。
最大の深さを2としているので、一つ目の分散測定方法を以下で定義する。
H(v) = βH_1(v) + (1 - β)H_2(v)
このとき、βが0ならレベル2のカテゴリーの分布が支配し、βが1ならレベル1のカテゴリーの分布が支配する。
β=0.75として、レベル1のカテゴリーの分布を重視することにした。

同じような方法でグラフ中のノードのsemantic coverageを測る二つ目の方法、joint entropy(HJ)を定義した。
T_L(v)のレベル2のノードcを考え、そのjoint probabilityをp(c) = p(c|parent(c))p(parent(c))として計算する。
得られた確率分布に標準エントロピー関数を適用して、HJを得る。

最後のsemantic featureとして、ランダムウォークで得られたベクトルp[v]に古典的なエントロピーの考え方を計算した。これをH_pとする。

4. APPLICATION TO WEB SPAM

Yahoo!UK search engineから得られたデータを使った。
1.6mのqueryをsamplingし、そのqueryから2.8mの別個のdocumentsに対するクリックが生じている。
また、2007年10月のDMOZのヒエラルキーをパースして得られた600,000の別個のカテゴリーの4.2mの別個のdocumentsを使った。

Table 1にqueryログから得られた6種類のグラフそれぞれに対して、queryノードの数、document（あるいはホスト）ノードの数、エッジの数、が書かれている。
また、k-th propagationステップでカテゴリーを割り当てられたノードの割合C_D(k)（documentノードの割合）、C_Q(k)（queryノードの割合）のうち、C_D(0)、C_Q(1)、C_D(2)が示されている。
また最大連結成分CC_maxと、連結成分の数|CC|が、いずれも全てのノードに対する割合で示されている。
すべてのグラフから、3.1、3.2で説明したsyntactic featuresとsemantic featuresを生成した。
またqueryごと、documentごとのクリックの数、見た数(views)、クリックされなかった数を統計情報として含んだ。これらの統計量は同じセッションで同じquery・documentのペアでの複数回のクリックをカウントするか、無視するかの２通りで計算した。
合計で、それぞれのノードに対して61のfeaturesが得られた。

Finding Web spam pages:
自動分類器を作りテストするために、click-graphに現れ、WEBSPAM-UK2006 dataset[2]にも現れるホストを使った。
このデータは既にcontent-based featuresとlink-based featuresで計算されている（http://webspam.lip6.fr/）。
Figure 1にはC_hのspamホストのH_pの分布と、normalホストのH_pの分布が示されており、明らかに違っており、本論文のusage-based featuresがspamホストとnormalホストをとてもよく区別している。（明らかに違うようには余り見えません。）
そして、cost-sensitive decicion tree with bagging（これらのテクニックのintroductionが[14]にある）を使い、以下のパフォーマンスメジャーを適用した。
true positive rate TP（recall）、　false positive rate FP、F_1 metric（= 2PR/(P+R), P:precision, R:recall）、AUC（area under the ROC curve、true positive rateのラインと、false positive rateのラインの間の面積）。
61のusage-based featuresを98のlink-based featuresと139のcontent-based featuresに対して比較した。
Table 2にはF_1とAUCの基準で実験結果を示してある。
global accuracyの観点からすると、(C∪L∪U)と(C∪L)と(L∪U)分類器はだいたい同じ。
にもかかわらず、(L∪C)分類器は[3]で紹介されている(C∪L)分類器よりも少ないfeaturesで、ページのコンテンツを見る必要が無い。

Finding queries that attract spam:
spam-attracting queryはその結果にspam hostsを多く含むqueryのこと。
WEBSPAM-UK2006を使って、V_hの一部のホストにspamかそうでないかのラベルをつける。
次に、queryのspamicityを以下のように定義する。
ユーザーに示され、かつspamラベルのホストの数/ユーザーに示されたすべてのラベルの付いたホストの数。
ノイズを減らすため、ユーザーに示されるホストのうちラベルの付いたホストが10以上のものだけを考えた。
次にqueriesをspammicityが0.5以上のグループと未満のグループの二つに分けた。
decision treeを使って、0.798のAUC、true positive rate73.7%、false positive rate29.0%を得た。
代わりにspamicity=0のqueriesをspamicityが0.5以上のqueriesに対して見つけることを考えると、AUCは0.838、true positive rateは74.0%、false positive rateは22.1%だった。
この結果からusage detaからたくさんのspamを結果として生み出すqueryを自動で抽出できると言える。
しかし、他のfeaturesがこのようなdetactionシステムの正確性を改善するためにおそらく必要。

5. CONCLUSION

spam発見の実験は興味深いパフォーマンスを示し、ときどきは知られた結果を改善し、同じようなパフォーマンスをより少ないfeaturesで達成できた。
spam-attracting queriesを見つけることは特に面白いと考える。なぜならWeb spamに対して、two-lineでdefenceを行えるから。indexingのときに典型的な自動分類器を作り、検索エンジンのqueryログの利用パターンを観察して、それに基づきspamを発見する。
知る限りでは、過去にusage-based spam発見メソッドは示されていない。

ここで提案したmetricsを洗練して、ほかの可能性のあるapplicationsを研究したい。
それぞれのグラフとfeatureの個々の影響を研究することもfuture workのtopic。

6. REFERENCE

[1] R. Baeza-Yates and A. Tiberi. Extracting semantic relations from query logs. In Procs KDD, 76–85, 2007.
[2] C. Castillo, D. Donato, L. Becchetti, P. Boldi, S. Leonardi, M. Santini, and S. Vigna. A reference collection for web spam. SIGIR Forum, 40(2):11–24, 2006.
[3] C. Castillo, D. Donato, A. Gionis, V. Murdock, and F. Silvestri. Know your neighbors: Web spam detection using the web topology. In Procs SIGIR, 423–430, 2007.
[4] N. Craswell and M. Szummer. Random walks on the click graph. In Procs ACM SIGIR, 239–246, 2007.
[5] D. Fetterly. Adversarial information retrieval: The manipulation of web content. ACM Computing Reviews, July 2007.
[6] Z. Gyöngyi and H. Garcia-Molina. Web spam taxonomy. In Procs AIRWEb, 39–47, 2005.
[7] A. Ntoulas, M. Najork, M. Manasse, and D. Fetterly. Detecting spam web pages through content analysis. In Procs WWW, 83–92, 2006.
[8] D. Puppin and F. Silvestri. The query-vector document model. In Procs CIKM, 880–881, 2006.
[9] G. Qiu, K. Liu, J. Bu, C. Chen, and Z. Kang. Quantify query ambiguity using ODP metadata. In Procs ACM SIGIR, 697–698, 2007.
[10] F. Radlinski and T. Joachims. Query chains: learning to rank from implicit feedback. In Procs ACM SIGKDD, 239–248, 2005.
[11] D. Shen, J.-T. Sun, Q. Yang, and Z. Chen. A comparison of implicit and explicit links for web page classification. In Procs WWW, 643–650, 2006.
[12] R. Song, Z. Luo, J.-R. Wen, Y. Yu, and H.-W. Hon. Identifying ambiguous queries in web search. In Procs WWW, 1169–1170, 2007.
[13] M. Szummer and T. Jaakkola. Partially labeled classification with markov random walks. In Advances in Neural Information Processing Systems, volume 14, 2001.
[14] I. H. Witten and E. Frank. Data Mining: Practical Machine Learning Tools and Techniques with Java Implementations. Morgan Kaufmann, October 1999.
[15] B. Wu and B. D. Davison. Detecting semantic cloaking on the web. In Procs WWW, 819–828, 2006.
[16] G.-R. Xue, Y. Yu, D. Shen, Q. Yang, H.-J. Zeng, and Z. Chen. Reinforcing web-object categorization through interrelationships. Data Min. Knowl. Discov., 12(2-3):229–248, 2006.
[17] G.-R. Xue, H.-J. Zeng, Z. Chen, Y. Yu, W.-Y. Ma, W. Xi, and W. Fan. Optimizing web search using web click-through data. In Procs CIKM, 118–126, 2004.

2008-11-27

Robust PageRank and Locally Computable Spam Detection Features

論文

R. Andersen, C. Borgs, J. Chayes, J. Hopcroft, K. Jain, V. Mirrokni, S. Teng
Robust PageRank and Locally Computable Spam Detection Features
Proceedings of Fourth International Workshop on Adversarial Information Retrieval on the Web
2008. Apr.
論文の在処

概要

Webのspamに関連した論文。
局所的に計算できるcontribution vector *1の近似を用いて、前半ではspamの発見方法の提案、後半ではRobust PageRankという文字通りPageRankをspamに対してrobustにしたランキングシステムの提案をしている。
contribution vectorの効率的な近似方法に付いては詳しく触れられていない。

1. INTRODUCTION

web spamはページのコンテンツやリンク構造をうまく使ってそのページのランキングをあげようとするもの。検索結果の劣化や、crawling、indexingの効率を下げ、storageを無駄にする[11]。
web spamを見つけるためのたくさんのアプローチがある。コンテンツを利用したもの、リンク構造を利用したもの、そのコンビネーションだったりする。

成功しているテクニックは、機械学習技術のlink-based featresへの適用[2]、コンテンツの解析[14,13]、TrustRank[9]、Anti-TrustRnk[15]、様々なfeaturesの統計的な解析[6]、transductive（転動的）link spam detection[18]などがある。
成功しているテクニックの一つが、PageRankに特に貢献しているノード（ページ）の集合を見つける方法。spamページは少ないノードを利用して（link farm）大きいPageRankを得ようとするだろうから、この方法は有効。supporting sets（spamページのPageRankのアップに貢献しているページの集合）とPageRankへの貢献の解析がspam発見に使われている。SpamRank algorithm of Benczur et al[3]、Spam Mass algorithm of Gyongyi et al[8]や最近ではZhow[17]など。

supporting setsの考えは、personalized PageRankに基づいてノードuのノードvのPageRankへの貢献を厳密に定義することで正確になる。
ウェブグラフをG = (V, E)とする。
teleportation constant（restart probability）をαとする。
$PRM_\alpha$ をu番目の行がノードuのpersonalized PageRanc vectorを表す行列とする。
uからvへのPageRank contributionは $pr_\alpha(u\rightarrow v)$ とし、 $PRM_\alpha$ の(u,v)成分で定義される。
ノードvのPageRankは $PRM_\alpha$ のv列目の和。つまりノードのPageRankは全ての他のノードからのcontributionの和と考えられる。
ノードvのcontribution vectorは $PRM_\alpha$ のv列目と定義し、それぞれのentriesは他のそれぞれのノードのvに対するcontribution。
ノードvのδ-supporting setは少なくともvのPageRankのδ-fractionの貢献をしているノードの集合。

最近の論文でcurrent authorsが特定の一つのノードに対してcontribution vectorを効率的に近似するアルゴリズムを紹介している[1]。このアルゴリズムはそのノードの近くの少ない数のノードだけ計算することでreasonableな近似を得る。グラフの小さな部分だけを利用してあるノードのpersonalized PageRank vectorを効率的に近似する方法[7,12,4,16]と似ている。それぞれのpersonalized PageRank vectorを近似し、それを列としてPageRank行列の近似を作り、その転置行列の列を取ってきてcontribution vectorの近似とする既存の方法（例えば[3]）と、このアルゴリズムとは違う。

この論文ではlacallyに計算されたsupporting setsの近似に基づいていくつかのspam-detection featuresを定義し、教師あり学習と教師なし学習両方のアプローチで利用する。これらのfeaturesの効果をスパム発見のベンチマークを使って実験し、計算コストの調査に大きなグラフを用いて実験。

この論文では最後にlink spam engneeringに対してrobustなRobust PageRankというものを定義する。Robust PageRankではそれぞれのノードは多くともある量までしか他のノードに貢献できない。Robust PageRankは上記のfeaturesとPageRankをcombineすることで効率的に近似される。このランキングシステムは[2]で研究されている、距離がd以下のノードのcontributionを無視するというTruncated PageRank algorithmに関連している。Robust PageRankでは距離が大きい方がより大きく貢献するので、Truncated PageRankのrefinmentと見なせる。

Organization

Section 2ではPageRank、personalized PageRank、PageRank contribution vectorsといった必要な背景をreviewする。
Section 3で特定のノードのsupporting setsを計算するためのアルゴリズムをreviewする。
Section 4でいくつかのlocallyに計算できるspam detection featuresを定義する。
Section 5で二つの実データでの実験結果を示す。
Section 6でRobust PageRankを定義し、その近似のためのアルゴリズムを説明し、Robust PageRankの使用を正当化するいくつかの実験結果を示す。

2. PRELIMINARIES

このsectionでは実験で用いられるalgorithmic toolsについて説明する。とくにPageRank contribution vectorsを近似するためのアルゴリズム[1]はなるべく簡潔に（証明や解析をしないで）説明する。

webは有向グラフでモデル化されるが、out-edgesのないdangling nodesの問題を扱うために人工的なself-loopを持つノードをグラフに加え、dagnling nodesからこのノードへのedgeを加える。
Aをグラフの隣接行列とし、 $d_{out}(u)$ をuの出次数、 $d_{in}(u)$ を入次数とし、 $D_{out}$ を出次数を対角成分とした対角行列とする。

teleportation constant αに対して、PageRank vector $pr_\alpha$ はBrinとPage[5]により以下の式を満たすものと定義されている。
$pr_\alpha = \alpha \cdot 1 + (1 - \alpha)\cdot pr_\alpha \cdot M$
Mはランダムウォークの遷移行列で、 $M = D_{out}^{-1}A$ で与えられる。1は単位行ベクトル。
ページuのPageRankは $pr_\alpha(u)$ 。
以降では誤解を招かない範囲でαを省略。
$\sum_u pr_\alpha(u) = |V|$ であることに注意。

同様にHaveliwala[10]に定義されたpersonalized PageRnak vector ppr(α,u)は以下の式を満たす。
$ppr(\alpha,u) = \alpha \cdot e_u + (1 - \alpha)\cdot ppr(\alpha,u)\cdot M$
$e_u$ はu番目の要素が1の行ベクトル

$PRM_\alpha$ をu番目の行がpersonalized PageRank vector ppr(α,u)である行列とする。
そして(global) PageRank vector $pr_\alpha$ は $1\cdot PRM_\alpha$ 、つまりpersonalized PageRank vectorsの和。
uからvへのPageRank contributionは $PRM_\alpha$ の(u,v)要素で、 $ppr_\alpha(u \rightarrow v)$ と書く。
vのcontribution vector、cpr(α,v)は $PRM_\alpha$ のv列目の転置。
c = cpr(α,v)のとき、c(S)はSに含まれるノードからvのPageRankへの貢献を表す。
なので $c(V) = pr_\alpha(v)$ で、 $c(u) = ppr_\alpha(u \rightarrow v)$ 。

3. LOCAL APPROXIMATION OF CONTRIBUTION VECTORS

このsectionではノードvのcontribution vector c = cpr(α,v)を近似するためのアルゴリズムを示す。この近似されたcontribution vectorsからspam detection featuresを得る。

定義１： $\tilde c$ はc = cpr(α,v)のε-absolute-approximationで全てのノードuに対して $\tilde c \leq 0$ 、 $c(u) - \varepsilon \leq \tilde c(u) \leq c(u)$ を満たす。

非負vectorである $\tilde c$ のsupportを $Supp(\tilde c)$ とし、 $\tilde c$ 内での要素がstrictly positiveであるようなノードの集合を表す。たとえば $\tilde c$ = (0,0,1,3,0,0)だったら3と4のノード。
vector cはcanonicalなε-absolute-approximationを持つ。 $\bar c-$ を
$\bar c = \bigl\{ {\begin{array}{cc} c(u) \; \; \; if \; c(u) < \varepsilon \\ 0 \; \; \; otherwise \end{array}$
とする。明らかに $\bar c$ はcのsmallest supportであるε-absolute-approximation。
さらに、 $||\bar c||_1 \leq ||c||_1$ なので $|Supp(\bar c)| \leq ||c||_1/\varepsilon$ 。
localのアルゴリズムは $\var c$ のsupport structureとにたようなsupport structureを持つcの近似 $\tilde c$ を見つけようとする。

ターゲットのノードvのcontribution vectorのε-absolute-approximationを計算するためのアルゴリズム、AproxContribを下記に示す。

アルゴリズムでexamineされるノードの数の上限を与える。この数は $pr_\alpha(v)$ 、ε、αに依存するが、グラフのノード数とは独立。
このアルゴリズムはpushback operationsと呼ばれるoperationの連続を行う。それぞれのpushback operationはグラフの一つのノードに対して行われ、そのノードの入次数に比例した時間がかかる。
pushback operationが行われる回数に上限を設け、計算時間を調節する。計算時間はpushback operationが行われたノードの入次数に依存する。
得られた近似contribution vectorのsupportの上限がoperation pushbackの数。

アルゴリズムとその解析の詳細は[1]に書いてある。
この論文では、アルゴリズムをブラックボックスとして扱い、効率的な時間で計算できるとする。
次のsectionではこれらの近似contribution vectorsから得られるspam detection featuresを説明する。

4. LOCALLY COMPUTABLE FEATURES

このsectionではspam detection featuresの計算方法を形式的に定義する。
主にlocalなアルゴリズムを用いてcontribution vectorsを近似する。
まず、ほとんどのfeatureをの定義に役立つ近似contributing setsを定義する。

4.1 Approximate contributing sets

ノードvが与えられたとき、以下のcontributing setを定義する
・δ-significant contributing set
$S_\delta(v) = \{u|ppr_\alpha(u \rightarrow v) > \delta \cdot pr_\alpha(v)\}$
・ρ-supporting set
$ppr_\alpha(S \rightarrow v) \geq \rho \cdot pr_\alpha(v)$

4.2 Unsupervised learning features

いくつかのリンク構造にのみ基づいたfeaturesを定義する。
これらのfeaturesがlocallyに計算できることと、パフォーマンスの実験の結果を示す。
以下がfeaturesのリスト。
1. Size of δ-significant contributing set
ノードvに対して、 $|S_\delta(v)| = |{u|ppr_\alpha(u \rightarrow v) > \delta \cdot pr_\alpha(v)}|$
spamのノードでnon-spamノードに対してこの値が著しく小さくなると考えられる。
2. Contribution from vertice in the δ-significant contributing set
ノードvに対して、 $\sum_{u\in S_\delta(v)} ppr_\alpha(u\rightarrow v)/pr_\alpha(v)$
3. $l_2$ norm of δ-significant contributing vector
ノードvに対して、 $\sum_{u\in S_\delta(v)} (ppr_\alpha(u\rightarrow v)/pr_\alpha(v))^2$
とくにδ=0のとき、L2Normと書き、 $\sum_{u\in V(G)} (ppr_\alpha(u\rightarrow v)/pr_\rightarrow(v))^2$

比較対象として、以下の簡単な教師なしのfeaturesを用いる。
1. ノードの入次数(Indegree)
2. ノードのPageRankのratioとその入次数(PRIndegree)

4.3 Approximate computation of features

上記のfeaturesの近似versionを計算するために、前述のε-approximate contribution vector $\tilde c$ を、 $\varepsilon = \delta \cdot pr_v$ で計算する。
$\tilde S_\delta$ を\tex:\tilde c]で $\delta \cdot pr_v$ 以上の値を持つノードの集合とする。

$\tilde S_\delta$ は1/αδ+1回のpushback operationsを行って計算できる。
この集合は $S_{2\delta}\subseteq \tilde S_\delta \subseteq S_\delta$ という意味では、vのsignificant contributorsの良い近似を与える。
以下にapproximate featuresを定義する。
1. (Approximate) size of the δ-significant contributing set (SuppSizeDelta)
ノードvに対して、 $|\tilde S_\delta| = |\{u|\tilde c(u) > \delta \cdot pr_\alpha(v)\}|$
ノードvのPageRankのδ倍よりも多く貢献しているようなノードの数。
2. (Approximate) contribution from δ-significant contributing set (ContributePercent)
ノードvに対して、 $\sum_{u\in \tilde S_\delta} \tilde c(u)/pr_\alpha(v)$
ノードvのPageRankのδ倍よりも多く貢献しているようなノードの貢献の和をvのPageRankで割って標準化。
3. (Approximate) l_2 norm of contribution vector (L2NormDelta)
ノードvに対して、 $\sum_{u\in V(G)} (\tilde c(u)/pr_\alpha(v))^2$
全てのノードのvに対するPageRank中での貢献の割合を二乗したものの和。極端に割合が大きいノードがあると大きくなる。

4.4 Supervised learning features

教室あり学習では既にラベルの付いたノードの集合をつかって、ラベルを付けられていないノードのラベルを予測する。
同様に $\tilde S_\delta(v)$ を近似supporting setする。
$\tilde T_\delta(v)$ を $\tilde S_\delta(v)$ の中でspamラベルの付いたノードの集合とする。
以下に教師あり学習でのlocallyに計算可能なfeaturesを示す。
1. Fraction of nodes in the supporting set labeled as spam (SupervisedUnweighted)
ノードvに対して、 $|\tilde T_\delta(v)|/|\tilde S_\delta(v)|$
ノードvのPageRankのδ倍よりも多く貢献しているようなノードの内、spamノードの割合。
2. Contribution from nodes in the supporting set labeled as spam(SupervisedWeighted)
ノードvに対して、 ${\sum_{u\in \tilde T_\delta(v)} \tilde c(u)}/{\sum_{u\in \tilde S_\delta(v) \tilde c(u)}$
ノードvのPageRankのδ倍よりも多く貢献しているようなノードのうち、spamノードの貢献の和を、そのようなノードのすべての貢献の和で割った値。

(SupervisedWeighted)は本質的にPageRankをspamラベルのノードを１としたstarting vectorで行うことで得られるfeatureの近似。

比較対象として、以下の基本的なfeatureを使う。
1. (SupervisedIndegree)
入次数と、その中でspamノードからのエッジとのratio

5. EVALUATION OF FEATURES

実験結果のsection。

5.1 Data Sets

Becchettiらが研究した[2]のUK hostグラフ(UKhost)を主に使う。
11402ノードで、平均次数は65。
ほとんど半分のノードが人の手でspamかnon-spamかラベル付けされている。
5750のhostsが人の手でラベル付けされ、いくつかのページを見てリンクファームがhost内にあればそのhostをspamとしている。結果は674のhostsがspamで4974のhostsが普通のhosts。

アルゴリズムの実行時間を計るため、2006年５月にMSN searchにより得られたdomain graph(MSNdom)を用いた。
約55mノードで約500mリンク。
largest strongly connected component（最大強連結成分）は約13m400,000ノード。
largest connected component（最大連結成分）は約44mノード。
最大連結成分に含まれ最大強連結成分には含まれていないノードのうち、21mノードは最大強連結成分からのエッジを持っていて、6m500,000ノードは最大強連結成分へのエッジを持っていた。
最大強連結成分に含まれないノードが多いことは、多くのdmainsが最大強連結成分からのリンクを得ようとしていることを示唆している。（なぜそのような結論に至るのかよくわかりません）

5.2 Running Time

δ-significant contribution setを見つけるアルゴリズム動かしたときのδ-significant contributing setsの平均のサイズと、pushbak operationsが行われた平均の回数と、これらのdata setsに対して行われたすべてのoperationsの平均の回数が示されている。
UKhostではPageRankの高いほうから24%のノード(2800くらい）。MSNdomでは5000のノードをPageRankの高い方から10%のノードの中からランダムに抽出して、それらのノードに対して計算した。

δが与えられたとき、pushback operationの回数は理論的にO(1/αδ)で、トータルの実行時間はpushback operationの行われたノードのindegreeの和に関係するが、実際のデータに対して実行した所、pushback operationsの回数は理論的に最悪な場合の回数に比べるとずっと小さかった。

5.3 Experimental Result

このsectionではUKhostでの紹介したfearuresのパフォーマンスを示す。
spam発見は高いPageRankのノードでより重要なので、高いPageRankのノードの集合でのみの結果を示す。
とくにPageRankが上位24%のノードをhigh PageRankノードと呼ぶことにする。

"spam"をspamとラベル付けされたhigh PageRankノードの集合、"nonspam"をnonspamとラベル付けされたhigh PageRankノードの集合とする。
それぞれのfeature fに基づいて、ノードの部分集合をspam、残りをnonspamとするclassifierを定義する。
このclassifierはclassifierごとの閾値に基づいてそれ以上かそれ以下かでノードを二分する。
classifierにspamと判断されたhigh PageRankノードの集合をreportedspamと呼ぶ。
それぞれのfeature fに対して、以下のパラメータを考える。

1. Average value (f-)
high PageRankノードのこのfeatureの平均値
2. Average value on spam (f-(spam))
reportedspamのこのfeatureの平均値
3. Average value on non-spam (f-(nonspam))
high PageRankノードでnon-spamのこのfeatureの平均値
4. Percentage of false positive (FalsePos)
nonspamなのにspamと判断されてしまった割合(nonspam∩reportedspam)/nonspam
5. Percentage of false negatives or Recall (Rec)（false negativeを間違って使っているような気がします。）
再現率。spamのうちspamと判断できた割合(spam∩reportedspam)/spam
6. Precision (Prec)
精度。spamと判断したうち本当にspamだった割合(spam∩reportedspam)/(nonspam∪spam)∩reportedspam

良いfeatureは小さいFalsePosで大きいRecとPrec。
ノードがspamかそうでないかを検証するのが大変なとき、多くのnon-spamノードをspamと判断するのは嫌である。
明らかにトレードオフがあるが、結果的にはそれぞれの閾値をFalsePosが5%（もしくは2%）以下になるように設定した。
もしもっと小さなFalsePosが求められたときのために、より良いFalsePosを得られる閾値を決められるようfeaturesのうちのいくつかでpercentile chartを示している。（どうやったらこのグラフから閾値を決めろというのかわかりません。）
percentile chartが示されているのは $\delta =10^{-4}$ のSuppSizeDelta、ContributePercentと、 $\delta =10^{-5}$ のSuppSizeDelta、L2NormDelta。
予想通り、教師ありのfeaturesの方がわすがに教師なしよりも良かった。

5.4 Observation

このsectionではいくつかの実験結果のsammarizeをする。
パラメータδでそれぞれのlocallyに計算可能なfeaturesに対して、アルゴリズムの実行時間はpushback operationsの回数かδ-significant contribution setのサイズによる。
UKhostではδ-significant contribution setのサイズは $\delta=10^{-2}, 10^{-3}, 10^{-4}, 10^{-5}$ でだいたい4, 25, 305, 5700だった。
教師なし学習のfeaturesではSuppSizeDeltaとContributePercentがベストだった。
L2NormDeltaもreasonableだったが、明らかに前の二つよりは劣った。
これらのfeaturesは基本的な教師なし学習のfeaturesであるIndegreeとPRIndegreeを著しく圧倒した。
$\delta=10^{-4}$ ではsupporting setはとても小さく（300くらい）、ContributePercentがベストなfeatureだった。
これらの教師なし学習のfeaturesは基本的な教師あり学習のfeaturesであるSupervisedIndegreeよりもわずかに良かった。
予想通り、SupervisedUnweightedがすべての教師なし学習よりもわずかに良かった。
すべての上記のfeaturesでパフォーマンスはパラメータδを小さくした方が良くなった。

最後に、ここで提案された教師なし学習のfeaturesはたかいPageRankをもったノードでしか使えないということを観察した。実際に全てのノードに対して行った所、結果は圧倒的に悪くなった。
例えばFalsePosを0.02と0.05にすると、Recは0.10から0.23、0.05から0.15の間で変化した。
なので、これらの値は記さずに、高いPageRankのノードへの適用を協調した。
高いPageRankのノードは検索結果の高い位置に出てくるであろうことから、そのようなノードに対するspam発見がより重要だということに注意。
この低いPageRankのノードでの悪いパフォーマンスにはそのようなノードの周りのリンク構造がspamminessの情報を予想するのに十分でないことが直感的真実として隠れている。

6. ROBUST PAGERANK

このsectionではcontribution setsのアイディアを使ってRobust PageRankと呼ばれるPageRankの改良版のランキングシステムを構築する。
このシステムはlink spamに対してより信頼できるということを実験結果で示す。

ノードvのPageRankは他のノードからのcontributionの和として以下のように表せる。
$pr_\alpha(v) = \sum_{u\in V(G)} ppr(u,v)$

robust PageRankのアイディアは、最もPageRankに貢献しているノードらの影響を少なくしようというアイディア。
このアイディアを実現するために、閾値δよりも多く貢献していノードのcontributionをδにすることで下記のように定式化する。
$Robustpr^\delta_\alpha(v) = \sum_{u\in V(G)} \min(ppr(u, v),\delta)$

少しの多く影響しているノードの貢献を減らすことで、spamノードのPageRankをnonspamノードよりも小さくすることができる。
次にどうやって近似contribution vectorsから近似robust PageRankを計算するを示し、性能の高さを示す実験結果を示す。

Robust PageRankは以下のように近似する。
まず、Robust PageRankを以下のように書き直す。
$\begin {array}{lll}Robustpr^\delta_\alpha(v) \\ \; \\ \; \end{array} \;\; \begin {array} {lll} = \sum_{u\in V(G)} \min(ppr(u,v), \delta) \\ = \sum_{u\in V(G)} ppr(u,v) - \sum_{u\in S_\delta(v)} min(ppr(u,v) - \delta) \\ = pr_\alpha(v) - \sum_{u\in S_\delta(v)} ppr(u,v) - \delta|S_\delta(v)| \end{array}$

ノードvのRobust PageRankを近似するときは、誤差 $\varepsilon = \delta \cdot pr_\alpha(v)$ としてcontribution vector $\tilde c$ を計算し、PageRanc contribution ppr(u,v)を $\tilde c(u)$ で置き換える。
そして、以下の定義を得る。
$ApproxRobustpr^\delta_\alpha(v) = pr_\alpha(v) - \sum_{u\in \tilde S_\delta(v)} \tilde c(u) - \delta|\tilde S_\delta(v)|$

6.1 Experiments with Robust PageRank

UKhostでPageRank上位24%のノードのPageRankとrobust PageRankのpercentile chartを見比べると明らかにspamの大きな部分がより低いランクにrobust PageRankではなっている。

上記のchartsを補完しPageRankに対してのrobust PageRankの優位性を示すため、ノードのrobust PageRankとPageRankのratioを計算し、featuresとして使った。
$NormalizedRobustPR = ApproxRobustpr^\delta_\alpha(v)/pr_\alpha(v)$

このfeatureの結果からspamノードの方がrobust PageRankの値がPageRankより小さくなっていることがわかる。
他のfeaturesと違い、δを小さくしていってもqualityはあがらず、 $\delta=10^{-3}$ でベストだった。 $\delta=10^{-3}$ ではこのfeatureは他の教師なし、教師あり学習のfeaturesより良かった。

7. CONCLUSION

この論文では近似PageRank contribution vectorsを使ってlocallyに計算できるlink spam detectionのfeaturesを調査した。
ほとんどのfeaturesはcontribution setのdesired approximation factorとしてパラメーターδを持つ。
実行時間とspam発見のパフォーマンスの間の適切なトレードオフを見つけるために、data setに基づきδは計算されるべき。
教師なし学習のfeatureではContributePercent、NormalizedRobustPR、SuppSizeDeltaが良かった。
UKhostではNormalizedRobustPRが $\delta10^{-3}$ で、ContributePercentが $\delta=10^{-4}$ でベストだった。
特にこれらのfeaturesは教師あり学習のSupervisedIndegreeよりも良かった。
教師あり学習のfeatureであるSupervisedUnweightedがすべてのfeaturesの中でベストだった。

8. PREFRENCE

[1] R. Andersen, C. Borgs, J. Chayes, J. Hopcroft, V. Mirrokni, and S. Teng. Local computation of PageRank contributions. In 5th International Workshop of Algorithms and Models for the Web-Graph, 2007.
[2] L. Becchetti, C. Castillo, D. Donato, S. Leonardi, and R. Baeza-Yates. Link-based characterization and detection of web spam. In In Proceedings of the 2nd International Workshop on Adversarial Information Retrieval on the Web (AIRWeb), 2006.
[3] A. Benczur, K. Csalogany, T. Sarlos, and M. Uher. Spamrank - fully automatic link spam detection. In First International Workshop on Adversarial Information Retrieval on the Web, 2005.
[4] P. Berkhin. Bookmark-coloring algorithm for personalized PageRank computing. Internet Math., 3(1):41–62, 2006.
[5] S. Brin and L. Page. The anatomy of a large-scale hypertextual Web search engine. Computer Networks and ISDN Systems, 30(1–7):107–117, 1998.
[6] D. Fetterly, M. Manasse, and M. Na jork. Spam, damn spam, and statistics: using statistical analysis to locate spam web pages. In WebDB ’04: Proceedings of the 7th International Workshop on the Web and Databases, pages 1–6, New York, NY, USA, 2004. ACM Press.
[7] D. Fogaras and B. Racz. Towards scaling fully personalized PageRank. In Proceedings of the 3rd Workshop on Algorithms and Models for the Web-Graph (WAW), pages 105–117, October 2004.
[8] Z. Gy¨ongyi, P. Berkhin, H. Garcia-Molina, and J. Pedersen. Link spam detection based on mass estimation. In Proceedings of the 32nd International Conference on Very Large Databases. ACM, 2006.
[9] Z. Gy¨ongyi, H. Garcia-Molina, and J. Pedersen. Combating web spam with trustrank. In VLDB, pages 576–587, 2004.
[10] T. H. Haveliwala. Topic-sensitive PageRank: A context-sensitive ranking algorithm for web search. IEEE Trans. Knowl. Data Eng., 15(4):784–796, 2003.
[11] M. Henzinger, R. Motwani, and C. Silverstein. Challenges in web search engines. In In: Proc. of the 18th International Joint Conference on Artiﬁcial Intel ligence, pages 1573–1579, 2003.
[12] G. Jeh and J. Widom. Scaling personalized web search. In Proceedings of the 12th World Wide Web Conference (WWW), pages 271–279, 2003.
[13] G. Mishne and D. Carmel. Blocking blog spam with language model disagreement, 2005.
[14] A. Ntoulas, M. Na jork, M. Manasse, and D. Fetterly. Detecting spam web pages through content analysis. In
WWW ’06: Proceedings of the 15th international conference on World Wide Web, pages 83–92, New York, NY, USA, 2006. ACM Press.
[15] R. Ra j and V. Krishnan. Web spam detection with anti-trust rank. In Proc. of the 2nd International Worshop on Adversarial Information Retreival on the Web, pages 381–389, 2006.
[16] T. Sarl´os, A. A. Bencz´ ur, K. Csalog´ any, D. Fogaras, and B. R´acz. To randomize or not to randomize: space optimal
summaries for hyperlink analysis. In WWW, pages 297–306, 2006.
[17] B. Zhou. Mining page farms and its application in link spam detection. Master’s Thesis, Simon Fraser University, 2007.
[18] D. Zhou, C. Burges, and T. Tao. Transductive link spam detection. In AIRWeb, 2007.

*1:本文中でも説明しているが、ノードに対して定義されるvectorでi番目の要素はそのノードからノードiへの貢献（contribution）を表す

2008-06-13

Knowledge Sharing and Yahoo Answers: Everyone Knows Something

論文

Lada A. Adamic and Jun Zhang and Eytan Bakshy and Mark S. Ackeerman
Knowledge Sharing and Yahoo Answers: Everyone Knows Something
International World Wide Web conference 2008
pp.665-674
PDFのある場所へのリンク

概要

Yahoo Answer（海外版Yahoo!知恵袋）の解析。
とにかくいろいろ解析しているが、結局何が言いたいのかよくわからない。

ABSTRACT

Yahoo Answers（YA）は広く多様なquestion-answer forumで、technical knowledgeを共有するための媒体としてだけでなく、adviceをseekしたり、opinionsをgatherしたり、いろいろな好奇心を満たすための場所としても機能している。
この論文ではYAの知識の共有の活動（knowledge sharing activity）についての理解を求める。
forumのカテゴリーを解析し、その中身の特徴とユーザー同士のinteractionのパターンによってクラスタリングする。
いくつかのカテゴリーのinteractionはexpertise sharing forumに似ていたが、他はdiscussion、everyday advice、supportをincorporateしていた。
カテゴリーの多様性にもかかわらず、幾人かのユーザーは特定のtopicにかろうじてfocusすることがわかった。他はカテゴリーをまたいで参加している。
このことによりrelatedカテゴリーをmapできるだけでなく、ユーザーのinterestのentropyをcharacterizeできる。
factual expertiseが中心のカテゴリーでのみlower entropyはhigher answer ratingにcorrelateすることがわかった。
与えられたカテゴリーの中で、特定のanswerがbest answerに選ばれるかどうかを予測するためにユーザーattributeとanswer characteristicをcombineする。

1. INTRODUCTION

knowledge exchange communityで最大のものの一つがYA。
現在23Mの質問が解決されている。
もし誰か何か知っていれば、YAには確実にそれをshareするample opportunityがある。
knowledge sharingは伝統的に難しかったが、YAは社会全般のbootstrap knowledgeのメカニズムと恐らくcollective intelligenceを提供することにより達成したように思われる。
YAで共有される知識はとても幅広いが、一般的にあまりdeepではない。
質問と回答の多様性、回答の幅、回答のqualityをexamineする。それに従ってnetwork and non-network analyzeを用いてカテゴリーを分析することにより、いくつかはtechnical expertise sharing forumに似ていて、他は違ったdynamicsを持っていることがわかった。
ユーザーのカテゴリーをまたいだ回答パターンによる知識の広がりを計るためにentropyの概念を利用した。
低いentropyを持つ、つまり高いfocusを持つことは特定のカテゴリーでのベスト回答の割合に関係することがわかった。これは質問が事実を求めるカテゴリーでだけ。
最後に回答のqualityをexamineしてreplierとanswer attributeがどの回答がベストになりそうかを予測するのに使えることがわかった。

2. PRIOR WORK

sharing knowledgeは少なくとも15年以上はresearch topicで、最近ではインターネットスケールでのそれが面白い。
Wikipediaなども含まれる。*1
この分野には４つのperspectiveがある。
一つ目はforumの違いを知ること。
Whittakerらは膨大なUsenet newsgroupのデータでgeneral demographic patternを明らかにし、解析を行っている。*2
これにはsocial network analysisも利用されている。
たとえばKouとZhangはasking-replying networkを掲示板のシステムから構成して人々のオンラインでのinteractionがpersonal interest spaceに強く影響していることを研究した。*3
FischerらとTurnerらはonline interactionのvisualizationの研究をした。*4 *5
二つ目はユーザーレベルにfocusした研究。
Wengerは違う役割の重要性と、それがコミュニティのformationとcontinuationにどう影響しているかを議論した。*6
NonneckeとPreeceはlurkerの振る舞いについて研究した。*7
Donathはonline forumでユーザーのvirtual identityをmineしてdeceptionをdetectする技術を調査した。*8
最近ではWelserらがonline forumでユーザーのego-networkを"structural signature"として利用し"discussion person"と"answer person"をidentifyできることに関して議論した。*9
三つ目はthreadとmessageレベルにfocusした研究。
Sackはvisualizationを使ってdiscussion threadにおけるconversationのパターンが様々であることを示した。*10
JoyceとKrautはmesseageレベルで内容の分析をし、newcomerのpostとrelated responcesが彼らが参加を続けるか否かに影響を与えているかどうかを研究した。*11 *12
四つ目はなぜ人々がonline communityに参加し，貢献するのかの研究。
これはたいてい小さなdeta collectionとsurveyにより行われる。例えばLakhaniとvon Hippel*13やButlerら*14。
our own workで、ある種類のonline forumの研究をした*15 *16。これらの研究のgoalはsharing knowledge and expertiseをinternet ageでサポートするためのより良いシステムとonline spaceをデザインすること。
研究を通して、online communityにおける大規模のknowledge sharing and expertiseのdistributionに関して比較的少ししか知られていないことを知った。
YAはその研究にちょうど良く、知る限りでは二つの研究しか行われていない。
SuらはYAのanswer ratingを使ってインターネットでのhuman reviewed dataのqualityについてテストした。*17
Kimらはhuman codingとcontent analysisを使ってベスト回答を選ぶ基準を研究した。*18

3. YAHOO ANSWERS AND DATA SET

YAでのinteractionは全てQ&A。
質問はtop-levelの25のカテゴリーと、lowerl levelの1002のカテゴリーに属する。
質問にはいろいろな種類がある。
"fact"を求めるもの。
助けや支援を求めるもの。
純粋にdiscussionが行われる場合もある。
ただ重要なのはこれらのthreadもYAのルールに支配されているということで、回答は２回以上できないし、自分自身には回答できない。この点は明らかに他のonline systemのthread interactionとは違う。
YA activityを１ヶ月分集めた。
8,452,337の回答と1,178,983の質問、433,402のuniqueな回答者と495,414のuniqueな質問者、質問・回答いずれもしていたのは211,372のユーザーだった。
この数字がすでにユーザーの多様性のヒントである。たくさんのユーザーによる少ないpost数。

4. CHARACTERIZING YA CATEGORIES

4.1 Basic characterics

それぞれのカテゴリーはfactual information、advice seeking、social converasationまたはdiscussionのrequestのミックスだと思う。
それを中身を読まずに正確に決めるのは難しいので、avarage thread length（１ポストあたりのreply数）、average post length（回答がどれだけ長いか）といった特徴を観察することで間接的に推定する。
プログラミング、科学、物理といったtechnical subjectsはreplyが少ないが、それらのreplyは比較的長いことが観察された。
超常現象など普通の科学からは飛び出しているものを扱ったsience subcategoryは多くのreplyがあった。
もう一つの極端なcategoryはJokes and Riddles categoryでreplyは短く、数は多かった。
discussion categoryでは普通の長さのreplyが多くあった。Wrestlingなどのスポーツのcategoryや、Philosophy、Religion、Politicsといったcategoryもそうだった。
またMarriage & Divorce Marriage、いくつかの育児に関するcategoryなどの個々の体験やアドバイスを探すようなcategoryもそうだった。
The Cats and Dogs categoryもそうだった。
他のcategory間での特徴の違いはasker/replier overlap。
ユーザーが技術的な専門知識を求めるようなforumでは大多数はnoviceであり、askerとreplierがかなり区別されることが予想される。*19
アドバイスやsupportが中心のforumではユーザーは求めも与えもし、askerいもreplierにもなりうるだろう。
discussion forumでは質問と回答はいずれもconversationを続けるための手段である。
それゆえにtechnical categoryのoverlapが低く、discussion forumが最も高かったのは驚くべきことではない。
このことに関してはSection 5.1で再び扱う。

4.2 Cluster analysis of categories

それぞれのカテゴリーに対していくつかのaggregate measurementをした。
それぞれのカテゴリーでのactivityはSingles & Datingで216,061の質問、Religion and Spiritualityで129,013の質問、Mathematicsで48,624の質問、Dining Out in Switzerlandではたったの5の質問と幅があった。
the most active categories（質問が1000以上のカテゴリー）の集合を、thread length、content length、asker/replier overlapの3つからなるベクトルによるk-means法でクラスタリングした。
thread length：１質問あたりの平均回答数
content length：１質問あたりの平均回答者数
asker/replier overlap：それぞれのユーザーの質問、回答の頻度を要素とする２つのベクトルのcosine similarity
解析したのは189のカテゴリーで全体の質問の91%を占める。
クラスターを３つにしたときに直感的に一番意味がありそうだった。
一つ目のクラスターはdiscussion forumからなっていて、質問も回答もするユーザーが多く、いろいろなスポーツのカテゴリーでは勝者についてdiscussしたり、Politicsではsquabble over partisanが行われていたり、Religion & Spiritualityではgodの本質についてdebateされたりしていて、そのような刺激的な質問は長いthread lengthの原因になっている。
二つ目のクラスターは、人々が、いくつか正解があったり唯一のfacutual answerが存在しないような質問でadviceyacommon-sense expertiseを探し、求めるようなカテゴリー。そこでは決定的な回答はほとんどなく、同時に多くがアドバイスをするのに適切に感じられるので、threadsは長くなる傾向があるのであろう。Fashion、Baby Names、Fast Food、Cats、Dogsなどがふくまれる。
三つ目のクラスターは多くの質問がfactual answerを含む。人々は質問も回答もし、thread lengthは短くなる傾向がある。Biology、Repairs、Programmingなどが含まれる。
次のセクションで質問と回答のdynamicsをそれぞれのクラスターを代表するカテゴリーのネットワーク構造の違いを解析することによりさらに調べる。

4.3 Network structure analysis

質問したユーザーをそれに回答したユーザーにつなぐことによりasker-replierグラフが構成でき、これをQAネットワークと呼ぶ。QAネットワークの解析はnon-network measureでは容易にcaptureできない重要なinterctionのaspectを解明する。このセクションでは三つのクラスターから典型的な3つのカテゴリー、Wrestling、Marriage & Divorce（Marriage)、Programming & Design（Programming）について調べる。

4.3.1 Detree distributions
それぞれのカテゴリーで出次数と入次数のcumulative distributionを観察した。
すべてのカテゴリーでユーザーのactivity levelの違いが観察された。
幾人かはたくさん回答し、他は１回か２回で質問や回答をやめてしまう。一方極端な例ではたくさんの質問に回答するユーザーもいた。
次にそれぞれのカテゴリーの違いも見えた。
３つともheavy tailed distributionであるが、入次数の分布においてMarrigeとWrestlingはよりbroaderであり、少数の人々は数千のresponseを１ヶ月間に貰っていた。
対照的にProgrammingでは最も質問をしているユーザーでも数十のreplyしか貰っていなかった。
一般的に、Yahoo answersのforumでは出次数の分布はbroadになる傾向がある。
Programingではこれはconsistentlyに他の人を助け、自分は助けを必要としないようなユーザーを反映している。
Marriageではこれらはregularlyにadviceを提供するようなユーザーあるいはWrestlingと同じようにdiscussionが好きなユーザー。
このroleのseparationはたとえユーザーが一つの質問か回答をしていると見なしても明らか。例えばProgrammingでは質問をしたユーザーの約57%は期間中一度も回答しておらず、同様に回答をしたユーザーの51%は質問していない。

4.3.2 Analysis of ego networks
Welserらがonline forumでの"answer person"と"discussion person"をego networkをみることにより見分けられると提案している*20。
ego networkはユーザーと直接関係のある人とその人たちの間のエッジでされる。
３つのカテゴリーからそれぞれランダムに100のego networkを抽出して比べている。
Wrestlingではhighly activeユーザーの隣人は彼ら自身highly connectedでそれは彼らが"discussion persons"であることを示している。
反対にProgrammingでは最もactiveなユーザーは、helpしているユーザーは繋がっておらず、"answer people"である。

4.3.3 Strongly connected components
それぞれのカテゴリーのノード数、エッジ数、平均次数、mutual edge、最大強連結成分を調べ比べている。
Wrestlingは強連結成分を持ち、比較的多くのmutual edgeを持っており、core social groupがカテゴリー内に形成されていることを示している。
Programmingにはほとんど強連結成分はなく、reciprocal edgeは完全にない。これは"helpers"と"askers"に役割が分かれている事によると信じている。
Marriageは中間。mutual edgeは少ないがゼロではなく、最大強連結成分は小さいが存在する。
次のsectionでより詳しく調べる。

4.3.4 Motif analysis
motif analysisにより特有のsocial dynamicsを示すinteractionのsmall localパターンを見つけられる。
それぞれのカテゴリーの全てのトライアドに注目して割合を数え、ランダムなネットワーク*21 *22 *23と比べた。
ランダムネットワークに比べどのカテゴリーでもfeed forward loopが多かった。これは一人が２人を助け、そのうちの一人がもう一人を助けるというmotif。Programmingで多くこれは、high levelのexpertiseがすべてのlevelの人々を助けlower expertiseもよりlowerな人を助ける、というhelp-seeking online communityでよく見られる*24特徴を示している。
WrestlingとMarriageではfully reciprocal triadが多く見られ、symmetricな関係がわかった。この二つのカテゴリーのもう一つの重要なtriadは２人のmutual edgeを持ったユーザー（たぶんforumのregular）とそのどちらにも回答しているユーザー（たぶんただ単に質問に答えるために参加しただけ）からなる。
Programmingではこれは少なく、これはお互いに質問に答えるチャンスを持っているregularはよりactiveでないユーザーから回答を得ていることをimplyしている。

4.4 Expertise depth

質問のdepthを決めるためにProgrammingからランダムに100の質問を抽出し、5つのlevelにrateした。
level3は数年プログラムについて学んだ学生くらいのexpertise。
level4はプロのプログラマーくらいのexpertise。
Programmingではlevel3を超えるexpertiseを必要とする質問は１％しかなかった。
手短に言えば、質問はとてもshallow。

5. EXPERTISE AND KNOWLEDGE ACROSS CATEGORIES

このsectionでは２つの視点からYAの広がりについて記述する。
最初はあるカテゴリーで活発に回答しているなユーザーが他のカテゴリーでも同様に総であるような範囲について考える。
次はユーザーのentropy、すなわち彼らの回答が落ちるtopicの幅を計る。

5.1 Relationships between categories

回答のパターンを追跡することにより関係のあるカテゴリーを見つけ出すことは簡単。
カテゴリー間の距離を、カテゴリー内で回答しているユーザーの集合のcosine similarityを用いて計り、階層クラスタリングしている。
コンピューター中心のカテゴリー、Computer & Internet、Consumer Electronics、Yahoo! Products、Games & Recreationなどは同じクラスターに含まれる。
同じようにPolitics & GovermnmentはNews & Eventsは繋がっている。
Home & GardenはFood & Drinkと繋がりFood & DrinkはDining Outと繋がり、Dining OutはLocal Businessesと繋がっている。
これらのカテゴリーをまたいだ関係はユーザー側からの興味のfocusを示唆している。
あるカテゴリーで回答したユーザーが同じカテゴリーあるいは他のどのカテゴリーで回答する傾向があるのかを質問と回答のパターンから調べる。
Sports、Politics、Society & Culture（Religionを含む）のようなdiscussionしがちなtopicを扱うforumではユーザーは質問と回答を同じforumで行うことが多いことをobserveした。
Education & Reference、Sience & Mathのサブカテゴリーに見られるような事実にdominateされたtopicでは質問も回答もするユーザーは少ない。
車と輸送に関して回答している人が、他のカテゴリーで回答していて、車について質問している人にほどには他のカテゴリーで質問しない傾向があることがわかった。
スポーツと政治での回答者は美容とスタイルに関してほとんど質問しない。
回答したカテゴリーに関係なく、ユーザーは一様にYahoo productsに関して質問していた。
回答したカテゴリーに関わらずHealthで質問するユーザーは多かった。しかし回答の多いカテゴリーでもあった。
Faimly & relationshipsもHealthと同じようであったが、relationshipに関する質問は概して他のカテゴリーでの回答とは関係なかった。
technicalカテゴリーとsupportカテゴリーでも非対称な関係があった。Relationships、Health、Parentingで回答しているユーザーはComputers & Internetでも質問するが、逆は少ない。
少なくとも数名のユーザーは全てのカテゴリーでランダムに回答している訳ではないので前述のカテゴリー間の関係はapparent。
なので無数のtopicでknowedgeを共有する機会があるが、ユーザーは範囲を限定する傾向がある。

5.2 User entropy

特定のtopicにどれだけユーザーが集中しているかの指標としてentropyを使う。集中していれば低くなる。
カテゴリーの階層も反映されるようなentropyの定義にした。
回答の頻度にはかなり差があり、topicにfocusしているのかただほとんど回答していないのかを考慮しなければならないので、40以上の回答をした41,266のユーザーにしぼって分析した。
これらのユーザの中でもentropyにはかなり幅があった。あるユーザーは自らを犬のトレーナーと称し、全ての回答はDogサブカテゴリーで、ゆえにentropyは0だった。
一方で40の質問が25あるtop-levelカテゴリーのうち17のカテゴリー、26のサブカテゴリーに散らばっていた。彼はどのカテゴリーでも僅か4つの回答しかしておらず、entropyは5.75だった。
entropyの分布は驚いたことにflatだった。何人かはとても低いentropyだが、高いentropyもYAの階層による限界まで比較的普通だった。
ユーザーのbest answerの確率を調べたところ、その分布は非対称でbest answer率6-8%のユーザーが一番多かった。次のsectionでユーザーのfocusとbest answerに選ばれることとの関係をdetermineするために二つのmetricをcorrelateする。

5.3 Correlating focus to best answers

直感的に回答が限られた範囲のカテゴリーにfocusしている場合、best answerに選ばれる頻度は大きい気がする。面白いことにentropyとbest answerに選ばれる確率には相関が無かった。
いくつかのdiscussion forumでの回答ではそうだろうが、場合によっては相関があると期待する。
カテゴリーにも違いがあり、factual informationを扱うカテゴリーは一部であることは既に学んだ。
support forumではbest answerは最もempathyあるいはcaringなadviceであろう。
discussion forumではbest answerは最も質問者の意見に賛成している回答であろう。
entertainment categoryでは最もwitな回答が勝つだろう。
先行研究で正確さや詳細さなどのcontent valueはbest answerを決める要素の17%でしかない、agreement、afferct、emotinal suppportなどのsocio-emotionalは33%をしめるのに対して*25。
best answerを選ぶことのもう一つの特徴は他の多くの良い回答が選ばれないということ。先行して行った実験ではProgramming、Cancer、Celebrityからそれぞれ100の質問をとって来て、回答に採点したが、本当のbest answerはたしかにbestであったが、best answerに選んだ者とは違っており、2番目、3番目にした回答だった。
つまり良い回答ばかりするユーザーを見つけ出すことができない。回答の多いカテゴリーではbest answerに選ばれる確率が小さくなってしまう。
それでも技術的なことや事実についてのカテゴリーでは低いentropyがperformanceに関係するとexpectする。
これを証明するためにentropyを2つ目の階層を分けて計算した。
その結果技術的なカテゴリーであるComputers & InternetとScience & Mathではあきらかな関係が見られた。
弱まりはするがadvice-ladenのカテゴリーであるFamily & Relationshipsでも関係が見られた。
Sportsでは関係はなかった。
最後にカテゴリー内でのユーザーの回答の割合とbest answerに選ばれた率をすべてのカテゴリーで関係づけた。
技術的なカテゴリーではfocusはbetterなscoreと関係していた。回答に知識が必要なカテゴリーでも弱まりはしたが明らかな関係があった。discussionカテゴリーでは全く関係がなかった。
asker-repliier overlapが低く、thread lengthが短いカテゴリーが高い関係を持っている。

6. PREDICTING BEST ANSWERS

いくつかの方法でその回答がbest answerに選ばれるかとどうかを予測することができるかテストする。conplementaryでconcurrentに、質問と回答のqualityに関する研究がAgichiteinらにより行われている*26。
ランダムにbest answerとそうでないものがbalanceするように回答を抽出し、very likelyにbestに選ばれそうな回答を除外した上で、いくつかの変数でロジスティック回帰を行った。
回答者の大半は回答数が少なすぎるのでentropyとfocusのmeasuerは使わなかった。
予測精度を得るために10倍のクロス確認をrandom guessesで0.5のbaselineで行った。
ProgrammingとMarriageとWrestlingで行った。
回答の長さと、他の回答の多さが大きく影響した。
回答の長さだけで62%の予測精度を得た。質問者がより長い回答が好きなことを示している。
ユーザーがそのカテゴリーで回答している数とbest answerに選ばれている数も良い予測を生み、これはProgrammingで他のカテゴリーより顕著だった。他のカテゴリーでbest answerに選ばれている数は関係なかった。
単純なユーザーの回答数はほんの僅かに改善させたが、best answerの数を考慮するとnegativeな影響を及ぼす。
この結果は以前に行ったSun's Java Forumでの結果と際立った対象をなしていた。Java Forumでは回答の数はexpertise levelと強く関係していた。
ユーザーの選んだbest answerとその領域のexpertが選んだ回答とを競争させるのは面白そう。回答の頻度とexpertise levelの関係があるのか、Java Forumのような専門的なcommunityと違いYahoo Answerのような一般的なcommunityではexpertise levelに大きな違いがあるのかなどを調べるのも面白そう。それらはfuture work。

7. CONCLUSIONS

まず
content propertyとカテゴリーをまたいだsocial network interactionを比較し、thread lengthとoverlapによりカテゴリーをクラスタリングできることをfindした。
discussion topicや事実に基づく回答を求めていないようなtopicでは長いthreadでactivity levelの分布は幅広く、ユーザーは質問も回答もする傾向があった。
事実を求める質問の多いカテゴリーではthread lengthは短く、典型的にユーザーは同じforumでhelperかaskerに徹していた。
これらの異なるdynamicsにdiffering interaction motifがcorrespondすることをfindした。
online forumでの先行研究と同じように、ego-networkがdiscussion threadが支配する傾向のあるYA categoryを、question-answer形式に縛られている中でさえ、簡単にrevealすることをfindした。
次に
関係のあるカテゴリーをidentifyした。あるカテゴリーで回答したユーザーが他のカテゴリーでも回答しやすいかをしらべることにより。
質問と回答を別々に考えたとき面白い非対称が見つかった。familiar topicに関する質問には多くのユーザーが回答する、多く質問するのがどこでも。specializedでtechnicalなカテゴリーで回答するようなユーザーは他のカテゴリーでは質問が少ない。
ユーザーがどれだけカテゴリーをまたいでknowledgeをshareしているかを調べ、多くのユーザーは多くの違ったカテゴリーで回答しており、specializedでtechnicalなカテゴリーではその傾向が少なかった。そのようなカテゴリーではそのカテゴリーにfocusしているユーザーの方がbest answerに選ばれやすかった。
最後に
best answerを予測しようと試みた。その質問への回答の数と回答者のtrack recordと同様に単純に回答の長さがもっとも予測に使えた。ユーザーのbest answerの数（expertizeのpotentialなindicator）は役に立ったがそれが最も総だったのはtechnically focused Programming categoryだった。
future workとしてYAでshareされているexpertiseのlevelをもっと調べたい。民主化したknowledge sharingによりYAは大きな偉業を達成した。みんな何かをしっている。そして解析により多くの人がいくつかのことを知っていてそれをYAでshareできることを知った。しかしその幅広さがdepthを犠牲にしているかどうかは未だunclear。我々が日々単純な質問の回答を得ているのに対して、top levelのexpertが違ったincentive mechanismによりYAに参加しているのかどうかを知りたい。

*1:T. Holloway, M. Bozicevic, and K. B¨orner. Analyzing and visualizing the semantic coverage of wikipedia and its authors: Research articles. Complexity, 12(3):30-40, 2007.

*2:S. Whittaker, L. Terveen, W. Hill, and L. Cherny. The dynamics of mass interaction. Proceedings of the 1998 ACM conference on Computer supported cooperative work, pages 257-264, 1998.

*3:K. Zhongbao and Z. Changshui. Reply networks on a bulletin board system. Phys. Rev. E, 67(3):036117, Mar 2003.

*4:D. Fisher, M. Smith, and H. Welser. You Are Who You Talk To: Detecting Roles in Usenet Newsgroups. In HICSS’06, 2006.

*5:T. Turner, M. Smith, D. Fisher, and H. Welser. Picturing Usenet: Mapping Computer-Mediated Collective Action. Journal of Computer-Mediated Communication, 10(4), 2005.

*6:E. Wegner. Communities of Practice: Learning, Meaning, and Identity, 1998.

*7:J. Preece, B. Nonnecke, and D. Andrews. The top ﬁve reasons for lurking: improving community experiences for everyone. Computers in Human Behavior, 20(2):201-223, 2004.

*8:J. S. Donath. Identity and deception in the virtual community. Communities in Cyberspace, pages 29-59, 1999.

*9:H. T. Welser, E. Gleave, D. Fisher, and M. Smith. Visualizing the signatures of social roles in online discussion groups. Journal of Social Structure, 8(2), 2007.

*10:W. Sack. Conversation map: a content-based Usenet newsgroup browser. In IUI’00, pages 233-240, 2000.

*11:J. Arguello, B. S. Butler, L. Joyce, R. Kraut, K. S. Ling, and X. Wang. Talk to me: foundations for successful individual-group interactions in online communities. In CHI’06, pages 959-968, 2006.

*12:E. Joyce and R. Kraut. Predicting Continued Participation in Newsgroups. Journal of Computer-Mediated Communication, 11(3):723-747, 2006.

*13:K. Lakhani and E. von Hippel. How open source software works:“free” user-to-user assistance. Research Policy, 32(6):923-943, 2003.

*14:B. Butler. Membership Size, Communication Activity, and Sustainability: A Resource-Based Model of Online Social Structures. Information Systems Research, 12(4):346-362, 2001.

*15:J. Zhang, M. Ackerman, and L. A. Adamic. Expertise networks in online communities: structure and algorithms. In WWW’07, pages 221-230, 2007.

*16:J. Zhang, M. S. Ackerman, and L. A. Adamic. Communitynetsimulator: Using simulations to study online community networks. In C & T’07, 2007.

*17:Q. Su, D. Pavlov, J. Chow, and W. Baker. Internet-scale collection of human-reviewed data. In WWW’07, pages 231-240, 2007.

*18:S. Kim, J. S. Oh, and S. Oh. Best-Answer Selection Criteria in a Social Q&A site from the User-Oriented Relevance Perspective. presented at ASIST, 2007.

*19:T. Turner, M. Smith, D. Fisher, and H. Welser. Picturing Usenet: Mapping Computer-Mediated Collective Action. Journal of Computer-Mediated Communication, 10(4), 2005.

*20:H. T. Welser, E. Gleave, D. Fisher, and M. Smith. Visualizing the signatures of social roles in online discussion groups. Journal of Social Structure, 8(2), 2007.

*21:R. Milo, S. Shen-Orr, S. Itzkovitz, N. Kashtan, D. Chklovskii, and U. Alon. Network Motifs: Simple Building Blocks of Complex Networks. Science, 298(5594):824–827, 2002.

*22:R. Milo, S. Itzkovitz, N. Kashtan, R. Levitt, S. Shen-Orr, I. Ayzenshtat, M. Sheﬀer, and U. Alon. Superfamilies of evolved and designed networks. Science, 303:1538–1542, 2004.

*23:S. Wernicke and F. Rasche. FANMOD: a tool for fast network motif detection. Bioinformatics, 22(9):1152–1153, 2006.

*24:J. Zhang, M. Ackerman, and L. A. Adamic. Expertise networks in online communities: structure and algorithms. In WWW’07, pages 221–230, 2007.

*25:S. Wernicke and F. Rasche. FANMOD: a tool for fast network motif detection. Bioinformatics, 22(9):1152–1153, 2006.

*26:E. Agichtein, C. Castillo, D. Donato, A. Gionis, and G. Mishne. Finding High-Quality Content in Social Media. WDSM’08, 2008.