ANUChem

X10-based SDP など X10 関係者に関係するページ

計算化学に関係する X10 ベースの計算ライブラリ
http://cs.anu.edu.au/~Josh.Milthorpe/anuchem.html
ソースコードも公開されています。

上記に関係する論文は以下の IPDPSの論文。
X10 as a parallel language for scientific computation: practice and experience
http://cs.anu.edu.au/~Josh.Milthorpe/publications/Milthorpe2011_IPDPS.pdf

Near-term Target Conferences

IPDPS2012 併設ワークショップ
2012 International Workshop on High Performance Data Intensive Computing(HPDIC2012)
http://cloud.hdu.edu.cn/HPDIC2012/
締め切り：2012/01/08
Research Contents: StreamGPU (Matsuura)



IPDPS2012 併設ワークショップ
ParLearning 2012
https://researcher.ibm.com/researcher/view_project.php?id=2591
- Real-time solutions for learning algorithms on parallel platforms
Due: 2012/01/18
Notification: 2012/02/01
Research Contents:
- StreamGPU (Morita and Ueno)
- Bipartite Graph

SYSTOR 2012
http://www.research.ibm.com/haifa/conferences/systor2012/dates.shtml
Due: 2012/2/13
Notification: 2012/3/26


IEEE CLOUD 2012
- VCTLPerf + Linear Road Benchmark
- Graph500 on Amazon EC2
Submission Deadline: February 10, 2012
Full Paper Submission Due Date: February 15, 2012
Decision Notification (Electronic): March 15, 2012



HPDC 2012
http://www.hpdc.org/2012/home/important-dates/
- Graph500 (Ueno)
- StreamGPU : GPU Task Parallelism (Ueno)
Abstracts Due: 16 January 2012
Papers Due: 23 January 2012, 11:59 PM Pacific Standard Time
Author Notifications: 19 March 2012

SACSIS 2012 (Domestic Conference)
http://sacsis.hpcc.jp/2012/
- StreamGPU (Ueno)
- StreamAPU (Matsuura)
- I-GIMV (Ganse)
- Incremental Spectral Clustering (Nishii)
- SDP with X10 (Watanabe)
Due: 2012/1/20
Notification: 2012/3


PLDI X10 Workwhop
http://x10-lang.org/workshop
Paper submission deadline: February 28, 2012
Author Notification: March 28, 2012
- X10-based X10 : Watanabe
- Performance Evaluation of X10-based Graph Algorithms on TSUBAME: Hashikawa and Watanabe

EuroPar 2012
http://europar2012.cti.gr/
Deadline for abstracts: January 31, 2012
Deadline for full papers: February 7, 2012
Decision notification: May 11, 2012

Supercomputing 2012
http://sc12.supercomputing.org/
- Graph500 (Ueno) (It depends on the result of HPDC)

Winter Simulation Conference 2012
http://www.wintersim.org/futureconf.htm
- Due: 2012/4
- Notification: 2012/6
- X10-based Large simulation platform

ACM Middleware Conferece
http://2011.middleware-conference.org/
- Due: 2012/5

IEEE IISWC 2012
- Due: 2012/6

The Fourth Paradigm: Data-Intensive Scientific Discovery

昨今注目されている書籍
http://research.microsoft.com/en-us/collaboration/fourthparadigm/

Of Hammers and Nails: An Empirical Comparison of Three Paradigms for Processing Large Graphs

マイクロソフトの新たなグラフ処理の論文。

Of Hammers and Nails: An Empirical Comparison of Three Paradigms for Processing Large Graphs
http://research.microsoft.com/pubs/155533/paper.pdf

