Search

The Graph Minors Structure Theorem of Robertson and Seymour asserts that, for every graph H, every H-minor-free graph can be obtained by clique-sums of "almost embeddable" graphs. Here a graph is "almost embeddable" if it can be obtained from a graph of bounded Euler-genus by pasting graphs of bounded pathwidth in an "orderly fashion" into a bounded number of faces, called the vortices, and then adding a bounded number of additional vertices, called apices, with arbitrary neighborhoods. Our main result is a full classification of all graphs H for which the use of vortices in the theorem above can be avoided. To this end, we identify a (parametric) graph \(\mathscr{S}_{t}\) and prove that all \(\mathscr{S}_{t}\) -minor-free graphs can be obtained by clique-sums of graphs embeddable in a surface of bounded Euler-genus after deleting a bounded number of vertices. We show that this result is tight in the sense that the appearance of vortices cannot be avoided for H-minor-free graphs, whenever H is not a minor of \(\mathscr{S}_{t}\) for some \(t\in \mathbb {N}\). Using our new structure theorem, we design an algorithm that, given an \(\mathscr{S}_{t}\) -minor-free graph G, computes the generating function of all perfect matchings of G in polynomial time. Our results, combined with known complexity results, imply a complete characterization of minor-closed graph classes where the number of perfect matchings is polynomially computable: They are exactly those graph classes that do not contain every \(\mathscr{S}_{t}\) as a minor. This provides a sharp complexity dichotomy for the problem of counting perfect matchings in minor-closed classes. [ABSTRACT FROM AUTHOR]

The article focuses on studying randomized greedy matching algorithms, particularly the Modified Randomized Greedy (MRG) algorithm and its weaker version named Random Decision Order (RDO). It mentions the RDO algorithm is shown to provide a 0.639-approximation for bipartite graphs and a 0.531-approximation for general graphs, leading to a substantial improvement in the approximation ratio of MRG.

We prove that in a connected graph, the distances between non-cut vertices are odd if and only if it is the line graph of a strong unique independence tree. We then show that any such tree can be inductively constructed from stars using a simple operation. Further, we study the connected graphs in which the distances between non-cut vertices are even (shortly, NCE-graphs). Our main results on NCE-graphs are the following: we give a criterion of NCE-graphs, show that any bipartite graph is an induced subgraph of an NCE-graph, characterize NCE-graphs with exactly two leaves, characterize graphs that can be subdivided to NCE-graphs, and provide a characterization for NCE-graphs which are maximal with respect to the edge addition operation. [ABSTRACT FROM AUTHOR]

A perfect Roman {3}‐dominating function on a graph G = (V, E) is a function f : V⟶{0, 1, 2, 3} having the property that if f(v) = 0, then ∑u∈N(v)f(u) = 3, and if f(v) = 1, then ∑u∈N(v)f(u) = 2 for any vertex v ∈ V. The weight of a perfect Roman {3}‐dominating function f is the sum ∑v∈Vf(v). The perfect Roman {3}‐domination number of a graph G, denoted by γR3pG, is the minimum weight of a perfect Roman {3}‐dominating function on G. In this paper, we initiate the study of a perfect Roman {3}‐domination, and we show that the decision problem associated with a perfect Roman {3}‐domination is NP‐complete for bipartite graphs. We also prove that if T is a tree of order n ≥ 2, then γR3pT≤32n/ and characterize trees achieving this bound, and we give an infinity set of trees T of order n for which γR3pT approaches this bound as n goes to infinity. Finally, we give the best upper bound of γR3pG for some classes of graphs including regular, planar, and split graphs in terms of the order of the graphs. [ABSTRACT FROM AUTHOR]

The deployment of increasingly diverse services on edge devices is becoming increasingly prevalent. Efficiently deploying functionally heterogeneous services to resource heterogeneous edge nodes while achieving superior user experience is a challenge that every edge system must address. In this paper, we propose a container-node graph (CN-Graph)-based container optimal matching deployment algorithm, edge Kuhn-Munkres algorithm (EKM) based on container-node graph, designed for heterogeneous environment to optimize system performance. Initially, containers are categorized by functional labels, followed by construction of a CN-Graph model based on the relationship between containers and nodes. Finally, the container deployment problem is transformed into a weighted bipartite graph optimal matching problem. In comparison with the mainstream container deployment algorithms, Swarm, Kubernetes, and the recently emerged ECSched-dp algorithm, the EKM algorithm demonstrates the ability to effectively enhance the average runtime performance of containers to 3.74 times, 4.10 times, and 2.39 times, respectively. [ABSTRACT FROM AUTHOR]

Introduction: Semantic network analysis is an important tool researchers can use to untangle the knots of tension that arise as communities debate and discuss complex issues. Yet words connect not only to each other in community discourse but to larger themes or issues. Methods: In this paper, we demonstrate the use of multilayer analysis for the study of semantic networks, helping to unravel connections within and between community tensions. In examining knotted tensions that arise in the wake of disaster, this study also spotlights how climate disasters exacerbate issues like housing equity, disproportionately affecting lower-income communities. We examine discourse across eight months of online neighborhood threads about community issues in the aftermath of Hurricane Ida. We identify core tensions related to environmental sustainability, overdevelopment, neighborhood identity preservation, and economic vitality. Our within-tension analysis reveals the community's struggle with such dilemmas, while our between-tension analysis shows the interconnectedness of these issues. Our approach highlights which stakeholders are best positioned to address specific community problems. Results: The findings challenge the conventional top-down disaster response narrative, proposing a theoretically informed method for employing semantic network analysis to examine community crises. Through this work, we extend organizational communication theories of knotted tensions, offering a nuanced lens to community discourse in the face of wicked problems. [ABSTRACT FROM AUTHOR]

Kalman filter (KF)-based methods for 3D multi-object tracking (MOT) in autonomous driving often face challenges when detections are missed due to occlusions, sensor noise, or objects moving out of view. This leads to data association failures and cumulative errors in the update stage, as traditional Kalman filters rely on linear state estimates that can drift significantly without measurement updates. To address this issue, we propose an enhanced Kalman filter with dummy nodes and prediction confidence (KDPBTracker) to improve tracking continuity and robustness in these challenging scenarios. First, we designed dummy nodes to act as pseudo-observations generated from past and nearby frame detections in cases of missed detection, allowing for stable associations within the data association matrix when real detections were temporarily unavailable. To address the uncertainty in these dummy nodes, we then proposed a prediction confidence score to reflect their reliability in data association. Additionally, we modified a constant acceleration motion model combined with position-based heading estimation to better control high-dimensional numerical fluctuations in the covariance matrix, enhancing the robustness of the filtering process, especially in highly dynamic scenarios. We further designed bipartite graph data association to refine Kalman filter updates by integrating geometric and motion information weighted by the prediction confidence of the dummy nodes. Finally, we designed a confidence-based retention track management module to dynamically manage track continuity and deletion based on temporal and reliability thresholds, improving tracking accuracy in complex environments. Our method achieves state-of-the-art performance on the nuScenes validation set, improving AMOTA by 1.8% over the baseline CenterPoint. Evaluation on the nuScenes dataset demonstrates that KDPBTracker significantly improves tracking accuracy, reduces ID switches, and enhances overall tracking continuity under challenging conditions. [ABSTRACT FROM AUTHOR]

