Large graphs are ubiquitous. Their sizes, rates of growth, and complexity, however, have significantly outpaced human capabilities to ingest and make sense of them. As a cost-effective graph simplification technique, graph summarization is aimed to reduce large graphs into concise, structure-preserving, and quality-enhanced summaries readily available for efficient graph storage, processing, and visualization. Concretely, given a graph G , graph summarization condenses G into a succinct representation comprising (1) a supergraph with supernodes representing disjoint sets of vertices of G and superedges depicting aggregate-level connections between supernodes, and (2) a set of correction edges that help reconstruct G losslessly from the supergraph. Existing graph summarization solutions offer non-optimal graph summaries and are time-demanding in real-world large graphs. In this paper, we propose a learning-enhanced graph summarization approach, Poligras ( Poli cy-based gra ph summarization), to model the most critical computational component in graph summarization: supernode selection and merging. Specifically, we design a probabilistic policy learned and optimized by neural networks for efficient optimal supernode pair selection. As the first learning-enhanced, scalable graph summarization method, Poligras achieves significantly improved performance over state-of-the-art graph summarization solutions in real-world large graphs.

Future wireless networks are expected to support diverse Internet of Things (IoT) applications under dynamic network conditions through effective resource allocation. However, the growing complexity of underlying optimization problems for resource allocation has brought many challenges to traditional centralized network operations due to inherent computational constraints. To overcome these challenges, this paper proposes a Distributed-Optimization with Centralized-Refining (DO-CR) mechanism to achieve more efficient resource allocation by engaging both access point and all devices. Specifically, the new DO-CR mechanism first utilizes the distributed processing capacity of all devices, allowing them to optimize their own resource allocation schemes through a new resource reservation and reporting technique. Then a centralized optimizer generates a graph of resource trading topology based on individual optimization results and achieves the Pareto optimal solution by the graph-based algorithm. This Pareto optimal solution simplifies the overall optimization problem and enables the central optimizer to solve it with smaller feasible regions. The analysis presents that the DO-CR mechanism’s performance is bounded by Pareto optimality as lower limit and global optimality as upper limit. Simulation results demonstrate that the proposed DO-CR mechanism significantly reduces processing time on the centralized optimizer while maintaining near-optimal utility performance compared to conventional optimization methods.

Optimization algorithms with momentum have been widely used for building deep learning models because of the fast convergence rate. Momentum helps accelerate Stochastic gradient descent in relevant directions in parameter updating, minifying the oscillations of the parameters update route. The gradient of each step in optimization algorithms with momentum is calculated by a part of the training samples, so there exists stochasticity, which may bring errors to parameter updates. In this case, momentum placing the influence of the last step to the current step with a fixed weight is obviously inaccurate, which propagates the error and hinders the correction of the current step. Besides, such a hyperparameter can be extremely hard to tune in applications as well. In this paper, we introduce a novel optimization algorithm, namely, Discriminative wEight on Adaptive Momentum (DEAM). Instead of assigning the momentum term weight with a fixed hyperparameter, DEAM proposes to compute the momentum weight automatically based on the discriminative angle. The momentum term weight will be assigned with an appropriate value that configures momentum in the current step. In this way, DEAM involves fewer hyperparameters. DEAM also contains a novel backtrack term, which restricts redundant updates when the correction of the last step is needed. The backtrack term can effectively adapt the learning rate and achieve the anticipatory update as well. Extensive experiments demonstrate that DEAM can achieve a faster convergence rate than the existing optimization algorithms in training the deep learning models of both convex and nonconvex situations.

Graph neural networks (GNNs) have shown convincing performance in learning powerful node representations that preserve both node attributes and graph structural information. However, many GNNs encounter problems in effectiveness and efficiency when they are designed with a deeper network structure or handle large-sized graphs. Several sampling algorithms have been proposed for improving and accelerating the training of GNNs, yet they ignore understanding the source of GNNs performance gain. The measurement of information within graph data can help the sampling algorithms to keep high-value information while removing redundant information and even noise. In this paper, we propose a Metric-Guided (MeGuide) subgraph learning framework for GNNs. MeGuide employs two novel metrics: Feature Smoothness and Connection Failure Distance to guide the subgraph sampling and mini-batch based training. Feature Smoothness is designed for analyzing the feature of nodes to retain the most valuable information, while Connection Failure Distance can measure the structural information to control the size of subgraphs. We demonstrate the effectiveness and efficiency of MeGuide in training various GNNs on multiple data sets.

Graph neural networks (GNNs) have achieved outstanding performance in learning graph-structured data and various tasks. However, many current GNNs suffer from three common problems when facing large-size graphs or using a deeper structure: neighbors explosion, node dependence, and oversmoothing. Such problems attribute to the data structures of the graph itself or the designing of the multi-layers GNNs framework, and can lead to low training efficiency and high space complexity. To deal with these problems, in this paper, we propose a general subgraph-based training framework, namely Ripple Walk Training (RWT), for deep and large graph neural networks. RWT samples subgraphs from the full graph to constitute a mini-batch, and the full GNN is updated based on the mini-batch gradient. We analyze the high-quality sub graphs to train GNNs in a theoretical way. A novel sampling method Ripple Walk Sampler works for sampling these high-quality subgraphs to constitute the mini-batch, which considers both the randomness and connectivity of the graph-structured data. Extensive experiments on different sizes of graphs demonstrate the effectiveness and efficiency of RWT in training various GNNs (GCN & GAT). Our code is released in the https://github.com/anonymous2review/RippleWalk.