Many phenomena and artifacts such as road networks, social networks and the web can be modeled as large graphs and analyzed
using graph algorithms. However, given the size of the underlying
graphs, efficient implementation of basic operations such as connected component analysis, approximate shortest paths, and linkbased ranking (e.g.PageRank) becomes challenging.
This paper presents an empirical study of computations on such
large graphs in three well-studied platform models, viz., a relational
model, a data-parallel model, and a special-purpose in-memory
model. We choose a prototypical member of each platform model
and analyze the computational efficiencies and requirements for
five basic graph operations used in the analysis of real-world graphs
viz., PageRank, SALSA, Strongly Connected Components (SCC),
Weakly Connected Components (WCC), and Approximate Shortest Paths (ASP). Further, we characterize each platform in terms of
these computations using model-specific implementations of these
algorithms on a large web graph. Our experiments show that there
is no single platform that performs best across different classes of
operations on large graphs. While relational databases are powerful and flexible tools that support a wide variety of computations,
there are computations that benefit from using special-purpose storage systems and others that can exploit data-parallel platforms

2部グラフ関連性解析の高速化およびシステムプロファイリング

- GPGPU による高速化
- システムプロファイリング：どこにどのぐらい時間を費やしているのか？
- 下位の基盤をSystem S 非依存にし、TSUBAME で大規模実行できるようにする

アプリケーション屋の要件

アプリ屋の requirement および実際に使っている手法等を知るため、情報交換の場をセットしていきましょう。
候補としては、まず上がるのが、東大松尾先生、東大鹿島先生、東工大杉山先生、IBM TRLのデータマイニング屋でお客様案件を担当している研究者など。

MovieLens

土屋さんの指導教官：横浜国立大学の長尾先生
http://www.nlab.sogo1.ynu.ac.jp/ynu/members/nagao.html
ネット企業との共同研究

MovieLens (映画に対する Rating) というデータセットを使って協調フィルタリング＋ベイジアンネットを使って解析
http://www.grouplens.org/node/73

Random Walks on Directed and Undirected Graphs

http://www.math.ucsd.edu/~phorn/math261/

Random walk with restart に対する高速な Top-k 検索

Random walk with restart に対する高速な Top-k 検索
db-event.jpn.org/deim2011/proceedings/pdf/d3-1.pdf

An In-Depth Study of Stochastic Kronecker Graphs

ICDM に参加中の村田先生からのメッセージ。

"An In-Depth Study of Stochastic Kronecker Graphs"
C. Seshadhri, Ali Pinar, and Tamara G. Kolda,
Proceedings of the 11th IEEE International Conference on
Data Mining, pp.587-596, 2011.
http://arxiv.org/abs/1102.5046

タイトルの通り、(Graph500で用いられる)Kronecker Graphの研究です。発表を聞いただけで論文はまだ読んでいないのですが、
・次数分布はheavy tailでもpower lawでもなく、論文中の図の
ように何度もバウンドしたような曲線になる
・ノイズを入れたnoisy SKGになると次数分布が直線に近づく
・孤立点が多い。k=42で74%が孤立点
・coreのサイズは実ネットワークのそれより小さい

MLG 2010 Workshop

http://www.cs.purdue.edu/mlg2011/speakers.html

RAMGRAPH: large scale graph processing in RAMCloud

http://code.google.com/p/ramgraph/

Recently, the pay-as-you-go computing paradigm in public clouds such as Amazon EC2 offers users to execute their computational tasks on the rented virtualized computation resources. Due to the lower cost than hosting a private cloud, this paradigm has become popular for medium- and small-sized Web companies such as Alexa and SmugMug. Mining and processing the large web and social networks is one of the common regular tasks for those Web companies. For example, a search engine typically uses a graph-based ranking scheme such as PageRank to give an order to the pages. Moreover, those mining and processing tasks are highly customized with various user-defined logics applied on the entire graph. The requirement of high efficiency in large scale graph processing challenges existing tools. This is because, most of current tools such as MapReduce and Hadoop are disk-based, where the hard disk is typically 100-1000x slower than the main memory. The random access nature of graph processing further harnesses the performance of disk-based graph processing. The low efficiency of current disk-based systems limits the popularity of graph mining and business intelligence in Web companies, and can result in low utilization of existing investment and lose potential business opportunities.

