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.