Graph neural networks (GNNs) have been widely used in various node-level tasks on graphs due to their powerful representation learning ability. Traditional GNNs rely on the homophily assumption that nodes with the same label in a graph tend to be connected to each other. But there are a large number of heterophily graphs in the real world, where most proximal nodes have different labels. So heterophily GNNs has been proposed, which tried to improve the performance of GNNs on heterophily graph by obtaining information from multi-hop neighbor nodes. A promising way for heterophily graphs is Graph Transformers (GTs). Without relying on the homophily assumption, GTs aggregate information of nodes depending on their similarity, thus is suitable for both homophily and heterophily graphs. Since the quadratic time complexity of GTs, most of existing GTs focus on how to reduce the complexity and make it applicable for nodes classification, their performance is still unsatisfied in heterophily graphs. To solve the above problem, Heterophilic Graph Transformer (HGphormer) is proposed in this paper. In order to reduce the interference between attribute embedding and structure embedding, a parallel architecture of Transformer is proposed. HGphormer also decouples the aggregated information into homophily and heterophily information and uses them adaptively to further improve the accuracy. A sample technique is proposed to sample neighbors from multiple hops and reduce the time complexity. Experiments show that the proposed HGphormer outperforms the state of the art methods on both homophily graph and heterophily graph datasets.

Graph neural networks greatly facilitate data processing in homogeneous and heterogeneous graphs. However, training GNNs on large-scale graphs poses a significant challenge to computing resources. It is especially prominent on heterogeneous graphs, which contain multiple types of nodes and edges, and heterogeneous GNNs are also several times more complex than the ordinary GNNs. Recently, Graph condensation (GCond) is proposed to address the challenge by condensing large-scale homogeneous graphs into small-scale informative graphs. Its label-based feature initialization and fully-connected design perform well on homogeneous graphs. While in heterogeneous graphs, label information generally only exists in specific types of nodes, making it difficult to be applied directly to heterogeneous graphs. In this paper, we propose heterogeneous graph condensation (HGCond). HGCond uses clustering information instead of label information for feature initialization, and constructs a sparse connection scheme accordingly. In addition, we found that the simple parameter exploration strategy in GCond leads to insufficient optimization on heterogeneous graphs. This paper proposes an exploration strategy based on orthogonal parameter sequences to address the problem. We experimentally demonstrate that the novel feature initialization and parameter exploration strategy is effective. Experiments show that HGCond significantly outperforms baselines on multiple datasets. On the dataset DBLP, HGCond can condense DBLP to 0.5% of its original scale to obtain DBLP-0.005. GNNs trained on DBLP-0.005 can retain nearly 99% accuracy compared to the GNNs trained on full-scale DBLP.

Graph Neural Networks (GNNs) have achieved prominent performance in the node classification task, by constructing an aggregation process to integrate node features and graph topology. The aggregation process makes the features of the connected nodes similar, which helps to classify. However, this will also cause nodes that are connected but belong to different classes to be more confusing. In this paper, we propose Repulsion-GNNs, in which a repulsion process is introduced to supplement the aggregation process. First, the nodes are divided into hyper nodes based on a basic node classification model. Then, the repulsion for each node can be obtained according to these hyper nodes. Finally, the node embeddings are obtained by combining the aggregation and repulsion. Many existing GNNs can be combined with the repulsion without adding any learnable parameter. Extensive experiments on benchmark datasets for node classification demonstrate that the repulsion can boost the performance of many GNNs, such as GCN, GAT, SAGE, and GCNII.

Computing the number ofk-hop paths is crucial for selecting services in social networks and analyzing graph data, for example, a service consumer require to evaluate the trustworthiness of a service provider along the social trust paths from a service consumer to the service provider, there are usually many social trust paths between two unconnected participants, people need to know the number of loop-freek-hop trust propogation paths; other applications include the similarity computation for services recommendation, information diffusion, etc. Previously, the number ofk-hop paths is roughly estimated by the elements in thekmultiplications of the network adjacency matrix. This method calculates much morek-hop paths than those actually exist, due to many paths with loops counted ask-hop paths, which may result in obvious errors in applications. Based on the idea of loops removing, accurate mathematical formulas for counting loop-free paths are obtained in this article for paths with five or less hops, an approximate method is provided for larger hops. Based on the proposed loop removing algorithm (LRA), the typical method for predicting trust between any two people in social networks is improved, the error rate is dramatically reduced; the traditional path based similarity indices are improved, which are much accurate than their antecedent counterparts; and a method for computing the spreading probability for information spreading between two unconnected vertices in the famous independent cascade (IC) model is also obtained. To reveal the effectiveness of the proposed LRA, this article also provide a traversal depth-first search algorithm (DFSA) for finding the true number ofk-hop loop-free paths.