To unleash the computation power of current cloud offerings, we propose Thunder, a large graph processing system in the main memories of hundreds or thousands of machines. Thunder stores and processes graphs entirely in the main memory, and uses hard disks only for backup and archrivals. The system provides APIs similar to Map and Reduce functions in MapReduce for users to implement their user-defined logics. These logics are automatically executed on the graph in a distributed manner.

The goal of designing and implementing Thunder is to exploit the advantage of in-memory processing, while remaining all the merits of conventional disk-based tools, namely excellent scalability, good fault-tolerance and ability of expressing arbitrary and complex customized logic. In particular, we are facing challenging issues like scalability, availability, complex memory management, network traffic reducing and so on.

Polonium: Tera-Scale Graph Mining and Inference for Malware Detection

http://siam.omnibooksonline.com/2011datamining/data/papers/052.pdf

We present Polonium, a novel Symantec technology
that detects malware through large-scale graph infer-
ence. Based on the scalable Belief Propagation algo-
rithm, Polonium infers every le's reputation,
agging
les with low reputation as malware. We evaluated
Polonium with a billion-node graph constructed from
the largest le submissions dataset ever published (60
terabytes). Polonium attained a high true positive rate
of 87% in detecting malware; in the eld, Polonium
lifted the detection rate of existing methods by 10 ab-
solute percentage points. We detail Polonium's design
and implementation features instrumental to its success.
Polonium has served 120 million people and helped an-
swer more than one trillion queries for le reputation.

Router: A Message Passing Model for Large-Scale Graph Mining

http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=6079403&tag=1

ABSTRACT

many parallel computational models have been employed in many papers to process the large-scale graph. In this paper, we propose a message passing model Router which could be invoked by most of current parallel computational models to process the large graph. The model is good at solving the multi-source traversal problem which often occurs in many complex graph algorithms. As the model can traverse the graph from different source at the same time, the multi-source traversal will finish in much less iteration than before. In this way, the total time of the algorithm involves multi-source traversal will be reduced in a large scale. Besides, the Router model is flexible enough to express a broad set of algorithms by implementing the Router's abstract method. Finally, the experiment shows the efficiency and scalability of the model.

Router: A Message Passing Model for Large-Scale Graph Mining

http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=6079403&tag=1

Large-Scale Graph Mining Using Backbone Refinement Classes

We present a new approach to large-scale graph mining
based on so-called backbone refinement classes. The method
efficiently mines tree-shaped subgraph descriptors under minimum frequency and significance constraints, using classes
of fragments to reduce feature set size and running times.
The classes are defined in terms of fragments sharing a common backbone. The method is able to optimize structural
inter-feature entropy as opposed to occurrences, which is
characteristic for open or closed fragment mining. In the
experiments, the proposed method reduces feature set sizes
by >90 % and >30 % compared to complete tree mining and
open tree mining, respectively. Evaluation using crossvalidation runs shows that their classification accuracy is similar to the complete set of trees but significantly better than
that of open trees. Compared to open or closed fragment
mining, a large part of the search space can be pruned due
to an improved statistical constraint (dynamic upper bound
adjustment), which is also confirmed in the experiments in
lower running times compared to ordinary (static) upper
bound pruning. Further analysis using large-scale datasets
yields insight into important properties of the proposed descriptors, such as the dataset coverage and the class size
represented by each descriptor. A final cross-validation run
confirms that the novel descriptors render large training sets
feasible which previously might have been intractable.

Tools for Large Graph Mining

http://www.cs.cmu.edu/~deepay/thesis.pdf

