Multi-Graph-View Learning for Complicated Object Classification

1 Introduction

Many real-world objects, such as chemical compounds in biopharmacy [Kong and Yu, 2010], images in webpages [Harchaoui and Bach, 2007], brain regions in brain network [Kong and Yu, 2014] and users in social network [Aggarwal and Subbian, 2014], contain rich features and structure information. In many cases, these objects are represented by using simple features in vector space. Such a simple feature-vector representation inherently loses the structure information of the object, such as chemical bounds regulating the attraction of atoms for chemical compounds and spatial correlations of regions inside an image [Morales-Gonzalez et al., 2014]. A structured representation, i.e., graph, can be used to preserve structure information of the objects.

When using graphs to represent objects for learning, most existing methods construct graphs from a single feature view. For example, for content-based image retrieval, each image can be represented as a single graph-view graph by using colour histogram as a feature, with each node denoting a small region and adjacent regions being connected using an edge [Morales-Gonzalez et al., 2014]. However, using graphs from a single view is inadequate to fully describe the content.

For example, colour and texture are different visual channels, and are both commonly used to represent images. Therefore, using graphs constructed from multiple feature views can potentially preserve accurate information to describe the structure and the content of the object. In this paper, we refer to graphs constructed from different feature views as multigraph-view graphs.

In reality, objects may have complicated characteristics, depending on how the objects are assessed and characterized. For example, in content-based image retrieval, an image may be labeled as "tiger" because it contains a tiger inside the image. However, not all regions of the image are relevant to the tighter and background regions may not be directly related to the label of the object. This representation and learning complication is known as "multi-instance" learning [Zhou, 2004], where most existing researches focus on feature-vector represented instances. In order to preserve the structure information of the object, an alternative way is to represent the object (e.g. an image) as a bag of graphs with each graph representing the object's local characteristics. If any region of the image contains an object-of-interest (e.g. a tiger), the bag will be labeled as positive. If no region inside the image contains any object-of-interest, the bag is labeled as negative.

The above observations raise a new graph-bag based multigraph-view learning, where the object is represented as a graph-bag, consisting of graphs collected from multiple graph-views. In order to build effective learning model, the technical challenge is twofold: (1) multiple graph-view representation: how to find effective subgraph features from different graph-views; (2) graph-bag based learning: how to integrate bag constraints, where labels are only available for a bag of graphs, for learning.

Intuitively, when objects are represented as bag of multigraph-view graphs, a straightforward learning solution is to propagate a bag's label to all graphs inside the bag. In this case, the problem is degraded as a "multi-graph-view graph learning" [Wu et al., 2014a]. Unfortunately, because not all graphs in a positive bag are positive, simple bag label propagation may cause some negative graphs being mislabeled and deteriorate the learning accuracy. Alternatively, one can first explore some frequent subgraphs to represent graphs into vector space, and transfer the problem to "multi-view multiinstance learning" [Mayo and Frank, 2011]. However, this is still suboptimal because simple frequent subgraph features do not have sufficient discriminative ability for learning.

In this paper, we propose a multi-graph-view bag learning (MGVBL) algorithm for accurate graph-bag classification. More specially, MGVBL progressively selects the most discriminative subgraph across different graph-views. It not only achieves maximum margins between labeled graph bags (positive vs. negative), but also has minimum loss on the graphs in negative bags. The key contribution of the paper is threefold:

1. We propose a new object representation model which preserves the structure and the complicated characteristics of the object for learning.
2. MGVBL integrates multiple graph-view subgraph exploration and learning into a unified framework. This is inherently different from many graph learning methods, which treat subgraph exploration and subsequent model learning in two separated processes [Wu et al., 2014c].
3. An upper bound discriminative score for each subgraph is derived to effectively prune subgraph search space.

2 ProblemDefinition and Overall Framework

Definition 1. (Connected Graph) A graph is represented as G = (V, E, L, l) where V = {v1, · · · , vnv } denotes vertices, with E ⊆ V × V as edges, and L represents symbols for the vertices and edges. l : V ∪ E → L is the function assigning labels to the vertices and edges. A connected graph must has a path between any pair of vertices.