For various optimization methods, gradient descent-based algorithms can achieve outstanding performance and have been widely used in various tasks. Among those commonly used algorithms, ADAM owns many advantages such as fast convergence with both the momentum term and the adaptive learning rate. However, since the loss functions of most deep neural networks are non-convex, ADAM also shares the drawback of getting stuck in local optima easily. To resolve such a problem, the idea of combining genetic algorithm with base learners is introduced to rediscover the best solutions. Nonetheless, from our analysis, the idea of combining genetic algorithm with a batch of base learners still has its shortcomings. The effectiveness of genetic algorithm can hardly be guaranteed if the unit models converge to close or the same solutions. To resolve this problem and further maximize the advantages of genetic algorithm with base learners, we propose to implement the boosting strategy for input model training, which can subsequently improve the effectiveness of genetic algorithm. In this paper, we introduce a novel optimization algorithm, namely Boosting based Genetic ADAM (BGADAM). With both theoretic analysis and empirical experiments, we will show that adding the boosting strategy into the BGADAM model can help models jump out the local optima and converge to better solutions.

Computing similarity between graphs is a fundamental and critical problem in graph-based applications, and one of the most commonly used graph similarity measures is graph edit distance (GED), defined as the minimum number of graph edit operations that transform one graph to another. Existing GED solutions suffer from severe performance issues due in particular to the NP-hardness of exact GED computation. Recently, deep learning has shown early promise for GED approximation with high accuracy and low computational cost. However, existing methods treat GED as a global, coarse-grained graph similarity value, while neglecting the type-specific transformative impacts incurred by different types of graph edit operations, including node insertion/deletion, node relabeling, edge insertion/deletion, and edge relabeling. In this paper, we propose a type-aware graph similarity learning and computation framework, TaGSim (T ype -a ware G raph Sim ilarity), that estimates GED in a fine-grained approach w.r.t. different graph edit types. Specifically, for each type of graph edit operations, TaGSim models its unique transformative impacts upon graphs, and encodes them into high-quality, type-aware graph embeddings, which are further fed into type-aware neural networks for accurate GED estimation. Extensive experiments on five real-world datasets demonstrate the effectiveness and efficiency of TaGSim, which significantly outperforms state-of-the-art GED solutions.

Optimization algorithms with momentum, e.g., (ADAM) helps accelerate SGD in parameter updating, which can minify the oscillations of parameters update route. However, the fixed momentum weight (e.g., β1in ADAM) will propagate errors in momentum computing. Besides, such a hyperparameter can be extremely hard to tune in applications. In this paper, we introduce a novel optimization algorithm, namely Discriminative wEight on Adaptive Momentum (DEAM). DEAM proposes to compute the momentum weight automatically based on the discriminative angle. The momentum term weight will be assigned with an appropriate value which configures the influence of momentum in the current step. In addition, DEAM also contains a novel backtrack term, which restricts redundant updates when the correction of the last step is needed. The backtrack term can effectively adapt the learning rate and achieve the anticipatory update as well. Extensive experiments demonstrate that DEAM can achieve a faster convergence rate than the existing optimization algorithms in training various models. A full version of this paper can be accessed in [1].

In recent years, many research works propose to embed the network structured data into a low-dimensional feature space, where each node will be represented as a feature vector. However, due to the detachment of the embedding process with external tasks, the learned embedding results by most existing embedding models can be ineffective for application tasks with specific objectives, e.g., community detection, network alignment or information diffusion. In this paper, we propose to study the application oriented heterogeneous social network embedding problem. Significantly different from the existing works, besides the network structure preservation, the problem should also incorporate the objectives of external applications in the objective function. To resolve the problem, we propose a novel network embedding framework, namely “application oriented network Embedding” (LATTE). In LATTE, the heterogeneous network structure can be applied to compute the node “diffusive proximity” scores, which capture both the local and global network structures. Based on these computed scores, LATTE learns the network representation feature vectors by extending the autoencoder model to the heterogeneous network scenario, which can also effectively unite the objectives of network embedding and external application tasks. Extensive experiments have been done on real-world heterogeneous social network datasets with community detection as an example task, and the experimental results have demonstrated the outstanding performance of LATTE. Experiental results on other tasks are provided in the full-version of this paper at [16].

This paper proposes a simple hybrid decode- compress- and-forward and compress-and-forward (DCF&CF) relay scheme for the coordinated multipoint (CoMP) uplink transmission. In particular, we consider a scenario that two mobile users (MUs) transmit signal to two access points (APs), which are linked to the central unit (CU) via lossless capacity-limited fronthaul. To characterize the achievable rate region of the considered system, a rate maximization problem is formulated and solved by exploiting the monotonicity and convexity of its objective function. Furthermore, maximum sum rate of the two MUs is obtained according to the maximized rate region boundary. Finally the analysis is validated by numerical results.