Motivation
Kernel-Based Link Analysis



WWW or citations are represented by a huge graph Node: web page, paper Edge: hyper link, citation

Methods to explore graph data are desired

Takahiko Ito

Nara Institute of Science and Technology

1
2

To recommend pages

Recommendation service
1.

2.

Users select favorite nodes (root nodes) – papers /web pages
based on links around of root nodes, the systemrecommend other nodes that may interest theusers



Link Analysis measures: Measures for analyzing the relationship amongnodes in graphs.
 However, classical link analysis measures havesome limitations, if they are applied torecommendation services

We proposed a new link analysis measure basedon kernel methods.

recommendation service

Link structure

１select
Recommend
other nodes

２
３
3

4

Co-citation/bibliographic coupling"relatedness"

Table of contentsIntroduce link analysis measures.
Co-citation coupling [Small et al., 1973]
defines relatedness as the numberof papers jointly citing the given
pair of papers

Propose a new link analysis measure forrecommendation services applying kernel methods
in graphs.

Bibliographic coupling [Kessler,1963]
defines relatedness as the numberof common citations made by twopapersAB

Co-citation coupling (A,B) = 4
ABBibliographic coupling (A,B) = 4

5Computing co-citation/bibliographiccoupling

6

HITS "importance"

Given adjacency matrix A of a citation graph,

HITS [Kleinberg, 1999]
assigns two scores to each node:
Authority score：
Nodes cited by many nodes receive a highauthority score
Hub score:
Node citing many authoritative nodes
receive a high hub score.

(i, j)-element of ATAÎ Co-citation relatedness between nodes i and j (i, j)-element of AAT
Î Bibliographic relatedness between nodes i andj

78

Fact: equivalence of HITS andeigenvector computation

Application of link analysis measures torecommendation service

Given an adjacency matrix A of a citation graph,
it is well known that
HITS authority vector = principal eigenvector ofATA
HITS hub vector = principal eigenvector of AAT

Importance measures recommend popular(important) nodes.
ÄHowever, system may return nodes withdifferent topic to root nodes



Relatedness measures recommend nodes on thesame topic to root nodes
Ä However, system may return low quality nodes

910

Proposed link analysis measure

Table of contents

We propose the measure that is aninterpolationbetween importance and relatedness
Ä System can recommend pages not only
popular but same topic.
Ä In addition, a parameter can control the bias
between importance and relatedness
This property allow each user to adjust theinduced link analysis measures to suit user’s
objectives by tuning of a parameter.

11Introduce link analysis measures.

Propose a new link analysis measure forrecommendation services applying kernel methods
in graphs.

12

Neumann kernels [Kandola et al., 2003]

Neumann kernels for link analysis

Original Neumann kernels compute document relatedness,but not on the basis of citations.
 They use graphs induced by the content of documents:
Edge between nodes (documents) has a weight basedon the number of common terms in their contents.

Neumann kernels in this work
 are applied directly to citation graphs.
 i.e., use adjacency matrix A of a citation graphin place of document-by-term matrix X.
Definition:NKβ(AAT) = AAT + β(AAT)2 + β2(AAT)3 + …
NKβ(ATA) = ATA + β(ATA)2 + β2(ATA)3 + …

Definition:NKβ(XXT) = XXT + β(XXT)2 + β2(XXT)3 + … (document relatedness)NKβ(XTX) = XTX + β(XTX)2 + β2(XTX)3 + …
(term relatedness)where X is a document-by-term matrix, and β is aweighting parameter of matrices.

What do (AAT)n and (ATA)n in these series
represent?
13(ATA)n tends towards HITS importance asn→∞

Meaning of (ATA)n(i, j)-element of (ATA)n = number of paths of lengthn between nodes i and j in a co-citation graph.
 Increasing n from 1 towards ∞ changes (ATA)n fromrelatedness to importance.

Theorem.
Given the co-citation matrix ATA,

12

A

13

B

12

CT

2

D14