Definition 2. (Subgraph) Let G = (V,E,L, l) and gi = (V ′ ,E′ ,L′ , l′ ) each denotes a connected graph. gi is a subgraph of G, i.e., gi ⊆ G, iff there exists an injective function ϕ : V ′ → V s.t. (1)∀v ∈ V ′ , l′ (v) = l(ϕ(v)); (2) ∀(u, v) ∈ E′ , (ϕ(u), ϕ(v)) ∈ E and l′ (u, v) = l(ϕ(u), ϕ(v)). If gi is a subgraph of G, then G is a supergraph of gi. In this paper, subgraphs and subgraph features are equivalent terms.

Definition 3. (Graph-View) A graph-view denotes a type of tuple (V, E, L, l) used to represent an object as a graph. Similarly, multi-graph-view represents multiple types of tuples used to represent the same object.

Definition 4. (Multi-Graph-View Graph-Bag) A multigraph-view graph-bag Bi = {B1 i , · · · ,Bk i , · · · ,Bv i } consists of some graph-bags, where Bk i denotes a single-view graph-bag from the kth view, and each Bk i contains a number of graphs Gkj constructed from the kth view. The class label of the graph bag Bi is denoted by Yi ∈ Y, with Y = {-1, +1}.

The set of all graph-bags is denoted by B. We can also aggregate all graphs in the negative bags as G-. In this paper, we use Gj to denote a multi-graph-view graph, and use superscript k to denote the kth view.

Given B = {B1 , · · · , Bk , · · · Bv } (i.e., a multi-graph-view bag set) containing labeled graph-bags from v views, the aim of multi-graph-view learning for graph-bag classification is to find the optimal subgraphs from the training graph set B to train classification models, and predict previously unseen multi-graph-view graph-bags with a maximum accuracy.

2.1 Overall Framework

Our proposed multi-graph-view bag classification framework is shown in Fig. 1. It consists of three major steps: 1) Optimal Subgraph Exploration: In each iteration, MGVBL explores a discriminative subgraph to improve the discriminative capability of the graph feature set g ∋ g∗; 2) Bag Margin Maximization: Based on the currently selected subgraphs g, a linear programming problem is solved to achieve maximum bag margin for graph bag classification; 3) Updating Bag and Graph Weights: After the linear programming is solved, the weight values for training bags and graphs are updated and repeated until the algorithm converges.

3 Multi-Graph-ViewGraph-Bag Learning

3.1 MaximumBagMargin Formulation

In graph-bag constrained learning, bag labels are asymmetric in the sense that all graphs in a negative bag are negative, while labels of graphs in positive bag are unknown. Accordingly, we can aggregate the linear constraints from two levels (bag- and graph- levels) as follows:

where wk s = (wB s )k + (wG s )k , ξi and ηj are the evaluation of the misclassification. mk is the number of subgraphs selected from the kth graph-view. C1 and C2 are tradeoff between hyperplane margin and errors. Because bag labels are known, the weighted errors are C1 ∑i:Bi∈B ξi. In addition, graphs in the negative bags are known being negative. Therefore, for the graph level the weighted errors are C2 ∑j:Gj∈B- ηj .

In Eq. (1), hgs (Bk i ) is a weak subgraph classifier, which outputs the class label of the bag Bk i in the kth view based on subgraph gs, and hgs (Gkj ) is a weak subgraph classifier for the graph Gkj in the kth view based on subgraph gs. More specially, for a subgraph gs, we can use it as a decision stump classifier for graph or bag in the kth view as

where gs ⊆ Bk i iff gs is a subgraph of any graph G in bag Bk i , i.e., ∃G ∈ Bk i ∧ gs ⊆ G. (ψB s )k and (ψG s )k (ψB s , ψG s ∈ Ψ = {-1,+1}) are parameters controlling the label of the classifiers, with I(·) being an indicator function. (wB s )(k) and (wG s )(k) denote the weights of the bag and graph in the kth view. For a subgraph set with size m = ∑k mk, The prediction rule for a graph-bag Bi or is a linear view combination of the corresponding weak classifiers as

3.2 Linear Programming Optimization

