An algorithm for directed graph estimation

Hideitsu Hino; Atsushi Noda; Masami Tatsuno; Shotaro Akaho; Noboru Murata

doi:10.1007/978-3-319-11179-7_19

An algorithm for directed graph estimation

Hideitsu Hino, Atsushi Noda, Masami Tatsuno, Shotaro Akaho, Noboru Murata

School of Advanced Science and Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

A problem of estimating the intrinsic graph structure from observed data is considered. The observed data in this study is a matrix with elements representing dependency between nodes in the graph. Each element of the observed matrix represents, for example, co-occurrence of events at two nodes, or correlation of variables corresponding to two nodes. The dependency does not represent direct connections and includes influences of various paths, and spurious correlations make the estimation of direct connection difficult. To alleviate this difficulty, digraph Laplacian is used for characterizing a graph. A generative model of an observed matrix is proposed, and a parameter estimation algorithm for the model is also proposed. The proposed method is capable of dealing with directed graphs, while conventional graph structure estimation methods from an observed matrix are only applicable to undirected graphs. Experimental result shows that the proposed algorithm is able to identify the intrinsic graph structure.

Original language	English
Title of host publication	Artificial Neural Networks and Machine Learning, ICANN 2014 - 24th International Conference on Artificial Neural Networks, Proceedings
Publisher	Springer Verlag
Pages	145-152
Number of pages	8
ISBN (Print)	9783319111780
DOIs	https://doi.org/10.1007/978-3-319-11179-7_19
Publication status	Published - 2014
Event	24th International Conference on Artificial Neural Networks, ICANN 2014 - Hamburg, Germany Duration: 2014 Sept 15 → 2014 Sept 19

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	8681 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	24th International Conference on Artificial Neural Networks, ICANN 2014
Country/Territory	Germany
City	Hamburg
Period	14/9/15 → 14/9/19

Keywords

digraph Laplacian
directed graph
graph estimation

ASJC Scopus subject areas

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1007/978-3-319-11179-7_19

Cite this

Hino, H., Noda, A., Tatsuno, M., Akaho, S., & Murata, N. (2014). An algorithm for directed graph estimation. In Artificial Neural Networks and Machine Learning, ICANN 2014 - 24th International Conference on Artificial Neural Networks, Proceedings (pp. 145-152). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8681 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-319-11179-7_19

An algorithm for directed graph estimation. / Hino, Hideitsu; Noda, Atsushi; Tatsuno, Masami et al.
Artificial Neural Networks and Machine Learning, ICANN 2014 - 24th International Conference on Artificial Neural Networks, Proceedings. Springer Verlag, 2014. p. 145-152 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8681 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Hino, H, Noda, A, Tatsuno, M, Akaho, S & Murata, N 2014, An algorithm for directed graph estimation. in Artificial Neural Networks and Machine Learning, ICANN 2014 - 24th International Conference on Artificial Neural Networks, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 8681 LNCS, Springer Verlag, pp. 145-152, 24th International Conference on Artificial Neural Networks, ICANN 2014, Hamburg, Germany, 14/9/15. https://doi.org/10.1007/978-3-319-11179-7_19

Hino H, Noda A, Tatsuno M, Akaho S, Murata N. An algorithm for directed graph estimation. In Artificial Neural Networks and Machine Learning, ICANN 2014 - 24th International Conference on Artificial Neural Networks, Proceedings. Springer Verlag. 2014. p. 145-152. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-11179-7_19

