Optimal Transport-Based Supervised Graph Summarization
Authors: Sepideh Neshatfar
Abram Magner
Salimeh Yasaei Sekeh
Venue: Submitted to ICLR 2023 (2023)
Keywords: Graph Summarization
Optimal Transport
Supervised Learning
Mutual Information

Abstract: Graph summarization is the problem of producing smaller graph representations of an input graph dataset, in such a way that
  the smaller ``compressed'' graphs capture relevant structural information for downstream tasks.  One graph summarization
  method, recently proposed in Garg & Jaakkola (2019), formulates an optimal transport-based framework that allows prior information
  about node, edge, and attribute importance to be incorporated into the graph summarization process. We extend the optimal transport framework to a supervised graph summarization setting, wherein we seek to preserve relevant information about a class label.  We first formulate the problem in terms of maximizing the mutual information between the summarized graph and the class label.  We then propose a method that incorporates mutual information estimates between random variables associated with sample graphs and class labels into
  the optimal transport compression framework from Garg & Jaakkola (2019).  We empirically show performance improvements over the previous work by Garg & Jaakkola (2019), in terms of classification and compression on synthetic and real datasets.  We then theoretically show limitations of the optimal transport approach: e.g., that it fails to satisfy a certain desirable information monotonicity property.  

Under review as a conference paper at ICLR 2023
OPTIMAL TRANSPORT-BASED SUPERVISED GRAPH SUMMARIZATION
Anonymous authors Paper under double-bling review
ABSTRACT
Graph summarization is the problem of producing smaller graph representations of an input graph dataset, in such a way that the smaller compressed graphs capture relevant structural information for downstream tasks. One graph summarization method, recently proposed in Garg & Jaakkola (2019), formulates an optimal transport-based framework that allows prior information about node, edge, and attribute importance to be incorporated into the graph summarization process. We consider the problem graph summarization in supervised setting, wherein we seek to preserve relevant information about a class label. We first formulate this problem in terms of maximizing the Shannon mutual information between the summarized graph and the class label. We propose a method that incorporates mutual information estimates between random variables associated with sample graphs and class labels into the optimal transport compression framework. We empirically show performance improvements over previous works in terms of classification accuracy and time synthetic and certain real datasets. We also theoretically explore the limitations of the optimal transport approach for the supervised summarization problem and we show that it fails to satisfy certain desirable information monotonicity property.
INTRODUCTION
Machine learning involving graphs has wide range of applications in artificial intelligence Scarselli al. ) Dessi et al. (2020), network analysis, and biological interactions Han et al. (2019);
Chen et al. (020)). Graph classification problems use the network structure of the underlying data to improve predictive decision outcomes. However, graph datasets are often enormous, and the algorithms used to extract relevant information from graphs are frequently computationally expensive. Graph summarization addresses these scalability issues by computing reduced representations of graph datasets while retaining relevant information. As with numerous other problems in machine learning, the precise meaning of "reduced representation" " does not have one single mathematical definition, and there is single objective function being optimized. There are thus various approaches to this problem. For survey, see Liu et al. (2018). The particular type of approach of interest in this paper takes dataset of graphs and number input and outputs, for each graph G in the dataset, a subgraph H C G is induced by & vertices.
Optimal transport, the general problem of moving one distribution of mass another as efficiently as possible, has been used in many recent graph-related problems, such as graph matching via the Gromov- Wasserstein distance Xu et al. (2019). One recent approach the graph summarization problem that allows for the incorporation of iiseeenngeeeree prior information is the Optimal Trans- port based Compression (OTC) approach of Garg & Jaakkola (2019). Their approach is as follows: a graph G, target number & of vertices, probability distribution Pe on the vertices of G, and cost function e E + R, where (G) denotes the set of edges of G. are given as input. A probability distribution Pi is computed by minimizing the Wasserstein distance respect to the cost function c, with the constraint, that the number vertices in the support of P1 is at most k. The output subgraph H is the one induced by the vertices in the support of P1- Prior information can be incorporated into the method via appropriately choosing Po and c, but in the prior work, this "prior information" is not learned, and Po and are heuristically.
G between Po and Pi with

---