In today's fast-evolving technological environment, ensuring confidentiality is of utmost importance. Cryptography stands as a critical discipline in safeguarding information from unauthorized access. It employs various encryption algorithms to secure data effectively. As digital threats evolve, there's a growing demand for unconventional encryption methods to counter traditional cyber-attacks. This paper introduces innovative encryption algorithms leveraging special graphs and public key cryptography techniques, enhancing security through modular arithmetic properties and enabling more robust communication safeguards. A partition V1, V2, . . ., Vk of the vertex set V is called a chromatic partition of G if each Vi, 1 = i = k is an independent set of G. The minimum order of a chromatic partition of G is called chromatic number X(G). A chromatic partition of G is called an ordered partition if |V1| = β0 and |Vi| = β0(V − ∪i j=1Vj). The order of a minimum ordered chromatic partition of G is called ordered chromatic number χ1(G). It is immediate that χ1(G) ≥ χ(G). In this paper we extend Nordhaus Gaddum results to ordered chromatic number. [ABSTRACT FROM AUTHOR]

We study the algebraic connectivity for several classes of random semi-regular graphs. For large random semi-regular bipartite graphs, we explicitly compute both their algebraic connectivity as well as the full spectrum distribution. For an integer d ∈ 3 , 7 , we find families of random semi-regular graphs that have higher algebraic connectivity than random d-regular graphs with the same number of vertices and edges. On the other hand, we show that regular graphs beat semi-regular graphs when d ≥ 8 . More generally, we study random semi-regular graphs whose average degree is d, not necessarily an integer. This provides a natural generalization of a d-regular graph in the case of a non-integer d . We characterize their algebraic connectivity in terms of a root of a certain sixth-degree polynomial. Finally, we construct a small-world-type network of an average degree of 2.5 with relatively high algebraic connectivity. We also propose some related open problems and conjectures. [ABSTRACT FROM AUTHOR]

The threshold protocol game is a graphical game that models the adoption of an idea or product through a population. There are two states players may take in the game, and the goal of the game is to motivate the state that begins in the minority to spread to every player. Here, the threshold protocol game is defined, and existence results are studied on infinite graphs. Many generalizations are proposed and applied. This work explores the impact of graph topology on the outcome of the threshold protocol game and consequently considers finite graphs. By exploiting the well-known topologies of complete and complete bipartite graphs, the outcome of the threshold protocol game can be fully characterized on these graphs. These characterizations are ideal, as they are given in terms of the game parameters. More generally, initial conditions in terms of game parameters that cause the preferred game outcome to occur are identified. It is shown that the necessary conditions differ between non-bipartite and bipartite graphs because non-bipartite graphs contain odd cycles while bipartite graphs do not. These results motivate the primary result of this work, which is an exhaustive list of achievable game outcomes on bipartite graphs. While possible outcomes are identified, it is noted that a complete characterization of when game outcomes occur is not possible on general bipartite graphs. [ABSTRACT FROM AUTHOR]

Solving maximum matching problems in bipartite graphs is critical in fields such as computational biology and social network analysis. This study introduces HybridGNN, a novel Graph Neural Network model designed to efficiently address complex matching problems at scale. HybridGNN leverages a combination of Graph Attention Networks (GATv2), Graph SAGE (SAGEConv), and Graph Isomorphism Networks (GIN) layers to enhance computational efficiency and model performance. Through extensive ablation experiments, we identify that while the SAGEConv layer demonstrates suboptimal performance in terms of accuracy and F1-score, configurations incorporating GATv2 and GIN layers show significant improvements. Specifically, in six-layer GNN architectures, the combinations of GATv2 and GIN layers with ratios of 4:2 and 5:1 yield superior accuracy and F1-score. Therefore, we name these GNN configurations HybridGNN1 and HybridGNN2. Additionally, techniques such as mixed precision training, gradient accumulation, and Jumping Knowledge networks are integrated to further optimize performance. Evaluations on an email communication dataset reveal that HybridGNNs outperform traditional algorithms such as the Hopcroft–Karp algorithm, the Hungarian algorithm, and the Blossom/Edmonds' algorithm, particularly for large and complex graphs. These findings highlight HybridGNN's robust capability to solve maximum matching problems in bipartite graphs, making it a powerful tool for analyzing large-scale and intricate graph data. Furthermore, our study aligns with the goals of the Symmetry and Asymmetry Study in Graph Theory special issue by exploring the role of symmetry in bipartite graph structures. By leveraging GNNs, we address the challenges related to symmetry and asymmetry in graph properties, thereby improving the reliability and fault tolerance of complex networks. [ABSTRACT FROM AUTHOR]

Personalized recommendation can recommend items of interest to different users and is widely used in the real world. Among them, graph collaborative filtering is a method of personalized recommendation. It can enrich the connection between users and items on the basis of collaborative filtering, to learn the embedded representation of nodes more accurately. Since graph collaborative filtering is based on bipartite graphs, few exciting graph collaborative methods consider the relationships between users (or items), the message between homogeneous nodes are diluted or ignored. Predicting and constructing the relationship between users (or items) has become a challenging. To solve this problem, we propose an enhanced sub-graph reconstruction graph neural network for recommendation (SRCF), using a heterogeneous graph neural network based encoder-decoder learn potential relationships between users (or items), and reconstruct sub-graphs based on those relationships. In the proposed model, the information of user and item sub-graphs is merged with the network of graph collaborative filtering, which enhances effective information transfer between homogeneous nodes, thereby improving the model performance. We have selected a number of data sets of different scenarios and different scales to comprehensively evaluate the performance of the model, and the experimental results confirmed the superiority of our model. [ABSTRACT FROM AUTHOR]