In order to support multi-graph-view graph-bag classification, a subgraph feature set g = {g1, · · · , gs, · · · , gm} is required. One straightforward solution is exhaustive enumeration, which enumerates all subgraphs to find the best ones for learning. In reality, the number of subgraphs may grow exponentially, so exhaustive enumeration is technically infeasible. This problem can be solved by column generation technique [Nash and Sofer, 1996], which works on the Lagrangian dual problem with respect to Eq. (1). Starting from an empty subgraph feature set g, column generation iteratively adds one subgraph gs, which violates the constraint in the dual problem, to g. Each time the subgraph set g is updated, column generation resolves the primal problem in Eq. (1) by solving the restricted dual problem. This procedure continues until no more subgraph violates the constraints in the dual problem, which can be formulated as

where γi and µj are Lagrange multipliers, with ∑k 1 = v. Note that, the dual problem has a limited number of variables, but a large number of constraints. Among them, each constraint ∑k (∑i:Bi∈B γiYihgs (Bk i ) - ∑j:Gj∈G- µjhgs (Gkj )) ≤ 2v indicates a subgraph feature

gs over all multi-graph-view graph-bags B, with the first and

a subgraph gs, its discriminative score can be measured by:

second terms of the left of constraint being the gain on the labeled graph-bags and graphs in negative bags, respectively. Intuitively, this constraint provides a metric to access the bag constraint based discriminative power of a given subgraph gs. Definition 5. (mgScore: Discriminative score) Given a graph-bag set B containing multiple graph-view graphs, for

To learn the multi-graph-view bag classification model, we need to find the most discriminative subgraph which considers each training bag weights and graph weights in negative bags across all graph-views for future learning.

3.3 Optimal Subgraph Exploration

In order to discover subgraphs for validation, one straightforward solution for finding an optimal subgraph set is exhaustive enumeration which enumerates all subgraphs and uses their mgScore scores for ranking. However, the number of subgraphs grows exponentially with the size of graphs in each graph-view, which makes the exhaustive enumeration approach impractical for real-world data.

Alternatively, we employ a Depth-First-Search (DFS) algorithm gSpan [Yan and Han, 2002] to iteratively enumerate subgraphs. The key idea of gSpan is that each subgraph has a unique DFS Code, defined by a lexicographic order of the discovery time during the search process. By employing a depth first search strategy on the tree, gSpan can effectively find all frequent subgraphs efficiently. In this paper, because subgraph search for each graph-view is independent, we derive an upper bound for mgScore in order to prune the search space in the DFS-code tree as follows:

Theorem 1. mgScore Upper Bound: Given two subgraphs gs and g′s , where g′s is a supergraph of gs (i.e., g′s ⊇ gs). The mgScore of g′s , £g′s is bounded by ˆ£gs , i.e., £g′s ≤ ˆ£gs , with ˆ£gs being defined as:

where

Proof. Considering decision stumps hgs (Bk i ) and hgs (Gkj ) defined in Eq. (2), we have

Algorithm 1 Discriminative Subgraph Exploration

Require:

• B = {B1 , · · · , Bk , · · · , Bv }: A multi-graph-view bag set;
• γ = {γ1, · · · , γ|B|}: A bag weight set;

µ = {µ1, · · · , µ|G-|}: A negative graph weight set;

min sup: The threshold of the frequent subgraph;

Ensure:

g∗: The most discriminative subgraph;

• 1: g∗ = ∅;
• 2: G = {G1 , · · · , Gk , · · · , Gv } ←Aggregate all graphs in B;
• 3: for all graph-views Gk , k = 1, · · · , v in G do
• 4: while Recursively visit the DFS Code Tree in gSpan do
• 5: gk s ← current visited subgraph in DFS Code Tree;
• 6: if freq(gk s ) < min sup, then
• 7: return;
• 8: Compute the mgScore £gk s for subgraph gk s using Eq. (5);
• 9: if £gk s ≥ £g∗ or g∗ == ∅ , then
• 10: g∗ ← gk s ;
• 11: if ˆ£gk s ≥ £g∗ , then
• 12: Depth-first search the subtree rooted from node gk s ;
• 13: end while
• 14: end for
• 15: return g∗;

For any ψs ((ψG s ) or (ψB s ) in any view), the value will be -1 or +1. When ψs = -1, £g′s can be rewritten as

Because

We have

