File Download
There are no files associated with this item.
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1145/3132847.3132885
- Scopus: eid_2-s2.0-85037373183
- WOS: WOS:000440845300016
Supplementary
- Citations:
- Appears in Collections:
Conference Paper: On Embedding Uncertain Graphs
Title | On Embedding Uncertain Graphs |
---|---|
Authors | |
Issue Date | 2017 |
Publisher | ACM. |
Citation | The 2017 ACM on Conference on Information and Knowledge Management, Singapore, 6-10 November 2017. In Proceedings of the 2017 ACM on Conference on Information and Knowledge Management, 2017, p. 157-166 How to Cite? |
Abstract | Graph data are prevalent in communication networks, social media, and biological networks. These data, which are often noisy or inexact, can be represented by uncertain graphs, whose edges are associated with probabilities to indicate the chances that they exist. Recently, researchers have studied various algorithms (e.g., clustering, classification, and k-NN) for uncertain graphs. These solutions face two problems: (1) high dimensionality: uncertain graphs are often highly complex, which can affect the mining quality; and (2) low reusability, where an existing mining algorithm has to be redesigned to deal with uncertain graphs. To tackle these problems, we propose a solution called URGE, or UnceRtain Graph Embedding. Given an uncertain graph G, URGE generates G's embedding, or a set of low-dimensional vectors, which carry the proximity information of nodes in G. This embedding enables the dimensionality of G to be reduced, without destroying node proximity information. Due to its simplicity, existing mining solutions can be used on the embedding. We investigate two low- and high-order node proximity measures in the embedding generation process, and develop novel algorithms to enable fast evaluation.
To our best knowledge, there is no prior study on the use of embedding for uncertain graphs. We have further performed extensive experiments for clustering, classification, and k-NN on several uncertain graph datasets. Our results show that URGE attains better effectiveness than current uncertain data mining algorithms, as well as state-of-the-art embedding solutions. The embedding and mining performance is also highly efficient in our experiments. |
Persistent Identifier | http://hdl.handle.net/10722/243248 |
ISBN | |
ISI Accession Number ID |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Hu, J | - |
dc.contributor.author | Cheng, CK | - |
dc.contributor.author | Huang, Z | - |
dc.contributor.author | Fang, Y | - |
dc.contributor.author | Luo, S | - |
dc.date.accessioned | 2017-08-25T02:52:12Z | - |
dc.date.available | 2017-08-25T02:52:12Z | - |
dc.date.issued | 2017 | - |
dc.identifier.citation | The 2017 ACM on Conference on Information and Knowledge Management, Singapore, 6-10 November 2017. In Proceedings of the 2017 ACM on Conference on Information and Knowledge Management, 2017, p. 157-166 | - |
dc.identifier.isbn | 978-1-4503-4918-5 | - |
dc.identifier.uri | http://hdl.handle.net/10722/243248 | - |
dc.description.abstract | Graph data are prevalent in communication networks, social media, and biological networks. These data, which are often noisy or inexact, can be represented by uncertain graphs, whose edges are associated with probabilities to indicate the chances that they exist. Recently, researchers have studied various algorithms (e.g., clustering, classification, and k-NN) for uncertain graphs. These solutions face two problems: (1) high dimensionality: uncertain graphs are often highly complex, which can affect the mining quality; and (2) low reusability, where an existing mining algorithm has to be redesigned to deal with uncertain graphs. To tackle these problems, we propose a solution called URGE, or UnceRtain Graph Embedding. Given an uncertain graph G, URGE generates G's embedding, or a set of low-dimensional vectors, which carry the proximity information of nodes in G. This embedding enables the dimensionality of G to be reduced, without destroying node proximity information. Due to its simplicity, existing mining solutions can be used on the embedding. We investigate two low- and high-order node proximity measures in the embedding generation process, and develop novel algorithms to enable fast evaluation. To our best knowledge, there is no prior study on the use of embedding for uncertain graphs. We have further performed extensive experiments for clustering, classification, and k-NN on several uncertain graph datasets. Our results show that URGE attains better effectiveness than current uncertain data mining algorithms, as well as state-of-the-art embedding solutions. The embedding and mining performance is also highly efficient in our experiments. | - |
dc.language | eng | - |
dc.publisher | ACM. | - |
dc.relation.ispartof | Proceedings of the 2017 ACM on Conference on Information and Knowledge Management | - |
dc.title | On Embedding Uncertain Graphs | - |
dc.type | Conference_Paper | - |
dc.identifier.email | Cheng, CK: ckcheng@cs.hku.hk | - |
dc.identifier.authority | Cheng, CK=rp00074 | - |
dc.description.nature | link_to_subscribed_fulltext | - |
dc.identifier.doi | 10.1145/3132847.3132885 | - |
dc.identifier.scopus | eid_2-s2.0-85037373183 | - |
dc.identifier.hkuros | 275521 | - |
dc.identifier.spage | 157 | - |
dc.identifier.epage | 166 | - |
dc.identifier.isi | WOS:000440845300016 | - |
dc.publisher.place | New York, NY | - |