A bipartite graph G(X, Y) is called a star-convex bipartite graph with convexity on X if there is an associated star T(X, F), such that for each vertex in Y, its neighborhood in X induces a subtree in T. A graph G is said to be a split graph if G can be partitioned into a clique (K) and an independent set (I). The objective of this study is twofold: (i) to strengthen the complexity results presented in Chen et al. (J Comb Optim 32(1):95–110, 2016) for the Hamiltonian cycle (HCYCLE), the Hamiltonian path (HPATH), and the Domination (DS) problems on star-convex bipartite graphs (ii) to reinforce the results of Müller (Discret Math 156(1–3):291–298, 1996) for HCYCLE, and HPATH on split graphs by introducing a convex ordering on one of the partitions (K or I). As part of our fine-grained analysis study with the diameter being the parameter, we first show that the diameter of star-convex bipartite graphs is at most six. Next, we observe that the reduction instances of Chen et al. (J Comb Optim 32(1):95–110, 2016) are star-convex bipartite graphs with at most diameter 4, and hence HCYCLE and HPATH are NP-complete on star-convex bipartite graphs with at most diameter 4. We strengthen this result and establish the following results on star-convex bipartite graphs: (i) HCYCLE is NP-complete for diameter 3, and polynomial-time solvable for diameters 2, 5, and 6 (a transformation in complexity: P to NPC to P) (ii) HPATH is polynomial-time solvable for diameter 2, and NP-Complete, otherwise (a dichotomy). Further, with convexity being the parameter, for split graphs with convexity on K (resp. I), we show that HCYCLE and HPATH are NP-complete on star-convex (resp. comb) split graphs with convexity on K (resp. I). Further, we show that HCYCLE is NP-complete on k 1 , r -free star-convex split graphs with convexity on I, r ≥ 6 . On the positive side, we show that for K 1 , 5 -free star-convex split graphs with convexity on I, HCYCLE is polynomial-time solvable. Thus, we establish a dichotomy for HCYCLE on star-convex split graphs with convexity on I. We further show that the dominating set problem (DS) and its variants (resp. Connected, Total, Outer-Connected, and Dominating biclique) are NP-complete on star-convex bipartite graphs with diameter 3 (resp. diameter 5, and diameter 6). On the parameterized complexity front, we prove that the parameterized version of the domination problem and its variants, with the parameter being the solution size, is not fixed-parameter tractable for star-convex bipartite graphs with diameter 3 (resp. diameter 5, and diameter 6), whereas it is fixed-parameter tractable when the parameter is the number of leaves in the associated star. Further, we show that for star-convex bipartite graphs with diameters 5, and 6, the domination problem and its variants cannot be approximated within (1 - ϵ) ln n unless NP ⊆ T I M E (2 n o (1) ) . [ABSTRACT FROM AUTHOR]

Let n1, n2, . . ., nk be integers and V1, V2, . . ., Vk be disjoint vertex sets with [Vi] = ni for each i = 1, 2, . . ., k. A k-partite k-uniform hypergraph on vertex classes V1, V2, . . ., Vk is defined to be the k-uniform hypergraph whose edge set consists of the k-element subsets S of V1 ∪ V2 ∪ ⋯ ∪ Vk such that [S ∩ Vi] = 1 for all i = 1, 2, . . ., k. We say that it is balanced if n1 = n2 = ⋯ = nk. In this paper, we give a distance spectral radius condition to guarantee the existence of perfect matching in k-partite k-uniform hypergraphs, this result generalize the result of Zhang and Lin [Perfect matching and distance spectral radius in graphs and bipartite graphs, Discrete Appl. Math., 304 (2021) 315-322]. [ABSTRACT FROM AUTHOR]

Consider a graph G = (V (G);E(G)), where a perfect matching in G is defined as a subset of independent edges with ... elements. A global forcing set is a subset S of E such that no two disjoint perfect matchings of G coincide on it. The minimum cardinality of global forcing sets of G is called the global forcing number (GFN for short). This paper addresses the NP-hard problem of determining the global forcing number for perfect matchings. The focus is on a Genetic Algorithm (GA) that utilizes binary encoding and standard genetic operators to solve this problem. The proposed algorithm is implemented on some chemical graphs to illustrate the validity of the algorithm. The solutions obtained by the GA are compared with the results from other methods that have been presented in the literature. The presented algorithm can be applied to various bipartite graphs, particularly hexagonal systems. Additionally, the results of the GA improve some results that have already been presented for finding GFN. [ABSTRACT FROM AUTHOR]

The timely and accurate prediction of maize (Zea mays L.) yields prior to harvest is critical for food security and agricultural policy development. Currently, many researchers are using machine learning and deep learning to predict maize yields in specific regions with high accuracy. However, existing methods typically have two limitations. One is that they ignore the extensive correlation in maize planting data, such as the association of maize yields between adjacent planting locations and the combined effect of meteorological features and maize traits on maize yields. The other issue is that the performance of existing models may suffer significantly when some data in maize planting records is missing, or the samples are unbalanced. Therefore, this paper proposes an end-to-end bipartite graph neural network-based model for trait data imputation and yield prediction. The maize planting data is initially converted to a bipartite graph data structure. Then, a yield prediction model based on a bipartite graph neural network is developed to impute missing trait data and predict maize yield. This model can mine correlations between different samples of data, correlations between different meteorological features and traits, and correlations between different traits. Finally, to address the issue of unbalanced sample size at each planting location, we propose a loss function based on the gradient balancing mechanism that effectively reduces the impact of data imbalance on the prediction model. When compared to other data imputation and prediction models, our method achieves the best yield prediction result even when missing data is not pre-processed. [ABSTRACT FROM AUTHOR]

Due to the complex nature and highly heterogeneous of cancer, as well as different pathogenesis and clinical features among different cancer subtypes, it was crucial to identify cancer subtypes in cancer diagnosis, prognosis, and treatment. The rapid developments of high-throughput technologies have dramatically improved the efficiency of collecting data from various types of omics. Also, integrating multi-omics data related to cancer occurrence and progression can lead to a better understanding of cancer pathogenesis, subtype prediction, and personalized treatment options. Therefore, we proposed an efficient multi-omics bipartite graph subspace learning anchor-based clustering (MBSLC) method to identify cancer subtypes. In contrast, the bipartite graph intended to learn cluster-friendly representations. Experiments showed that the proposed MBSLC method can capture the latent spaces of multi-omics data effectively and showed superiority over other state-of-the-art methods for cancer subtype analysis. Moreover, the survival and clinical analyses further demonstrated the effectiveness of MBSLC. The code and datasets of this paper can be found in https://github.com/Julius666/MBSLC. [ABSTRACT FROM AUTHOR]

User–item bipartite graphs and knowledge graphs are frequently employed in recommender systems due to their ability to provide rich information for user and item modeling. However, existing recommender systems predominantly focus on modeling either the user or item individually, with few studies simultaneously considering both aspects. In this paper, we propose a novel double-ended recommendation model, DEKGCI, which aims to fully leverage the advantages of these two information sources. Specifically, DEKGCI harnesses the high-order connectivity information in the user–item bipartite graph to extract user representations, while utilizing the semantic information in the knowledge graph to enrich item representations. By doing so, DEKGCI concurrently learns both user and item representations, effectively capturing the intricate interaction information between users and items. The DEKGCI model was evaluated on three real-world datasets. Computational results demonstrate the high effectiveness of the proposed DEKGCI model compared to seven state-of-the-art reference methods from the literature. In particular, compared to the best-performing KFGAN model, DEKGCI achieved AUC gains of 0.335% in movie recommendations, and F1 gains of 0.023%, 2.203%, and 0.530% in movie, book, and music recommendations, respectively. The code and data are available at https://github.com/miaomiao924/DEKGCI. [ABSTRACT FROM AUTHOR]

