We propose in this paper an efficient heuristic method to learn a set of classification rules from a set of graph objects. Graph classification has various real-life applications, however, this is a very challenging problem due to the intrinsic complex structure of graphs. The proposed rule constructing method is based on two lines of research. The first line of research is on Boosting [11] in which a weak-hypothesis is regarded as a rule and is assigned with a real-valued confidence. In our research, a rule is comprised by a set of subgraphs that maximize an objective function in each round of boosting. The second line of research is on utilizing the poset order of the Formal Concept Lattice of subgraphs to accelerate the process of generating rule candidates. The learned rule set is compact, comprehensible and obtains high classification accuracy on tested datasets.
Acosta-MendozaN.AlonsoA.G. and Medina-PagolaJ.E., Frequent approximate subgraphs as features for graph-based image classification,Knowledge-Based System27 (2012), 381–392.
2.
BorgwardtK.M. and KriegelH.P., Shortest-path kernels on graphs, In DM-05, 2005, pp. 74–81.
3.
BringmannB.ZimmermannA.RaedtL.D. and NijssenS., Don’t be afraid of simpler patterns, In 10th European Conference on Principles and Practice of Knowledge Discovery in Databases PKDD, 2006, pp. 55–66.
4.
BunkeH. and ShearerK., A graph distance metric based on the maximal common subgraph, Pattern Recognition Letters19 (1998), 255–259.
5.
CohenW.W. and SingerY., A simple, fast, and effective rule learner, In Proceedings of the Sixteenth National Conference on Artificial Intelligence, 1999, pp 335–342.
6.
DaveyB. and PriestleyH., Introduction to lattices and order, Cambridge University Press, 2 edition, 2002.
7.
DemirizA.BennettK. and Shawe-TaylorJ., Linear programming boosting via column generation, Machine Learning46(1–3) (2002), 225–254.
8.
DeshpandeM.KuramochiM. and KarypisG., Frequent sub-structure-based approaches for classifying chemical compounds, In ICDM-03, 2003, pp. 35–42.
9.
DobsonP.D. and DoigA.J., Distinguishing enzyme structures from non-enzymes without alignments, Journal of Molecular Biology330(4) (2003), 771–783.
10.
FeiH. and HuanJ., Structured sparse boosting for graph classification,ACM Trans. Knowl. Discov. Data9(1) (2014), 1–22.
11.
FreundY. and SchapireR.E., A decision-theoretic generalization of on-line learning and an application to boosting, Journal of Computer and System Sciences55(1) (1997), 119–139.
12.
GanterB. and WilleR., Formal Concept Analysis, Mathematical Foundations. Springer, 1998.
13.
GärtnerT.FlachP. and WrobelS., On graph kernels: hardness results and efficient alternatives, In COLT-03, 2003, pp. 129–2003.
14.
GartnerT.FlachP. and WrobelS., On graph kernels: Hardness results and efficient alternatives, In Learning Theory and Kernel Machines, volume 2777, 2003, pp. 129–143.
15.
GonzalezJ.A.HolderL.B. and CookD.J., Graph-based relational concept learning, In Proceedings of the Nineteenth International Conference on Machine Learning, 2002, pp. 219–226.
16.
IchigakuT. and HisorhiM., Graph mining: procedure, application to drug discovery and recent advances, Drug Discovery Today18(1–2) (2013), 50–57.
17.
JinN.YoungC. and WangW., Graph classification based on pattern co-occurrence, In Proceedings of the 18th ACM Conference on Information and Knowledge Management, CIKM ’09, 2009, pp. 573–582.
18.
KashimaH.TsudaK. and InokuchiA., Marginalized kernels between labeled graphs, In Proceedings of the Twentieth International Conference on Machine Learning, 2003, pp. 321–328.
19.
KongX.FanW. and YuP.S., Dual active feature and sample selection for graph classification, In Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’11, 2011, pp. 654–662.
20.
KongX. and YuP.S., Semi-supervised feature selection for graph classification, In Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’10, 2010, pp. 793–802.
21.
KudoT.MaedaE. and MatsumotoY., An application of boosting to graph classification, In NIPS 2004, 2004, pp. 729–736.
22.
LingC.X.HuangJ. and ZhangH., Auc: A better measure than accuracy in comparing learning algorithms, In Proceedings of the 16th Canadian Society for Computational Studies of Intelligence Conference on Advances in Artificial Intelligence, 2003, pp. 329–341.
23.
MahéP.RalaivolaL.StovenV. and VertJ.P., The pharmacophore kernel for virtual screening with support vector machines, Journal of Chemical Information and Modeling46(5) (2006), 2003–2014.
24.
MonjardetB., The presence of lattice theory in discrete problems of mathematical social sciences why, Mathematical Social are Either Active or Inactive in a Screen for Anti-Cancer ActivitySciences46(2) (2003), 103–144.
25.
MoonesingheH.D.K.ValizadeganH.FodehS.J. and TanP., A probabilistic substructure-based approach for graph classification, In 19th IEEE International Conference on Tools with Artificial Intelligence (ICTAI 2007), October 29–31, 2007, Patras, Greece, Volume 1, 2007, pp. 346–349.
26.
NguyenV.A. and YamamotoA., Learning from graph data by putting graphs on the lattice, Expert Systems with Applications39(12) (2012), 11172–11182.
27.
RalaivolaL.SwamidassS.J.SaigoH. and BaldiP., Graph kernels for chemical informatics, Neural Networks18(8) (2005), 1093–1110.
28.
RamonJ. and GärtnerT., Expressivity versus efficiency of graph kernels, In Workshop on Mining Graphs, Trees and Sequences, 2003, pp. 65–74.
29.
SaigoH.NowozinS.KadowakiT.KudoT. and TsudaK., gBoost: A mathematical programming approach to graph classification and regression, Machine Learning75(1) (2009), 69–89.
30.
TangL. and LiuH., Graph mining applications to social network analysis, In Managing and Mining Graph Data, volume 40 of Advances in Database Systems, 2010, pp. 487–513.
31.
ThomaM.ChengH.GrettonA.HanJ.KriegelH.SmolaA.SongL.YuP.YanX. and BorgwardtK., Near-optimal supervised feature selection among frequent subgraphs, In SDM-09, 2009.
32.
WaleN.WatsonI.A. and KarypisG., Comparison of descriptor spaces for chemical compound retrieval and classification, Information System14(3) (2008), 347–375.
33.
WallisW.D.ShoubridgeP.KraetzM. and RayD., Graph distances using graph union, Pattern Regcognition Letters22 (2001), 701–704.
34.
YanX.ChengH.HanJ. and YuP.S., Mining significant graph patterns by leap search, In ICMD-08, 2008, pp. 433–444.
35.
YanX. and HanJ., gSpan: graph-based substructure pattern mining, In ICDM-02, 2002, pp. 721–724.
36.
YanX. and HanJ., Closegraph: Mining closed frequent graph patterns, In KDD-03, 2003, pp. 286–295.
37.
ZhaoY.KongX. and YuP.S., Positive and unlabeled learning for graph classification, In Proceedings of the 2011 IEEE 11th International Conference on Data Mining, ICDM ’11, 2011, pp. 962–971.
