Mahmood Amintoosi
Abstract
A popular research topic in Graph Convolutional Networks (GCNs) is to speedup the training time of the network. The main bottleneck in training GCN is the exponentially growing of computations. In Cluster-GCN based on this fact that each node and its neighbors are usually grouped in the same ...
Read More
A popular research topic in Graph Convolutional Networks (GCNs) is to speedup the training time of the network. The main bottleneck in training GCN is the exponentially growing of computations. In Cluster-GCN based on this fact that each node and its neighbors are usually grouped in the same cluster, considers the clustering structure of the graph, and expand each node's neighborhood within each cluster when training GCN.The main assumption of Cluster-GCN is the weak relation between clusters; which is not correct at all graphs. Here we extend their approach by overlapped clustering, instead of crisp clustering which is used in Cluster-GCN. This is achieved by allowing the marginal nodes to contribute to training in more than one cluster. The evaluation of the proposed method is investigated through the experiments on several benchmark datasets.The experimental results show that the proposed method is more efficient than Cluster-GCN, in average.
Hashem Ezzati; Mahmood Amintoosi; Hashem Tabasi
Abstract
Graph matching is one of the most important problems in graph theory and combinatorial optimization, with many applications in various domains. Although meta-heuristic algorithms have had good performance on many NP-Hard and NP-Complete problems, but for graph matching problem, there were not reported ...
Read More
Graph matching is one of the most important problems in graph theory and combinatorial optimization, with many applications in various domains. Although meta-heuristic algorithms have had good performance on many NP-Hard and NP-Complete problems, but for graph matching problem, there were not reported superior solutions by these sort of algorithms. The reason of this inefficiency has not been investigated yet. In this paper it has been shown that Simulated Annealing (SA) as an instance of a meta-heuristic method is unlikely to be even close to the optimal solution for this problem. Mathematical and experimental results showed that the chance to reach to a partial solution, is very low, even for small number of true matches. In addition to theoretical discussion, the experimental results also verified our idea; for example, in two sample graphs with $10000$ vertices, the probability of reaching to a solution with at least three correct matches is about $0.02$ with simulated annealing.