Network analysis, element correlation analysis and phylogenetic analysis are applied in the visualization methods study of mineral crystal chemistry data. Taking P-bearing minerals as an example, force-directed network and bipartite network diagram of mineral composition and genesis, phylogenetic tree of mineral crystal characteristics and correlation heat maps of mineral component elements are drawn. These methods also take into account the spatial and temporal distribution, evolutionary diversity and physical and chemical properties of minerals. The use of these visual analysis methods is helpful to explore the evolution of the Earth's environment using mineralogical records through deep time and understand its evolutionary process and driving mechanism. [ABSTRACT FROM AUTHOR]

We develop a model of contests on networks. Each player is connected to a set of contests and exerts a single effort to increase the probability of winning each contest to which she is connected. We explore how behavior is shaped by the pattern of interactions and characterize the networks that tend to induce greater effort; in particular, we show that the complete bipartite network is the unique structure that maximizes aggregate player effort. We also obtain a new exclusion result—akin to the Exclusion Principle of Baye et al. (Am Econ Rev 83(1):289-294, 1993)—which holds under the lottery CSF, and contrasts prior work in contests. Finally, new insight into uniqueness of equilibrium for network contest games is provided. Our framework has a broad range of applications, including research and development, advertising, and research funding. [ABSTRACT FROM AUTHOR]

Given a nonnegative matrix A=(Aij) , the matrix scaling problem asks whether A can be scaled to a doubly stochastic matrix D1AD2 for some positive diagonal matrices D1, D2. The Sinkhorn algorithm is a simple iterative algorithm, which repeats row-normalization Aij←Aij/∑jAij and column-normalization Aij←Aij/∑iAij alternatively. By this algorithm, A converges to a doubly stochastic matrix in limit if and only if the bipartite graph associated with A has a perfect matching. This property can decide the existence of a perfect matching in a given bipartite graph G, which is identified with the 0, 1-matrix AG. Linial et al. (2000) showed that O(n2log n) iterations for AG decide whether G has a perfect matching. Here, n is the number of vertices in one of the color classes of G. In this paper, we show an extension of this result. If G has no perfect matching, then a polynomial number of the Sinkhorn iterations identifies a Hall blocker—a vertex subset X having neighbors Γ(X) with |X|>|Γ(X)| , which is a certificate of the nonexistence of a perfect matching. Specifically, we show that O(n2log n) iterations can identify one Hall blocker and that further polynomial iterations can also identify all parametric Hall blockers X of maximizing (1−λ)|X|−λ|Γ(X)| for λ∈[0,1]. The former result is based on an interpretation of the Sinkhorn algorithm as alternating minimization for geometric programming. The latter is on an interpretation as alternating minimization for Kullback–Leibler (KL) divergence and on its limiting behavior for a nonscalable matrix. We also relate the Sinkhorn limit with parametric network flow, principal partition of polymatroids, and the Dulmage–Mendelsohn decomposition of a bipartite graph. Funding: K. Hayashi was supported by the Japan Society for the Promotion of Science [Grant JP19J22605]. H. Hirai was supported by Precursory Research for Embryonic Science and Technology [Grant JPMJPR192A]. [ABSTRACT FROM AUTHOR]

Consider a bipartite network where N consumers choose to buy or not to buy M different products. This paper considers the properties of the logit fit of the N × M array of "i‐buys‐j" purchase decisions, Y=[Yij]1≤i≤N,1≤j≤M, onto a vector of known functions of consumer and product attributes under asymptotic sequences where (i) both N and M grow large, (ii) the average number of products purchased per consumer is finite in the limit, (iii) there exists dependence across elements in the same row or same column of Y (i.e., dyadic dependence), and (iv) the true conditional probability of making a purchase may, or may not, take the assumed logit form. Condition (ii) implies that the limiting network of purchases is sparse: only a vanishing fraction of all possible purchases are actually made. Under sparse network asymptotics, I show that the parameter indexing the logit approximation solves a particular Kullback–Leibler Information Criterion (KLIC) minimization problem (defined with respect to a certain Poisson population). This finding provides a simple characterization of the logit pseudo‐true parameter under general misspecification (analogous to a (mean squared error (MSE) minimizing) linear predictor approximation of a general conditional expectation function (CEF)). With respect to sampling theory, sparseness implies that the first and last terms in an extended Hoeffding‐type variance decomposition of the score of the logit pseudo composite log‐likelihood are of equal order. In contrast, under dense network asymptotics, the last term is asymptotically negligible. Asymptotic normality of the logistic regression coefficients is shown using a martingale central limit theorem (CLT) for triangular arrays. Unlike in the dense case, the normality result derived here also holds under degeneracy of the network graphon. Relatedly, when there "happens to be" no dyadic dependence in the data set in hand, it specializes to recently derived results on the behavior of logistic regression with rare events and i.i.d. data. Simulation results suggest that sparse network asymptotics better approximate the finite network distribution of the logit estimator. A short empirical illustration, and additional calibrated Monte Carlo experiments, further illustrate the main theoretical ideas. [ABSTRACT FROM AUTHOR]

We determine the forbidden induced subgraphs for the intersection of the classes of chordal bipartite graphs and line graphs of acyclic directed graphs. This is a first step towards finding the forbidden induced subgraphs for the class of line graphs of directed graphs. [ABSTRACT FROM AUTHOR]

Matrix factorization has demonstrated outstanding performance in machine learning. Recently, graph-based matrix factorization has gained widespread attention. However, graph-based methods are only suitable for handling small amounts of data. This paper proposes a fast semi-supervised learning method using only matrix factorization, which considers both global and local information. By introducing bipartite graphs into symmetric matrix factorization, the technique can handle large datasets effectively. It is worth noting that by utilizing tag information, the proposed symmetric matrix factorization becomes convex and unconstrained, i.e., the non-convex problem min x (1 − x 2) 2 is transformed into a convex problem. This allows it to be optimized quickly using state-of-the-art unconstrained optimization algorithms. The computational complexity of the proposed method is O (n m d) , which is much lower than that of the original symmetric matrix factorization, which is O (n 2 d) , and even lower than that of other anchor-based methods, which is O (n m d + m 2 n + m 3) , where n represents the number of samples, d represents the number of features, and m ≪ n represents the number of anchors. The experimental results on multiple public datasets indicate that the proposed method achieves higher performance in less time. [ABSTRACT FROM AUTHOR]

The timely and accurate prediction of maize (Zea mays L.) yields prior to harvest is critical for food security and agricultural policy development. Currently, many researchers are using machine learning and deep learning to predict maize yields in specific regions with high accuracy. However, existing methods typically have two limitations. One is that they ignore the extensive correlation in maize planting data, such as the association of maize yields between adjacent planting locations and the combined effect of meteorological features and maize traits on maize yields. The other issue is that the performance of existing models may suffer significantly when some data in maize planting records is missing, or the samples are unbalanced. Therefore, this paper proposes an end-to-end bipartite graph neural network-based model for trait data imputation and yield prediction. The maize planting data is initially converted to a bipartite graph data structure. Then, a yield prediction model based on a bipartite graph neural network is developed to impute missing trait data and predict maize yield. This model can mine correlations between different samples of data, correlations between different meteorological features and traits, and correlations between different traits. Finally, to address the issue of unbalanced sample size at each planting location, we propose a loss function based on the gradient balancing mechanism that effectively reduces the impact of data imbalance on the prediction model. When compared to other data imputation and prediction models, our method achieves the best yield prediction result even when missing data is not pre-processed. [ABSTRACT FROM AUTHOR]

Given a graph G = (V,E) and a list of available colors L(v) for each vertex v ∈ V, where L(v) ⊆ {1, 2,..., k}, List k-Coloring refers to the problem of assigning colors to the vertices of G so that each vertex receives a color from its own list and no two neighboring vertices receive the same color. The decision version of the problem, List k-Coloring, is NP-complete even for bipartite graphs. As an application of list coloring problem we are interested in the Futoshiki Problem. Futoshiki is an NP-complete Latin Square Completion Type Puzzle. Considering Futoshiki puzzle as a constraint satisfaction problem, we first give a list coloring based algorithm for it which is efficient for small boards of fixed size. To thoroughly investigate the efficiency of our algorithm in comparison with a proposed backtracking-based algorithm, we conducted a substantial number of computational experiments at different difficulty levels, considering varying numbers of inequality constraints and given values. Our results from the extensive range of experiments indicate that the list coloring-based algorithm is much more efficient. [ABSTRACT FROM AUTHOR]

Let GS be the graph of order n and containing σ self-loops. The energy E(GS) of graph GS is defined as E(GS) = n∑i=1 | λi - σ/n |, where λ1, λ2, . . ., λn be the eigenvalues of the adjacency matrix of GS. Two non-isomorphic graphs G1 and G2 of the same order are said to be equienergetic if they have same energy. The proposed research is an effort to expand the concept of equienergetic graphs from simple graphs to graphs having self-loops. In the present work, we have obtained a pair of equienergetic graphs and the energy of complete graphs as well as complete bipartite graphs with self loops. [ABSTRACT FROM AUTHOR]

The identification of drug–target interaction (DTI) is crucial for drug discovery. However, how to reduce the graph neural network's false positives due to its bias and negative transfer in the original bipartite graph remains to be clarified. Considering that the impact of heterogeneous auxiliary information on DTI varies depending on the drug and target, we established an adaptive enhanced personalized meta-knowledge transfer network named Meta Graph Association-Aware Contrastive Learning (MGACL), which can transfer personalized heterogeneous auxiliary information from different nodes and reduce data bias. Meanwhile, we propose a novel DTI association-aware contrastive learning strategy that aligns high-frequency drug representations with learned auxiliary graph representations to prevent negative transfer. Our study improves the DTI prediction performance by about 3%, evaluated by analyzing the area under the curve (AUC) and area under the precision–recall curve (AUPRC) compared with existing methods, which is more conducive to accurately identifying drug targets for the development of new drugs. [ABSTRACT FROM AUTHOR]

Recently, considerable attention has been directed toward graph-based semi-supervised learning (GSSL) as an effective approach for data labeling. Despite the progress achieved by current methodologies, several limitations persist. Firstly, many studies treat all samples equally in terms of weight and influence, disregarding the potential increased importance of samples near decision boundaries. Secondly, the detection of outlier-labeled data is crucial, as it can significantly impact model performance. Thirdly, existing models often struggle with predicting labels for unseen test data, restricting their utility in practical applications. Lastly, most graph-based algorithms rely on affinity matrices that capture pairwise similarities across all data points, thus limiting their scalability to large-scale databases. In this paper, we propose a novel GSSL algorithm tailored for large-scale databases, leveraging anchor points to mitigate the challenges posed by large affinity matrices. Additionally, our method enhances the influence of nodes near decision boundaries by assigning different weights based on their importance and using a mapping function from feature space to label space. Leveraging this mapping function enables direct label prediction for test samples without requiring iterative learning processes. Experimental evaluations on two extensive datasets (Norb and Covtype) demonstrate that our approach is scalable and outperforms existing GSSL methods in terms of performance metrics. [ABSTRACT FROM AUTHOR]

In this paper, we introduce an efficient and effective algorithm for Graph-based Semi-Supervised Learning (GSSL). Unlike other GSSL methods, our proposed algorithm achieves efficiency by constructing a bipartite graph, which connects a small number of representative points to a large volume of raw data by capturing their underlying manifold structures. This bipartite graph, with a sparse and anti-diagonal affinity matrix which is symmetrical, serves as a low-rank approximation of the original graph. Consequently, our algorithm accelerates both the graph construction and label propagation steps. In particular, on the one hand, our algorithm computes the label propagation in closed-form, reducing its computational complexity from cubic to approximately linear with respect to the number of data points; on the other hand, our algorithm calculates the soft label matrix for unlabeled data using a closed-form solution, thereby gaining additional acceleration. Comprehensive experiments performed on six real-world datasets demonstrate the efficiency and effectiveness of our algorithm in comparison to five state-of-the-art algorithms. [ABSTRACT FROM AUTHOR]

With the widespread adoption of metagenomic sequencing, new perspectives have emerged for studying microbial ecological networks, yielding metabolic evidence of interspecies interactions that traditional co‐occurrence networks cannot infer. This protocol introduces the integrated Network Analysis Pipeline 2.0 (iNAP 2.0), which features an innovative metabolic complementarity network for microbial studies from metagenomics sequencing data. iNAP 2.0 sets up a four‐module process for metabolic interaction analysis, namely: (I) Prepare genome‐scale metabolic models; (II) Infer pairwise interactions of genome‐scale metabolic models; (III) Construct metabolic interaction networks; and (IV) Analyze metabolic interaction networks. Starting from metagenome‐assembled or complete genomes, iNAP 2.0 offers a variety of methods to quantify the potential and trends of metabolic complementarity between models, including the PhyloMint pipeline based on phylogenetic distance‐adjusted metabolic complementarity, the SMETANA (species metabolic interaction analysis) approach based on cross‐feeding substrate exchange prediction, and metabolic distance calculation based on parsimonious flux balance analysis (pFBA). Notably, iNAP 2.0 integrates the random matrix theory (RMT) approach to find the suitable threshold for metabolic interaction network construction. Finally, the metabolic interaction networks can proceed to analysis using topological feature analysis such as hub node determination. In addition, a key feature of iNAP 2.0 is the identification of potentially transferable metabolites between species, presented as intermediate nodes that connect microbial nodes in the metabolic complementarity network. To illustrate these new features, we use a set of metagenome‐assembled genomes as an example to comprehensively document the usage of the tools. iNAP 2.0 is available at https://inap.denglab.org.cn for all users to register and use for free. Highlights: The updated integrated Network Analysis Pipeline (iNAP 2.0) is an advanced platform that facilitates the calculation of various metabolic complementarity and competition indices, including the PhyloMint index, SMETANA (species metabolic interaction analysis), and metabolic distance, as well as the construction and analysis of metabolic interaction networks.Innovatively, iNAP 2.0 uses the random matrix theory (RMT) approach to determine the threshold for metabolic interaction networks.PhyloMint PTM in iNAP 2.0 allows users to view potentially transferable metabolites between microbial interactions and integrate them as network nodes to construct a microbe‐metabolite bipartite network alongside the microbial interaction network. [ABSTRACT FROM AUTHOR]

The concept of Roman domination has been a subject of intrigue for more than two decades, with the fundamental Roman domination problem standing out as one of the most significant challenges in this field. This article studies a practically motivated generalization of this problem, known as the k-strong Roman domination. In this problem variant, defenders within a network are tasked with safeguarding any k vertices simultaneously, under multiple attacks. The aim is to find a feasible mapping that assigns a (integer) weight to each vertex of the input graph with a minimum sum of weights across all vertices. A function is considered feasible if any non-defended vertex, i.e. one labeled by zero, is protected by at least one of its neighboring vertices labeled by at least two. Furthermore, each defender ensures the safety of a non-defended vertex by imparting a value of one to it while retaining a one for themselves. To the best of our knowledge, this paper represents the first theoretical study on this problem. The study presents results for general graphs, establishes connections between the problem at hand and other domination problems, and provides exact values and bounds for specific graph classes, including complete graphs, paths, cycles, complete bipartite graphs, grids, and a few selected classes of convex polytopes. Additionally, an attainable lower bound for general cubic graphs is provided. [ABSTRACT FROM AUTHOR]

Sombor index of a graph G is defined by SO(G) = ∑uv∈E(G) √d² G(u) + d² G(v), where dG(v) is the degree of the vertex v of G. An r-degree graph is a graph whose degree sequence includes exactly r distinctive numbers. In this article, we study r-degree connected graphs with integer Sombor index for r ∈ {5, 6, 7}. We show that: if G is a 5-degree connected graph of order n with integer Sombor index then n ≥ 50 and the equality occurs if only if G is a bipartite graph of size 420 with SO(G) = 14830; if G is a 6-degree connected graph of order n with integer Sombor index then n ≥ 75 and the equality is established only for the bipartite graph of size 1080; and if G is a 7-degree connected graph of order n with integer Sombor index then n ≥ 101 and the equality is established only for the bipartite graph of size 1680. [ABSTRACT FROM AUTHOR]

Graph neural networks (GNNs) have indeed shown significant potential in the field of personalized recommendation. The core approach is to reorganize interaction data into a user–item bipartite graph, leveraging high-order connectivity between user and item nodes to enhance their representations. However, most existing methods only deploy graph neural networks on parallel interaction graphs and treat the information propagated from all neighbors as equivalent, failing to adaptively capture user preferences. Therefore, the representations obtained may contain redundant or even noisy information, leading to non-robustness and suboptimal performance. The recently proposed Multimodal Graph Attention Network (MGAT) disentangles personal interests at the granularity of modality, operating on individual modal interaction graphs while utilizing a gated attention mechanism to differentiate the impacts of different modalities on user preferences. However, MGAT merely uses averaging to fuse multimodal features, which might overlook unique or critical information within each modality. To address this issue, this paper proposes a multimodal preference-based graph attention network. Firstly, for each individual modality, a single-modality graph network is constructed by integrating the user–item interaction bipartite graph, enabling it to learn user preferences for that modality. GNNs are used to aggregate neighborhood information and enhance the representation of each node. Additionally, a GRU module is utilized to determine whether to aggregate neighborhood information, thereby achieving noise reduction. In addition, a lightweight complementary attention mechanism is proposed to fuse user and item representations learned from different modal graphs. The complementary attention mechanism can not only avoid information redundancy, but also alleviate the problem of modal loss to a certain extent, and ultimately input the fusion results into the prediction module. Experimental results on the MovieLens and TikTok datasets demonstrate the effectiveness of the multimodal information and attention fusion mechanism in improving recommendation accuracy. Compared to baseline state-of-the-art algorithms, the proposed model achieves significant improvements in the Precision@K, Recall@K, NDCG@K and AUC metrics. Our code is publicly available on GitHub: [https://github.com/Oasisway624/mgpat]. [ABSTRACT FROM AUTHOR]

Network analysis has become a crucial tool in genetic research, enabling the exploration of associations between genes and diseases. Its utility extends beyond genetics to include the assessment of environmental factors. Unipartite network analysis is commonly used in genomics to visualize initial insights and relationships among variables. Syndromic diseases, such as metabolic syndrome, are characterized by the simultaneous occurrence of various signs, symptoms, and clinicopathological features. Metabolic syndrome encompasses hypertension, diabetes, obesity, and dyslipidemia, and both genetic and environmental factors contribute to its development. Given that relevant data often consist of distinct sets of variables, a more intuitive visualization method is needed. This study applied multipartite network analysis as an effective method to understand the associations among genetic, environmental, and disease components in syndromic diseases. We considered three distinct variable sets: genetic factors, environmental factors, and disease components. The process involved projecting a tripartite network onto a two-mode bipartite network and then simplifying it into a one-mode network. This approach facilitated the visualization of relationships among factors across different sets and within individual sets. To transition from multipartite to unipartite networks, we suggest both sequential and concurrent projection methods. Data from the Korean Association Resource (KARE) project were utilized, including 352,228 SNPs from 8840 individuals, alongside information on environmental factors such as lifestyle, dietary, and socioeconomic factors. The single-SNP analysis step filtered SNPs, supplemented by reference SNPs reported in a genome-wide association study catalog. The resulting network patterns differed significantly by sex: demographic factors and fat intake were crucial for women, while alcohol consumption was central for men. Indirect relationships were identified through projected bipartite networks, revealing that SNPs such as rs4244457, rs2156552, and rs10899345 had lifestyle interactions on metabolic components. Our approach offers several advantages: it simplifies the visualization of complex relationships among different datasets, identifies environmental interactions, and provides insights into SNP clusters sharing common environmental factors and metabolic components. This framework provides a comprehensive approach to elucidate the mechanisms underlying complex diseases like metabolic syndrome. [ABSTRACT FROM AUTHOR]

Due to their large size and obligate nature, Cymothoid isopods inflict a high degree of tissue damage to fish. Still, they are understudied at an ecosystem level despite their global presence and ecological role. In this work, we collected fish host‐isopod parasite data, along with their life history and ecological traits, from the northern part of the east coast of India and investigated patterns in host specialisation and preference of isopod parasites using a trait‐based network perspective. We observed that the region of attachment of the parasite (buccal cavity, branchial cavity, and skin) and host fish ecology (schooling behaviour and habitat characteristics) influenced host specialisation and preference. We found that branchial cavity‐attaching parasites preferred schooling, pelagic fishes, whereas buccal cavity‐attaching parasites preferred mostly non‐schooling, demersal fishes. Skin‐attaching parasites were found to be generalists and had no preference based on our examined host traits. [ABSTRACT FROM AUTHOR]

In this paper, we present a noise-robust approach for the 3D pose estimation of multiple people using appearance similarity. The common methods identify the cross-view correspondences between the detected keypoints and determine their association with a specific person by measuring the distances between the epipolar lines and the joint locations of the 2D keypoints across all the views. Although existing methods achieve remarkable accuracy, they are still sensitive to camera calibration, making them unsuitable for noisy environments where any of the cameras slightly change angle or position. To address these limitations and fix camera calibration error in real-time, we propose a framework for 3D pose estimation which uses appearance similarity. In the proposed framework, we detect the 2D keypoints and extract the appearance feature and transfer it to the central server. The central server uses geometrical affinity and appearance similarity to match the detected 2D human poses to each person. Then, it compares these two groups to identify calibration errors. If a camera with the wrong calibration is identified, the central server fixes the calibration error, ensuring accuracy in the 3D reconstruction of skeletons. In the experimental environment, we verified that the proposed algorithm is robust against false geometrical errors. It achieves around 11.5% and 8% improvement in the accuracy of 3D pose estimation on the Campus and Shelf datasets, respectively. [ABSTRACT FROM AUTHOR]

Simple Summary: This study investigates the complex interactions between quill mites of the family Syringophilidae and starlings. We identified five species of quill mites infesting 24 species of starlings, uncovering intricate host–parasite dynamics across the Palaearctic, Afrotropical, Oriental, and Oceanian zoogeographical regions. A detailed statistical analysis of the Picobiinae–Sturnidae network revealed low connectivity but high modularity, indicating specific relationships between the mites and their starling hosts. The network structure demonstrated four distinct modules, highlighting the specialised and compartmentalised characteristics of these associations. Furthermore, the distribution of Picobia mites was found to align with the phylogeny of their starling hosts, with particular mites targeting specific starling clades. The social and breeding behaviours of starlings were observed to contribute to the high prevalence of these mites. This comprehensive network analysis provides new insights into the ecological dynamics of host–parasite interactions. The subfamily Picobiinae (Acariformes: Syringophilidae) comprises obligate and permanent parasites of birds found exclusively in the quills of contour feathers. We studied associations of picobiine mites with birds of the family Sturnidae (Aves: Passeriformes) across the Palaearctic, Afrotropical, Oriental, and Oceanian zoogeographical regions. Among the 414 examined bird individuals belonging to 44 species (35.2% of all sturnids), 103 individuals from 24 species (54.5% of examined species) were parasitised by quill mites. The diversity of mites was represented by five species, including one newly described, Picobia malayi Patan and Skoracki sp. n. Statistical analysis of the Picobiinae–Sturnidae bipartite network demonstrated a low connectance value (Con = 0.20) and high modularity, with significant differences in the H2′ specialisation index compared to null model values. The network structure, characterised by four distinct modules, highlighted the specificity and limited host range of the Picobiinae–Sturnidae associations. The distribution of Picobia species among starlings was congruent with the phylogeny of their hosts, with different mites parasitising specific clades of starlings. Additionally, the findings suggest that the social and breeding behaviours of starlings influence quite a high prevalence. Finally, our studies support the validity of museum collections to study these parasitic interactions. [ABSTRACT FROM AUTHOR]

Chain graphs and threshold graphs play a very important role in Spectral Graph Theory, since the maximizers for the largest eigenvalue of the adjacency matrix (for graphs of fixed order and size, either connected or disconnected) belong to these classes (threshold graphs in the general case, and chain graphs in the bipartite case). Nesting in the neighborhood of vertices in these graphs has gained the attention of various researchers. Motivated by this structure, we generalize and define a new class of graphs named it as 'partial threshold graphs' and study the properties. In this article, we give bounds and expressions for the Wiener index and Hyper-Wiener index of a partial threshold graph. We extend the study further and give a set of integers, except which every other integer is the Wiener index of some partial threshold graph. The highlight of the article is an algorithm for the inverse Wiener index problem of partial threshold graphs. [ABSTRACT FROM AUTHOR]

Social recommendation often incorporates trusted social links with user-item interactions to enhance rating prediction. Although methods that aggregate explicit social links have shown promising prospects, they are often constrained by the absence of explicit social data and the assumption of homogeneity, thus overlooking variations in social influence and consistency. These limitations hinder semantic expression and recommendation performance. Therefore, we propose a novel framework for social recommendation. First, we design a bipartite network embedding scheme, which learns vertex representations in the embedding space by modeling 1st-order explicit relations and higher-order implicit relations between vertices. Then, the similarity of the embedding vectors is used to extract top-k semantically consistent friends for each user. Next, we design an algorithm to assign a specific influence value to each user. Finally, we combine the top-k friends of the user and their influence values into an ensemble and add it as a regularization term to the rating prediction process of the user to correct the bias. Experiments on three real benchmark datasets show significant improvements in EISF over state-of-the-art methods. [ABSTRACT FROM AUTHOR]

Innovative Industrial Clusters (IIC), characterized by geographical aggregation and technological collaboration among technology enterprises and institutions, serve as pivotal drivers of regional economic competitiveness and technological advancements. Prior research on cluster identification, crucial for IIC analysis, has predominantly emphasized geographical dimensions while overlooking technological proximity. Addressing these limitations, this study introduces a comprehensive framework incorporating multiple indices and methods for accurately identifying IIC using patent data. To unearth latent technological insights within patent documents, Latent Dirichlet Allocation (LDA) is employed to generate topics from a collection of terms. Utilizing the applicants' names and addresses recorded in patents, an Application Programming Interface (API) map systems facilitates the extraction of geographic locations. Subsequently, a Multivariate Density-Based Spatial Clustering of Applications with Noise (MDBSCAN) algorithm, which accounts for both technological and spatial distances, is deployed to delineate IIC. Moreover, a bipartite network model based on patent geographic information collected from the patent is constructed to analyze the technological distribution on the geography and development mode of IIC. The utilization of the model and methodologies is demonstrated through a case study on the China flexible electronics industry (FEI). The findings reveal that the clusters identified via this novel approach are significantly correlated with both technological innovation and geographical factors. Moreover, the MDBSCAN algorithm demonstrates notable superiority over other algorithms in terms of computational precision and efficiency, as evidenced by the case analysis. [ABSTRACT FROM AUTHOR]

We consider the controllability of multi-agent dynamical systems modeled by a particular class of bipartite graphs, called chain graphs. Our main focus is related to chain graphs with exactly one repeated degree. We determine all chain graphs with this structural property and derive some properties of their Laplacian eigenvalues and associated eigenvectors. On the basis of the obtained theoretical results, we compute the minimum number of leading agents that make the system in question controllable and locate the leaders in the corresponding graph. Additionaly, we prove that a chain graph with exactly one repeated degree, that is not a star or a regular complete bipartite graph, has the second smallest Laplacian eigenvalue (also known as the algebraic connectivity) in (0.8299,1) and we show that the second smallest eigenvalue increases when the number of vertices increases. This result is of a particular interest in control theory, since families of controllable graphs whose algebraic connectivity is bounded from below model the systems with a small risk of power or communication failures. [ABSTRACT FROM AUTHOR]

In the realm of credit card fraud detection, the landscape is continually evolving, demanding innovative approaches to stay ahead of increasingly sophisticated fraudulent activities. Our research pioneers a groundbreaking methodology that amalgamates the power of bipartite graph visualization with advanced machine learning techniques. This fusion yields a comprehensive framework capable of effectively evaluating the efficacy of a random forest classifier in uncovering fraudulent credit card transactions. Our study showcases the compelling application of this methodology, offering a paradigm shift in how we analyze and understand credit card fraud detection systems. By seamlessly integrating machine learning algorithms with network analysis, we provide a holistic view of the data, unveiling intricate patterns hidden within. At the heart of our approach lies the innovative use of bipartite graphs, which serve as a dynamic visual bridge between model predictions and real-world outcomes. This visual representation not only enhances interpretability but also facilitates a deeper understanding of the classifier’s performance. By visually mapping the relationships between transactions and their respective classifications, our methodology offers actionable insights into both successful detection and potential areas for improvement. Empowering analysts and stakeholders, our approach facilitates informed decisionmaking by enabling them to fine-tune model parameters and enhance the overall effectiveness of fraud detection systems. Through this synergy between cutting-edge machine learning and network analysis techniques, we provide a powerful tool to combat the critical challenge of credit card fraud prevention. Step into the future of fraud detection with our innovative methodology, where every transaction is scrutinized with precision, and where security is not just a possibility, but a promise fulfilled. [ABSTRACT FROM AUTHOR]

Background: Conducting traditional wet experiments to guide drug development is an expensive, time-consuming and risky process. Analyzing drug function and repositioning plays a key role in identifying new therapeutic potential of approved drugs and discovering therapeutic approaches for untreated diseases. Exploring drug-disease associations has far-reaching implications for identifying disease pathogenesis and treatment. However, reliable detection of drug-disease relationships via traditional methods is costly and slow. Therefore, investigations into computational methods for predicting drug-disease associations are currently needed. Results: This paper presents a novel drug-disease association prediction method, RAFGAE. First, RAFGAE integrates known associations between diseases and drugs into a bipartite network. Second, RAFGAE designs the Re_GAT framework, which includes multilayer graph attention networks (GATs) and two residual networks. The multilayer GATs are utilized for learning the node embeddings, which is achieved by aggregating information from multihop neighbors. The two residual networks are used to alleviate the deep network oversmoothing problem, and an attention mechanism is introduced to combine the node embeddings from different attention layers. Third, two graph autoencoders (GAEs) with collaborative training are constructed to simulate label propagation to predict potential associations. On this basis, free multiscale adversarial training (FMAT) is introduced. FMAT enhances node feature quality through small gradient adversarial perturbation iterations, improving the prediction performance. Finally, tenfold cross-validations on two benchmark datasets show that RAFGAE outperforms current methods. In addition, case studies have confirmed that RAFGAE can detect novel drug-disease associations. Conclusions: The comprehensive experimental results validate the utility and accuracy of RAFGAE. We believe that this method may serve as an excellent predictor for identifying unobserved disease-drug associations. [ABSTRACT FROM AUTHOR]

We consider the adjacency spectrum of cycle-spliced signed graphs (CSSG), i.e., signed graphs whose blocks are (independent) signed cycles. For a signed graph S, the nullity η(S) is the multiplicity of the 0-eigenvalue. The adjancency spectrum of cycle-spliced (signed) graphs is studied in the literature for the relation between the nullity η and the cyclomatic number c, in particular, it is known that 0 = η(S) = c(S) + 1. In this paper, nonsingular cycle-spliced bipartite signed graphs are characterized. For cycle-spliced signed graphs S having only odd cycles, we show that η(S) is 0 or 1. Finally, we compute the nullity of CSSGs consisting of at most three cycles. [ABSTRACT FROM AUTHOR]

The bipartite polarization problem is an optimization problem where the goal is to find the highest polarized bipartition on a weighted and labeled graph that represents a debate developed through some social network, where nodes represent user's opinions and edges agreement or disagreement between users. This problem can be seen as a generalization of the maxcut problem, and in previous work, approximate solutions and exact solutions have been obtained for real instances obtained from Reddit discussions, showing that such real instances seem to be very easy to solve. In this paper, we further investigate the complexity of this problem by introducing an instance generation model where a single parameter controls the polarization of the instances in such a way that this correlates with the average complexity to solve those instances. The average complexity results we obtain are consistent with our hypothesis: the higher the polarization of the instance, the easier is to find the corresponding polarized bipartition. In view of the experimental results, it is computationally feasible to implement transparent mechanisms to monitor polarization on online discussions and to inform about solutions for creating healthier social media environments. [ABSTRACT FROM AUTHOR]

In the paper, we introduce the signless Laplacian A B C -matrix Q ̃ (G) = D ¯ (G) + A ̃ (G) , where D ¯ (G) is the diagonal matrix of A B C -degrees and A ̃ (G) is the A B C -matrix of G. The eigenvalues of the matrix Q ̃ (G) are the signless Laplacian A B C -eigenvalues of G. We give some basic properties of the matrix Q ̃ (G) , which includes relating independence number and clique number with signless Laplacian A B C -eigenvalues. For bipartite graphs, we show that the signless Laplacian A B C -spectrum and the Laplacian A B C -spectrum are the same. We characterize the graphs with exactly two distinct signless Laplacian A B C -eigenvalues. Also, we consider the problem of the characterization of the graphs with exactly three distinct signless Laplacian A B C -eigenvalues and solve it for bipartite graphs and, in some cases, for non-bipartite graphs. We also introduce the concept of the trace norm of the matrix Q ̃ (G) − t r (Q ̃ (G)) n I , called the signless Laplacian A B C -energy of G. We obtain some upper and lower bounds for signless Laplacian A B C -energy and characterize the extremal graphs attaining it. Further, for graphs of order at most 6, we compare the signless Laplacian energy and the A B C -energy with the signless Laplacian A B C -energy and found that the latter behaves well, as there is a single pair of graphs with the same signless Laplacian A B C -energy unlike the 26 pairs of graphs with same signless Laplacian energy and eight pairs of graphs with the same A B C -energy. [ABSTRACT FROM AUTHOR]