加载中…
个人资料
Yode
Yode
  • 博客等级:
  • 博客积分:0
  • 博客访问:595,259
  • 关注人气:250
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
相关博文
推荐博文
谁看过这篇博文
加载中…
正文 字体大小:

Common ways to construct graph

(2008-02-28 21:03:57)
标签:

杂谈

分类: 半监督图排序
    Sometimes we face the dataset with limited domain knowledge,some common ways of construting graph will be discussed in the following.
    Fully connected graphs :One can create a fully connected graph with an edge between all pairs of nodes. The graph needs to be weighted so that similar nodes have large edge weight between them. The advantage of a fully connected graph is in weight learning – with a differentiable(可微的) weight function,one can easily take the derivatives(导数) of the graph w.r.t. weight hyperparameters. The disadvantage is in computational cost as the graph is dense (although sometimes one can apply fast approximate algorithms like N-body problems). Furthermore we have observed that empirically fully connect graphs performs worse than sparse graphs.
Sparse graphs
 One can create kNN or NN graphs as shown below, where each node connects to only a few nodes. Such sparse graphs are computationally
fast
. They also tend to enjoy good empirical performance. We surmise(假设) it is because spurious(假的) connections between dissimilar nodes (which tend to be in different classes) are removed. With sparse graphs, the edges can be unweighted or weighted. One disadvantage is weight learning – a change in weight hyperparameters will likely change the neighborhood, making optimization awkward.
kNN graphs 
Nodes i, j are connected by an edge if i is in j's k-nearest neighborhood
or vice versa. k is a hyperparameter that controls the density of the graph.kNN has the nice property of “adaptive scales,” because the neighborhood radius is different in low and high data density regions. Small k may result in disconnected graphs. For Label Propagation this is not a problem if each connected component has some labeled points. For other algorithms introduced later in the thesis, one can smooth the Laplacian.
NN graphs
Nodes i, j are connected by an edge, if the distance d(i, j)< . The
hyperparameter controls neighborhood radius. Although is continuous,
the search for the optimal value is discrete, with at most O(n2) values (the edge lengths in the graph).
tanh-weighted graphs
wij = (tanh( a1(d(i, j)

0

阅读 评论 收藏 转载 喜欢 打印举报/Report
  • 评论加载中,请稍候...
发评论

    发评论

    以上网友发言只代表其个人观点,不代表新浪网的观点或立场。

      

    新浪BLOG意见反馈留言板 电话:4000520066 提示音后按1键(按当地市话标准计费) 欢迎批评指正

    新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

    新浪公司 版权所有