For any g′s ⊇ gs under ψs = -1, we have £g′s ≤ £-gs . Similarly, £g′s ≤ £+gs under ψs = +1. In this case, the maximum one (i.e. max(£-gs ,£+gs )) will be selected as the final upper bound ˆ£gs . Once a subgraph gs is generated, all its supergraphs are upper bounded by ˆ£gs . Therefore, this theorem can help prune the search space efficiently.

Algorithm 2 MGVBL: Multi-Graph-View Bag Learning

Input:

B = {B1 , · · · , Bk , · · · , Bv }: A multi-graph-view bag set; min sup: The threshold of the frequent subgraph; m: the maximum number of iteration;

Output:

The target class label Yc of a test multi-graph-view bag Bc; // Training Phase:

• 1: g ← ∅; t ← 0;
• 2: while t ≤mdo
• 3: g∗ ←Apply B and min sup to obtain the most discriminative subgraph ; // Algorithm 1
• 4: if £g∗ /2v ≤ 1 + ϵ then
• 5: break;
• 6: g ← g ∪ g∗;
• 7: Solve Eq. (1) based on g to get wB and wG, and the Lagrange multipliers of Eq. (4) γ and µ;
• 8: t ← t + 1;
• 9: end while

// Testing Phase:

• 11: return Yc.

The above upper bound can be utilized to prune DFS code tree in gSpan by using branch-and-bound pruning, where the complete subgraph feature exploration approach is listed in Algorithm 1. The algorithm enumerates subgraph features by searching the whole DFS code tree in each graph-view. If a current subgraph gk s in the kth view is not frequent, both gk s and its related subtree will be discarded (lines 6-7). Otherwise, the mgScore of the gk s (i.e. £gk s ) will be calculated (line 8). If £gk s is greater than the current optimal mgScore £g∗ or it is the first step (i.e. the optimal subgraph £g∗ is empty), £gk s will be regarded as the current optimal subgraph £g∗ (lines 9-10). Subsequently, the upper bound pruning module will check if ˆ£gk s is less than the £g∗ , which means that the mgScore value of any supergraph gk s ′ of gk s (i.e. gk s ′ ⊇ gk s ) will not be greater than £g∗ . If so, the subtree rooted from gk s will be safely pruned. If ˆ£gk s is indeed greater than the mgScore of g∗, the search process will sequentially visit nodes from the subtree of gk s (lines 11-12).

3.4 MGVBL

The complete procedures of the proposed subgraph mining and classification framework MGVBL are listed in Algorithm 2, which iteratively extracts informative subgraphs across different graph-views to expand the candidate subgraph set g, by using mgScore. After m iterations, MGVBL boosts the m selected weak classifiers to form a final classification model.

MGVBL starts from an empty subgraph set g = ∅ (line 1), and iteratively selects the most discriminative subgraph g∗ in each round (line 3) according to Algorithm 1. If the current optimal subgraph no longer violates the constraint, the iteration process terminates (lines 4-5). Because the difference of the optimal values in the last few iterations is relatively small, a threshold ϵ is used to relax the stopping condition, so MGVBL terminates if the difference between two consecutive iterations is less than the threshold ϵ (we set ϵ = 0.05 in our experiments). After that, MGVBL solves the linear programming problem by using the current optimal subgraph set g to recalculate two groups of weight values: 1)wB and wG: the weights for bag-level and graph-level weak subgraph decision stumps, respectively; 2) γ and µ: the weights of training bags and graphs in negative bags for optimal subgraph mining in the next round, which can be obtained from the Lagrange multipliers of the primal problem (line 7). Once the algorithm converges or the number of maximum iteration is reached, the training phase of MGVBL is finished. During the testing phase, the label Yc of a test bag Bc is determined by the final classier sign(∑k ∑gs∈g (wB s )k hgs (Bk c )).

4 Experiments

4.1 Experimental Settings

All reported results are based on 10 times 10-fold crossvalidation. Unless specified otherwise, we set minimum support threshold min sup = 3% for scientific publication data (Section 4.3) and min sup = 2% for content-based image retrieval (Section 4.4).

4.2 Baseline Methods

