\documentclass[11pt,twoside]{article}\makeatletter

\IfFileExists{xcolor.sty}%
  {\RequirePackage{xcolor}}%
  {\RequirePackage{color}}
\usepackage{colortbl}
\usepackage{wrapfig}
\usepackage{ifxetex}
\ifxetex
  \usepackage{fontspec}
  \usepackage{xunicode}
  \catcode`⃥=\active \def⃥{\textbackslash}
  \catcode`❴=\active \def❴{\{}
  \catcode`❵=\active \def❵{\}}
  \def\textJapanese{\fontspec{Noto Sans CJK JP}}
  \def\textChinese{\fontspec{Noto Sans CJK SC}}
  \def\textKorean{\fontspec{Noto Sans CJK KR}}
  \setmonofont{DejaVu Sans Mono}
  
\else
  \IfFileExists{utf8x.def}%
   {\usepackage[utf8x]{inputenc}
      \PrerenderUnicode{–}
    }%
   {\usepackage[utf8]{inputenc}}
  \usepackage[english]{babel}
  \usepackage[T1]{fontenc}
  \usepackage{float}
  \usepackage[]{ucs}
  \uc@dclc{8421}{default}{\textbackslash }
  \uc@dclc{10100}{default}{\{}
  \uc@dclc{10101}{default}{\}}
  \uc@dclc{8491}{default}{\AA{}}
  \uc@dclc{8239}{default}{\,}
  \uc@dclc{20154}{default}{ }
  \uc@dclc{10148}{default}{>}
  \def\textschwa{\rotatebox{-90}{e}}
  \def\textJapanese{}
  \def\textChinese{}
  \IfFileExists{tipa.sty}{\usepackage{tipa}}{}
\fi
\def\exampleFont{\ttfamily\small}
\DeclareTextSymbol{\textpi}{OML}{25}
\usepackage{relsize}
\RequirePackage{array}
\def\@testpach{\@chclass
 \ifnum \@lastchclass=6 \@ne \@chnum \@ne \else
  \ifnum \@lastchclass=7 5 \else
   \ifnum \@lastchclass=8 \tw@ \else
    \ifnum \@lastchclass=9 \thr@@
   \else \z@
   \ifnum \@lastchclass = 10 \else
   \edef\@nextchar{\expandafter\string\@nextchar}%
   \@chnum
   \if \@nextchar c\z@ \else
    \if \@nextchar l\@ne \else
     \if \@nextchar r\tw@ \else
   \z@ \@chclass
   \if\@nextchar |\@ne \else
    \if \@nextchar !6 \else
     \if \@nextchar @7 \else
      \if \@nextchar (8 \else
       \if \@nextchar )9 \else
  10
  \@chnum
  \if \@nextchar m\thr@@\else
   \if \@nextchar p4 \else
    \if \@nextchar b5 \else
   \z@ \@chclass \z@ \@preamerr \z@ \fi \fi \fi \fi
   \fi \fi  \fi  \fi  \fi  \fi  \fi \fi \fi \fi \fi \fi}
\gdef\arraybackslash{\let\\=\@arraycr}
\def\@textsubscript#1{{\m@th\ensuremath{_{\mbox{\fontsize\sf@size\z@#1}}}}}
\def\Panel#1#2#3#4{\multicolumn{#3}{){\columncolor{#2}}#4}{#1}}
\def\abbr{}
\def\corr{}
\def\expan{}
\def\gap{}
\def\orig{}
\def\reg{}
\def\ref{}
\def\sic{}
\def\persName{}\def\name{}
\def\placeName{}
\def\orgName{}
\def\textcal#1{{\fontspec{Lucida Calligraphy}#1}}
\def\textgothic#1{{\fontspec{Lucida Blackletter}#1}}
\def\textlarge#1{{\large #1}}
\def\textoverbar#1{\ensuremath{\overline{#1}}}
\def\textquoted#1{‘#1’}
\def\textsmall#1{{\small #1}}
\def\textsubscript#1{\@textsubscript{\selectfont#1}}
\def\textxi{\ensuremath{\xi}}
\def\titlem{\itshape}
\newenvironment{biblfree}{}{\ifvmode\par\fi }
\newenvironment{bibl}{}{}
\newenvironment{byline}{\vskip6pt\itshape\fontsize{16pt}{18pt}\selectfont}{\par }
\newenvironment{citbibl}{}{\ifvmode\par\fi }
\newenvironment{docAuthor}{\ifvmode\vskip4pt\fontsize{16pt}{18pt}\selectfont\fi\itshape}{\ifvmode\par\fi }
\newenvironment{docDate}{}{\ifvmode\par\fi }
\newenvironment{docImprint}{\vskip 6pt}{\ifvmode\par\fi }
\newenvironment{docTitle}{\vskip6pt\bfseries\fontsize{22pt}{25pt}\selectfont}{\par }
\newenvironment{msHead}{\vskip 6pt}{\par}
\newenvironment{msItem}{\vskip 6pt}{\par}
\newenvironment{rubric}{}{}
\newenvironment{titlePart}{}{\par }

\newcolumntype{L}[1]{){\raggedright\arraybackslash}p{#1}}
\newcolumntype{C}[1]{){\centering\arraybackslash}p{#1}}
\newcolumntype{R}[1]{){\raggedleft\arraybackslash}p{#1}}
\newcolumntype{P}[1]{){\arraybackslash}p{#1}}
\newcolumntype{B}[1]{){\arraybackslash}b{#1}}
\newcolumntype{M}[1]{){\arraybackslash}m{#1}}
\definecolor{label}{gray}{0.75}
\def\unusedattribute#1{\sout{\textcolor{label}{#1}}}
\DeclareRobustCommand*{\xref}{\hyper@normalise\xref@}
\def\xref@#1#2{\hyper@linkurl{#2}{#1}}
\begingroup
\catcode`\_=\active
\gdef_#1{\ensuremath{\sb{\mathrm{#1}}}}
\endgroup
\mathcode`\_=\string"8000
\catcode`\_=12\relax

\usepackage[a4paper,twoside,lmargin=1in,rmargin=1in,tmargin=1in,bmargin=1in,marginparwidth=0.75in]{geometry}
\usepackage{framed}

\definecolor{shadecolor}{gray}{0.95}
\usepackage{longtable}
\usepackage[normalem]{ulem}
\usepackage{fancyvrb}
\usepackage{fancyhdr}
\usepackage{graphicx}
\usepackage{marginnote}

\renewcommand{\@cite}[1]{#1}


\renewcommand*{\marginfont}{\itshape\footnotesize}

\def\Gin@extensions{.pdf,.png,.jpg,.mps,.tif}

  \pagestyle{fancy}

\usepackage[pdftitle={Relevance Search via Bipolar Label Diffusion on Bipartite Graphs},
 pdfauthor={}]{hyperref}
\hyperbaseurl{}

	 \paperwidth210mm
	 \paperheight297mm
              
\def\@pnumwidth{1.55em}
\def\@tocrmarg {2.55em}
\def\@dotsep{4.5}
\setcounter{tocdepth}{3}
\clubpenalty=8000
\emergencystretch 3em
\hbadness=4000
\hyphenpenalty=400
\pretolerance=750
\tolerance=2000
\vbadness=4000
\widowpenalty=10000

\renewcommand\section{\@startsection {section}{1}{\z@}%
     {-1.75ex \@plus -0.5ex \@minus -.2ex}%
     {0.5ex \@plus .2ex}%
     {\reset@font\Large\bfseries}}
\renewcommand\subsection{\@startsection{subsection}{2}{\z@}%
     {-1.75ex\@plus -0.5ex \@minus- .2ex}%
     {0.5ex \@plus .2ex}%
     {\reset@font\Large}}
\renewcommand\subsubsection{\@startsection{subsubsection}{3}{\z@}%
     {-1.5ex\@plus -0.35ex \@minus -.2ex}%
     {0.5ex \@plus .2ex}%
     {\reset@font\large}}
\renewcommand\paragraph{\@startsection{paragraph}{4}{\z@}%
     {-1ex \@plus-0.35ex \@minus -0.2ex}%
     {0.5ex \@plus .2ex}%
     {\reset@font\normalsize}}
\renewcommand\subparagraph{\@startsection{subparagraph}{5}{\parindent}%
     {1.5ex \@plus1ex \@minus .2ex}%
     {-1em}%
     {\reset@font\normalsize\bfseries}}


\def\l@section#1#2{\addpenalty{\@secpenalty} \addvspace{1.0em plus 1pt}
 \@tempdima 1.5em \begingroup
 \parindent \z@ \rightskip \@pnumwidth 
 \parfillskip -\@pnumwidth 
 \bfseries \leavevmode #1\hfil \hbox to\@pnumwidth{\hss #2}\par
 \endgroup}
\def\l@subsection{\@dottedtocline{2}{1.5em}{2.3em}}
\def\l@subsubsection{\@dottedtocline{3}{3.8em}{3.2em}}
\def\l@paragraph{\@dottedtocline{4}{7.0em}{4.1em}}
\def\l@subparagraph{\@dottedtocline{5}{10em}{5em}}
\@ifundefined{c@section}{\newcounter{section}}{}
\@ifundefined{c@chapter}{\newcounter{chapter}}{}
\newif\if@mainmatter 
\@mainmattertrue
\def\chaptername{Chapter}
\def\frontmatter{%
  \pagenumbering{roman}
  \def\thechapter{\@roman\c@chapter}
  \def\theHchapter{\roman{chapter}}
  \def\thesection{\@roman\c@section}
  \def\theHsection{\roman{section}}
  \def\@chapapp{}%
}
\def\mainmatter{%
  \cleardoublepage
  \def\thechapter{\@arabic\c@chapter}
  \setcounter{chapter}{0}
  \setcounter{section}{0}
  \pagenumbering{arabic}
  \setcounter{secnumdepth}{6}
  \def\@chapapp{\chaptername}%
  \def\theHchapter{\arabic{chapter}}
  \def\thesection{\@arabic\c@section}
  \def\theHsection{\arabic{section}}
}
\def\backmatter{%
  \cleardoublepage
  \setcounter{chapter}{0}
  \setcounter{section}{0}
  \setcounter{secnumdepth}{2}
  \def\@chapapp{\appendixname}%
  \def\thechapter{\@Alph\c@chapter}
  \def\theHchapter{\Alph{chapter}}
  \appendix
}
\newenvironment{bibitemlist}[1]{%
   \list{\@biblabel{\@arabic\c@enumiv}}%
       {\settowidth\labelwidth{\@biblabel{#1}}%
        \leftmargin\labelwidth
        \advance\leftmargin\labelsep
        \@openbib@code
        \usecounter{enumiv}%
        \let\p@enumiv\@empty
        \renewcommand\theenumiv{\@arabic\c@enumiv}%
	}%
  \sloppy
  \clubpenalty4000
  \@clubpenalty \clubpenalty
  \widowpenalty4000%
  \sfcode`\.\@m}%
  {\def\@noitemerr
    {\@latex@warning{Empty `bibitemlist' environment}}%
    \endlist}

\def\tableofcontents{\section*{\contentsname}\@starttoc{toc}}
\parskip0pt
\parindent1em
\def\Panel#1#2#3#4{\multicolumn{#3}{){\columncolor{#2}}#4}{#1}}
\newenvironment{reflist}{%
  \begin{raggedright}\begin{list}{}
  {%
   \setlength{\topsep}{0pt}%
   \setlength{\rightmargin}{0.25in}%
   \setlength{\itemsep}{0pt}%
   \setlength{\itemindent}{0pt}%
   \setlength{\parskip}{0pt}%
   \setlength{\parsep}{2pt}%
   \def\makelabel##1{\itshape ##1}}%
  }
  {\end{list}\end{raggedright}}
\newenvironment{sansreflist}{%
  \begin{raggedright}\begin{list}{}
  {%
   \setlength{\topsep}{0pt}%
   \setlength{\rightmargin}{0.25in}%
   \setlength{\itemindent}{0pt}%
   \setlength{\parskip}{0pt}%
   \setlength{\itemsep}{0pt}%
   \setlength{\parsep}{2pt}%
   \def\makelabel##1{\upshape ##1}}%
  }
  {\end{list}\end{raggedright}}
\newenvironment{specHead}[2]%
 {\vspace{20pt}\hrule\vspace{10pt}%
  \phantomsection\label{#1}\markright{#2}%

  \pdfbookmark[2]{#2}{#1}%
  \hspace{-0.75in}{\bfseries\fontsize{16pt}{18pt}\selectfont#2}%
  }{}
      \def\TheFullDate{2012-01-15 (revised: 15 January 2012)}
\def\TheID{\makeatother }
\def\TheDate{2012-01-15}
\title{Relevance Search via Bipolar Label Diffusion on Bipartite Graphs}
\author{}\makeatletter 
\makeatletter
\newcommand*{\cleartoleftpage}{%
  \clearpage
    \if@twoside
    \ifodd\c@page
      \hbox{}\newpage
      \if@twocolumn
        \hbox{}\newpage
      \fi
    \fi
  \fi
}
\makeatother
\makeatletter
\thispagestyle{empty}
\markright{\@title}\markboth{\@title}{\@author}
\renewcommand\small{\@setfontsize\small{9pt}{11pt}\abovedisplayskip 8.5\p@ plus3\p@ minus4\p@
\belowdisplayskip \abovedisplayskip
\abovedisplayshortskip \z@ plus2\p@
\belowdisplayshortskip 4\p@ plus2\p@ minus2\p@
\def\@listi{\leftmargin\leftmargini
               \topsep 2\p@ plus1\p@ minus1\p@
               \parsep 2\p@ plus\p@ minus\p@
               \itemsep 1pt}
}
\makeatother
\fvset{frame=single,numberblanklines=false,xleftmargin=5mm,xrightmargin=5mm}
\fancyhf{} 
\setlength{\headheight}{14pt}
\fancyhead[LE]{\bfseries\leftmark} 
\fancyhead[RO]{\bfseries\rightmark} 
\fancyfoot[RO]{}
\fancyfoot[CO]{\thepage}
\fancyfoot[LO]{\TheID}
\fancyfoot[LE]{}
\fancyfoot[CE]{\thepage}
\fancyfoot[RE]{\TheID}
\hypersetup{citebordercolor=0.75 0.75 0.75,linkbordercolor=0.75 0.75 0.75,urlbordercolor=0.75 0.75 0.75,bookmarksnumbered=true}
\fancypagestyle{plain}{\fancyhead{}\renewcommand{\headrulewidth}{0pt}}

\date{}
\usepackage{authblk}

\providecommand{\keywords}[1]
{
\footnotesize
  \textbf{\textit{Index terms---}} #1
}

\usepackage{graphicx,xcolor}
\definecolor{GJBlue}{HTML}{273B81}
\definecolor{GJLightBlue}{HTML}{0A9DD9}
\definecolor{GJMediumGrey}{HTML}{6D6E70}
\definecolor{GJLightGrey}{HTML}{929497} 

\renewenvironment{abstract}{%
   \setlength{\parindent}{0pt}\raggedright
   \textcolor{GJMediumGrey}{\rule{\textwidth}{2pt}}
   \vskip16pt
   \textcolor{GJBlue}{\large\bfseries\abstractname\space}
}{%   
   \vskip8pt
   \textcolor{GJMediumGrey}{\rule{\textwidth}{2pt}}
   \vskip16pt
}

\usepackage[absolute,overlay]{textpos}

\makeatother 
      \usepackage{lineno}
      \linenumbers
      
\begin{document}

             \author[1]{Dr. Zhang  Liang}

             \affil[1]{  }

\renewcommand\Authands{ and }

\date{\small \em Received: 13 December 2011 Accepted: 2 January 2012 Published: 15 January 2012}

\maketitle


\begin{abstract}
        


The task of relevance search is to find relevant items to some given queries, which can be viewed either as an information retrieval problem or as a semi-supervised learning problem. In order to combine both of their advantages, we develop a new relevance search method using label diffusion on bipartite graphs. And we propose a heat diffusion-based algorithm, namely bipartite label diffusion (BLD). Our method yields encouraging experimental results on a number of relevance search problems.

\end{abstract}


\keywords{Relevance search, ranking, graph diffusion, bipartite graphs.}

\begin{textblock*}{18cm}(1cm,1cm) % {block width} (coords) 
\textcolor{GJBlue}{\LARGE Global Journals \LaTeX\ JournalKaleidoscope\texttrademark}
\end{textblock*}

\begin{textblock*}{18cm}(1.4cm,1.5cm) % {block width} (coords) 
\textcolor{GJBlue}{\footnotesize \\ Artificial Intelligence formulated this projection for compatibility purposes from the original article published at Global Journals. However, this technology is currently in beta. \emph{Therefore, kindly ignore odd layouts, missed formulae, text, tables, or figures.}}
\end{textblock*}


\let\tabcellsep& 	 	 		 
\section[{I. INTRODUCTION}]{I. INTRODUCTION}\par
he problem of relevance search (RS) has been recognized as an important and interesting problem in machine learning and information retrieval, which refers to finding relevant items to a small query set given by the user. Along with the ability to find a cluster of data that shares some common properties to the query, it is also a primary goal of the information retrieval (IR) systems. Typical applications of RS include the discovery of relevant words in a text corpus \hyperref[b0]{[1]}\hyperref[b1]{[2]}\hyperref[b2]{[3]}\hyperref[b3]{[4]} , answers to community questions \hyperref[b4]{[5,}\hyperref[b5]{6]} , features in conceptlearning problems \hyperref[b6]{[7]} , recommendations in collaborative filtering systems \hyperref[b7]{[8,}\hyperref[b8]{9]} , among others.\par
Google Sets \hyperref[b9]{[10]} is a well-known and successful representative of RS systems that has been widely used. It uses vast amount of web-pages to create a list of related items from a few examples, such as people, movies, words, places, etc. Most of the other RS systems are similar to Google Sets in that they perform some ranking algorithm on a large corpus of documents or web-pages. Ghahramani and Heller \hyperref[b10]{[11]} proposed the Bayesian Sets algorithm that uses a model-based concept of clusters and performs Bayesian inference to compute the ranking scores of items. Sun et al. \hyperref[b11]{[12]} used bipartite graphs to model the data and introduced random walks with restarts to rank the items.\par
The RS problem can be viewed from several angles. First, finding relevant items to the query is a standard IR task \hyperref[b10]{[11,}\hyperref[b12]{13]} , which may be solved using classic IR algorithms, such as HITS \hyperref[b13]{[14]} , nearest neighbors, naïve Bayes and Rocchio's algorithm. These algorithms can compute a list of items ordered by the relevance to the query. However, there is no explicit boundary between "relevant" and "irrelevant" items. Second, RS can be interpreted as a special case of semi-supervised learning (SSL) problem with a few positive examples given as the query \hyperref[b10]{[11]} .\par
It is essentially a one-class classification/clustering problem, which can be solved using one-class learning techniques like mappingconvergence \hyperref[b14]{[15]} and OC-SVMs \hyperref[b15]{[16,}\hyperref[b16]{17]} . The relevant and irrelevant items can be explicitly classified through SSL algorithms. However, most of these algorithms do not provide the rank order of items, which is of importance in IR systems.\par
In this paper, we propose and evaluate a new RS method called bipartite label diffusion (BLD) that can be seen as a hybrid between IR and SSL. BLD is a diffusion-based algorithm that works on bipartite graph. User queries are mapped to vertices with positive labels on the graph. BLD performs local computation at every vertex of the graph and develops a global classifier through the label diffusion process. The diffusion process is often modeled using a Markov chain on the graph. In BLD, we modified the diffusion model by adopting the "label spreading" method \hyperref[b17]{[18]} to allow negative labels diffuse on the graph. If the word/document is relevant to the queries, the score value is positive, otherwise the value is negative. The more the item is relevant, the higher the score is. Thus BLD can be seen as a semi-supervised learning method.\par
The rest of this paper is organized as follows. We first model the corpus data as document-word bipartite graphs in section 2. The detail of the BLD algorithm is given in section 3. In section 4, we present empirical results to demonstrate the effectiveness of BLD on relevance search problems. Finally, some concluding remarks are given in section 5. 
\section[{II. BIPARTITE GRAPH MODEL}]{II. BIPARTITE GRAPH MODEL}\par
Bipartite graph models have been successfully applied in many fields such as text clustering \hyperref[b18]{[19]}\hyperref[b19]{[20]}\hyperref[b20]{[21]} , collaborative filtering \hyperref[b22]{[22,}\hyperref[b23]{23]} , and content-based image retrieval \hyperref[b24]{[24]} . The first step of our method is to model the document-word dataset as a bipartite model. We also employ a query expansion scheme to enhance the searching capacity. Detailed description is given in this section.\par
Suppose we are given a set of n documents , \}i j i j E d w d w = ? ? D\par
W is the set of edges between two sets of vertices D and W . In the bipartite graph G, there are no edges between words or between documents. An edge e (i, j) exists if word w j appears in document d i . which is denoted by j i w d . And it indicates an association between a word and a document, which may be quantitatively expressed by assigning positive weights on the edges. Assume we are given the user's query set of wordsQ W ( , Q Q ? ? ? W W W ), or documents Q D ( , Q Q ? ? ? D D W )\par
, or both of them, the RS problem can be cast to a semi-supervised learning task where the query set contains the initial labeled examples. Fig. \hyperref[fig_0]{1} shows a simple example of the bipartite graph model.\par
Figure \hyperref[fig_0]{1}: Example of a document-word bipartite graph which has 3 documents and a vocabulary of 4 words. The user's query set is1 \{ \} Q w = W and 1 \{ \} Q d = D\par
. The goal of this similar sets retrieval problem is to discover a set of words that are similar to Q W , and a set of documents that are similar to Q D There are many edge-weighting schemes in information retrieval research, among them we adopt the popular "tf-idf" weight:ln\#( , ) tf-idf ( , ) ln ln \#( , ) \{ : \textasciitilde  \} i j i j i k j k d w n d w d w d w d = ? ? where \#( , )\par
i j d w is the number of occurrence of word w j in document d i . Words with high tf-idf values imply a strong relationship with the document they appear in.\par
We can define an n m × edge weight matrix M: \{ , tf-idf ( , ), if edge ( , ) exists, 0, otherwise.i j i j i j d w d w M =\par
To interpret the edge weight matrix from the perspective of Markov chains on graph, which will be described in section 3, we define the transition probability from d i to w j as:, , ,\textbf{1}m i j i j i p p P M M = = ?\textbf{(1)}\par
And the transition probability from w j to d i is given by, , , , 1n j i i j p j p Q M M = = ?\textbf{(2)}\par
The Markov transition matrix P normalizes M such that every row sum up to 1, and Q normalizes M T such that every row sum up to 1. 
\section[{Thus the (}]{Thus the (}\par
) ( ) m n m n + × + adjacency matrix A of the bipartite graph may be written as:? ? = ? ? ? ? 0 Q A P 0 ,\par
Where the vertices of the graph is ordered such that the first m vertices index the words and the last n vertices index the documents.\par
Note that bipartite graph can also be a good model in the scenario of collaborative filtering or recommendation systems. A standard collaborative filtering problem often involves a user set U , an item set I , and a vote set V . In a similar manner, we can build a bipartite graph ( , , )E = G U I\par
. The normalized vote scores of V can directly serve as the weight matrix. Moreover, the aim of collaborative filtering is to discover new items that an active user may like based on her voted items, which could be easily translated to a RS problem by finding similar items to the user's favorite ones (items with high voting scores). 
\section[{III.}]{III.} 
\section[{LABEL DIFFUSION ON BIPARTITE GRAPHS}]{LABEL DIFFUSION ON BIPARTITE GRAPHS}\par
In general, there are two primary approaches to cluster vertices on a bipartite graph: one is to partition the graph to disjoint parts corresponding to different clusters \hyperref[b25]{[25,}\hyperref[b26]{26]} ; the other is to compute a rank value for each vertex indicating the probability that the vertex is in a cluster \hyperref[b24]{[24,}\hyperref[b27]{27]} . To capture the uncertainties on datacluster assignments, we investigate the problem from the latter angle. 
\section[{a) Markov Chains on the Graph}]{a) Markov Chains on the Graph}\par
In a bipartite graph, there are no direct relationships among the words or among the documents. However, in diffusion-based methods \hyperref[b17]{[18,}\hyperref[b27]{27]} , the strength of the similarities among elements on the same side of the bipartite graph may be captured by a local probability evolution process, which can be integrated to obtain a global view of the data.\par
We define a Markov chain to describe the diffusion process over the bipartite graph. Assume there is a discrete time random walk on the bipolar graph G, the row-normalized adjacency matrix A is the one-step transition matrix that , i j A is the probability of moving to the jth vertex of v given that the current step is at the ith vertex. More specifically, P is the document-word transition matrix containing the transition probabilities ofw 1 d 2 d 3 w 2 w 3 w 4 W ( D D D D ) D\textbf{2012}\par
Year moving from a document vertex to a word vertex, and Q is the word-document transition matrix. Since the document-word graph is bipartite, all the paths from w i to w j must go through vertices in D . As is shown in [15, 18], the similarity of two words w i and w j , is a quantity proportional to the probability of direct transitions between them, denoted by p(w i , w j ), ( , ) ( ) ( | ) = = ? ?\par
Obviously, it is a 2-step stochastic process that first maps w i to the document set, and then maps the documents back to w j .\par
Similarly, the conditional transition probability from d i to d j is given by, , ,\textbf{( | )} 
\section[{? ?}]{? ?}\par
Therefore, by formulating the relationship between documents and words as Markov chains on the bipartite graph, we have the word-word transition probability matrix QP , and the document-document transition probability matrix PQ . 
\section[{b) Diffusion Process}]{b) Diffusion Process}\par
Intuitively, our bipolar diffusion framework works as following: First, we construct a bipartite graph with two poles as is described in section 2.3. The heat pole stands for the words and documents that are most relevant to the query, while the cold pole contains the "strongest negative" words and documents. Then a certain amount of heat is injected to the graph through the heat pole, and the cold polar extracts the heat out of the system as a heat sink. And the heat diffuses through the edges of the graph. Since the system has two poles, we name the heat diffusion as the "bipolar diffusion process".\par
The diffusion process may be thought of as a Markov chain on the graph. The fundamental property of a Markov chain is the Markov property, which make it possible to predict the future state of a system from its present state ignoring its past states. We denote p  {\ref (t)} and q (t) as the labels of documents and words at time t. The Markov process then defines a dynamic system,( 1) ( ) ( ) t t t + = ? = Q QP p q p (\textbf{3}) ( 1) ( ) ( ) t t t + =? = P PQ q p q (4)\par
This simple 2-step diffusion process captures the interaction between the two sets of vertices on the graph. It requires p  {\ref (t)} and q (t) be the probability distributions of Markov states with non-negative values.\par
However, in our bipolar graph diffusion framework, the vertices of the cold pole are labeled by negative values. In the following, we cast the diffusion process as a semisupervised learning problem, which makes it possible to diffuse heat and cold simultaneously on the graph. First, we use an (n+2)-vector p  {\ref (0)} to denote the initial labels of documents, ? (0) \{1, 0,...0, 1\} T n = ? p ; and an (m+2)-vector q (0) to denote the initial labels of words,? (0) \{1, 0,...0, 1\} T m = ? q\par
. The virtual vertices of heat pole are labeled by positive values, which allow heat diffuses through the graph; while negative values representing "cold" are assigned to the virtual vertices of cold pole.\par
And the vertices keep exchanging these two kinds of energy as the diffusion process proceeds.\par
Then we adopt the "label spreading" method \hyperref[b17]{[18]} to allow negative labels diffuse on the graph. The iteration in Eq. ( \hyperref[formula_13]{3}) and Eq. (  {\ref 4}) can be rewritten as,( 1) (0) ( ) (\textbf{1})t t ? ? + = + ? ? Q p p q ( 1) (0) ( ) (\textbf{1})t t ? ? + = + ? ? P q q p\par
Where ? and ? are scaling parameters both in (0,1), which specify the relative amount of the heat/cold a vertex received from its neighbors and its initial label information. To simplify the diffusion process, we set 1 2\par
? ? = = . The iteration equations indicate that when1 t ? (5) (6)\par
Where and . Since P ? and Q ? are row-normalized matrices, Eq. (  {\ref 5}) follows that when t ? ? , \hyperref[b0]{( 1)} t+ p converges to,\par
And Eq. (  {\ref 6}) converges to,\par
© 2012 Global Journals Inc. (US) 
\section[{Global Journal of Computer Science and Technology}]{Global Journal of Computer Science and Technology}\par
Volume XII Issue X Version I21 ( D D D D ) D ( 1) (0) ( ) (0) (0)\textbf{( 1) 1 (0)}(0) (0) 0 1 1 1 1 () 2 2 4 4 11 ( )( ) 24 t t t t it i ?? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? Q Q QP ? Q ? p p q p q p p q p ( 1)\textbf{(0) ( ) (0) (0) ( 1) 1 (0)}(0) (0) 0 1 1 1 1 () 2 2 4 4 11 ( )( ) 24 t t t t it i ?? ? ? ? ? ? ? ? ? ? ? ? ? ? ? P P PQ Î?" P Î?" q q p q p q q p q 1 4 ? ? QP ? ? 1 4 ? Î?" PQ ? ? ( ) 1 (0) (0) 11 ( ) ( ) 24 ?? ? ? ? I ? Q p p q ( ) 1 (0)\textbf{(0) 11 ( ) ( ) 24 ??}? ? ? I Î?" P q q p IV. EXPERIMENTS\par
Our proposed BLD method is applicable to discover similar items to a query set from a corpus of text data or user rating data. In this section, we experiment with our model on a set of RS problems.\par
The experiments are performed on two standard text datasets: Reuters-21578 1 , and a collaborative filtering dataset: MovieLens 2 
\section[{Datasets}]{Datasets}\par
. All of the text datasets were preprocessed by removing the stopwords and stemming. And for Reuters-21578, we use a subset of the ten most frequent categories with highest number of positive examples, namely Reuters-10. The main features of the datasets are summarized in Table  {\ref 1}. We conducted two experiments on both the text dataset Reuter-10 and the movie rating dataset MovieLens to evaluate the RS ability of our method. The results and comparisons with Google Sets 3 , Internet movie database (IMDB) \hyperref[b3]{4} query: science + technology , and Bayesian Sets are given in tables 2, 3 and 4. Concerning the application of movie recommending, the query takes the form of a set of movies. We regard movies as documents and users as words, and the rating scores are equivalent to word frequencies. Thus our algorithm can be easily adapted to collaborative filtering datasets.  Among the tested algorithms and systems, Google Sets is a baseline RS system that is based on vast amount of web data. Although the Google Sets algorithm is not available for us to run it on our datasets, it is still informative and worth to be compared with; IMDB provides movie recommendations by generating a list of 5 movies most related to the query, which is based on collaborative filtering technology; Bayesian Sets views RS as a Bayesian inference problem and gives the corresponding ranking algorithm. We experiment with an online Bayesian Sets recommending system on Movie Lens dataset.\par
From the query results of the relevant words discovery task and the movie suggestion task, we can make the following comments: 1. Table  {\ref 2} shows that both Google Sets and our method can achieve to some extent similar sets to the query. There is not an objective standard to tell the exact similarity between words or movies. However, the words that our method retrieved are obviously more sensible than some results of Google Sets, e.g. "war" and "Intel" for the query of "market" and "price". We think this is because Google Sets and our method have different learning mechanisms and are based on different corpuses. 2. Our method serves as a good algorithm for recommending systems on the MovieLens dataset.\par
The recommended movies to the query "Full Metal Jacket" are all related to war. And for "The Graduate", most of the results are romance and drama movies. We notice that IMDB's suggestions are often popular and new, while Bayesian Sets and our method, limited by the MovieLens dataset, tend to generate classic movies. 
\section[{V. CONCLUSION}]{V. CONCLUSION}\par
In this paper we developed a new graph diffusion algorithm for RS. We used bipartite graphs to model the relationships between documents and words. We also modeled the diffusion process using a Markov chain on the graph, and presented the corresponding label diffusion algorithm. In future work, we will extend the proposed method to other applications (e.g. social networks, question answering systems).\par
VI.\begin{figure}[htbp]
\noindent\textbf{1}\includegraphics[]{image-2.png}
\caption{\label{fig_0}1 \{}\end{figure}
 \begin{figure}[htbp]
\noindent\textbf{I} \par 
\begin{longtable}{P{0.16822916666666665\textwidth}P{0.2125\textwidth}P{0.20364583333333333\textwidth}P{0.20364583333333333\textwidth}P{0.06197916666666667\textwidth}}
\tabcellsep \#\tabcellsep \#\tabcellsep \#\tabcellsep nonzero\\
\tabcellsep documents/uses\tabcellsep words/items\tabcellsep entries\\
Reuters-10\tabcellsep 9,989\tabcellsep 5,180\tabcellsep \multicolumn{2}{l}{373,440}\\
MovieLens\tabcellsep 943\tabcellsep 1,682\tabcellsep \multicolumn{2}{l}{100,000}\end{longtable} \par
 
\caption{\label{tab_2}Table I :}\end{figure}
 \begin{figure}[htbp]
\noindent\textbf{II} \par 
\begin{longtable}{P{0.3431818181818182\textwidth}P{0.18409090909090908\textwidth}P{0.19772727272727272\textwidth}P{0.125\textwidth}}
\multicolumn{4}{l}{Sets and Bld Based on the Same Given Queries. Bld}\\
\tabcellsep \multicolumn{2}{l}{Runs on Reuters-10}\tabcellsep \\
\tabcellsep \tabcellsep \multicolumn{2}{l}{query: market + price}\\
Google Sets\tabcellsep BLD\tabcellsep Google Sets\tabcellsep BLD\\
science\tabcellsep scienc\tabcellsep market\tabcellsep market\\
technology\tabcellsep technologi\tabcellsep price\tabcellsep pric\\
business\tabcellsep univers\tabcellsep overview\tabcellsep money\\
sports\tabcellsep engineer\tabcellsep view\tabcellsep stock\\
health\tabcellsep educat\tabcellsep risk\tabcellsep valu\\
\multicolumn{2}{l}{entertainment research}\tabcellsep gains\tabcellsep bond\\
education\tabcellsep comput\tabcellsep forecasts\tabcellsep busi\\
politics\tabcellsep life\tabcellsep war\tabcellsep compani\\
travel\tabcellsep develop\tabcellsep Intel\tabcellsep trade\\
computers\tabcellsep cultur\tabcellsep losses\tabcellsep economic\end{longtable} \par
 
\caption{\label{tab_3}Table II :}\end{figure}
 \begin{figure}[htbp]
\noindent\textbf{III} \par 
\begin{longtable}{P{0.258067940552017\textwidth}P{0.18949044585987262\textwidth}P{0.003609341825902335\textwidth}P{0.1912951167728238\textwidth}P{0.018046709129511677\textwidth}P{0.18949044585987262\textwidth}}
\multicolumn{4}{l}{Query: Full Metal Jacket (1987)}\tabcellsep \\
Google Sets\tabcellsep IMDB\tabcellsep \tabcellsep \multicolumn{2}{l}{Bayesian Sets}\tabcellsep BLD\\
Saving Private Ryan (1998)\tabcellsep \multicolumn{2}{l}{Platoon (1986)}\tabcellsep \multicolumn{2}{l}{The Terminator (1984)}\tabcellsep Platoon (1986)\\
Apocalypse Now (1979)\tabcellsep \multicolumn{2}{l}{All Quiet on the Western Front (1930)}\tabcellsep Star Episode (1980)\tabcellsep Wars V\tabcellsep Rambo:First Blood (1982)\\
Platoon (1986)\tabcellsep Cidade Deus (2002)\tabcellsep de\tabcellsep \multicolumn{2}{l}{Raiders of the Lost Ark (1981)}\tabcellsep Braveheart (1995)\\
Pulp Fiction (1994)\tabcellsep Batoru Rowaiaru (2000)\tabcellsep \tabcellsep \multicolumn{2}{l}{Aliens (1986)}\tabcellsep Apocalypse Now (1979)\\
Hamburger Hill (1987)\tabcellsep If? (1968)\tabcellsep \tabcellsep Die (1988)\tabcellsep Hard\tabcellsep Star Wars Episode V (1980)\end{longtable} \par
 
\caption{\label{tab_4}Table III :}\end{figure}
 \begin{figure}[htbp]
\noindent\textbf{IV} \par 
\begin{longtable}{P{0.24933333333333332\textwidth}P{0.17944444444444443\textwidth}P{0.23422222222222222\textwidth}P{0.17755555555555555\textwidth}P{0.009444444444444445\textwidth}}
\multicolumn{3}{l}{Query: The Graduate (1967)}\tabcellsep \tabcellsep \\
Google Sets\tabcellsep IMDB\tabcellsep Bayesian Sets\tabcellsep BLD\tabcellsep \\
Chinatown\tabcellsep Mysterious\tabcellsep Casablanca\tabcellsep Casablanca\tabcellsep \\
(1974)\tabcellsep Skin (2004)\tabcellsep (1942)\tabcellsep (1942)\tabcellsep \\
Midnight Cowboy (1969)\tabcellsep Giant (1956)\tabcellsep The Wizard of Oz (1939)\tabcellsep Annie (1977)\tabcellsep Hall\\
Annie Hall (1977)\tabcellsep The Notebook (2004)\tabcellsep One over Nest (1975) Flew the Cuckoo's\tabcellsep \multicolumn{2}{l}{Gone with the Wind (1939)}\\
Taxi Driver (1976)\tabcellsep Bigfish (2003)\tabcellsep The Godfather (1972)\tabcellsep To Mockingbird Kill (1962)\tabcellsep a\\
Bonnie and Clyde (1967)\tabcellsep Notes on a Scandal (2006)\tabcellsep Amadeus (1984)\tabcellsep Giant (1956)\tabcellsep \end{longtable} \par
 
\caption{\label{tab_5}Table IV :}\end{figure}
 			\footnote{http://www.daviddlewis.com/resources/testcollections/reuters21578/ 2 http://www.grouplens.org/system/files/ml-data.tar\textunderscore \textunderscore 0.gz 3 http://labs.google.com/sets 4 http://www.imdb.com/} 		 		\backmatter   			 
\subsection[{ACKNOWLEDGMENT}]{ACKNOWLEDGMENT} 			  			  				\begin{bibitemlist}{1}
\bibitem[Google and Sets]{b9}\label{b9} 	 		\textit{},  		 			Google Google 		,  		 			Sets 		.  		 \url{<http://labs.google.com/sets>}  		 	 
\bibitem[Deng et al. ()]{b4}\label{b4} 	 		‘A generalized Co-HITS algorithm and its application to bipartite graphs’.  		 			H Deng 		,  		 			M R Lyu 		,  		 			I King 		.  	 	 		\textit{Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining},  				 (the 15th ACM SIGKDD international conference on Knowledge discovery and data mining)  		2009. p. .  	 
\bibitem[Lavrenko ()]{b1}\label{b1} 	 		\textit{A generative theory of relevance},  		 			V Lavrenko 		.  		2004.  		 			University of Massachusetts Amherst 		 	 
\bibitem[Blondel et al. ()]{b0}\label{b0} 	 		‘A measure of similarity between graph vertices: Applications to synonym extraction and web searching’.  		 			V D Blondel 		,  		 			A Gajardo 		,  		 			M Heymans 		,  		 			P Senellart 		,  		 			P V Dooren 		.  	 	 		\textit{Siam Review}  		2004. 46  (4)  p. .  	 
\bibitem[Kleinberg ()]{b13}\label{b13} 	 		‘Authoritative sources in a hyperlinked environment’.  		 			J M Kleinberg 		.  	 	 		\textit{J. ACM}  		1999. 46  (5)  p. .  	 
\bibitem[Lin ()]{b2}\label{b2} 	 		‘Automatic retrieval and clustering of similar words’.  		 			D Lin 		.  	 	 		\textit{Proceedings of the 36th Annual Meeting of the Association for Computational Linguistics and 17th International Conference on Computational Linguistics (COLING/ACL-98},  				 (the 36th Annual Meeting of the Association for Computational Linguistics and 17th International Conference on Computational Linguistics (COLING/ACL-98)  		1998. p. .  	 
\bibitem[Cohen ()]{b6}\label{b6} 	 		‘Automatically extracting features for concept learning from the web’.  		 			W W Cohen 		.  	 	 		\textit{Proceedings of the 17th International Conference on Machine Learning},  				 (the 17th International Conference on Machine Learning)  		2000. p. .  	 
\bibitem[Ghahramani and Heller ()]{b10}\label{b10} 	 		‘Bayesian sets’.  		 			Z Ghahramani 		,  		 			K A Heller 		.  	 	 		\textit{Advances in Neural Information Processing Systems},  				2005. 18.  	 
\bibitem[Rege et al. ()]{b26}\label{b26} 	 		‘Bipartite isoperimetric graph partitioning for data coclustering’.  		 			M Rege 		,  		 			M Dong 		,  		 			F Fotouhi 		.  	 	 		\textit{Data Min. Knowl. Discov}  		2008. 16  (3)  p. .  	 
\bibitem[Dhillon ()]{b18}\label{b18} 	 		‘Co-clustering documents and words using bipartite spectral graph partitioning’.  		 			I S Dhillon 		.  	 	 		\textit{Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining},  				 (the 17th ACM SIGKDD international conference on Knowledge discovery and data mining)  		2001. p. .  	 
\bibitem[Shieh et al. ()]{b23}\label{b23} 	 		‘Collaborative knowledge semantic graph image search’.  		 			J.-R Shieh 		,  		 			Y.-T Yeh 		,  		 			C.-H Lin 		,  		 			C.-Y Lin 		,  		 			J.-L Wu 		.  	 	 		\textit{Proceedings of the 17th international conference on World Wide Web},  				 (the 17th international conference on World Wide Web)  		2008. p. .  	 
\bibitem[Bauckhage ()]{b24}\label{b24} 	 		‘Distance-free image retrieval based on stochastic diffusion over bipartite graphs’.  		 			C Bauckhage 		.  	 	 		\textit{Proceedings of the 18th British Machine Vision Conference},  				 (the 18th British Machine Vision Conference)  		2007. p. .  	 
\bibitem[Sindhwani and Melville ()]{b20}\label{b20} 	 		‘Document-Word Co-regularization for Semi-supervised Sentiment Analysis’.  		 			V Sindhwani 		,  		 			P Melville 		.  	 	 		\textit{Proceedings of the},  				 (the)  		2008. 2008.  	 
\bibitem[Eighth IEEE International Conference on Data Mining]{b21}\label{b21} 	 		\textit{Eighth IEEE International Conference on Data Mining},  				p. .  	 
\bibitem[Schölkopf et al. ()]{b16}\label{b16} 	 		‘Estimating the Support of a High-Dimensional Distribution’.  		 			B Schölkopf 		,  		 			J C Platt 		,  		 			J C Shawe-Taylor 		,  		 			A J Smola 		,  		 			R C Williamson 		.  	 	 		\textit{Neural Comput}  		2001. 13  (7)  p. .  	 
\bibitem[Wang and Cohen ()]{b3}\label{b3} 	 		‘Languageindependent set expansion of named entities using the web’.  		 			R C Wang 		,  		 			W W Cohen 		.  	 	 		\textit{Proceedings of the 17th IEEE International Conference on Data Mining},  				 (the 17th IEEE International Conference on Data Mining)  		2007. p. .  	 
\bibitem[Kunegis and Lommatzsch ()]{b22}\label{b22} 	 		‘Learning spectral graph transformations for link prediction’.  		 			J Kunegis 		,  		 			A Lommatzsch 		.  	 	 		\textit{Proceedings of the 26th Annual International Conference on Machine Learning},  				 (the 26th Annual International Conference on Machine Learning)  		2009. p. .  	 
\bibitem[Zhou et al. ()]{b17}\label{b17} 	 		‘Learning with local and global consistency’.  		 			D Zhou 		,  		 			O Bousquet 		,  		 			T N Lal 		,  		 			J Weston 		,  		 			B Schölkopf 		.  	 	 		\textit{Advances in Neural Information Processing Systems},  				2004. 16 p. .  	 
\bibitem[Manevitz and Yousef ()]{b15}\label{b15} 	 		‘One-class svms for document classification’.  		 			L M Manevitz 		,  		 			M Yousef 		.  	 	 		\textit{J. Mach. Learn. Res}  		2002. 2 p. .  	 
\bibitem[Yu et al. ()]{b14}\label{b14} 	 		‘PEBL: Web Page Classification without Negative Examples’.  		 			H Yu 		,  		 			J Han 		,  		 			K C Chang 		,  		 			.-C 		.  	 	 		\textit{IEEE Trans. on Knowl. and Data Eng}  		2004. 16  (1)  p. .  	 
\bibitem[Hu et al. ()]{b19}\label{b19} 	 		‘Preserving Patterns in Bipartite Graph Partitioning’.  		 			T Hu 		,  		 			C Qu 		,  		 			C L Tan 		,  		 			S Y Sung 		,  		 			W Zhou 		.  	 	 		\textit{Proceedings of the 18th IEEE International Conference on Tools with Artificial Intelligence},  				 (the 18th IEEE International Conference on Tools with Artificial Intelligence)  		2006. p. .  	 
\bibitem[Wang and Hancock ()]{b8}\label{b8} 	 		‘Probabilistic relaxation labelling using the Fokker-Planck equation’.  		 			H Wang 		,  		 			E R Hancock 		.  	 	 		\textit{Pattern Recogn}  		2008. 41  (11)  p. .  	 
\bibitem[Lafferty and Zhai ()]{b12}\label{b12} 	 		‘Probabilistic relevance models based on document and query generation. In Language Modeling and Information Retrieval’.  		 			J Lafferty 		,  		 			C Zhai 		.  	 	 		\textit{Kluwer International Series on Information Retrieval}  		2002.  	 
\bibitem[Wang et al. ()]{b5}\label{b5} 	 		‘Probabilistic relevance ranking for collaborative filtering’.  		 			J Wang 		,  		 			S Robertson 		,  		 			A P Vries 		,  		 			M J Reinders 		.  	 	 		\textit{Inf. Retr}  		2008. 11  (6)  p. .  	 
\bibitem[Basu et al. ()]{b7}\label{b7} 	 		‘Recommendation as classification: using social and content-based information in recommendation’.  		 			C Basu 		,  		 			H Hirsh 		,  		 			W Cohen 		.  	 	 		\textit{Proceedings of the 15th national/tenth conference on Artificial intelligence/Innovative applications of artificial intelligence},  				 (the 15th national/tenth conference on Artificial intelligence/Innovative applications of artificial intelligence)  		1998. p. .  	 
\bibitem[Sun et al. ()]{b11}\label{b11} 	 		‘Relevance search and anomaly detection in bipartite graphs’.  		 			J Sun 		,  		 			H Qu 		,  		 			D Chakrabarti 		,  		 			C Faloutsos 		.  	 	 		\textit{SIGKDD Explor. Newsl}  		2005. 7  (2)  p. .  	 
\bibitem[Yu et al. ()]{b27}\label{b27} 	 		‘Soft clustering on graphs’.  		 			K Yu 		,  		 			S Yu 		,  		 			V Tresp 		.  	 	 		\textit{Advances in Neural Information Processing Systems 18},  				2005.  	 
\bibitem[Fern and Brodley ()]{b25}\label{b25} 	 		‘Solving cluster ensemble problems by bipartite graph partitioning’.  		 			X Z Fern 		,  		 			C E Brodley 		.  	 	 		\textit{Proceedings of the 21st International Conference on Machine learning (ICML04)},  				 (the 21st International Conference on Machine learning (ICML04))  		2004. p. 36.  	 
\end{bibitemlist}
 			 		 	 
\end{document}