nwhereBBCCBDDCC DD
AAA BAAAA
15234031 02
014 192906
3175316 496
A 146
BB
1932920
26130225
5 12301422901
741
78 2002
BB 403
TA)
32 4=
1TT
5(A=(A(AA)A) == CCCC 753
601312515123
67143 322
10248
2305306
2901
7454
DD
2016
0 14022003
1048
2 230236
85306
78
1683800
DD 496nAftern=5,(Aallrowsof (A A) give
identical ranking
C>D>B>A.
TA)
n representsAt
n=1,
theanco-citaion
matrixThis ranking also matches the HITS authority ranking.
As n is increased…
15⎛ ATA ⎞⎟⎟ → xx T⎜⎜
λ⎠⎝as n → ∞λ is the principal eigenvalue of matrix ATA, andx is its principal eigenvector (HITS authority vector),
N.B., every row/column of xxT gives the same ranking of nodes as
HITS authority.
Corollary.
Given any two nodes i and j with Authority(i) > Authority(j), there is aninteger m s.t.
(ATA)n [i,k] > (ATA)n [j,k]for all n>m and for any node k.
16

To sum up, Neumann kernel isSummary

Computing a weighted sum of path weights between nodes.
 And it is a “mixture” of relatedness and importance.

We showed that
NKβ(ATA)interpolation between co-citation coupling and HITS
authority scoresNKβ(AAT)interpolation between bibliographic coupling and HITS
hub scoresNKβ(ATA) = ATA + β(ATA)2 + β2(ATA)3 + β3(ATA)4+…

Relatedness

Importance

Small β Î NK is biased towards relatedness
 Special case at β=0:
NKβ(ATA) reduces to the co-citation coupling matrix
Large β Î NK is biased towards importanceCo-citation coupling
Neumann kernels
Bibliographic coupling
βsmallHITS
large

1718Experiments

Neumann kernel with large β (β=.005)

Compare Neumann kernels
with HITS

Top ranked papers with respect to the “root” paper:
Marilyn A.kernel
Walkergives
and Johanna
D. Moore.
Empiricalstudies in
Neumannthe sameranking
as HITSdiscourse. Computational Linguistics Vol. 23, No. 1, 1997.
NKDataset:
Citation graph consisting of 2687 papers on naturallanguage processing

19HITSTitle

1

1 Building a large annotated corpus of English: the Penn Treebank

2

2 A stochastic parts program and noun phrase parser for unrestricted text3

3 Statistical decision-tree models for parsing

4

4 A new statistical parser based on bigram lexical dependencies

5

5 Unsupervised word sense disambiguation rivaling supervised methods

6

6 Word-sense disambiguation using statistical models of Roget's

7

7 The mathematics of statistical machine translation: parameter estimation

20

Comparison between Neumann kernels
and ＨＩＴS (quantitative evaluation)

Neumann kernel with small β (β=.001)
Top ranked papers with respect to the paper:

The titles of papers show that most of the high-ranked papers
Marilyn A. Walker and Johanna D. Moore. Empirical studies inarerelated
to the root Linguistics
paper Vol. 23, No. 1, 1997.
discourse.
ComputationalNKHITS
1Title1 Building a large annotated corpus of English: the Penn Treebank

2771 Empirical studies in discourse

350 Attention, intentions, and the structure of discourse

476 Assessing agreement on classification tasks: the Kappa statistic

5201 The reliability of a dialogue structure coding scheme

6604 Message Understanding Conference (MUC) Tests of Discourse Processing

71061

The difference between Neumann kernels and HITS authority
ranking Making each of paper one by one as the root node
 Using K-min distance [Fagin et al., 2003]：
z If two ton-n lists have similar rankings ⇒ smallz If two top-n lists have similar rankings ⇒ large
MAX：100 MIN： 0

Neumann kernels （λ）

Effects of variable initiative on linguistic behavior in human-computer
spoken natural language dialogue

ＨＩＴＳ

λ=0.0001

0.001

0.003

0.004

0.004 0.004
580.005

89.9

89.9

88.7

86.2

81.7

20.4

73.3

21Conclusions


22References

Neumann kernels on citation graphs provide a newlink analysis measure that is feasible forrecommendation services.

23

M. M. Kessler. Bibliographic coupling between scientfic
papers. American Documentation 14:10-25, 1963

J. Kandola, J. Shawe-Taylor, and N. Cristianini. Learning
semantic similarity. In Proc. NIPS 15, 2003.

H. Small. Co-citation in the scientific literature: a new
meature of the relationship between two documents. J. Am.
Soc. Information Science, 24:265-269, 1973.

S. White and P. Smyth. Algorithms for estimating relative
importance in networks. In Proc. ACM SIGKDD, 2003.

24