Hino, Hideitsu ; Noda, Atsushi ; Tatsuno, Masami et al. / An algorithm for directed graph estimation. Artificial Neural Networks and Machine Learning, ICANN 2014 - 24th International Conference on Artificial Neural Networks, Proceedings. Springer Verlag, 2014. pp. 145-152 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{9bb09960ea6d42b7964de91a37f7f6f0,

title = "An algorithm for directed graph estimation",

abstract = "A problem of estimating the intrinsic graph structure from observed data is considered. The observed data in this study is a matrix with elements representing dependency between nodes in the graph. Each element of the observed matrix represents, for example, co-occurrence of events at two nodes, or correlation of variables corresponding to two nodes. The dependency does not represent direct connections and includes influences of various paths, and spurious correlations make the estimation of direct connection difficult. To alleviate this difficulty, digraph Laplacian is used for characterizing a graph. A generative model of an observed matrix is proposed, and a parameter estimation algorithm for the model is also proposed. The proposed method is capable of dealing with directed graphs, while conventional graph structure estimation methods from an observed matrix are only applicable to undirected graphs. Experimental result shows that the proposed algorithm is able to identify the intrinsic graph structure.",

keywords = "digraph Laplacian, directed graph, graph estimation",

author = "Hideitsu Hino and Atsushi Noda and Masami Tatsuno and Shotaro Akaho and Noboru Murata",

year = "2014",

doi = "10.1007/978-3-319-11179-7_19",

language = "English",

isbn = "9783319111780",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "145--152",

booktitle = "Artificial Neural Networks and Machine Learning, ICANN 2014 - 24th International Conference on Artificial Neural Networks, Proceedings",

note = "24th International Conference on Artificial Neural Networks, ICANN 2014 ; Conference date: 15-09-2014 Through 19-09-2014",

}

TY - GEN

T1 - An algorithm for directed graph estimation

AU - Hino, Hideitsu

AU - Noda, Atsushi

AU - Tatsuno, Masami

AU - Akaho, Shotaro

AU - Murata, Noboru

PY - 2014

Y1 - 2014

N2 - A problem of estimating the intrinsic graph structure from observed data is considered. The observed data in this study is a matrix with elements representing dependency between nodes in the graph. Each element of the observed matrix represents, for example, co-occurrence of events at two nodes, or correlation of variables corresponding to two nodes. The dependency does not represent direct connections and includes influences of various paths, and spurious correlations make the estimation of direct connection difficult. To alleviate this difficulty, digraph Laplacian is used for characterizing a graph. A generative model of an observed matrix is proposed, and a parameter estimation algorithm for the model is also proposed. The proposed method is capable of dealing with directed graphs, while conventional graph structure estimation methods from an observed matrix are only applicable to undirected graphs. Experimental result shows that the proposed algorithm is able to identify the intrinsic graph structure.

AB - A problem of estimating the intrinsic graph structure from observed data is considered. The observed data in this study is a matrix with elements representing dependency between nodes in the graph. Each element of the observed matrix represents, for example, co-occurrence of events at two nodes, or correlation of variables corresponding to two nodes. The dependency does not represent direct connections and includes influences of various paths, and spurious correlations make the estimation of direct connection difficult. To alleviate this difficulty, digraph Laplacian is used for characterizing a graph. A generative model of an observed matrix is proposed, and a parameter estimation algorithm for the model is also proposed. The proposed method is capable of dealing with directed graphs, while conventional graph structure estimation methods from an observed matrix are only applicable to undirected graphs. Experimental result shows that the proposed algorithm is able to identify the intrinsic graph structure.

KW - digraph Laplacian

KW - directed graph

KW - graph estimation

UR - http://www.scopus.com/inward/record.url?scp=84958542694&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84958542694&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-11179-7_19

DO - 10.1007/978-3-319-11179-7_19

M3 - Conference contribution

AN - SCOPUS:84958542694

SN - 9783319111780

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 145

EP - 152

BT - Artificial Neural Networks and Machine Learning, ICANN 2014 - 24th International Conference on Artificial Neural Networks, Proceedings

PB - Springer Verlag

T2 - 24th International Conference on Artificial Neural Networks, ICANN 2014

Y2 - 15 September 2014 through 19 September 2014

ER -

An algorithm for directed graph estimation

Abstract

Publication series

Other

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this