Because no existing approaches are available to solve the proposed research problem, we use the following two types of baselines (bag-level and graph-level) for comparison studies. Bag-level approaches firstly discover some informative subgraphs to represent graphs in the bag set (i.e. transferring multi-graph set to a multi-instance set), and then employ the existing multi-view multi-instance learning MIVBL [Mayo and Frank, 2011] for classification. Graph level methods propagate bag labels to all graphs inside the bag, so the problem is transferred to a recently proposed multi-graph-view graph learning (MGVGL) [Wu et al., 2014a].

Bag-level approach

A number of top-k frequent subgraphs are explored to represent graphs as feature-vector instances, and transfer the problem as multi-view multi-instance learning. After that, MIVBL is applied to directly train multi-instance boosting classifier (MIBoost) [Xu and Frank, 2004] by treating each view independently and combining classifiers across all views for prediction. Previous research [Mayo and Frank, 2011] has indicated that sophisticated combining approaches, such as stacking [Wolpert, 1992], are possible but their initial experiments did not yield improved results and the training times were an order of magnitude greater. So we only use simple combination in our experiments.

Graph-level approach

Because labels are only available for bags, graph-level approaches directly propagate bag labels to graphs inside each bag. By doing so, the problem is transferred to a graph learning task with multiple graph-views. After that, graph-level approaches first explore an optimal set of subgraphs as features to transfer multi-graph-view graphs into feature-vectors, with an AdaBoost [Telgarsky, 2012] classifier being trained for final prediction. It is worth noting that we use AdaBoost because our proposed MGVBL is a boosting formwork, so it makes sense to compare with a boosting based method.

In addition, we also implement a bMVGBL approach (i.e. MVGBL without using the graph level constraint) as a baseline to explore the efficiency of the unified two level (bagand graph- level) framework.

4.3 Scientific Publication Text Categorization

A scientific publication can be represented as multi-graphview graphs. To build multiple graph-view, we use information from (1) abstract; and (2) paper ID, title, and references, to form two graph-views. More specifically, for abstract view graphs, each paper is converted into an undirected graph by using the correlation of keywords in the abstract with edges denoting keyword correlations. For paper ID, title, and reference view graph, each node denotes Paper ID or a keyword in the title and each edge denotes the citation relationship between papers or keyword relations in the title (detailed in [Pan et al., 2015]). For each paper, each reference cited by the paper is also a graph, so each paper with its citations, corresponds to a graph bag with two views (i.e., abstract view vs. reference relationship view). More specifically, assume paper A cites papers A1, A2, and A3, and the label of A is "Positive". For each view, we will first generate one graph from A, A1, A2, and A3, respectively. After that, we put all four graphs as one bag, and label the bag as "Positive".

The Digital Bibliography & Library Project (DBLP) data set 1 consists of bibliography in computer science. Each record in DBLP contains information such as abstract, authors, year, title, and references. To build a multi-graphview graph-bag, we select papers published in two relevant research fields: Artificial Intelligence (AI: IJCAI, AAAI, NIPS, UAI, COLT, ACL, KR, ICML, ECML, and IJCNN), and Database (DB: SIGMOD, KDD, PODS, VLDB, ICDE, CIKM, DASFAA, ICDT, and SSDBM) to form a multigraph-view graph-bag learning task. The objective is to predict whether a paper belongs to the AI or DB field.

For each abstract in the abstract graph-view, a fuzzy cognitive map (E-FCM) [Luo et al., 2011] based approach is used to extract a number of keywords and correlations between keywords, which form nodes (keywords) and edges (keyword correlations) of each graph. A threshold (0.005) is used to remove edges whose correlations are less than the threshold. At the last step, the graph is converted into an unweighted graph by setting the weight of all remaining edges as "1". In the experiments, we choose 600 papers in total (corresponding to 600 multiple graph-views bags) to form positive (AI) bags (300 bags with 1756 graphs) and negative (DB) bags (300 bags with 1738 graphs).

Fig. 2 (A) reports accuracy for multi-graph-view graphbag classification. When the number of selected subgraphs is less than 10, the performances of all algorithms are comparably low, mainly because a small number of subgraph stumps (i.e. weak classifiers) lead to inferior classification accuracies in early iterations. By contrast, MGVBL consistently outperforms baselines when the number of selected subgraphs is 20 or more. During last a few iterations, MGVGL can obtain a high accuracy, but this type of baselines still cannot outperform the best performance achieved by MGVBL.