The most fundamental task of network representation learning (NRL) is nodes classification which requires an algorithm to map nodes to vectors and use machine learning models to predict nodes' labels. Recently, many methods based on neighborhood aggregation have achieved brilliant results in this task. However, the recursive expansion of neighborhood aggregation poses scalability and efficiency problems for deep models. Existing methods are limited to shallow architectures and cannot capture the high order proximity in networks. In this article, we propose the deep aggregation network (DAN). DAN uses a layer-wise greedy optimization strategy which stacks several sequential trained base models to form the final deep model. The high order neighborhood aggregation is performed in a dynamic programming manner, which allows the recursion nature of neighborhood aggregation to be eliminated. The reverse random walk is also proposed, and combined with the classic random walk in formulating a novel sampling strategy that allows DAN to flexibly adapt to different tasks related to communities or structural roles. DAN is more efficient and effective than previous neighborhood aggregation based methods, especially when it is intended to handle large-scale networks with dense connections. Extensive experiments are conducted on both synthetic and real-world networks to empirically demonstrate the effectiveness and efficiency of the proposed method.

The minimum vertex cover (MVC) is a well-known combinatorial optimization problem. A game-based memetic algorithm (GMA-MVC) is provided, in which the local search is an asynchronous updating snowdrift game and the global search is an evolutionary algorithm (EA). The game-based local search can implement (k,l)-exchanges for various numbers of k and l to remove k vertices from and add l vertices into the solution set, thus is much better than the previous (1,0)-exchange. Beyond that, the proposed local search is able to deal with the constraint, such that the crossover operator can be very simple and efficient. Degree-based initialization method is also provided which is much better than the previous uniform random initialization. Each individual of the GMA-MVC is designed as a snowdrift game state of the network. Each vertex is treated as an intelligent agent playing the snowdrift game with its neighbors, which is the local refinement process. The game is designed such that its strict Nash equilibrium (SNE) is always a vertex cover of the network. Most of the SNEs are only local optima of the problem. Then an EA is employed to guide the game to escape from those local optimal Nash equilibriums to reach a better Nash equilibrium. From comparison with the state of the art algorithms in experiments on various networks, the proposed algorithm always obtains the best solutions.

Community detection is important in understanding the structures and functions of complex networks. Many algorithms have been proposed. The most popular algorithms detect the communities through optimizing a criterion function known as modularity, which suffer from the resolution limit problem. Some algorithms require the number of communities as a prior. In this paper, a non-modularity based compression optimization algorithm for community detection is proposed without any prior knowledge, which is efficient and is suitable for large scale networks.

Recently, MOEA/D (multi-objective evolutionary algorithm based on decomposition) has achieved great success in the field of evolutionary multi-objective optimization and has attracted a lot of attention. It decomposes a multi-objective optimization problem (MOP) into a set of scalar subproblems using uniformly distributed aggregation weight vectors and provides an excellent general algorithmic framework of evolutionary multi-objective optimization. Generally, the uniformity of weight vectors in MOEA/D can ensure the diversity of the Pareto optimal solutions, however, it cannot work as well when the target MOP has a complex Pareto front (PF; i.e., discontinuous PF or PF with sharp peak or low tail). To remedy this, we propose an improved MOEA/D with adaptive weight vector adjustment (MOEA/D-AWA). According to the analysis of the geometric relationship between the weight vectors and the optimal solutions under the Chebyshev decomposition scheme, a new weight vector initialization method and an adaptive weight vector adjustment strategy are introduced in MOEA/D-AWA. The weights are adjusted periodically so that the weights of subproblems can be redistributed adaptively to obtain better uniformity of solutions. Meanwhile, computing efforts devoted to subproblems with duplicate optimal solution can be saved. Moreover, an external elite population is introduced to help adding new subproblems into real sparse regions rather than pseudo sparse regions of the complex PF, that is, discontinuous regions of the PF. MOEA/D-AWA has been compared with four state of the art MOEAs, namely the original MOEA/D, Adaptive-MOEA/D, [Formula: see text]-MOEA/D, and NSGA-II on 10 widely used test problems, two newly constructed complex problems, and two many-objective problems. Experimental results indicate that MOEA/D-AWA outperforms the benchmark algorithms in terms of the IGD metric, particularly when the PF of the MOP is complex.

A number of studies has focused on the community detection in complex networks in recent years. Single-objective approaches which have only one optimization function (e.g., modularity or modularity density) may have weaknesses such as just a single community structure can be obtained or resolution limit. In this paper, a spectral clustering-based adaptive hybrid multi-objective harmony search algorithm (SCAH-MOHSA) combined with a local search strategy is proposed to detect the community structure in complex networks. At first, an improved spectral method is employed to convert the community detection problem into a data clustering issue while the length of the representation of a harmony in the harmony memory can be determined. Then, an adaptive hybrid multi-objective harmony search algorithm is used to solve the multi-objective optimization problem so as to resolve the community structure. The experiments on both synthetic and real world networks demonstrate our method achieves partition results which fit the real situation in an even better fashion.