Graphs show up in a surprisingly diverse set of disciplines, ranging from computer networks to sociology, biology, ecology and many more. How do such “normal” graphs look like? How can we spot abnormal subgraphs within them? Which
nodes/edges are “suspicious?” How does a virus spread over a graph? Answering
these questions is vital for outlier detection (such as terrorist cells, money laundering rings), forecasting, simulations (how well will a new protocol work on a realistic
computer network?), immunization campaigns and many other applications.
We attempt to answer these questions in two parts. First, we answer questions
targeted at applications: what patterns/properties of a graph are important for solving
specific problems? Here, we investigate the propagation behavior of a computer virus
over a network, and find a simple formula for the epidemic threshold (beyond which
any viral outbreak might become an epidemic). We find an “information survival
threshold” which determines whether, in a sensor or P2P network with failing nodes
and links, a piece of information will survive or not. We also develop a scalable,
parameter-free method for finding groups of “similar” nodes in a graph, corresponding
to homogeneous regions (or CrossAssociations) in the binary adjacency matrix of the
graph. This can help navigate the structure of the graph, and find un-obvious patterns.
In the second part of our work, we investigate recurring patterns in real-world
graphs, to gain a deeper understanding of their structure. This leads to the development
of the R-MAT model of graph generation for creating synthetic but “realistic” graphs,
which match many of the patterns found in real-world graphs, including power-law
and lognormal degree distributions, small diameter and “community” effects.

Workshop on Graph Mining

MLG 2011 : Ninth Workshop on Mining and Learning with Graphs
http://www.cs.purdue.edu/mlg2011/speakers.html


http://www.ourglocal.com/event/?eventid=10468%2C1
http://www.cs.umd.edu/mlg2010/
MLG2009

Temporal analysis of semantic graphs using ASALSAN ∗

http://csmr.ca.sandia.gov/~tgkolda/pubs/bibtgkfiles/ICDM07.pdf

ASALSAN is a new algorithm for computing three-way
DEDICOM, which is a linear algebra model for analyzing
intrinsically asymmetric relationships, such as trade among
nations or the exchange of emails among individuals, that
incorporates a third mode of the data, such as time. ASALSAN is unique because it enables computing the three-way
DEDICOM model on large, sparse data. A nonnegative version of ASALSAN is described as well. When we apply these
techniques to adjacency arrays arising from directed graphs
with edges labeled by time, we obtain a smaller graph on latent semantic dimensions and gain additional information
about their changing relationships over time. We demonstrate these techniques on international trade data and the
Enron email corpus to uncover latent components and their
transient behavior. The mixture of roles assigned to individuals by ASALSAN showed strong correspondence with
known job classifications and revealed the patterns of communication between these roles. Changes in the communication pattern over time, e.g., between top executives and
the legal department, were also apparent in the solutions.

Matching Structure and Semantics: A Survey on Graph-Based Pattern Matching

http://briangallagher.net/pubs/gallagher-aaaifall-2006.pdf

Find Me If You Can: Improving Geographical Prediction with Social and Spatial Proximity

http://cameronmarlow.com/media/backstrom-geographical-prediction_0.pdf