1 http://dblp.uni-trier.de/xml/

4.4 Content-based Image Retrieval

In this section, we report MGVBL's performance for content based image retrieval. The original images [Li and Wang, 2008] from Corel data set 2 are preprocessed by using VLFeat segmentation [Vedaldi and Fulkerson, 2008], with each image being segmented into multiple regions and each region corresponding to one graph. For each region, Simple Linear Iterative Clustering (SLIC) [Achanta et al., 2012] is applied to obtain graph representation, so each node indicates one superpixel and each edge represents the adjacency relationship between two superpixels [Wu et al., 2014b].

In order to build multiple graph-views, we employ two types of features, including Hue-Saturation-Value (HSV) in colour space and Local Binary Patterns (LBP) in the texture space. Specifically, HSV is a commonly used color model, where HSV stands for hue, saturation and intensity, and LBP represents texture in a local region. For HSV feature, we first extract a 3-channel HSV feature for each pixel. The extracted HSV representations are fed to k-means clustering to construct a 256-dimensional codebook. After that, a onedimensional code is assigned to each pixel based on the similarity between the pixel representation and the cluster centers. The HSV-based representation for a superpixel is constructed as a 256-dimensional histogram-based vector by computing the statistics of the occurrences of the codes. For LBP, we adopt the uniform LBP and generate a 59-bin code for each pixel, where each pixel is assigned to one bin according to the local texture pattern. Therefore, a 59-dimensional histogram is constructed for each superpixel encoding its statistics.

To build positive bags, we use category "Cats", which consists of "Tiger", "Lion" and "Leopard", as positive bags (300 bags with 2679 graphs) and randomly draw 300 images of other animals to form negative bags with 2668 graphs (i.e. image regions). Fig. 2(B) shows the classification results from 1 to 100 iterations. With the two bag- and graphlevel constraints, MGVBL achieves better performance than bMGVBL (only considers bag level constraints), indicating that information in negative bags is very helpful for learning the model. MIVBL has the worst performance, mainly because their frequent subgraphs are not carefully selected and therefore are not discriminative. Although MGVGL is comparable to bMGVBL, MGVGL is inferior compared to the proposed MGVBL, due to the fact that MGVGL directly propagates bag labels to graphs and cause negative graphs in positive bags being mislabeled as positive. Overall, the proposed MGVBL has the best learning performance.

2 https://sites.google.com/site/dctresearch/Home/content-basedimage-retrieval

4.5 Efficiency of the Pruning Strategy

In order to evaluate the efficiency of the proposed pruning module for searching subgraphs as described in Section 3.3, we implement an UMGVBL approach with no pruning module and compare its runtime with MGVBL. In our implementation, UMGVBL first uses gSpan to find a frequent subgraph set, and then selects the optimal subgraph by using the same evaluation criteria as MGVBL.

The results in Fig. 3 show that increasing min sup values decreases the runtime of UMGVBL, mainly because a larger min sup value reduces the candidate number for validation. By using pruning strategy (i.e. the constraints including threshold min sup and upper bound ˆ£gs = max(£-gs , £+gs ) as shown in Algorithm 1), MGVBL's runtime performance is relatively stable w.r.t. different min sup values. Overall, MGVBL demonstrates clear advantage compared to unbounded UMGVBL, especially when min sup is small.

5 Conclusion

This paper investigated the representation and classification of complicated objects by using graph-bag based multigraph-view learning. We argued that many real-world objects contain structure information from different views, and multi-graph-view graph-bag representation provides an effective way to preserve structure and complicated features of the object for learning. To build a learning model for multi-graphview classification, we formulated an objective function to jointly regularize multiple graph-views, and enforce labeling constraints at bag and graph levels, respectively, so our algorithm can discover most effective subgraph features across all graph-views to optimize the learning. The key contribution of the paper, compared to existing works, is threefold: (1) a new multi-graph-view representation model to represent complicated objects; (2) a cross graph-view search space pruning strategy; and (3) a combined cross-view subgraph feature exploration and learning method.

Acknowledgments

The work was supported by Australian Research Council (ARC) Discovery Projects under Grant No. DP140100545 and DP140102206.