Boosting for multi-graph classification. Wu, J., Pan, S., Zhu, X., & Cai, Z. IEEE Transactions on Cybernetics (TCYB), 45(3):430-43, Institute of Electrical and Electronics Engineers Inc., 3, 2015. doi abstract bibtex In this paper, we formulate a novel graph-based learning problem, multi-graph classification (MGC), which aims to learn a classifier from a set of labeled bags each containing a number of graphs inside the bag. A bag is labeled positive, if at least one graph in the bag is positive, and negative otherwise. Such a multi-graph representation can be used for many real-world applications, such as webpage classification, where a webpage can be regarded as a bag with texts and images inside the webpage being represented as graphs. This problem is a generalization of multi-instance learning (MIL) but with vital differences, mainly because instances in MIL share a common feature space whereas no feature is available to represent graphs in a multi-graph bag. To solve the problem, we propose a boosting based multi-graph classification framework (bMGC). Given a set of labeled multi-graph bags, bMGC employs dynamic weight adjustment at both bag- and graph-levels to select one subgraph in each iteration as a weak classifier. In each iteration, bag and graph weights are adjusted such that an incorrectly classified bag will receive a higher weight because its predicted bag label conflicts to the genuine label, whereas an incorrectly classified graph will receive a lower weight value if the graph is in a positive bag (or a higher weight if the graph is in a negative bag). Accordingly, bMGC is able to differentiate graphs in positive and negative bags to derive effective classifiers to form a boosting model for MGC. Experiments and comparisons on real-world multi-graph learning tasks demonstrate the algorithm performance.
@article{
title = {Boosting for multi-graph classification},
type = {article},
year = {2015},
keywords = {Boosting,graph classification,multi-graph,multi-instance learning,subgraph mining},
pages = {430-43},
volume = {45},
month = {3},
publisher = {Institute of Electrical and Electronics Engineers Inc.},
id = {ef9cdda8-1807-3ee4-840c-5596cfdac04c},
created = {2016-04-29T05:47:47.000Z},
accessed = {2016-04-29},
file_attached = {false},
profile_id = {079852a8-52df-3ac8-a41c-8bebd97d6b2b},
last_modified = {2022-04-10T12:11:19.238Z},
read = {false},
starred = {false},
authored = {true},
confirmed = {true},
hidden = {false},
citation_key = {Wu2015a},
folder_uuids = {2327f56c-ffc0-4246-bac0-b9fa6098ebfb,a5961aba-0e48-4cf8-9566-d73aaba73d2c},
private_publication = {false},
abstract = {In this paper, we formulate a novel graph-based learning problem, multi-graph classification (MGC), which aims to learn a classifier from a set of labeled bags each containing a number of graphs inside the bag. A bag is labeled positive, if at least one graph in the bag is positive, and negative otherwise. Such a multi-graph representation can be used for many real-world applications, such as webpage classification, where a webpage can be regarded as a bag with texts and images inside the webpage being represented as graphs. This problem is a generalization of multi-instance learning (MIL) but with vital differences, mainly because instances in MIL share a common feature space whereas no feature is available to represent graphs in a multi-graph bag. To solve the problem, we propose a boosting based multi-graph classification framework (bMGC). Given a set of labeled multi-graph bags, bMGC employs dynamic weight adjustment at both bag- and graph-levels to select one subgraph in each iteration as a weak classifier. In each iteration, bag and graph weights are adjusted such that an incorrectly classified bag will receive a higher weight because its predicted bag label conflicts to the genuine label, whereas an incorrectly classified graph will receive a lower weight value if the graph is in a positive bag (or a higher weight if the graph is in a negative bag). Accordingly, bMGC is able to differentiate graphs in positive and negative bags to derive effective classifiers to form a boosting model for MGC. Experiments and comparisons on real-world multi-graph learning tasks demonstrate the algorithm performance.},
bibtype = {article},
author = {Wu, Jia and Pan, Shirui and Zhu, Xingquan and Cai, Zhihua},
doi = {10.1109/TCYB.2014.2327111},
journal = {IEEE Transactions on Cybernetics (TCYB)},
number = {3}
}
Downloads: 0
{"_id":"ZsYaQaaEZGPhYE9SZ","bibbaseid":"wu-pan-zhu-cai-boostingformultigraphclassification-2015","downloads":0,"creationDate":"2015-10-13T03:08:49.797Z","title":"Boosting for multi-graph classification","author_short":["Wu, J.","Pan, S.","Zhu, X.","Cai, Z."],"year":2015,"bibtype":"article","biburl":"https://bibbase.org/service/mendeley/079852a8-52df-3ac8-a41c-8bebd97d6b2b","bibdata":{"title":"Boosting for multi-graph classification","type":"article","year":"2015","keywords":"Boosting,graph classification,multi-graph,multi-instance learning,subgraph mining","pages":"430-43","volume":"45","month":"3","publisher":"Institute of Electrical and Electronics Engineers Inc.","id":"ef9cdda8-1807-3ee4-840c-5596cfdac04c","created":"2016-04-29T05:47:47.000Z","accessed":"2016-04-29","file_attached":false,"profile_id":"079852a8-52df-3ac8-a41c-8bebd97d6b2b","last_modified":"2022-04-10T12:11:19.238Z","read":false,"starred":false,"authored":"true","confirmed":"true","hidden":false,"citation_key":"Wu2015a","folder_uuids":"2327f56c-ffc0-4246-bac0-b9fa6098ebfb,a5961aba-0e48-4cf8-9566-d73aaba73d2c","private_publication":false,"abstract":"In this paper, we formulate a novel graph-based learning problem, multi-graph classification (MGC), which aims to learn a classifier from a set of labeled bags each containing a number of graphs inside the bag. A bag is labeled positive, if at least one graph in the bag is positive, and negative otherwise. Such a multi-graph representation can be used for many real-world applications, such as webpage classification, where a webpage can be regarded as a bag with texts and images inside the webpage being represented as graphs. This problem is a generalization of multi-instance learning (MIL) but with vital differences, mainly because instances in MIL share a common feature space whereas no feature is available to represent graphs in a multi-graph bag. To solve the problem, we propose a boosting based multi-graph classification framework (bMGC). Given a set of labeled multi-graph bags, bMGC employs dynamic weight adjustment at both bag- and graph-levels to select one subgraph in each iteration as a weak classifier. In each iteration, bag and graph weights are adjusted such that an incorrectly classified bag will receive a higher weight because its predicted bag label conflicts to the genuine label, whereas an incorrectly classified graph will receive a lower weight value if the graph is in a positive bag (or a higher weight if the graph is in a negative bag). Accordingly, bMGC is able to differentiate graphs in positive and negative bags to derive effective classifiers to form a boosting model for MGC. Experiments and comparisons on real-world multi-graph learning tasks demonstrate the algorithm performance.","bibtype":"article","author":"Wu, Jia and Pan, Shirui and Zhu, Xingquan and Cai, Zhihua","doi":"10.1109/TCYB.2014.2327111","journal":"IEEE Transactions on Cybernetics (TCYB)","number":"3","bibtex":"@article{\n title = {Boosting for multi-graph classification},\n type = {article},\n year = {2015},\n keywords = {Boosting,graph classification,multi-graph,multi-instance learning,subgraph mining},\n pages = {430-43},\n volume = {45},\n month = {3},\n publisher = {Institute of Electrical and Electronics Engineers Inc.},\n id = {ef9cdda8-1807-3ee4-840c-5596cfdac04c},\n created = {2016-04-29T05:47:47.000Z},\n accessed = {2016-04-29},\n file_attached = {false},\n profile_id = {079852a8-52df-3ac8-a41c-8bebd97d6b2b},\n last_modified = {2022-04-10T12:11:19.238Z},\n read = {false},\n starred = {false},\n authored = {true},\n confirmed = {true},\n hidden = {false},\n citation_key = {Wu2015a},\n folder_uuids = {2327f56c-ffc0-4246-bac0-b9fa6098ebfb,a5961aba-0e48-4cf8-9566-d73aaba73d2c},\n private_publication = {false},\n abstract = {In this paper, we formulate a novel graph-based learning problem, multi-graph classification (MGC), which aims to learn a classifier from a set of labeled bags each containing a number of graphs inside the bag. A bag is labeled positive, if at least one graph in the bag is positive, and negative otherwise. Such a multi-graph representation can be used for many real-world applications, such as webpage classification, where a webpage can be regarded as a bag with texts and images inside the webpage being represented as graphs. This problem is a generalization of multi-instance learning (MIL) but with vital differences, mainly because instances in MIL share a common feature space whereas no feature is available to represent graphs in a multi-graph bag. To solve the problem, we propose a boosting based multi-graph classification framework (bMGC). Given a set of labeled multi-graph bags, bMGC employs dynamic weight adjustment at both bag- and graph-levels to select one subgraph in each iteration as a weak classifier. In each iteration, bag and graph weights are adjusted such that an incorrectly classified bag will receive a higher weight because its predicted bag label conflicts to the genuine label, whereas an incorrectly classified graph will receive a lower weight value if the graph is in a positive bag (or a higher weight if the graph is in a negative bag). Accordingly, bMGC is able to differentiate graphs in positive and negative bags to derive effective classifiers to form a boosting model for MGC. Experiments and comparisons on real-world multi-graph learning tasks demonstrate the algorithm performance.},\n bibtype = {article},\n author = {Wu, Jia and Pan, Shirui and Zhu, Xingquan and Cai, Zhihua},\n doi = {10.1109/TCYB.2014.2327111},\n journal = {IEEE Transactions on Cybernetics (TCYB)},\n number = {3}\n}","author_short":["Wu, J.","Pan, S.","Zhu, X.","Cai, Z."],"biburl":"https://bibbase.org/service/mendeley/079852a8-52df-3ac8-a41c-8bebd97d6b2b","bibbaseid":"wu-pan-zhu-cai-boostingformultigraphclassification-2015","role":"author","urls":{},"keyword":["Boosting","graph classification","multi-graph","multi-instance learning","subgraph mining"],"metadata":{"authorlinks":{"pan, s":"https://bibbase.org/service/mendeley/079852a8-52df-3ac8-a41c-8bebd97d6b2b"}},"downloads":0},"search_terms":["boosting","multi","graph","classification","wu","pan","zhu","cai"],"keywords":["boosting","graph classification","multi-graph","multi-instance learning","subgraph mining"],"authorIDs":["561c75c18d7cb332200004ce","561c77518d7cb332200004db","5de872e7e66c23df0100005d","5e0176b9219bd5df010000c1","5e114756495520de010000a9","5e12c60370e2c4f201000052","5e199a3b204503de0100007f","5e36614a4b25bbf2010000a4","k6fB9cczWrDbvaPzR"],"dataSources":["mKA5vx6kcS6ikoYhW","ya2CyA73rpZseyrZ8","AoeZNpAr9D2ciGMwa","fcdT59YHNhp9Euu5k","m7B7iLMuqoXuENyof","Byqq56wkTmdCSSibG","2252seNhipfTmjEBQ","HmWAviNezgcH2jK9X"]}