Geography and social relationships are inextricably inter-
twined; the people we interact with on a daily basis almost
always live near us. As people spend more time online,
data regarding these two dimensions { geography and so-
cial relationships { are becoming increasingly precise, allow-
ing us to build reliable models to describe their interaction.
These models have important implications in the design of
location-based services, security intrusion detection, and so-
cial media supporting local communities.
Using user-supplied address data and the network of asso-
ciations between members of the Facebook social network,
we can directly observe and measure the relationship be-
tween geography and friendship. Using these measurements,
we introduce an algorithm that predicts the location of an
individual from a sparse set of located users with perfor-
mance that exceeds IP-based geolocation. This algorithm
is e cient and scalable, and could be run on hundreds of
millions of users.

SIAM AN10 Minisymposium on Analyzing Massive Real-World Graphs

http://www.graphanalysis.org/workshop2010.html

10:30-10:55 People You May Know
Lars Backstrom, Facebook
Facebook's friend recommendation system helps people connect with their friends. Our system, called People You May Know, uses a combination of results from sociology and machine learning to make the best suggestions possible. We will look at some of the challenges involved in building a system that can handle the scale of Facebook and provide high quality recommendations. In this talk I will discuss both the algorithmic and machine learning challenges that we have faced and overcome in building this system.


11:00-11:25 Modularity and Graph Algorithms
Joe McCloskey, National Security Agency; David A. Bader, Georgia Institute of Technology
A number of graph partitioning algorithms are based on the concept of modularity. In particular Clauset, Newman and Moore (CNM) have developed a greedy agglomerative graph partitioning algorithm that scales well but is known to have several flaws. Fortunato and Barthelemy have performed a rigorous analysis of the CNM algorithm that elucidates it problems. More recently Berry, Hendrickson, Laviolette, and Phillips have derived a weighted variant of CNM that performs much better in practice. This talk will focus on a different version of the parent CNM algorithm based on a statistical re-interpretation of CNM that also addresses some of the issues with the original algorithm.
11:30-11:55 Exploiting Sparsity in the Statistical Analysis of Gene Expression Data
Padma Raghavan, Anirban Chatterjee, and Francesca Chiaromonte, Pennsylvania State University

12:00-12:25 Scalable Methods for Representing, Characterizing, and Generating Large Graphs
Ali Pinar, Sandia National Laboratories

Monday, July 12
4:00 PM - 6:00 PM
Room: Spirit of Pittsburgh B - Level 3

4:00-4:25 Hybrid Parallel Programming for Massive Graph Analysis
Kamesh Madduri, Lawrence Berkeley National Laboratory

4:30-4:55 Tools and Primitives for High-performance Graph Computation
John Gilbert, University of California, Santa Barbara

5:00-5:25 Practical Heuristics for Inexact Subgraph Isomorphism
Jon Berry, Sandia National Laboratories

5:30-5:55 Spectral Methods for Subgraph Detection
Nadya Bliss and Benjamin A. Miller, Massachusetts Institute of Technology; Patrick J. Wolfe, Harvard University
We describe a statistical test for subgraph detection and localization using spectral properties of the so-called modularity matrix, a type of residual under the Chung-Lu random graph model. We show that the resultant algorithmic procedure can be applied to very large graphs ($< 10^6$ vertices), with complexity dominated by that of standard sparse eigensolver methods, and can successfully isolate anomalous vertices in real data examples.
Workshop Organizer:

Graph-based technologies for intelligence analysis

Cyber Security

http://dl.acm.org/citation.cfm?id=971643
http://ngc.sandia.gov/assets/documents/IAProblemsNetworkFormulations_JICRD2010.pdf

A graph-theoretic analysis of the human protein-interaction network using multicore parallel algorithms

http://dl.acm.org/citation.cfm?id=1456988&CFID=73076166&CFTOKEN=19740521


Due to fundamental physical limitations and power constraints, we are witnessing a paradigm shift in commodity microprocessor architecture to multicore designs. Continued performance now requires the exploitation of concurrency at the algorithm level. In this article, we demonstrate the application of high performance computing techniques in systems biology and present multicore algorithms for the important research problem of protein-interaction network (PIN) analysis. PINs play an important role in understanding the functional and organizational principles of biological processes. Promising computational techniques for key systems biology research problems such as identification of signaling pathways, novel protein function prediction, and the study of disease mechanisms, are based on topological characteristics of the protein interactome. Several complex network models have been proposed to explain the evolution of protein networks, and these models primarily try to reproduce the topological features observed in yeast, the model eukaryote interactome. In this article, we study the structural properties of a high-confidence human interaction network, constructed by assimilating recent experimentally derived interaction data. We identify topological properties common to the yeast and human protein networks. Betweenness is a quantitative measure of centrality of an entity in a complex network, and is based on computing all-pairs shortest paths in the graph. A novel contribution of our work is the analysis of the degree-betweenness centrality correlation in the human PIN. Jeong et al. empirically showed that betweenness is positively correlated with the essentiality and evolutionary age of a protein. We observe that proteins with high betweenness, but low degree (or connectivity) are abundant in the human PIN. We have designed efficient and portable parallel implementations for the exact calculation of betweenness and other compute-intensive centrality metrics relevant to interactome analysis. For example, on the Sun Fire T2000 server with the UltraSparc T1 (Niagara) processor, we achieve a relative speedup of about 16 using 32 threads for a typical instance of betweenness centrality on a PIN, reducing the running time from nearly 312min to 13s.

Andy's work on dataflow language

http://datasys.cs.iit.edu/events/MTAGS09/a05-yoo-slides.pdf

Survey (2)

Closeness Centralityの高いノードを発見する高速アルゴリズム
http://www.ieice.org/ken/paper/20111021b0j3/

グラフマイニングとその統計的モデリングへの応用

グラフマイニングとその統計的モデリングへの応用

http://www.ism.ac.jp/editsec/toukei/pdf/54-2-315.pdf

逆探索法によるグラフ系列マイニングの高速化
http://db-event.jpn.org/deim2011/proceedings/pdf/b10-2.pdf


グラフ系列マイニング
http://latent-dynamics.net/02/13_Inokuchi.ppt.pdf

頂点により誘導される頻出グラフ系列パターンのマイニング
http://www-erato.ist.hokudai.ac.jp/html/php/seminar5_docs/inokuchi.pdf

多頻度グラフマイニングを利用した動画の解析
http://www.ieice.org/ken/paper/20081218kahU/
多頻度グラフマイニングとは，大量のグラフ構造から，頻出するグラフパターンを意味のあるものとして抽出する手法である．本研究では，多頻度グラフマイニングを動画像の解析に用いる．本稿では，監視カメラの前を移動物体が通過するような動画を対象に多頻度グラフマイニングを用いてグラフベースの背景除去手法を提案する．具体的には，各ビデオフレームを領域分割し，各領域を節点，各領域間の隣接関係を辺としてグラフ構造を作る．この時，背景部分が頻出パターンとなることを利用して背景除去を行
う．

非整列RNA配列群からの頻出パターンのマイニング
http://www.mizuho-ir.co.jp/publication/giho/pdf/001_10.pdf

ページ閲覧時間を考慮した Web ログマイニング手法の提案
http://www.aiet.ecei.tohoku.ac.jp/~mihara/reference/refICS148.pdf
近年，Web サイトの複雑化・大規模化に伴い，Web サイト管理者がユーザのニーズ
に合わせて Web サイトを適宜改善していく必要が高まっている．このユーザのニーズを
知る手がかりの一つとして有用なのが Web アクセスログである．Web アクセスログを解
析することで，ユーザの Web サイト内での行動の様子を知ることができる．本稿では，
Web アクセスログ解析にデータマイニングを応用する Web ログマイニングに関連して，
ユーザが各ページを閲覧した時間を考慮したアクセスパターンを抽出する手法を提案す
る．

グラフ分析を利用した文書集合からの話題構造マイニング
http://sc.chat-shuffle.net/paper/uid:110007380661

グラフマイニングを応用した系列データ解析
http://www.ai-gakkai.or.jp/jsai/conf/2008/program/pdf/100318.pdf

メタデータ付き推薦のためのグラフマイニング
https://kaigi.org/jsai/webprogram/2011/pdf/231.pdf


時系列データを用いたWebグラフマイニング
http://db-event.jpn.org/deim2009/proceedings/files/B9-2.pdf

背景の分割に対応したグラフマイニングベースの動画像からの背景除去
Graph Mining based Background Removal from Videos Solving Background Separation

グラフマイニングアルゴリズムを用いたギャップを含むコードクローン情報の生成
http://iss.ndl.go.jp/books/R000000004-I10809124-00
http://ci.nii.ac.jp/naid/110008584014


グラフマイニングを用いたブロードバンドサービスエリア分類手法の一考察
https://kaigi.org/jsai/webprogram/2010/paper-422.html

多段ＧＢＩツールを利用した化学物質の部分構造情報の有効利用
http://www.sccj.net/event/nenkai/2005au/program/abstract-pdf/2O-02.pdf

線形グラフのマイニングアルゴリズム
http://www-erato.ist.hokudai.ac.jp/html/php/symposium3_docs/tabei-preview-20101129.pdf

多頻度グラフマイニングの一般化

阪大・猪口先生 (元TRL) のご研究
http://www.ar.sanken.osaka-u.ac.jp/papers/2006-12/jsai_v19_n5.pdf

大規模社会ネットワーク分析の事例と展望

http://crev.jp/zinbun/zinbun_v094.pdf