Under review as a conference paper at ICLR 2023
In the present work, propose novel supervised summarization algorithm based on Optimal Transport that estimates principled values for the parameters from input data. We show that empirically surpasses the state-of state-of-the-arr performance (including the performance of the specific method proposed in OTC) on selected real and synthetic datasets. The novelty of the summarization algorithm is that we our optimal transport parameters in terms of node attributes' and edge indicators' information about class variables. Along the way, we develop an estimator for the mutual information between a latent position vector graph and class label. This extends the well- studied problem of ceemmatiiontthhorrtie measure estimation Kraskov et al. (2004); ): Moon et al.
(2017); Noshad et al.] (2017) Our estimator is inspired by EDGE's fast and relatively accurate implementation Noshad et al. (2019).
Toward providing theory for the limitations of our approach to graph summarization, we propose a natural information-theoreiie Cover & Thomas (199T); Yasaei Sekeh et al. (2018) objective function for the task of supervised graph summarization and show that is NP-hard to optimize. Using this new framework, explore the limitations of the optimal-transport -essortt---dddd---e approach, both theoretically and empirically. Specifically, we formulate a notion of information monotonicity of an optimal transport parameter pair with respect to data distribution. This is the desirable property that means the flow cost decreases monotonically as the mutual information of the resulting summarized graph data with the corresponding class labels increases. This means that optimizing flow cost increases class label information (but may not optimize it). We show that any optimal transport parameter pair satisfying natural properties fails exhibit information monotonicity for at least some data distributions.
Contribution: We summarize our contribution in this paper as follows: We propose a novel informationnthherree attributed graph summarization problem formulation in which the goal is to choose a graph summary that maximizes the mutual information between sample graphs and class labels. We theoretically prove that the problem of maximization of the mutual information between attributed graphs and class variables with the knowledge of the data distribution is NP-hard, even approximately. We then show via explicit constructions some limitations of the optimal transport graph compression approach in Garg & Jaakkola (OTC). We then introduce supervised graph summarization framework based on optimal transport and experimentally show that it outperforms the baseline (no compression) and the unsupervised OTC method in terms of post-compression classification time and test accuracy, despite suffering from the fundamental limitations of our theoretical contribution.
2 PROBLEM FORMULATION: SUPERVISED GRAPH SUMMARIZATION
We formulate the supervised graph summarization problem as follows. We fix a target compression ratio E (0. 1), which will be the ratio of the number of vertices in summarized graph to the number in the original graph. A probability distribution D over tuples (G, X, C)) is fixed by nature and unknown to the summarizer and the classifier. Here, the graphs G are defined on single common set V of vertices, X is a [V] x d matrix whose rows are d-dimensional feature vectors corresponding to the vertices of G, and C' is class label coming from some fixed set C. A dataset {(G,, X,, C ~ DD consisting of m independent and identically distributed (iid) samples from D is presented to us. Our task is, given sample {G,, X,, C but no knowledge of distribution D, to select a subset H C V of vertices satisfying the following:
H =
arg max T(GGv UCV.UUISMM
Here, GV is the subgraph of G induced by the vertices in U, and Xu is the matrix of corresponding feature vectors. The standard definition of function [(:--) is the Shannon mutual information Corvver Cover & Thomas 2006), defined as follows: for random variables X and Y on a common probability space,
I(X:Y) = EP(XY log P(X,Y) Y)
P(X))(Y))
where the expectation is taken with respect to the joint distribution of X and Y. The objective function in (T) i.e. MI between an attributed graph and its class label is defined as follows: An attributed graph consists of both graph and collection of node features. Let g : (0, oo) R be convex function with g1) = O. Given graph Gy with fixed set of vertices V = { {E....., 2n and features set Xy {X Xx,, J. the mutual information between (Gv, Xv) and class variable
2

---

Under review as a conference paper at ICLR 2023
C' with prior probability se is given by
I(Gv, C) mo ( (P(GV)XV))))
(
Xv)me
Epo 9 P(Cv,
(3)
where Pa = P(Gv. and me is the prior probability of class C.
Going back to ① intuitively, H is subset of nodes of G with size at most <|V| whose induced attributed subgraph has maximum mutual information with the class label C. To justify (T). as we observe in (2) the mutual information measures the nonlinear dependency between input graphs and their class labels. Thus, an optimal subset of vertices that maximizes this measure should preserve classification performance. While this is very natural formulation of supervised graph summarization, we immediately run into computational complexity difficulties, as our first main result shows.
Theorem 1 (NP-hardness of supervised graph summarization). The problem of maximizing W in with knowledge of the data distribution 'D is NP-hard.
Proof: We prove this via a reduction from the k-clique problem to ours. Given a graph G, we would like determine whether not has k-clique. We will do this by constructing instance of the supervised graph summarization problem above. We let the class label be C ~ Bernoulli(1 /2). We construct complete graph G'' on the same node set G. We assign an event E, each (undirected) edge e in G' as follows: if e is in G, then we set EV, to be Ev,w ~ Bernoullip). where = C/2, independent of any other edge weight. If, on the other hand, e is not present in G. then set E. to be O. We set all node features to 1. Note that, with this distribution, we have that the mutual information between the subgraph H induced by any set of lo nodes in G' is given by
(H):)) (H:
Σ I(Ee C)2
where VH is the set of the nodes on subgraph H. This is (*) if and only if is a k-clique in G. and it is less if there are missing edges. Thus, if we could solve our optimization problem in polynomial time, then we could solve the k-clique problem in polynomial time. This completes the proof.
In fact, the reduction that we exhibited yields a stronger result: our approximation problem is, in general, NP-hard to approximate within a constant factor of the optimum. This follows from the NP-hardness of approximation of the max clique problem.
Thus, in the search for practical approaches to graph summarization in supervised setting, we must be more modest in our expectations, and we not solve the above optimization problem, though remains the intuitive motivator of our approach. In Section 3 we describe our approach via optimal transport and the framework of OTC.
3 SUPERVISED GRAPH SUMMARIZATION VIA OPTIMAL TRANSPORT
In this section, we review the optimal transport summarization framework from Garg & Jaakkola (2019), then propose our supervised method via iefommtiion-thoreee measures.
3.1 PRELIMINARIES: OPTIMAL TRANSPORT ON GRAPHS
We first describe the framework of optimal transport on graphs. Fix a graph G on n vertices
[n] 21, n with edge set E(G). We let E(G) denote the directed edge set of G, given by
D(G) = {vv, w) (u, E E(G)).
(5)
Let Pos P1 be two probability distributions on [n],, viewed as vectors. Let e E(G) + R be an arbitrary cost function. A flow on G is a function J E(G) + oo). The cost of flow is defined:
W(J) Σ c(e)
(6)
eEB(G)
3

---

Under review as a conference paper at ICLR 2023
The result of a flow J with initial distribution Po is defined by R(J) = Po + F.J. Finally, the set of flows from Pu with the result P1 is denoted by Fa( Next we define the Wasserstein distance between Po and p1 which is the minimum cost of any flow transporting Po to p on G as follows: inf (J).
Wo(po.P1) JEFo(PO-P1)
The method proposed in Garg & Jaakkola (2019) takes G. Po. C, and a compression ratio x as input and finds a Pr with support size I <|V [[G] with minimal Wasserstein distance to Po. The summarizing graph H is then the one induced by the vertices in the support of p1. The selling point of their method is that prior information about "node/edge importance" can be encoded in po and c. They do not formally define any importance measures. They perform experiments in which Po assigns a probability to node v proportional to its degree (so Po is the stationary distribution of the random walk on G. if it is ergodic) and c assigns a higher cost to edges connecting nodes with different attributes (all of their experiments are on graphs with categorical attributes). Unlike the framework that we develop in the present paper, their framework is not a priori supervised. Furthermore, no justification given for their choice of Po and c. In addition, their framework ignores dataset-level statistics (since their setting of po and e is entirely dependent on the individual graph being compressed) and ignores the absence of edges, which can be informative.
3.2 OUR METHOD: SUPERVISED OT VIA INFORMATION THEORETIC MEASURES
In this section, we extend the above framework to the supervised setting. The core idea is to use the training dataset to learn measures of informativeness about the class label of node features and edges. We then use these to construct the initial distribution and cost function, which can then be used in the framework of the previous work applied to the complete graph on n nodes to find a subset H of nodes such that the subgraphs induced by H/ in the test set are informative about the class label while being a small subset of the original vertex set. We run the OTC algorithm on the complete graph because we wish to take into account the informativeness of the presence/absence of edges. The method proposed in the prior work only does this indirectly. We define the initial distribution po by:
I(X,;Q0 C)
Po(u) Ewe(n) ((x::
(8)
where T(:--) is the MI between node attributes and class label and defined in Next, we propose the cost function .(..)) as follows:
c(u, w) (RI(Fr, IC= 0 || Fu,. w C + Ru,, where
(9)
R = [(x;; C (xx)) + I(Xw; C (xx),
(10)
and D denotes the K L-diverrgence Cover& & Thomas (0066 from a random variable A to random variable B (See Algorithm 1). The intuition for this definition of po is that we consider nodes to be important if their features carry a significant amount of information about the class label. The intuition behind the definition of cost in (9) is follows: in optimal transport,
want large amount of flow across an edge if and only if the edge itself is not too informative about C, and the feature of one of the vertices incident the edge is not too informative about C, conditioned on the value of the other vertex's ' feature (in other words, the vertices contain redundant information about C). In this case, we want the edge cost be small.
Running the optimal transport compression routine of OTC on the complete graph Kn with Po, c, as parameters results in a subset I/ of nodes of cardinality (approximately) sn. To compress graph G in the test set, we simply take the subgraph of G induced by H.
Crucial the performance of our method is the ability to estimate the mutual information and KL divergence quantities in the expressions for Po and c directly without estimating the distribu- tions Yasaei Sekeh & Hero (2018). We chose EDGE Noshad et al. (219)) because it has been shown that it achieves optimal computational complexity O(N) where N is the sample size. This is significantly faster than its plug-in competitors Kraskov et al. (0044): Moon et al. 2017). It is proved that in addition to fast implementation EDGE has the optimal parametric MSE rate of O(1/N) under a specific condition. The KL divergences are estimated via the plug-in method. In Section 5 we evaluate method on synthetic and generated graphs from real datasets. We show that it empiriclll outperforms significantly the previous work on all of the considered datasets, in terms of running time and, on some datasets, in terms of test accuracy.
4

---

Under review as a conference paper at ICLR 2023
Algorithm I: Supervised Optimal Transport Compression
Data:
Size n of graphs, target subgraph size k; dataset D = [[G C)) where Gj is an n. x adjacency matrix, X, E Rexd is matrix of vertex features, Ej is matrix of edge features, and C E {0, 1] a class label Result: A subset S S [n] of size k
// Compute initial distribution Po on nodes.
for v = to do
// Compute the MI between the features of node j and the class label.
1(x,C)) Set po(e) = Emev [(X.;C)
end
Set s = 2i= Po(i);
for j = 1 to n do
Set (o( po(j)/s:
end
// Compute for u F do Set c(v, w) = DKL (B C=0 Eo,w C²= 1) + end
n cost matrix cost.
11 Set OTCopresss PD, cost);
return S;
LIMITATIONS OF THE OPTIMAL TRANSPORT APPROACH
In this section, we explore the limitations of the optimal transport approach for the purposes of maximizing the mutual information of graphs (G, X) with a class label C. To solve this optimization problem via OT we require initial distribution and cost function c. Here, we first specify the kinds of initial distribution and cost function we propose (8) and (9)
Definition (Data distribution-dependee
parameters). Fix graph size n. An edge cost function is function from the joint distribution of (G, C) (call this the data distribution) and pairs of vertices (i.e., numbers [nl) to non-negative real numbers or co. If the data distribution is given, then is just mapping from pairs of verlices to [0, oo).
Similarly, an initial distribution map is a mapping from the data distribution to probability distributions on [m)] (which are meant to be values for Po). If the data distribution is given, then po is a function mapping vertices to probabilities (which must sum to 1).
Below we define a property of OT parameter pairs called information monotonicity, which guarantees that using a pair with this property, flow cost decreases as the mutual information between the resulting compressed subgraph and class label increases. We will study to what exent OT parameter pairs satisfy this property.
Definition 2 (Information monotonicity). An OT parameter pair (c, L) is said to be information monotone for data distribution (G, Xv, if. for any two flows f()), , f() G resulting in subgraphs (0), H1),, respectively, we have
W(F S (() = ((HH'))HHH)))
I(HHU)XH))) X)n):C).
(11)
4.1 A MONOTONICITY COUNTEREXAMPH
this section, we construct an example graph for which the Wasserstein distance between Po and p not monotone with respect to the mutual information between the graph and the class label random variable. Let us suppose that all vertex features are independent of the graph structure and of the class label, so they provide no information about either. In this case, Po is the uniform distribution over all n vertices. Furthermore, let's suppose that the edges are generated as follows: the class label C ~ Bernoullipp) and then, conditioned C c, each edge appears with probability
5

---

Under review as a conference paper at ICLR 2023
(0) de independent of everything else. Intuitively, those edges with large (0) -qe provide more information about the value of C.
(1)
Set n = 3, so we have a triangle. We can cook up settings of (c) such that the costs of the three edges are proportional to 3, i. we have the cost function c(1, 2)
3
C C=4
c(1,3) 4, c(2, 5 scaled appropriately.
To be more explicit about the calculation of the cost of one edge e, we write:
(0)
q
log gr
c(e) = (E. C= = 0 E. C = 1) = de log
+ + _
(12)
ge
(Note that the Rg term vanishes in our example because of our independence assumption.) The cost c(e) can take any value between 0 and co, if suitable values of qz and de are chosen. We thus can cook up choices these parameters that give exactly the values 3, 4, 5. Let us consider two flows:
In one, we set 2(1 = ((1 = 1/6 and set the flow across all other edges to O. The cost of this flow is 3- 3/66 + 4 4--4411/0 1/6 = 7/6. The distribution p1 = 1/2, 1/2). This leaves in the compressed graph the edge 32. which had cost 5 (so, the highest possible mutual information with the class label).
In the other, we set J(2, 3 1/3 = 1. The distribution cost (so, not the highest possible mutual information with the class label).
1/3 and set all other flows to The cost of this flow is
(2/3, 0, 1/3). This leaves the edge {1, 3]. which had
Discussion: In this counterexample, we used a specific choice of cost function and showed that there a fundamental limitation the OT approach Garg & Jaakkola (2019) for classification problems.
Now, we have the following theorem regarding non- non-monotonicity of optimal transport solutions with respect to mutual information, which generalizes the above example.
Theorem 2 monotoontoyyyctyy ). Let c(..)) be cost function satisfying the following properties:
c(u, u) strictly monotone increasing with the mutual information between Frg,o and C and is when the two are independent.
Let be an initial distribution map satisfying the following properties:
if Xv is independent of C, both unconditionally and conditioned on G, then po, is the uniform distribution.
Then there exist data distributions for which (c, L) is not citemaation-monotoon
Proof: We will prove this by explicit construction. We first describe the data distribution that leads to counterexample: Let us suppose that all vertex features are independent of the graph structure and the class label, so they provide no information about either. In this case, Po is the uniform distribution over all vertices. Furthermore, let's suppose that the edges generated follows: the class label C ~ Bernoull(p)). and then, conditioned on C = c, each edge e appears with probability
( independent of everything else. Intuitively, those edges with large lg gf22) provide more information about the value of C' (this is true regardless of what the cost function is). Let e, denote the edge for which -/50) d is maximized. Suppose that the vertices of e, are vo, Wy. Let edge. We will construct two flows: f(0)
{11, Wi} denote some arbitrary non-information-opiine will move all probability mass e., while (1) will move all mass
(i) for any u & (vo, Wo), fo sends all 1/n of the mass on u to zu(u) = arg min x(u,x).
(ii) for any u & {01, w1). }. fi sends all 1/n 'n of the mass of 21 (w) arg min x).
The resulting total cost of (() for b E (0, 1). is (() Eng(or, c(u, (w))
Now, it remains show that (() > W(F(1), for some choice of model parameters (b)

---

Under review as a conference paper at ICLR 2023
b E {0, 1}. This is easy to guarantee since the edge sets of which the two sums indexed are disjoint, and we can make the costs arbitrarily close to 0 for the edges in fi by decreasing 14..2 qu.ir sufficiently. Since we only decrease this quantity for edges that are not Cx2 this does not affect the optimal edge. This completes the proof.
The above counterexample suggests the following intuition behind the shortcomings of the optimal transport approach: an edge may be very informative, but it may be isolated from the rest of the graph by high-cost (informative) edges. That is, the informativeness of an edge may have nothing to do with the cost of its surrounding edges. In this case, optimal transport might find it hard to pick it out, simply because there a lower cost associated with flowing elsewhere. Hence, there's a tension: if an informative edge has a high cost, then it may be costly to flow to it. If an informative edge has a low cost, then it may be too cheap to direct flow out of it.
EXPERIMENTAL STUDY
We conducted several experiments to compare the performance of our method with that of the OT approach and baseline (no-compression). We use graph summarization methods including OTC, Ours (Algorithm[]. D). and Coarsening(GG)) Jin et al. (2020) on each graph classification dataset, then use the resulting summarized dataset to train and test a classifier as described later in this section. We evaluate work using both real and synthetic datasets as described below. All the datasets have binary class labels. Note that we first identify senssseensitie nodes for all datasets by using the measure p Exxy, (otp-/(P(X////PP//
where P(Xv |C) and P(Xv) are conditional and marginal density functions, respectively. p determines how the distribution of node features changes given class labels. This way we focus on nodes whose features carry more information for class labels to deliver further emphasis on the contribution of both features and edges in graph classification. The node size in Table T is after applying p.
Image-based Dataset:
The real vision datasets that we are using here are based on MNIST Deng (Vnyaal
(0012). CIFAR-IO Krizhevsky| (2009) and MinilmageNet |Viyyals et al. (2016) datasets. Each pixel in an image is assigned to node in a graph and each image is a graph of attributed nodes where the edges between the nodes are based on their spatial relationships: adjacent pixels are linked by an edge similar to Defferrard et al. (2016). It is notable that the number of nodes for each graph would be tremendous since images are 784 784 pixels and we have a huge adjacency matrix for each graph. So, compressing the nodes here would be necessary specifically when considering a lot of non-useful pixels that might even negatively impact the classification.
Transport-based Dataset: As a non-vision real dataset, the New York Taxi Data (2010-2013)
Donovan & Work (016)) is used to generate an attributed graph dataset with a fixed node size among all samples. In the raw data, there are about 7 million trips by Taxis in New York City (NYC), and 703 graph samples are extracted out of them with the pre- pre-processing as the following. Firstly, invalid trips are eliminated and then the "vendor id"s into two categories based on their vendor ids. In each category, the trips of each day are considered as one single sample, and the nodes, edges, and nodes' attributes are generated for each sample. For generating the nodes, each element of a grid over the NYC map is assigned to node. So, each node in each sample shows a neighborhood on the map in a day. The attributes of these nodes are calculated as the summation of the time that taxis spend on a trip when they pick up and drop off people only that neighborhood. There is an edge between two nodes if there was at least trip on that day between those two nodes.
considered the labels. So, the trips are divided
Synthetic Dataset: The invoked synthetic data has lusss-labelddependdee node features and edges. The feature of node is generated randomly from Gaussian distribution with standard deviations and means j/[V| x 5 for class 0 and j/[V| x for class 1. Edges are randomly added to the graphs using the probability assigned to the class label.
Experimental design: For the classification accuracy experiments, for each dataset and method, we train the summarization method on training set, then apply the summarization method with the learned parameters to a test set. We then use the resulting summarized dataset as input to a classification pipeline: this pipeline is trained/tested using 5-fold cross-validation We report the average and standard deviation of the test accuracy over 5 trials for each compression and classifier. We also report the running time of the training (when applicable) and testing phase of the compression
7

---

Under review as a conference paper at ICLR 2023
time, well the running time of the classification pipeline the summarized dataset. We note that the latter running time is important because one of the central purposes of graph summarization is to make subsequent tasks, such as classification, more computationally efficient while not sacrificing too much accuracy. These statistics are not reported in prior work Garg & Jaakkola (2019). The same experiment is performed with multiple compression ratios. For the classification model, apply a support vector machine (SVM) with the GraphHopper kernel Feragen et al. (2013). We use this kernel because of its ability handle continuous node attributes.
5.1 PERFORMANCE ANALYSIS ON GRAPII CLASSIFICATION DATASETS
To evaluate our method and analyze its performance we compared the test accuracy of our method, OTC, Graph Coarsening (GC) Jin et al. (2020), and baseline (i.e. compression). Among other methods, we focused on only Graph Coarsening and OTC which already outperforms several existing works. Table summarizes the performances for each compression ratio. As the numbers in bold indicate, our method outperformed the other methods across the datasets on most compression ratios in expectation. Our method outperforms OTC, GC, and bascline on MNIST, NYC and Synthetic datasets for all compression ratios while for CIFAR16 10 and minilmageNet we could beat OTC on some the ratios (0.3-0.6 for CIFAR10 and 0.6, 0.7 for minilmageNet).
Table 1: This table demonstrates the accuracy of OTC, Ours, and Graph Coarsening(GC)) Jin et al. (2020) methods several real and synthetic datasets for some compression ratios. The methods with the best performance are indicated in bold font in each case. Here Ours+(p) is the experiment to improve "Ours" accuracy. For fairness "Ours" is the result that should be compared against OTC.
Compression Ratios
Dataset
Method
0.2
0.3
0.4
0.5
0.6
0.7
0.8
1.0
MNIST
GC
53811.066|.4961..000
.99.1.081
558.1.022
57111.70
55221.070
.5111.081
Graphs:300
OTC
6874.113 6334..12
.74.151
673:1.139
7874.161
.761 122
.7474.128
Nodes: 100
Ours
937:1.061 .4541.078
93711.061..45...77. 93991.999
.271
.17
.833 136
.8361..199
Edges:
179.8
Baseline
7733..017
CIFAR10
GC
492+
002++.002)444++.007 000.4492.220500-222221
506+.000
Graphs: 600
OTC
.16+.0021 .51+.027
493+.029
493+.009
503+.046
.557
.53=.027
Nodes: 200
Ours
501 .44100033.411.311111
549+.038.5444
.599+.022
532++003
.53+.026
.521+.021
Edges:
335.15
Ours+<p)
50711.031
522.1.033
536.1.032
.5311.034
528.1.030
.500
.528.1.226
Baseline
.311.012
MiniImageNet GC
4931.003
5044.006
49311.003
4934
587:5.003
.5041.006
.5041:000
Graphs: 1000
OTC
5734.027
57611002
583
564.1.037
5594.041
.5994.040
.57111.029
Nodes: 250
5654.039
562.1.033
568.1.02
5611.041
11991.038.569-1000
.567.1.043
Edges:
111.06
Ours+<p) 58+.029
.57+.038
566-.043
566-.042
.599+.09
.588+.038
.57=.036
Baseline
569-.029 .028
NYC
GC
524+ .048|
529+
522+.037
520+:.044
510+.008
5256++.041
Graphs: 703
отC
N/A
874+.051
922++031
.952+.02
.18+ 025
.88
.18
Nodes: 100
Ours
N/A
.61..017
955
.220
9431.006
.2911.031
.9071.047
88911.059
Edges::
418.13
Baseline
.871 8711
Synthetic
625+t.026
655-1.533 053
656:1.013
70R-1.031
.73241035
.763-4.027
Graphs: 1500
OTC
886:1.09
918.1.016
957
966.1.013
9841 005
.86... 004
092-1.003
Nodes: 100
Ours
.9091.014 .50-1.01
.981
005
007
1.861.014..00
.9931.004
Edges:4017 7.41
Baseline
992.1.005
It is notable that we outperform other methods' test accuracy in half of the real datasets, along with the synthetic dataset, by a large margin. We hypothesize that this is not happening for CIFARIO and MinilmageNet because informativeness each node. In such complex image classification tasks, pixels in isolation are less informative than in global image structure. This may result in our method failing perform
chosen optimal transpose parameters only incorporate the local
8

---

Under review as a conference paper at ICLR 2023
significantly better than the baseline in terms of test accuracy. To improve the accuracy of our method for CIFARI0 and minilmageNet, we have run another experiment using again p (called "Ourstp on Table D. We succeed on 0.7 ratio for CIFAR 10nd0.22, 0.5 ratio for minilmageNet. Note that for the sake of fairness "Ours" is the result that should be compared against OTC as the sensitive nodes are selected only once in OTC.
As observed the table for most of the examined datasets, the standard deviations are sufficiently large similar to the other well-known graph compression methods- that we cannot make empirical high-probability statements of superiority over other methods. Here "baseline" means a classification performance on mon--nnnmmnnn summarized graph.
Furthermore, classification error is not the only important evaluation metrie; training and testing speed is also essential. Our method uniformly superior to the baseline in terms of these metries, because the baseline performs the optimal transport summarization on each new graph, whereas in our method this only done on the training set. Figure demonstrates that our method outperforms OTC with a very large margin in terms of compression time. It shows that our method outperforms both OTC and baseline (no compression) in terms classification times, This is because they find the best-compressed vertex set for each sample individually while we find a single best-compressed vertex set for the whole sample.
CIFAR-10
New York City
Compression
Classificetion
Compression
Classification
80
0.78
0.5
0.30
m.
1000
0.0
Time (Sec)
50-
Time (sec)
800
40-
413
0.30
400
20
0.10
200
Our
10
OTC
OTC
0.05
Dazeline
0.04
Daseline
0.2
0.4
0.6
0.6
1.0
0.2
04
0.6
0.8 1.0
0.4
0.8
1.
02
04
0.6
0.8
1.0
Compression Ratio
Compression Ratio
Compression Ratio
Compression Ratio
Figure I: The compression and classification time for both Ours and OTC methods is shown for both CIFAR-10 and NYC. Our method substantially outperforms OTC and baseline (no compression) in both classification and compression times. The classification time for the compression ratio with the best accuracy for our method is less than half of that of the baseline.
CONCLUSION
We have introduced a theoretical formulation of supervised graph summarization in terms of maxi- mization of the mutual information between the class labels and graphs to be classified. We showed that the solution to this problem, even approximately, is NP-hard, and so we took different approach. In particular, we showed how the unsupervised optimal transport graph summarization framework of Garg & Jaakkola (019) can be adapted nontrivially to supervised setting via estimation of commmation-thhoretee measures incorporating both graph structure and node features. This is in contrast to the parameter settings of the previous work, which only took into account the degree distribution of the graph and compressed graphs in isolation, failing to take into account dataset- statistics. We also elucidated limitations of the optimal transport solution for maximization of the mutual information objective in our summarization framework.
Looking ahead Further work is necessary to elucidate the precise power/limitations of the optimal transport approach to graph summarization. For instance, its connections to other methods, such graph clustering-batt optimal transpose method to the supervised setting requires further development to accommodate graph datasets in which different graphs do not share common vertex
methods deserve further examination. Moreover, our adaptation of the

---

Under review as a conference paper at ICLR 2023
REFERENCES
Xin Chen, Xien Liu, and Ji Wu. Gen-bmp: Investigating graph representation learning for ddi prediction task. Methods, 179:47-54, 2020.
Cover and J. Thomas. Elements of information theory. 1st edn. John Wiley & Sons, Chichester, 1991.
Thomas M. Cover and Joy A. Thomas. Elements of Information Theory (Wiley Series in Telecommu-- nications and Signal Processing). Wiley- Wiley-Interscience,, USA, 2006. ISBN 0471241954.
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. In Advances in Neural Information Processing Systems, 2016. URLtttps::/aaret
org/ abs / 606. 09375
Li Deng. The mnist database of handwritten digit images for machine learning research. IEEE Signal Processing Magazine, 29(6):141-12,, 2012.
Danilo Dessi, Francesco Osborne, Diego Reforgiato Recupero, Davide Buscaldi, Enrico Motta, and Harald Sack. Ai-kg: an automatically generated knowledge graph of artificial intelligence. In International Semantic Web Conference, pp. 127-143. Springer, 2020.
Brian Donovan and Dan Work. New york city taxi trip data (2010-2013), 2016. URL https:
//doi orw...rg.1..00 13010////910022 //
Aasa Feragen, Niklas Kasenburg, Jens Petersen, Marleen de Bruijne, and Karsten Borgwardt. Scal- able kernels for graphs with continuous attributes.
J. C. Burges, Bottou, M. Welling, Z. Ghahramani, and K. Q. Weinberger (eds.), Advances in Neural Information Processing Systems, volume 26. Curran Associates, Inc., 2013. URL htt.t: http:::::///ccoeeeeeeeooo new.ieerrppp. cc/ Paper.pd.
Vikas Garg and Tommi Jaakkola. Solving graph compression via optimal transport. In Advances in Neural Information Processing Systems 32, 2019.
Peng Han, Peng Yang. Peilin Zhao. Shuo Shang, Yong Liu, Jiayu Zhou, Xin Gao, and Panos Kalnis. Gcn-mf: disease-gene association identification by graph convolutional networks and matrix factorization. In Proceedings of the 25th ACM SIGKDD international conference on knowledge discovery & data mining, pp. 705-713, 2019.
Yu Jin, Andreas Loukas, and Joseph JaJa. Graph coarsening with preserved spectral properties. In International Conference Artificial Intelligence and Statistics, pp. 4452 4462. PMLR, 2020.
Alexander Kraskov, Harald Stögbauer, and Peter Grassberger. Estimating mutual information.
Physical review E, 69(6):066138 2004.
Alex Krizhevsky, Learning multiple layers of features from tiny images. Technical report, 2009.
Yike Liu, Tara Safavi, Abhilash Dighe, and Danai Koutra. Graph summarization methods and applications: A survey. ACM Comput. Surv., 51(3), June 2018. ISSN 0360-0300. doi: 10.1145/ 3186727. URL httpt: org 11....111111122
Kevin R Moon, Kumar Sricharan, and Alfred O Hero. Ensemble estimation of mutual information. In 2017 IEEE International Symposium Information Theory (ISIT), pp. 3030-3034. IEEE, 2017.
Morteza Noshad, Kevin R Moon, Salimeh Yasaei Sekeh, and Alfred O Hero. Direct estimation of information divergence using nearest neighbor ratios. In 20/7 EEEE International Symposium on Information Theory (ISIT), pp. 903-907. IEEE, 2017.
Morteza Noshad, Yu Zeng, and Alfred O Hero. Scalable mutual information estimation using dependence graphs. In ICASSP 2019-2019 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 2962-2966. IEEE, 2019.
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE transactions on neural networks, 20(1):61-80, 2008.
10

---

Under review as a conference paper at ICLR 2023
Oriol Vinyals, Charles Blundell, Timothy Lillicrap, Daan Wierstra, al. Matching networks for one shot learning. Advances in neural information processing systems, 29, 2016.
Hongteng Xu, Dixin Luo, Hongyuan Zha, and Lawrence Carin Duke, Gromov- Soeny-Wasee Wasserstein learning for graph matching and node embedding. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 6932 6941. PMLR, 09-15 Jun 2019. URL m.. pww.://sn.w......s.s./e.......ee /v9 x 9b. html.
httpsss//prcceeinssssn......
S Yasaci Sekeh and A O Hero. Geometric estimatioon of multivariate dependency. Entropy (Special Issue on Women Information Theory), 2188):787-841 2018.
S. Yasaei Sekeh, B. Oselio, and A. O. Hero. A Hiieensioninndepende discriminant between distributions. In proc. IEEE Int. Conf. on Image Processing (ICASSP), 2018.


Reviews:
[{"review_id": "xf8u5GuSE4", "reviewer": "Reviewer_MXgV", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper introduces a variant over the OT-based graph summarization technique introduced in (Garg & Jaakola, 2019). The improvement relies on taking supervised information into account (when it exists) through the use of Mutual Information.", "summary_of_the_review": "The paper proposes a method to use supervised information for graph summarization using Optimal Transport.\nThe proposed method is of limited scope (even experiments do not clearly illustrate its interest) and the presentation is not sufficiently clear to convey the overall message.", "strength_and_weaknesses": "* Strengths\n    * The use of supervised information to guide the summarization process makes sense\n    * Relying on Information-theoretic measures for that seems like a reasonable choice\n    * The study of the inherent limitations of OT-based approaches for graph summarization is interesting\n* Weaknesses\n    * The contribution in terms of method is rather limited\n    * The paper is presented in such a way that it makes it hard to grasp the repercussions of the findings\n\nIn more details:\n\n* Regarding the limited contribution\n    * The contribution focuses on setting node weights $\\rho_0$ and cost based on an information-theoretic criterion, rather than based on vertex / edge importance, as done in the OT baseline, which is reasonable yet not ground-breaking.\n    * In terms of performance, the average gain seems rather limited when compared to the reported standard deviations, except on the Synthetic dataset, which is build on purpose to match the method's specificities. This is rather disappointing given that the OT baseline uses no information for the graph summarization step.\n* Regarding the lack of clarity\n    * In general, the paper lacks both structure and discussions about the potential impacts of the findings. The paper should be largely rewritten to improve on understandability.\n        * Regarding Structure, as an example, Section 5 is interesting but it misses an important point which is to discuss whether the proposed method (Section 4.2) suffers from the limitations presented in Theorem 2 or not\n            * This is discussed in the experimental section (6.2) but it would be nice to provide insights on this question in Section 5\n        * Regarding discussions, here are a few examples:\n            * In Section 4.3, the assumption \"that the random node attributes are independent\" seems rather strong and not sufficiently motivated. Also, I do not understand the formulation in Equation (13): could the authors detail their derivation for $P(G_V | X_V, C)$ and the underlying assumptions if there are any?\n            * In Section 5, the counter-example should be better discussed so as to convey the important message about why this specific example is a counter example, rather than focusing on calculations. Maybe starting with the Theorem + proof and then using the example could avoid redundancy in the text and help focus the counter-example on its illustrative power\n            \n\n* Minor issues\n    * Strange that authors do not cite anything related to Gromov-Wasserstein for graphs in their literature about the use of Optimal Transport on graphs\n    * Section 2 is a copy-paste of the beginning of Section 3!\n    * Theorem 2: $X_G$ => $X_V$?\n    * I do not understand what the authors mean by \"we tag best out of XX% of nodes as sensitive using ...\"", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "xOGwoJEcgdf", "reviewer": "Reviewer_9TND", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper seems to work on graph summarization problem taking into account node attribute and class label, hence, supervised graph summarization. ", "summary_of_the_review": "The paper didn't have a proper presentation that allows readers to follow, let alone judging its quality. ", "strength_and_weaknesses": "+The problem motivation is valid (if the solution is available)\n- The paper's writing is too unclear and erroneous to the level that I could not follow. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "o_Ve_MitGw", "reviewer": "Reviewer_atLk", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors propose a method for summarising graphs in such a way that they are compressed into a smaller representation while retaining the information required for the downstream task. The authors extend an optimum transport-based framework method for graph summarization (Garg & Jaakkola (2019)) to a supervised graph summarization method which also preserves information for the class label by maximising their mutual information. The effectiveness of the proposed method was demonstrated on several datasets such as MNIST outperforming the baseline that is based on optimum transport.", "summary_of_the_review": "Please see the Strengths and Weaknesses.", "strength_and_weaknesses": "Strengths\n- This work is well-motivated in terms of how employing supervised graph summarization might help enhance the model in downstream tasks. \n\n- I like how this work presents the limitations of existing work on OT and then attempts to address them with a new method.\n\n- Showing that supervised graph summarization is NP-hard is good information because it encourages researchers to think of fast ways to estimate the solution, which the authors attempted to do.\n\nWeaknesses\n- The colors in Table 1 are confusing as colors are usually used to identify which results are state-of-the-art and second place. Also, I found it difficult to associate each result with its corresponding method. I would find it a lot easier to read if there was a column \"model\" that shows the model for each row of results.\n- It is not clear what is meant by OT since most methods are Optimal Transport based. It would be easier to parse the results if a citation is provided next to the method's name such as OT. Is this one by Garg & Jaakkola (2019)?\n- Results on larger-scale datasets like ImageNet are missing. Having large scale datasets as part of the benchmark is important since this method's main strength is to compress large graphs while maintaining information that helps in the downstream task. \n- It would be useful to know concrete numbers on how many gigabytes of size would be reduced with compression and speed-up in seconds to identify the practical aspect of this work.\n- The 100% accuracy on MNIST is a bit suspicious because as far as I know there are few images there that are ambiguous to humans even. Can you elaborate more on how the proposed method got 100% accuracy?\n- The results in many cases do not seem significant between the baseline and the proposed method, except on MNIST, can you clarify why that is happening? Also, it seems strange that the compressed graph allows the classifier to train better than the uncompressed version, how did that happen?\n\nOverall this work brings interesting insights and methodology to the table, and I am curious about clarifications on the points I mentioned in the Weaknesses. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "iSFuMp_J52B", "reviewer": "Reviewer_u1qZ", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "In this work the authors address the problem of graph summarization using optimal transport with class labels in mind. In doing so the author proposes to formulate the problem as an optimal transport that mutual information about a class label is maximized. Empirically the author conducts several experiments to show the improvement over the previous work.", "summary_of_the_review": "Based on the strengths and weaknesses, I would recommend 6: marginally above the acceptance threshold", "strength_and_weaknesses": "Overall this is a neat extension of Garg & Jaakkola (2019) which proposed to address graph summarization from optimal transport point of view. The formation of mutual information under the existing optimal transportation is novel.\n\nWhile the work overall is a good one, this works' contribution, however,  is limited in that it mostly extends Garg & Jaakkola (2019). Although the theoretically information NON-monotonicity is pointed out, it's not sure how this empirically affects the summarization. Furthermore the experiments would be better improvised with further datasets (e.g. several standard graph datasets in  Garg & Jaakkola (2019)) and visualizations.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject