More Like this

1. Mechanistic Mode Connectivity

   Lubana, Ekdeep Singh; Eric J. Bigelow; Robert P. Dick; David Krueger; Hidenori Tanaka. (July 2023, Proc. Int. Conf. on Machine Learning)

   We study neural network loss landscapes through the lens of mode connectivity, the observation that minimizers of neural networks retrieved via training on a dataset are connected via simple paths of low loss. Specifically, we ask the following question: are minimizers that rely on different mechanisms for making their predictions connected via simple paths of low loss? We provide a definition of mechanistic similarity as shared invariances to input transformations and demonstrate that lack of linear connectivity between two models implies they use dissimilar mechanisms for making their predictions. Relevant to practice, this result helps us demonstrate that naive fine-tuning on a downstream dataset can fail to alter a model’s mechanisms, e.g., fine-tuning can fail to eliminate a model’s reliance on spurious attributes. Our analysis also motivates a method for targeted alteration of a model’s mechanisms, named connectivity-based fine-tuning (CBFT), which we analyze using several synthetic datasets for the task of reducing a model’s reliance on spurious attributes. 

   more » « less
2. Connectivity graph‐codes

   https://doi.org/10.1002/rsa.21222  

   Alon, Noga (October 2024, Random Structures & Algorithms)

   The symmetric difference of two graphs on the same set of vertices is the graph on whose set of edges are all edges that belong to exactly one of the two graphs . For a fixed graph call a collection of spanning subgraphs of a connectivity code for if the symmetric difference of any two distinct subgraphs in is a connected spanning subgraph of . It is easy to see that the maximum possible cardinality of such a collection is at most , where is the edge‐connectivity of and is its minimum degree. We show that equality holds for any ‐regular (mild) expander, and observe that equality does not hold in several natural examples including any large cubic graph, the square of a long cycle and products of a small clique with a long cycle. 

   more » « less
3. Generalized Connectivity Matrix Response Regression with Applications in Brain Connectivity Studies

   https://doi.org/10.1080/10618600.2022.2074434  

   Zhang, Jingfei; Sun, Will Wei; Li, Lexin (January 2023, Journal of Computational and Graphical Statistics)
4. Contour Algorithm for Connectivity

   https://doi.org/10.1109/HiPC58850.2023.00022  

   Du, Zhihui; Rodriguez, Oliver Alvarado; Li, Fuhuan; Dindoost, Mohammad; Bader, David A (December 2023, IEEE)

   Finding connected components in a graph is a fundamental problem in graph analysis. In this work, we present a novel minimum-mapping based Contour algorithm to efficiently solve the connectivity problem. We prove that the Contour algorithm with two or higher order operators can identify all connected components of an undirected graph within O(log d_max) iterations, with each iteration involving O(m) work, where d_max represents the largest diameter among all components in the given graph, and m is the total number of edges in the graph. Importantly, each iteration is highly parallelizable, making use of the efficient minimum-mapping operator applied to all edges. To further enhance its practical performance, we optimize the Contour algorithm through asynchronous updates, early convergence checking, eliminating atomic operations, and choosing more efficient mapping operators. Our implementation of the Contour algorithm has been integrated into the open-source framework Arachne. Arachne extends Arkouda for large-scale interactive graph analytics, providing a Python API powered by the high-productivity parallel language Chapel. Experimental results on both real-world and synthetic graphs demonstrate the superior performance of our proposed Contour algorithm compared to state-of-the-art large-scale parallel algorithm FastSV and the fastest shared memory algorithm ConnectIt. On average, Contour achieves a speedup of 7.3x and 1.4x compared to FastSV and ConnectIt, respectively. All code for the Contour algorithm and the Arachne framework is publicly available on GitHub {https://github.com/Bears-R-Us/arkouda-njit), ensuring transparency and reproducibility of our work. 

   more » « less
5. Optimal vertex connectivity oracles

   https://doi.org/10.1145/3519935.3519945  

   Pettie, Seth; Saranurak, Thatchaphol; Yin, Longhui (June 2022, ACM Symposium on Theory of Computing)